数据结构教学清华大纲

1、计算机科学与技术系（本科）数据结构课程教学大纲第一部分大纲说明一、课程的性质和任务数据结构是计算机科学与技术专业本科生的一门必修课程。本课程介绍如何组织各种数据在计算机中的、传递和转换。内容包括：数组、表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等。课程采用面象的观点数据结构技术，并以兼有面向过面识和面象双重特色的 ) 语言作为算法的描述工具，强化数据结构基本知象程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。二、先修课要求面象程序设计、计算机数学 离散数学 。三、课程的教学基本要求1、掌握重要数据结构的概念、使用方法及实现技术；

2、2、学会做简单的算法分析，包括算法的时间代价和空间代价。、教学方法和教学形式建议面授为主，结合面授辅导、电子邮件答疑，进行必要的上机实验。五、课程教学要求的层次1、熟练掌握：要求学生能够全面、深入理解和熟练掌握所学内容，并能够用其知识分析、设计和解答相关的应用问题。2、掌握：要求学生能够较好地理解和掌握，并且能够做简单的分析。3、了解：要求学生能够一般地了解的所学内容。四第二部分多种总体设计初步方案一、学时分配课程教学总学时数为96 学时，4 学分，其中讲授学时 64，实验 32二、教学环节1、面授教学本课程是计算机专业基础课，内容多且带有一定的抽象性，学习起来有一定难度。为保证教学效果，采取

3、教师授课方式，尽可能利用多种学生能够很快掌握课程的主要知识和解决问题的方法。2、面授辅导或答疑进行教学，使本课程教学过程中，面授辅导和答疑是必不可少的教学环节。由专任助教任教，以习题课、专题方法进行总结和深入或答疑的方式，对课程中的重要概念和典型问题的解决，巩固和加深课堂内学到的知识。必要时可采用电子邮件方式直接与教师联系进行答疑。3、与练习是获取知识的重要。教师讲课只是起到抛砖引玉的作用，关键还在于学生的。为达到的效果，除读懂教科书中所讲内容外，还需大量做题。其目的是要通过做题弄懂、加深对概念的理解，提高程序设计，解决问题的能力。为此，安排一定的实验上机学时。要求学生珍惜实验机时，真正做到学

4、有所获。学生在上机做实验前，应事先将程序、调试数据、上机操作顺序准备好，并教学内容讲授学时一、数据结构基本概念及算法分析4 学时二、数组4 学时三、链表4 学时四、栈和队列4 学时五、递归4 学时六、树与森林12 学时七、集合与搜索6 学时八、图10 学时九、排序10 学时十、索引与散列结构6 学时提前使用这些调试数据人工执行过。目的是提高上机的效率和成功率，严禁或拷贝他人的成果，自觉培养科学、严谨的作风。除学校提供的时间外，要求课外学生利用自己可能拥有的计算机条件，完成的练习，不通过大量的实践，能力和知识水平得不到有效得提高。4、是对学生掌握知识水平的检验。本着多练多考的原则，各地方电大可以

5、再平时多做一些小考。要求内容紧扣大纲要求，既要能够检验学生的掌握情况，又要体现水平。因此，不要出难题、怪题，但也不要过于简单，适当有一些编程题。学生的本课程成绩按平时作业满分 30 分，期中分 50 分分配，合计计算。满分 20 分，期末满第三部分教学内容和教学要求第一章 数据结构基本概念及简单的算法分析1、教学内容：数据结构抽象数据类型及面象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言数据结构的抽象层次算法定义性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂度2、教学要求：

6、了解：数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系了解：么是面数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什象了解：算法的定义、算法的特性、算法的时间代价、算法的空间代价掌握：用 C+语言描述算法的方法，能够使用 C+语言编写程序第二章 数组1、教学内容：作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序方式顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、除；使用顺序表的事例和删字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配2、教学要求：了解：线性表的逻辑结构特性，以及线性表的两种实现方

7、式了解：作为抽象数据类型的数组的定义，数组的按行顺序与按列顺序存储熟练掌握：顺序表的定义与实现，包括搜索、删除算法的实现及其平均比较次数的计算，掌握应用顺序表作为集合的简单操作了解：稀疏矩阵的定义及其数组实现熟练掌握：字符串的定义及实现第三章 链表1、教学内容：单链表：单链表的结构；单链表的类定义；单链表中的结点的单链表；用模板定义的单链表类；静态链表与删除；带表头循环链表：循环链表的类定义；用循环链表解多项式及其相加：多项式的类定义；多项式的加法双向链表2、教学要求：问题；了解：链表与数组一样，是一种实现级结构。有动态链表和静态链表之分了解：链表有单链表、循环单链表、双向链表之分了解：单链表

8、的结构、特点掌握：单链表的类定义、构造函数、单链表的与删除算法了解：带表头结点的单链表的优点和类定义及相应操作的实现熟练掌握：用模板定义的单链表类了解：循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法掌握：双向链表的特点，双向链表的类定义及相关操作的实现，解决问题的方法。向链表第四章栈和队列1、教学内容：栈：栈的抽象数据类型；栈的顺序表示；栈的表示表达式求值：中缀表达式求值；中缀表示到后缀表示的转换队列 ：队列的抽象数据类型；队列的顺序队列的应用举例表示；队列的表示；优先级队列：优先级队列的定义；优先级队列的2、教学要求：表示熟练掌握：栈的定义、特性和栈的抽象数据类型，栈的顺序表

9、示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件了解：在表达式计算时栈是如何使用的，重点了解用后缀表示计算表达式及中缀表示改后缀表示的方法和算法思路熟练掌握：队列的定义、特性和队列的抽象数据类型，队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况掌握：优先级队列的定义、特性和优先级队列的抽象数据类型，优先级队列的与删除算法第五章 递归与广义表1、教学内容：递归的概念：递归问题的求解递归过程与递归工作栈：单向递归和尾递归的迭代实现；一般递归问题利用栈实现非递归解法广义表：广义表的概念；广义表的表示及操作；广义表结构的实现；广义表的算法；广义表的递归算法2

10、、教学要求：掌握：递归的概念。包括求解方法递归，有那些种类的递归，递归问题的递归掌握：递归过程的机制与利用递归工作栈实现递归的方法了解：迷宫问题的递归求解思路及如何利用栈实现迷宫问题的非递归解法掌握：利用递归解决问题的分治法和回溯法掌握：广义表的定义及其实现方法掌握：广义表的递归算法第六章 树与森林1、教学内容：树和森林的概念：树的定义；树的术语；树的抽象数据类型二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型二叉树的表示：顺序表示；二叉链表表示遍历二叉树：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二叉树的计数线索化二叉树：线索；中序线索化二叉树堆：堆的定义；堆的建立；堆的与

11、删除；堆的调整算法树与森林：树的表示；森林与二叉树的转换；遍历树；遍历森林树：路径长度；2、教学要求：树；编码了解：树和森林的概念。包括树的定义、树的术语、树的抽象数据类型掌握：二叉树的概念、性质及二叉树的表示熟练掌握：二叉树的遍历方法及树的游标类定义掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法熟练掌握：堆的定义，堆的建立、堆的算法以及用来实现优先级队列的方法与删除、堆的向上和向下调整等掌握：树与森林的实现，重点在用二叉树实现掌握：森林与二叉树的转换；树的遍历算法掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法掌握：树的实现方法、构造编码的方法及带权路径长度的计算第七章 集合

12、与搜索1、教学内容：集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型并查集：并查集的定义；并查集的实现简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的顺序搜索和折半搜索二叉搜索树：二叉搜索树的定义；二叉搜索树上的搜索；二叉搜索树的二叉搜索树的删除；AVL 树：AVL 树定义；平衡化旋转；AVL 树的和删除；AVL 树高度2、教学要求：掌握：集合的基本概念及其表示方法，包括位数组及有序链表的表示及其相关操作的实现算法掌握：利用并查集实现集合的方法熟练掌握：静态搜索表的顺序搜索和折半搜索算法及其性能分析方法熟练

13、掌握：二叉搜索树的表示、搜索、删除算法及其性能分析方法掌握：AVL 树的平衡化旋转、构造、删除时的调整方法及其性能分析第八章 图1、教学内容：图的基本概念：图的基本概念；图的抽象数据类型图的表示：邻接矩阵；邻接表；邻接多重表图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；关节点与重连通分量最小生成树：kruskul 算法；prim 算法单源最短路径问题：dijkstra 算法活动网络：AOV 网络与拓扑排序；AOE 网络与关键路径2、教学要求：理解：图的基本概念和图的抽象数据类型掌握：图的 3 种表示：邻接矩阵、邻接表和邻接多重表。对于前两种，要求掌握典型操作，如构造、求根、找第一个邻

14、接顶点、找下一个邻接顶点等操作的实现算法熟练掌握：图的两种遍历算法与求解连通性问题的方法。包括深度优先搜索和广度优先搜索算法、求连通分量的方法(不要求算法)理解：求解关节点及构造重连通图的方法(不要求算法)掌握：构造最小生成树的Prim 算法和Kruskal 算法，要求理解算法理解：如何用 Dijkstra 方法求解单源最短路径问题(不要求算法)熟练掌握：活动网络的拓扑排序算法掌握：求解关键路径的方法第九章 排序1、教学内容：概述排序：直接排序；折半排序；链表排序；排序交换排序：起泡排序；快速排序选择排序：直接选择排序；锦标赛排序；堆排序归并排序：归并；迭代的归并排序算法；递归的链表归并排序基数排序：多关键码排序；链式基数排序外排序：外排序的基本过程；k 路平衡归并；初始归并段的生成；最佳归并树2、教学要求：掌握：排序的基本概念和性能分析方法掌握：分析方法排序、交换排序、选择排序、归并排序等内排序的方法及其性能了解：基数排序方法及其性能分析方法掌握：多路平衡归并等外排序方法及败者树构造方法掌握：生成初始归并段及败者树构造方法掌握：最佳归并