数据结构课程标准

1、数据结构课程标准（专科）一、课程的性质：数据结构是计算机专业的一门必修专业基础课，它是一门理论性强，但有一定的实践性和较强实用性的基础课程。二、课程的教学目的与任务：本课程的任务是讨论数据的各种逻辑结构、存储结构以及有关操作的算法。目的是使学生掌握分析研究计算机加工的数据对象的特性，以便对所要处理的数据对象选择合适的数据结构和存储结构，并在此基础上掌握对这些数据的操作（查找、插入、删除和修改等）。同时培养学生运用C语言编写结构清晰、正确易读的算法，并具备初步评价算法的能力，为学生今后继续学习和研究打下坚实的基础。三、课程的教学手段和方法：本课程理论讲授采用教材与多媒体相配合的教学手段。本课程包

2、括课堂教学与实践教学两大部分。课堂教学在方法上， 采用课堂讲授、课后自学、课堂讨论、课外作业、平时测验等教学形式。实践教学部分主要是实验。四、课程内容及学时分配（共72学时,其中讲课60学时,实验12学时）：第一部分讲授内容（60学时）第一章绪论（共4学时）第一节有关概念和术语（2学时）一、基本要求：掌握数据结构的一些基本概念，了解抽象数据类型的定义和使用。二、教学重点及难点：本节重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。教学难点是什么是数据的逻辑结构及物理结构？三、讲授内容：（一）数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算

3、法等。（二）抽象数据类型。四、思考题：举出一个数据结构的例子，叙述其逻辑结构、存储结构、结构上的操作内容。 第二节算法及算法分析（2学时）一、基本要求：掌握算法的时间复杂度和空间复杂度的分析方法，了解算法的描述方法。二、教学重点及难点：本节重点是算法的各种描述方法和算法分析（时间复杂度及空间复杂度）。教学难点是对一个算法时 间复杂度的分析。三、讲授内容：（一）描述算法所用的 C语言中的一些有关问题。（二）算法时间复杂度和空间复杂度的分析。四、思考题：编写算法，求一元多项式Pn（x）=a o+aix+a2x2+a3x3+a nxn的值R（xo），要求时间复杂度尽可能小。第二章线性表（12学时）第

4、一节线性表的顺序存储结构（6学时）一、基本要求：理解线性表的定义和基本操作；掌握数组的存储（例如：数组元素在内存位置的计算方法）和在顺序 存储结构上的基本操作（如插入、删除、合并、戈怆和比较等）的实现。二、教学重点及难点：C语言描述、基本操作实现方法和简单应用。本节重点是线性表的逻辑结构、线性表的顺序存储存构 教学难点是用C语言实现基本操作和如何通过顺序存储结构解决实际问题。三、讲授内容:（一）线性表的定义和基本操作；（二）线性表的顺序存储结构；（三）定义在顺序存储结构上的基本操作的实现;（四）应用举例及分析。四、思考题：设有两个按元素值递增有序顺序表A和B,编一程序将A表和B表归并成一个新的

5、递增有序的顺序表C （值相同的元素均保留在 C表中）。第二节线性表的链式存储结构（6学时）一、基本要求：掌握单链表的基本结构及基本操作（如建立、查找、插入和删除等）；掌握循环链表和双向链表；能 用单链表解决一些实际问题。二、教学重点及难点:本节重点是顺序存储结构及链式存储结构的优缺点，如何用C语言实现链式存储结构，单链表上基本操作的实现，各种链表的结构：循环链表，双向链表和单链表的一些简单应用。教学难点是单链表上基本 操作的实现和建立在链表上的一些应用。三、讲教内容：（一）链式存储结构的实现方法；（二）单链表的基本操作；（三）循环链表及双向链表的实现;（四）应用举例。四、思考题：分析单链表、循

6、环链表和双向链表的相同点、不同点及各自的特点。 第三章栈和队列（8学时）第一节栈（4学时）一、基本要求：掌握栈的定义，掌握顺序和链式存储的栈的基本操作实现。二、教学重点及难点：本节重点是栈的逻辑结构定义，用C语言实现栈的两种方式：顺序存储结构及链式存储结构，栈的基本操作的实现。教学难点是栈的基本操作的实现和一些具体应用。三、讲授内容:（一）栈的定义及基本运算;（二）栈的顺序存储和链接存储的表示；（三）在栈的顺序存储和链接存储上进行各种栈操作的算法;（四）栈的应用举例。四、思考题：求2阶Fib on acci数列的递归算法。第二节对（4学时）一、基本要求：掌握队列的定义、顺序存储及链接存储时的操

7、作，掌握顺序存储下循环队列的插入、删除运算算法。二、教学重点及难点：本节重点是队列的逻辑定义，用C语言实现队列的两种方式：顺序存储结构及链式存储结构，队列的基本操作实现和循环队列的实现。教学难点是队列的基本操作的实现和循环队列的实现方式。三、讲授内容:（一）队列的类型定义；（二）队列的顺序存储（循环队）表示及各种操作的实现算法;（三）队列的链接存储表示及各种操作的实现算法。四、思考题：队列管理的模拟算法（队列采用带头结点的链表结构）。 第四章串和数组（4学时）第一节串（2学时）一、基本要求：掌握用C语言如何实现物理存储结构： 顺序存储结构及堆结构和串的合并、理解串的定义和基本操作, 定位、比较

8、算法。二、教学重点及难点：本节重点是串的物理存储结构和串的基本操作的实现。教学难点是串的堆分配结构。三、讲授内容：（一）串的类型定义；（二）串的存储结构；（三）串的基本操作的实现。四、思考题：设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。第二节数组（2学时）一、基本要求：掌握二维数组的存储结构和稀疏矩阵的压缩存储。了解稀疏矩阵的转置算法。二、教学重点及难点：本节重点是矩阵的向量存储结构和稀疏矩阵的压缩存储。教学难点是稀疏矩阵的压缩存储。三、讲授内容：（一）二维数组的存储结构;（二）稀疏矩阵；（三）应用举例。四、思考题：稀疏矩阵转

9、置算法。第五章树和二叉树（10学时）第一节二叉树（6学时）一、基本要求：掌握树的定义，相关术语及基本操作；掌握二叉树的定义，性质，存储结构，基本操作和二叉树的遍 历。教学重点及难点：本节重点是树的定义，二叉树的定义、性质、存储结构、基本操作和遍历。教学难点是二叉树的性质。讲授内容：（一）树的概念与基本操作;（二）二叉树的定义、性质;（三）二叉树的存储结构；（四）二叉树的遍历；（五）二叉树的举例四、思考题：建立二叉树并写出其前序遍历、中序遍历的非递归算法。第二节树与森林（4学时）一、基本要求：掌握树的存储结构，树、森林与二叉树的转化，树和森林的遍历；掌握哈夫曼树和哈夫曼编码。二、教学重点及难点：

10、本节重点是树、森林与二叉树的转化，树和森林的遍历操作，哈夫曼树。教学难点是树的存储结构, 树、森林与二叉树的转化和哈夫曼树。三、讲授内容:（一）树的存储结构；（二）树、森林与二叉树的转化；（三）树和森林的遍历；（四）哈夫曼树的定义、构造哈夫曼树的方法;（五）哈夫曼编码的方法。四、思考题：在以孩子兄第链表结构存储的树中，写出求树中结点孩子的算法。 第六章图（8学时）第一节图的存储和遍历（4学时）一、基本要求：掌握图的定义和术语，图的存储表示和遍历方式。二、教学重点及难点：本节重点是图的定义和术语，图的存储结构，图的遍历。教学难点是图的存储结构和图的遍历方式。三、讲授内容：（一）图的定义和术语；（

11、二）图的邻接矩阵和邻接表表示；（三）图的深度和广度优先查找。四、思考题：编写算法：在无向图的邻接距阵结构上，生成无向图的邻接链表结构。第二节图的应用（4学时）一、基本要求：掌握图的生成树及最小生成树，求最短路径，拓扑排序。二、教学重点及难点：本节重点是最小生成树问题，最短路径问题，拓扑排序的方法。教学难点是最小生成树问题和求最短 路径。三、讲授内容:（一）图的生成树和最小生成树；（二）最短路径；（三）拓扑排序。四、思考题：对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 关键路径是什么？第七章查找（6学时）第一节静态查找和动态查找（3学时）一、基本要求：掌握查找的基本方式；

12、掌握静态表上顺序查找，有序表的折半查找和分块查找；掌握动态查找：二叉 排序树的生成和插入，二叉排序树上的查找。二、教学重点及难点：本节重点是顺序查找，有序表的折半查找，查找成功查找长度分析和二叉排序树上的查找。教学难点 是成功查找及不成功查找分析。三、讲授内容：（一）静态查找：顺序查找，有序表的折半查找和分块查找；（二）动态查找：二叉排序树上的查找。四、思考题：对长度为10的有序表进行折半查找的判定树，并求其等概时查找成功的平均查找长度。 第二节哈希表（3学时）一、基本要求：掌握哈希表的查找方式，常用哈希函数的构造方法，解决冲突的主要方法，哈希表的查找及性能分析。二、教学重点及难点：本节重点是

13、哈希表的查找方式 ，哈希函数的构造，解决冲突的方法，哈希表的查找及性能分析。教学 难点是哈希表的查找和如何解决冲突。三、讲授内容：（一）哈希表和哈希方法；（二）常用哈希函数的构造方法；（三）处理冲突的方法；（四）哈希表的查找及性能分析。四、思考题：为什么说当装填因子非常接近1时，线性探查类似于顺序查找 ？为什么说当装填因子比较小（比如a =0.7左右）时，散列查找的平均查找时间为0（1）?第七章排序（8学时）一、基本要求：掌握直接插入排序、冒泡排序、简单选择排序的方法及其实现；掌握快速排序、堆排序、二路归并排 序的方法；掌握各种排序方法的稳定性、时间复杂度和空间复杂度。二、教学重点及难点：本节

14、重点是各种排序（直接插入排序，冒泡排序，简单选择排序，快速排序，堆排序，归并排序和基 数排序）及时间复杂度分析。教学难点是各种排序方法的优缺点及时间复杂度分析。三、讲授内容：直接插入排序；冒泡排序；直接选择排序；（四）（五）快速排序；堆排序；（六）（七）四、思考题:归并排序；基数排序。试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、第二部分实验内容（12学时） 插入、删除、合并、查找（4学时） -建立二叉树、遍历二叉树（2学时）寻找两顶点间边数最少的一条路径（2学时） 静态、动态查找算法（2学时） 数组、链表排序算法（2学时）1.线性表操作2.3.4.树和二叉树的应用图的应用查找排序稳定性和适用情况。5.五、开课时间（时长）、规定学时及成绩考核、评定方式：本课程开课时长：一学期；规定学时：72学时，其中讲课60学时,实验12学时；本课程的考核以闭卷 考试进行，总成绩：平时成绩占30%，期末闭卷考试占70% 。六、使用教材及主要参考书、参考文献：教材：数据结构（C语言版）邓文华 李益明编著 电子工业出版社 参考书：1. 数据结构（C语言版） 严蔚敏 吴伟民编著 清华大学出版社2. 数据结构题集（C语言版）严蔚敏吴伟民编著清华大学出版社3. 数据结构导论习题祥解黄明梁旭