《数据结构》课程教学大纲.doc

数据结构数据结构课程教学大纲（本科）（黑体小三）课程教学大纲（本科）（黑体小三）注意：所有正文内容宋体小四注意：所有正文内容宋体小四第一部分：大纲说明（黑体四号）第一部分：大纲说明（黑体四号）一、 课程的性质和任务（黑体小四） 数据结构是计算机专业本、专科生的一门必修课程。本课程介绍如何 组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈 和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索 引与散列结构等。课程采用面向对象的观点讨论数据结构技术，并以兼有面向 过程和面向对象双重特色的 C+语言作为算法的描述工具，强化数据结构基本 知识和面向对象程序设计基本能力的双基训练。为后续计算机专业课程的学习 打下坚实的基础。 二、先修课程（黑体小四） 高级语言程序设计（Pascal 或 C 语言）、离散数学。 三、课程的教学基本要求（黑体小四） 1、掌握重要数据结构的概念、使用方法及实现技术； 2、学会做简单的算法分析，包括算法的时间代价和空间代价。 四、教学方法和教学形式建议（黑体小四）面授为主，进行必要的上机实验。 五、课程教学要求的层次（黑体小四） 1、熟练掌握：要求学生能够全面、深入理解和熟练掌握所学内容，并能够 用其知识分析、设计和解答相关的应用问题。 2、掌握：要求学生能够较好地理解和掌握，并且能够做简单的分析。 3、了解：要求学生能够一般地了解的所学内容。请按以下格式撰写第二部分：教材初步方案第二部分：教材初步方案一、学时分配课程教学总学时数为 96 学时，其中讲授学时 72，实验 24教 学 内 容讲授学时实验学时 一、数据结构基本概念及算法分析4 学时 二、数组 6 学时2 学时 三、链表6 学时4 学时 四、栈和队列 6 学时2 学时 五、递归 4 学时2 学时 六、树与森林 12 学时4 学时 七、集合与搜索 8 学时2 学时 八、图 10 学时4 学时 九、排序 10 学时4 学时 十、索引与散列结构 6 学时二、教学环节 1 1、面授（宋体小四加粗）、面授（宋体小四加粗） 本课程是计算机专业基础课，内容多且带有一定的抽象性，学习起来有一 定难度。为保证教学效果，采取集中授课方式。聘请有经验的教师担任主讲教 师，尽可能利用多种媒体进行教学，使学生能够很快掌握课程的主要知识和解 决问题的方法。 2 2、面授辅导或答疑（宋体小四加粗）、面授辅导或答疑（宋体小四加粗） 本课程教学过程中，面授辅导和答疑是必不可少的教学环节。应聘请有经 验、认真负责的教师任教，以习题课、专题讨论或答疑的方式，对课程中的重 要概念和典型问题的解决方法进行总结和深入讨论，巩固和加深课堂内学到的 知识。面授辅导或答疑安排两周一次为宜。 3 3、自学与练习（宋体小四加粗）、自学与练习（宋体小四加粗） 自学是获取知识的重要手段。教师讲课只是起到抛砖引玉的作用，关键还 在于学生的自学。为达到自学的效果，除读懂教科书中所讲内容外，还需大量 做题。其目的是要通过做题弄懂、加深对概念的理解，提高程序设计，解决问 题的能力。为此，安排一定的实验上机学时。要求学生珍惜实验机时，真正做 到学有所获。 学生在上机做实验前，应事先将程序、调试数据、上机操作顺序准备好， 并提前使用这些调试数据人工执行过。目的是提高上机的效率和成功率，严禁 抄袭或拷贝他人的成果，自觉培养科学、严谨的作风。 此部分从原大纲中删去：在最后要求每位学生完成一个综合作业，要求事 先写出预习报告，对需要完成的任务进行任务分解，对程序体系结构和模块结 构设计、采用的调试数据、上机操作过程进行描述，事后进行整理，写出实习 报告。报告内容包括预习报告的全部修改后的内容，再加上实验过程遇到那些 问题，这些问题如何解决，最后实习的成果等内容。除学校提供的时间外，要求课外学生利用自己可能拥有的计算机条件，完 成更多的练习，不通过大量的实践，能力和知识水平得不到有效得提高。 4 4、考试（宋体小四加粗）、考试（宋体小四加粗） 考试是对学生掌握知识水平的检验。本着多练多考的原则，可以再平时多 做一些小考。要求考试内容紧扣大纲要求，既要能够检验学生的掌握情况，又 要体现水平。因此，不要出难题、怪题，但也不要过于简单，适当有一些编程 题。 期末考试学生的本课程成绩按平时作业满分 20 分，期末考试满分 80 分分 配，合计计算。 第三部分 教学内容和教学要求（黑体四号）一、数据结构基本概念及简单的算法分析 3 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 什么是数据结构 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面 向对象的概念；用于描述数据结构的语言 数据结构的抽象层次 算法定义 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计； 空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复 杂度 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 了解：什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与 物理结构、逻辑结构与物理结构间的关系 了解：什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解 什么是面向对象 了解：算法的定义、算法的特性、算法的时间代价、算法的空间代价 掌握：用 C+语言描述算法的方法，能够使用 C+语言编写程序 二、数组 3 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数 组；数组的顺序存储方式 顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和 删除；使用顺序表的事例 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 了解：线性表的逻辑结构特性，以及线性表的两种存储实现方式 了解：作为抽象数据类型的数组的定义，数组的按行顺序存储与按列顺序 存储。 熟练掌握：顺序表的定义与实现，包括搜索、插入、删除算法的实现及其 平均比较次数的计算，掌握应用顺序表作为集合的简单操作 了解：稀疏矩阵的定义及其数组实现 熟练掌握：字符串的定义及实现三、链表 3 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表 头结点的单链表；用模板定义的单链表类；静态链表 循环链表：循环链表的类定义；用循环链表解约瑟夫问题； 多项式及其相加：多项式的类定义；多项式的加法 双向链表 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 了解：链表与数组一样，是一种实现级结构。有动态链表和静态链表之分 了解：链表有单链表、循环单链表、双向链表之分 了解：单链表的结构、特点 掌握：单链表的类定义、构造函数、单链表的插入与删除算法 了解：带表头结点的单链表的优点和类定义及相应操作的实现 熟练掌握：用模板定义的单链表类 了解：循环链表的特点，循环链表的类定义，以及用循环链表解决问题的 方法 掌握：双向链表的特点，双向链表的类定义及相关操作的实现，用双向链 表解决问题的方法。 四、栈和队列 3 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示 表达式求值：中缀表达式求值；中缀表示到后缀表示的转换 队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示； 队列的应用举例 优先级队列：优先级队列的定义；优先级队列的存储表示 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 熟练掌握：栈的定义、特性和栈的抽象数据类型，栈的顺序表示、链表表 示以及相应操作的实现。特别注意栈空和栈满的条件 了解：在表达式计算时栈是如何使用的，重点了解用后缀表示计算表达式 及中缀表示改后缀表示的方法和算法思路 熟练掌握：队列的定义、特性和队列的抽象数据类型，队列的顺序表示、 链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况 掌握：优先级队列的定义、特性和优先级队列的抽象数据类型，优先级队 列的插入与删除算法 五、递归 3 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 递归的概念：递归问题的求解 递归过程与递归工作栈：单向递归和尾递归的迭代实现；一般递归问题利 用栈实现非递归解法 广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现； 广义表的访问算法；广义表的递归算法 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 掌握：递归的概念。包括什么是递归，有那些种类的递归，递归问题的递 归求解方法掌握：递归过程的机制与利用递归工作栈实现递归的方法 了解：迷宫问题的递归求解思路及如何利用栈实现迷宫问题的非递归解法 掌握：利用递归解决问题的分治法和回溯法 掌握：广义表的定义及其实现方法 掌握：广义表的递归算法 六、树与森林 9 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 树和森林的概念：树的定义；树的术语；树的抽象数据类型 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型 二叉树的表示：顺序表示；二叉链表表示 遍历二叉树：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例； 二叉树的计数 线索化二叉树：线索；中序线索化二叉树 堆：堆的定义；堆的建立；堆的插入与删除；堆的调整算法 树与森林：树的存储表示；森林与二叉树的转换；遍历树；遍历森林 霍夫曼树：路径长度；霍夫曼树；霍夫曼编码 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 了解：树和森林的概念。包括树的定义、树的术语、树的抽象数据类型 掌握：二叉树的概念、性质及二叉树的表示 熟练掌握：二叉树的遍历方法 掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法 熟练掌握：堆的定义，堆的建立、堆的插入与删除、堆的向上和向下调整 等算法以及用来实现优先级队列的方法 掌握：树与森林的实现，重点在用二叉树实现 掌握：森林与二叉树的转换；树的遍历算法 掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握：霍夫曼树的实现方法、构造霍夫曼编码的方法及带权路径长度的计 算 七、集合与搜索 5 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量 实现集合抽象据类型；用有序链表实现集合的抽象数据类型 并查集：并查集的定义；并查集的实现 简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序 表的顺序搜索和折半搜索 二叉搜索树：二叉搜索树的定义；二叉搜索树上的搜索；二叉搜索树的插 入；二叉搜索树的删除 AVL 树：AVL 树定义；平衡化旋转；AVL 树的插入和删除；AVL 树高度 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 掌握：集合的基本概念及其表示方法，包括位数组及有序链表的表示及其 相关操作的实现算法 掌握：利用并查集实现集合的方法 熟练掌握：静态搜索表的顺序搜索和折半搜索算法及其性能分析方法 熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法掌握：AVL 树的平衡化旋转、构造、插入、删除时的调整方法及其性能分 析 八、图 7 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 图的基本概念：图的基本概念；图的抽象数据类型 图的存储表示：邻接矩阵；邻接表；邻接多重表 图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；关节点与 重连通分量 最小生成树：kruskul 算法；prim 算法 单源最短路径问题：dijkstra 算法 活动网络：AOV 网络与拓扑排序；AOE 网络与关键路径 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 理解：图的基本概念和图的抽象数据类型 掌握：图的 3 种存储表示：邻接矩阵、邻接表和邻接多重表。对于前两种， 要求掌握典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等 操作的实现算法 熟练掌握：图的两种遍历算法与求解连通性问题的方法。包括深度优先搜 索和广度优先搜索算法、求连通分量的方法(不要求算法) 理解：求解关节点及构造重连通图的方法(不要求算法) 掌握：构造最小生成树的 Prim 算法和 Kruskal 算法，要求理解算法 理解：如何用 Dijkstra 方法求解单源最短路径问题(不要求算法) 熟练掌握：活动网络的拓扑排序算法 掌握：求解关键路径的方法 九、排序 7 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 概述 插入排序：直接插入排序；折半插入排序；链表插入排序；希尔排序 交换排序：起泡排序；快速排序 选择排序：直接选择排序；锦标赛排序；堆排序 归并排序：归并；迭代的归并排序算法；递归的链表归并排序 基数排序：多关键码排序；链式基数排序 外排序：外排序的基本过程；k 路平衡归并；初始归并段的生成；最佳归 并树 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 掌握：排序的基本概念和性能分析方法 掌握：插入排序、交换排序、选择排序、归并排序等内排序的方法及其性 能分析方法 了解：基数排序方法及其性能分析方法 掌握：多路平衡归并等外排序方法及败者树构造方法 掌握：生成初始归并段及败者树构造方法 掌握：最佳归并树的建立方法 十、索引与散列结构 5 学时（黑体小四） 1 1、教学内容：（宋体小四加粗）、教学内容：（宋体小四加粗） 静态索引结构：线性索引；倒排索引；m 路静态查找树动态索引结构：动态的 m 路查找树；B 树的定义；B 树的插入；B 树的删除； B+树 散列：散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出 的开散列方法；散列表分析 2 2、教学要求：（宋体小四加粗）、教学要求：（宋体小四加粗） 熟练掌握：静态索引结构，包括线性索引、倒排索引、静态索引树的搜索 和构造方法 熟练掌握：动态索引结构，包括 B 树、B+树的搜索和构造方法 熟练掌握：散列法，包括散列函数的构第四部分 相关说明（黑体四号）1、适用专业及层次（黑体小四）： 2、推荐教材（黑体小四）： 3、参考书（黑体小四）： 4、相关网络资源（黑体小四）：