数据结构课程标准终审稿)

数据结构课程标准

文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58-

《数据结构》课程标准（专科）

一、课程的性质：

《数据结构》是计算机专业的一门必修专业基础课，它是一门理论性强，但有一定的实践性和较强实用性的基础课程。 二、课程的教学目的与任务：

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

本课程理论讲授采用教材与多媒体相配合的教学手段。

本课程包括课堂教学与实践教学两大部分。课堂教学在方法上，采用课堂讲授、课后自学、课堂讨论、课外作业、平时测验等教学形式。实践教学部分主要是实验。 四、课程内容及学时分配（共 72学时,其中讲课60学时,实验12学时）：

第一部分 讲授内容（60学时） 第一章 绪论（共4学时）

第一节 有关概念和术语（2学时） 一、基本要求：

掌握数据结构的一些基本概念，了解抽象数据类型的定义和使用。 一、 教学重点及难点：

本节重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。教学难点是什么是数据的逻辑结构及物理结构？

三、讲授内容：

（一）数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。

（二）抽象数据类型。 四、思考题：

举出一个数据结构的例子，叙述其逻辑结构、存储结构、结构上的操作内容。 第二节 算法及算法分析（2学时） 一、基本要求：

掌握算法的时间复杂度和空间复杂度的分析方法，了解算法的描述方法。 二、教学重点及难点：

本节重点是算法的各种描述方法和算法分析（时间复杂度及空间复杂度）。教学难点是对一个算法时间复杂度的分析。 三、讲授内容：

（一）描述算法所用的C语言中的一些有关问题。

（二）算法时间复杂度和空间复杂度的分析。 四、思考题：

23n

编写算法，求一元多项式Pn(x)=a0+a1x+a2x+a3x+…anx的值Pn(x0)，要求时间复杂度尽可能小。

第二章 线性表（12学时）

第一节 线性表的顺序存储结构（６学时） 一、基本要求：

理解线性表的定义和基本操作；掌握数组的存储（例如：数组元素在内存位置的计算方法）和在顺序存储结构上的基本操作（如插入、删除、合并、划分和比较等）的实现。 二、教学重点及难点：

本节重点是线性表的逻辑结构、线性表的顺序存储存构C语言描述、基本操作实现方法和简单应用。教学难点是用C语言实现基本操作和如何通过顺序存储结构解决实际问题。

三、讲授内容：

（一）线性表的定义和基本操作； （二）线性表的顺序存储结构；

（三）定义在顺序存储结构上的基本操作的实现； （四）应用举例及分析。 四、思考题：

设有两个按元素值递增有序顺序表A和B，编一程序将A表和B表归并成一个新的递增有序的顺序表C（值相同的元素均保留在C表中）。 第二节 线性表的链式存储结构（６学时） 一、基本要求：

掌握单链表的基本结构及基本操作（如建立、查找、插入和删除等）；掌握循环链表和双向链表；能用单链表解决一些实际问题。 二、教学重点及难点：

本节重点是顺序存储结构及链式存储结构的优缺点，如何用C语言实现链式存储结构，单链表上基本操作的实现，各种链表的结构：循环链表，双向链表和单链表的一些简单应用。教学难点是单链表上基本操作的实现和建立在链表上的一些应用。 三、讲教内容：

（一）链式存储结构的实现方法； （二）单链表的基本操作；

（三）循环链表及双向链表的实现； （四）应用举例。 四、思考题：

分析单链表、循环链表和双向链表的相同点、不同点及各自的特点。

第三章 栈和队列（8学时）

第一节 栈（4学时） 一、基本要求：

掌握栈的定义，掌握顺序和链式存储的栈的基本操作实现。

二、教学重点及难点：

本节重点是栈的逻辑结构定义，用C语言实现栈的两种方式：顺序存储结构及链式存储结构，栈的基本操作的实现。教学难点是栈的基本操作的实现和一些具体应用。 三、讲授内容：

（一）栈的定义及基本运算；

（二）栈的顺序存储和链接存储的表示；

（三）在栈的顺序存储和链接存储上进行各种栈操作的算法； （四）栈的应用举例。 四、思考题：

求2阶Fibonacci数列的递归算法。 第二节 对（4学时） 一、基本要求：

掌握队列的定义、顺序存储及链接存储时的操作，掌握顺序存储下循环队列的插入、删除运算算法。

二、教学重点及难点：

本节重点是队列的逻辑定义，用C语言实现队列的两种方式：顺序存储结构及链式存储结构，队列的基本操作实现和循环队列的实现。教学难点是队列的基本操作的实现和循环队列的实现方式。 三、讲授内容：

（一）队列的类型定义；

（二）队列的顺序存储(循环队)表示及各种操作的实现算法； （三）队列的链接存储表示及各种操作的实现算法。 四、思考题：

队列管理的模拟算法（队列采用带头结点的链表结构）。

第四章 串和数组（4学时）

第一节 串（2学时） 一、基本要求：

理解串的定义和基本操作，掌握用C语言如何实现物理存储结构：顺序存储结构及堆结构和串的合并、定位、比较算法。 二、教学重点及难点：

本节重点是串的物理存储结构和串的基本操作的实现。教学难点是串的堆分配结构。 三、讲授内容：

（一）串的类型定义； （二）串的存储结构；

（三）串的基本操作的实现。 四、思考题：

设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。 第二节 数组（2学时） 一、基本要求：

掌握二维数组的存储结构和稀疏矩阵的压缩存储。了解稀疏矩阵的转置算法。 二、教学重点及难点：

本节重点是矩阵的向量存储结构和稀疏矩阵的压缩存储。教学难点是稀疏矩阵的压缩存储。

三、讲授内容：

（一）二维数组的存储结构； （二）稀疏矩阵； （三）应用举例。 四、思考题：

稀疏矩阵转置算法。

第五章 树和二叉树（10学时）

第一节 二叉树（6学时） 一、基本要求：

掌握树的定义，相关术语及基本操作；掌握二叉树的定义，性质，存储结构，基本操作和二叉树的遍历。 二、教学重点及难点：

本节重点是树的定义，二叉树的定义、性质、存储结构、基本操作和遍历。教学难点是二叉树的性质。 三、讲授内容：

（一）树的概念与基本操作； （二）二叉树的定义、性质； （三）二叉树的存储结构； （四）二叉树的遍历； （五）二叉树的举例 四、思考题：

建立二叉树并写出其前序遍历、中序遍历的非递归算法。 第二节 树与森林（4学时） 一、基本要求：

掌握树的存储结构，树、森林与二叉树的转化，树和森林的遍历；掌握哈夫曼树和哈夫曼编码。

二、教学重点及难点：

本节重点是树、森林与二叉树的转化，树和森林的遍历操作，哈夫曼树。教学难点是树的存储结构，树、森林与二叉树的转化和哈夫曼树。 三、讲授内容：

（一）树的存储结构；

（二）树、森林与二叉树的转化； （三）树和森林的遍历；

（四）哈夫曼树的定义、构造哈夫曼树的方法； （五）哈夫曼编码的方法。 四、思考题：

在以孩子兄第链表结构存储的树中，写出求树中结点孩子的算法。

第六章 图（8学时）

第一节 图的存储和遍历（4学时） 一、基本要求：

掌握图的定义和术语，图的存储表示和遍历方式。 二、教学重点及难点：

本节重点是图的定义和术语，图的存储结构，图的遍历。教学难点是图的存储结构和图的遍历方式。 三、讲授内容：

（一）图的定义和术语；

（二）图的邻接矩阵和邻接表表示； （三）图的深度和广度优先查找。 四、思考题：

编写算法：在无向图的邻接距阵结构上，生成无向图的邻接链表结构。 第二节 图的应用（4学时） 一、基本要求：

掌握图的生成树及最小生成树，求最短路径，拓扑排序。 二、教学重点及难点：

本节重点是最小生成树问题，最短路径问题，拓扑排序的方法。教学难点是最小生成树问题和求最短路径。 三、讲授内容：

（一）图的生成树和最小生成树； （二）最短路径； （三）拓扑排序。 四、思考题：

对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____和_____。

关键路径是什么？

第七章 查找（6学时）

第一节 静态查找和动态查找（3学时） 一、基本要求：

掌握查找的基本方式；掌握静态表上顺序查找，有序表的折半查找和分块查找；掌握动态查找：二叉排序树的生成和插入，二叉排序树上的查找。 二、教学重点及难点：

本节重点是顺序查找，有序表的折半查找，查找成功查找长度分析和二叉排序树上的查找。教学难点是成功查找及不成功查找分析。 三、讲授内容：

（一）静态查找：顺序查找，有序表的折半查找和分块查找； （二）动态查找：二叉排序树上的查找。

四、思考题：

对长度为 10 的有序表进行折半查找的判定树，并求其等概时查找成功的平均查找长度。

第二节 哈希表（3学时） 一、基本要求：

掌握哈希表的查找方式,常用哈希函数的构造方法，解决冲突的主要方法，哈希表的查找及性能分析。

二、教学重点及难点：

本节重点是哈希表的查找方式,哈希函数的构造，解决冲突的方法，哈希表的查找及性能分析。教学难点是哈希表的查找和如何解决冲突。 三、讲授内容：

（一）哈希表和哈希方法；

（二）常用哈希函数的构造方法； （三）处理冲突的方法；

（四）哈希表的查找及性能分析。 四、思考题：

为什么说当装填因子非常接近1时，线性探查类似于顺序查找为什么说当装填因子比较小(比如α=0.7左右)时，散列查找的平均查找时间为O(1)

第七章 排序（8学时）

一、基本要求：

掌握直接插入排序、冒泡排序、简单选择排序的方法及其实现；掌握快速排序、堆排序、二路归并排序的方法；掌握各种排序方法的稳定性、时间复杂度和空间复杂度。 二、教学重点及难点：

本节重点是各种排序（直接插入排序，冒泡排序，简单选择排序，快速排序，堆排序，归并排序和基数排序）及时间复杂度分析。教学难点是各种排序方法的优缺点及时间复杂度分析。 三、讲授内容：

（一）直接插入排序； （二）冒泡排序；

（三）直接选择排序； （四）快速排序； （五）堆排序； （六）归并排序； （七）基数排序。 四、思考题：

试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。

第二部分 实验内容（12学时）

1. 线性表操作 ——插入、删除、合并、查找（4学时）

2. 树和二叉树的应用 ——建立二叉树、遍历二叉树（2学时） 3. 图的应用 ——寻找两顶点间边数最少的一条路径（2学时） 4. 查找 ——静态、动态查找算法（2学时） 5. 排序 ——数组、链表排序算法（2学时）

五、开课时间（时长）、规定学时及成绩考核、评定方式：

本课程开课时长:一学期；规定学时：72学时,其中讲课60学时,实验12学时；本课程的考核以闭卷考试进行，总成绩：平时成绩占 30%，期末闭卷考试占 70% 。 六、使用教材及主要参考书、参考文献：

教材：《数据结构》（C语言版）邓文华 李益明编着 电子工业出版社 参考书：

1．《数据结构》（C语言版） 严蔚敏 吴伟民编着 清华大学出版社

2．《数据结构题集》（C语言版） 严蔚敏 吴伟民编着 清华大学出版社 3．《数据结构导论习题祥解》黄明 梁旭编着 机械工业出版社 七、实践教学的指导思想及方式： 实践教学的指导思想：

1．能根据实际问题的需要选择合适的数据结构设计出相应的算法； 2．能上机调试并最终得出正确结果； 3．能评价程序的优劣并用较好的方法编程。

每章有相当数量的上机题，要求学生选部分习题编程，上机调试，完成上机调试、获取实验结果、写出实习报告。 八、其它说明：

１．本课程开设之前先修《C语言程序设计》课程。

２．本课程应理论与实践相结合，教学中保证必要的上机时间。 ３．本大纲适用于计算机专业专科学生。