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

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

英文名称：DataStructure

适用专业：计算机科学与技术（考试）、软件工程（考试）、数字媒体技术（考

试）、网络工程（考试）、通信工程（考试）

学时：64学分：3.5

课程类别：学科大类基础课

课程性质：必修课

一、课程的性质和目的

数据结构是计算机学科的核心专业基础课程，是计算机程序设计的重要理论

和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数

组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能

和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软

件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和

上机编程实践，编程能力有了进一步提高。

二、课程教学内容

第一章绪论

基本内容：

1.了解数据结构的基本概念；

2.了解数据类型和抽象数据类型的概念；

3.理解算法的设计目标；

4.掌握算法的时间复杂度概念和算法的时间复杂度分析方法。

教学难点：

1.算法的时间复杂度概念；

2.算法的时间复杂度分析方法。

第二章线性表

基本内容：

1.了解线性表的逻辑结构和基本操作；

2.理解线性表的顺序存储结构和实现方法；

3.理解线性表的链式存储结构和实现方法；

4.了解单循环链表和双向链表的概念和基本设计方法。

教学重点：

1.顺序存储结构和顺序表的设计方法；

2.链式存储结构和单链表的设计方法。

教学难点：

单链表的设计方法，主要是单链表操作实现的算法语句学生理解有困难。

第三章堆栈和队列

基本内容：

1.理解堆栈的概念、顺序堆栈和链式堆栈的设计方法；

2.理解队列的概念、顺序循环队列和链式队列的设计方法；

3.了解堆栈和队列的应用方法。

教学重点：

1.顺序堆栈和链式堆栈的设计方法；

2.顺序循环队列和链式队列的设计方法。

教学难点：

顺序循环队列的几种典型队空和队满判断方法。

第四章串

基本内容：

1.理解串的概念和串的基本操作；

2.理解串的静态存储结构、动态存储结构和链式存储结构；

3.了解串基本操作的实现方法；

4.了解串的BF模式匹配方法。

教学重点：

串的动态存储结构。

第五章数组

基本内容：

1.理解数组的概念和数组的静态、动态存储结构；

2.了解特殊矩阵的压缩存储方法；

3.了解稀疏矩阵的基本压缩存储方法，包括稀疏矩阵的三元组概念，以及稀

疏矩阵三元组的顺序表、单链表和十字链表存储结构。

教学重点：

数组的动态存储结构。

第六章递归

基本内容：

1.理解递归的概念、递推公式的归纳方法和递归算法的执行过程；

2.掌握递归算法的问题分析和算法设计方法；

3.了解递归算法时间效率低的原因；

教学重点：

1.递推公式的归纳；

2.递归算法的执行过程；

3.递归算法的设计方法。

教学难点：

设计递归算法的问题分析方法。

第七章树和二叉树

基本内容：

1.了解树的定义、树的表示方法和树的几种典型存储结构；

2.理解二叉树的定义、二叉树的性质、二叉树的存储结构和二叉树操作的

实现方法；

3.掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现；

4.理解哈夫曼树的概念和哈夫曼树在编码方面的应用方法；

5.理解树与二叉树的转换方法；

6.理解树的遍历方法。

教学重点：

1.二叉树的性质、二叉树的存储结构；

2.二叉树的遍历算法和二叉树遍历算法的应用；

3.哈夫曼树在编码方面的应用方法。

教学难点：

1.二叉树的性质以及利用这些性质分析问题的方法；

2.二叉树问题的遍历算法设计分析和实现。

第八章图

基本内容：

1.了解图的基本概念和术语；

2.掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；

3.理解图的深度和广度遍历方法和算法设计方法；

4.理解最小生成树的概念、以及普里姆算法和克鲁斯卡尔算法；

5.了解最短路径问题的基本概念和从一个结点到其余各结点最短路径的算

法

教学重点：

1.图的邻接矩阵和图的邻接表存储结构；

2.图的深度和广度遍历方法；

3.普里姆算法和克鲁斯卡尔算法。

教学难点：

图操作的实现方法。

第九章排序

基本内容：

1.掌握排序的基本概念和排序算法的评判标准；

2.理解直接插入排序、希尔排序、直接选择排序、堆排序、快速排序、二

路归并排序、基数排序的算法思想和算法设计方法；

3.理解各种排序方法的性能特点。

教学重点：

希尔排序、堆排序、快速排序、二路归并排序和基数排序的算法思想。

教学难点：

堆排序、快速排序、二路归并排序和基数排序的算法设计方法。

第十章查找

基本内容：

1.掌握查找的基本概念和查找方法的评判标准；

2.理解顺序查找和有序查找的算法设计方法，理解索引查找的基本结构；

3.了解二叉排序树和B-树的基本结构和插入、删除方法；

4.哈希函数、哈希冲突函数和哈希表的构造方法。

教学重点：

1.二叉排序树和B-树的插入和删除方法；

2.哈希函数、哈希冲突函数和哈希表的构造方法。

三、课程教学的基本要求

1.本课程的教学包括课堂讲授、学生自学、课程设计（独立设课）、作业、

辅导答疑、期末考试等教学环节。

2.课堂教学以课堂讲授为主，要求在必要时采用CAI课件以增大信息量。

3.要求算法设计内容采用vc++开发环境，配合大屏幕投影演示，以理论结

合实际和提高学生的学习兴趣。

4.通过本课程的教学，学生在理解和掌握大纲所要求的知识内容的基础上，

具有编写简单数据结构问题或简单算法的上机编程能力，为后续课程的学习奠定

坚实的理论和实践基础。

四、课程学时分配

讲课内容学时

1.绪论2

2.线性表10

3.堆栈和队列6

4.串2

5.数组2

6.递归2

7.树和二叉树10

8.图6

9.排序6

10.查找6

11.上机实验12