《《数据结构》教学大纲》由会员分享，可在线阅读，更多相关《《数据结构》教学大纲（19页珍藏版）》请在金锄头文库上搜索。
1、浙江财经学院东方学院数据结构（电子商务）（含实验）教 学 大 纲信息分院电子商务教研室 2012年 4月目 录前 言（2）第一章 绪论（3）第二章 集合（4）第三章 线性表（5）第四章 栈和队列（6）第五章 二叉树（7）第六章 图（9）第七章 检索（10）第八章 排序（11）附：数据结构课程实验教学大纲（13）前 言一、课程简介数据结构是电子商务专业的技术基础课程，一般安排为必修课。授课学时数54，上机学时数36（具体学时分配见附表）。预修课程有：计算机基础或计算机概论，高级语言程序设计（Java）等。本课程通过介绍数据的逻辑结构、存储结构以及建立在一定结构之上的有关算法，系统地讲授基本的数据
2、结构，并对计算机领域中的一些重要问题，包括问题求解、算法分析、程序设计方法等作进一步的介绍。主要内容包括：线性结构的线性表、栈、队列等的存储及有关算法，排序和检索算法，非线性结构的数组、树、图的存储、遍历算法及应用等。二、课程的教学目标和总的教学要求“数据结构”是计算机程序设计的重要理论基础，它所讨论的内容和提倡的技术方法，对进一步学习计算机领域的其它课程，或从事软件的开发，都有着不可替代的作用。通过本课程的学习，使学生学会从问题入手，分析研究计算机处理的数据对象的特性，学会数据组织的方法、以及把现实世界中的问题在计算机内部的表示方法，初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是
3、进行复杂程序设计的训练过程，要求学生学习书写符合软件工程规范的文档、程序，培养学生基本的、良好的程序设计能力.三、适用对象电子商务。四、课程性质必修课。五、总课时及各章的分配授课总课时数为85学时，其中，理论学时为51，实验学时34，各章的学时具体安排如下：章 节内 容教学课时实验课时备 注1概论32集合323线性表864栈和队列655二叉树和树876图867查找648排序64复习3合计5134六、使用教材及主要参考书目（一）选用教材数据结构教程（java语言描述）徐孝凯 主编 清华大学出版社。（二）主要参考书目2数据结构与抽象（Java语言版），Frank Carrano Walter Sa
4、vitch著，严蔚敏译 清华大学出版社。3Java软件开发（第二版）英Russel Winder等，人民邮电出版社。4 数据结构与算法（Java语言） 德罗兹迪克（Drozdek.A.）机械工业出版社5数据结构，许卓群编，高等教育出版社。6数据结构算法设计指导，胡学钢编，清华大学出版社。第一章 绪论教学目的和要求： 熟悉数据结构的概念和术语，理解数据结构的两个层次（逻辑结构和物理结构），理解数据结构与算法的关系；2了解算法的五个要素、算法的描述方法；3了解算法的时间。学生自学要求：自学空间复杂度的估算方法重点：数据结构的类型，数据结构与算法的关系 教学难点： 第一节 基本概念一、数据 数据时人
5、们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动所做的抽象描述。二、数据元素它是一个数据整体中可以标识和访问的数据单元。三、 数据记录 数据处理领域组织数据的基本单位。四、数据结构数据结构是指数据及其相互之间的联系（逻辑关系）。数据时对现实世界中的事物及其活动的抽象描述，而任何事物及其活动度不是孤立存在的，都是在一定意义上相互联系、相互影响的。第二节 算法描述一个算法可以借助各种不同的工具和手段加以描述。流程图工具描述第三节 算法评价 一、正确性设计和评价一个算法的首要指标。二、 健壮性三、 可读性四、 时间复杂度 又称计算复杂度 五、空间复杂度（自学）复习思考题：1、数据结构
6、包括罗志结构和存储结构，他们分别包括哪几种结构？2、算法的评价包括那几个方面？3、算法的时间复杂度用什么方式进行表示？第二章 集合教学目的和要求： 了解集合在顺序存储和链式存储下的特点；掌握集合的描述方法、基本运算的实现。学生自学要求：教学重点：集合在顺序存储教学难点： 集合的链式存储第一节 集合的定义和运算一、集合的定义它是有相同类型的互不相同的数据元素聚集而成，元素之间不存在任何逻辑关系。二、集合的抽象数据类型包括数据和操作两个部分。集合的抽象数据类型定义三、集合运算举例第二节 集合的顺序存储结构和操作实现一、 初始化集合为空二、 向集合插入一个元素三、 从集合中删除一个元素四、 判断一个
7、元素是否属于集合 第三节 集合的链接存储结构和操作实现一、链接存储的概念二、链接集合类的定义和实现第四节 集合应用举例复习思考题：1、集合的链接存储和顺序存储的异同？2、集合常用的运算有哪些？第三章 线性表教学目的和要求： 了解线性表在顺序存储和链式存储下的特点；熟练掌握顺序表的描述方法、基本运算的实现；掌握链表的描述方法、基本运算的实现；掌握从时间和空间效率上比较顺序表和链表。学生自学要求：有序线性表的定义和实现等教学重点：顺序表的描述方法、基本运算的实现教学难点： 链表的描述方法、基本运算的实现第一节 线性表的定义地和运算一、定义线性表是具有相同类型带护具的一个有限序列二、抽象数据类型抽象
8、数据类型定义三、 运算举例第二节 线性表的顺序存储和操作实现线性表顺序存储结构利用一维数组来实现，线性表顺序存储结构示意图。操作包括：初始化线性表为空、得到线性表中低pos个元素的值等操作第三节 有序线性表的定义和实现（自学） 第四节 链接存储的一般概念和方法一、 链接存储的一般概念二、 线性表的单链接存储 几种单链表的形式介绍及示意图三、 线性表的双链接存储 几种双链表的形式介绍及示意图 第五节 链接存储的一般概念和方法 链接线性表类的定义 操作包括：初始化线性表为空、得到线性表中低pos个元素的值等操作 第六节 有序线性表的链接存储和操作实现（自学） 第七节 多项式计算（自学） 复习思考题
9、：1、使用顺序存储的线性表类sequenceList的编程练习2、使用链接存储的线性表类linkList的编程练习3、解决约瑟夫问题的算法第四章 栈和队列教学目的和要求：熟练掌握栈和队列这两种数据结构的特点；掌握栈的定义和基本运算；掌握队列的定义和基本运算；掌握递归算法执行过程中栈的状态变化。学生自学要求： 队列的链接存储结构和操作实现教学重点：栈的定义和基本运算，队列的定义和基本运算教学难点： 第一节 栈的定义和基本运算一、 栈的定义二、 栈的抽象数据类型 栈的抽象数据类型的定义，栈接口Stack的具体定义三、 栈的运算举例 第二节 栈的顺序存储结构和操作实现栈的顺序存储结构需要使用一个数组
10、和一个整形变量来实现操作包括：初始化顺序栈为空；栈顶插入元素等第三节 栈的链接存储结构和操作实现 栈的链接存储结构与线性表的链接存储结构相同，通过由节点构成的单链表实现 栈的链接存储结构及操作示意图 链栈类的定义和操作方法第四节 栈的简单应用举例第五节 栈与递归 递归的概念描述 递归应用举例：求解迷宫问题 第七节 队列一、队列的定义二、队列的抽象数据类型 队列的抽象数据类型的定义，队列接口Queue的具体定义三、 队列的顺序存储结构和操作实现 队列顺序存储结构需要使用一个数组和2、3个整形变量来实现 操作包括：初始化队列为空；向队列栈顶插入元素等四、 队列的链接存储结构和操作实现 复习思考题：
11、1、栈与队列的异同？2、栈与递归的关系及解决迷宫问题的算法3、队列的具体应用？第五章 二叉树与树教学目的和要求：熟悉树和二叉树的基本概念；熟悉二叉树和树的各种存储结构；熟练掌握遍历二叉树的递归和非递归算法，了解遍历过程中栈的状态，能灵活运用遍历算法实现二叉树的其它运算；熟练掌握二叉排序树的建立与运算；学生自学要求：排序、哈夫曼树的实现教学重点：二叉树和树的各种存储结构二叉树和树的各种存储结构;遍历二叉树的递归和非递归算法教学难点： 二叉树的非递归遍历算法第一节 树的概念一、树的定义二、树的表示三、树的基本术语四、树的性质第二节 二叉树一、二叉树的定义二、二叉树的性质三、二叉树的抽象数据类型包括
12、数据和操作两部分，给出二叉树的抽象数据类型的具体定义给出在java语言中的对应的接口定义四、 二叉树的存储结构 顺序存储结构、链接存储结构第三节 二叉树遍历分前序、中序、后序遍历，分别给出遍历算法第四节 二叉树其他运算包括建立二叉树、检查二叉树是否为空、求二叉树深度等第五节 二叉搜索树一、 二叉搜索树的定义二、 二叉搜索树的抽象数据类型和链接存储类三、 二叉搜索树的运算方法复习思考题：1、二叉树的存储方法的特点是什么？2、二叉树的主要性质有哪些？3、有哪些二叉树的额遍历方法，算法如何？第六章 图教学目的和要求：熟悉图的有关概念；掌握图的存储结构；了解图的遍历算法；了解图的最小生成树、最短路径、
13、拓扑排序、关键路径等算法。学生自学要求： 图的其他运算的算法教学重点：图的存储结构教学难点： 图的遍历算法第一节 图的概念一、图的定义分类：有向图，无向图二、 图的基本术语 （1）端点和邻接点（2）顶点的度、入度、出度（3）完全图、稠密图、稀疏图（4）子图（5）权和网第二节 图的存储结构一、邻接矩阵 概念，邻接矩阵的表示方法二、 邻接表 概念、表示方法 边结点类的定义三、 边集数组 概念 边集数组中的元素类定义第三节 图的抽象数据类型和接口类包括数据和操作两部分抽象数据类型的具体定义用java语言描述的图的接口类定义第四节 图的邻接矩阵和邻接表存储类一、图的邻接矩阵存储类二、图的邻接表存储类第五节 图的遍历一、图的深度优先搜索遍历二、图的官渡优先搜索遍历 第五节 图的其他运算的算法（自学）第七
