《数据结构》详细教学大纲

……………………………………………………………………装……订……线…………………………………………………………………………………………………………… 3、教学重点：

1、二叉树的定义、性质和存储结构 2、二叉树的各种遍历方法及实现

3、建立二叉树、输出二叉树、求二叉树深度等操作方法及实现 4、哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生 4、难点：

1、二叉树的定义、性质和存储结构 2、二叉树的各种遍历方法及实现

3、建立二叉树、输出二叉树、求二叉树深度等操作方法及实现 4、哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生

第五章：图（10学时）

1、讲授内容：

1、图的定义和术语

了解图的定义、性质和表示方法。 2、图的邻接矩阵、邻接表表示

掌握图的邻接矩阵、邻接表表示，能够画出正确的示意图。 3、图的深度和广度优先搜索遍历

掌握图的深度和广度优先搜索遍历，了解相应的算法设计。 4、图的生成树和最小生成树

掌握图的生成树和最小生成树的原理，了解相应的算法设计。 5、拓扑排序

掌握拓扑排序的原理，了解相应的算法设计。 2、教学要求：

了解：图的定义、性质和表示方法，图的深度和广度优先搜索遍历相应的算法设计，图的生成树和

最小生成树的相应的算法设计以及拓扑排序的相应的算法设计。

理解：

掌握：图的邻接矩阵、邻接表表示，能够画出正确的示意图。掌握图的深度和广度优先搜索遍历，

图的生成树和最小生成树的原理，拓扑排序的原理.

3、教学重点：

1、图的邻接矩阵、邻接表表示 2、图的深度和广度优先搜索遍历

……………………………………………………………………装……订……线…………………………………………………………………………………………………………… 3、图的生成树和最小生成树 4、难点：

1、图的邻接矩阵、邻接表表示 2、图的深度和广度优先搜索遍历 3、图的生成树和最小生成树

第六章：查找（10学时）

1、讲授内容：

1、顺序查找和二分查找

掌握顺序查找和二分查找的原理，掌握相应的算法设计。 2、索引查找和分块查找

掌握索引查找和分块查找的原理，了解相应的算法设计。 3、散列查找

掌握散列查找的原理，了解相应的算法设计。 2、教学要求：

了解：索引查找和分块查找以及散列查找相应的算法设计。 理解：

掌握：顺序查找和二分查找的原理，掌握相应的算法设计。掌握索引查找和分块查找以及散列查找

的原理。

3、教学重点：顺序查找和二分查找 4、难点：

1、索引查找和分块查找 2、散列查找

第七章：排序（8学时）

1、讲授内容：

1、排序的基础概念

了解排序的基础概念和相应算法的分析方法。 2、直接插入排序和变形

掌握直接插入排序的原理和相应的算法设计。 3、冒泡排序和快速排序

掌握冒泡排序和快速排序的原理和相应的算法设计。 4、直接选择排序和堆排序

掌握直接选择排序和堆排序的原理和相应的算法设计。

……………………………………………………………………装……订……线…………………………………………………………………………………………………………… 5、归并排序

了解归并排序的原理和相应的算法设计。 6、基数排序

了解基数排序的原理和相应的算法设计。 2、教学要求：

了解：排序的基础概念和相应算法的分析方法。了解归并排序的原理和相应的算法设计。了解基数

排序的原理和相应的算法设计。

理解：

掌握：直接插入排序的原理和相应的算法设计。掌握冒泡排序和快速排序的原理和相应的算法设计。

掌握直接选择排序和堆排序的原理和相应的算法设计。

3、教学重点：

1、冒泡排序和快速排序 2、直接选择排序和堆排序 4、难点：直接插入排序和变形

三、各教学环节的基本要求

（一）课堂讲授 1、教学方法 讲授法、实验法 2、教学手段

（1）采用启发式、讨论式、实例分析教学等多种方式，充分利用多媒体等现代化教学手段，整体优

化教学过程和教学内容，调动学生学习积极性；

（2）贯彻精讲的原则，注重三基内容的讲解，突出重点，照顾一般，图文并貌，重在基本概念的理

解；

（3）贯彻理论和实践相结合的原则，给学生出一定量的思考题、设计题，并要求学生完成一定量的

作业，以提高学生对数据结构课程基本概念和理论技巧的深入理解，提高其动手操作的能力。 （4）分析与总结相结合，对讲授内容及时总结，对重点内容深入分析，深入浅出，循序渐进。 3、教学辅助资料

[1] 马春江. 新编数据结构教程. 电力出版社，2006,3.

[2] 朱站立. 数据结构(使用C语言)（第3版）．西安交通大学出版社，2004,1. [3] 朱站立. 数据结构学习指导与典型题解. 西安交通大学出版社，2002,3. [4] 陈元春、张亮、王勇. 实用数据结构基础. 中国铁道出版社，2003，第1版.

……………………………………………………………………装……订……线…………………………………………………………………………………………………………… （二）作业、答疑和质疑 1、作业

1、线性表基本操作的编程实现，掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链接结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

2、堆栈和队列基本操作的编程实现，掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

3、二叉树基本操作的编程实现，掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用链接结构，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

4、图基本操作的编程实现，掌握图的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构可以在顺序结构或链接结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

5、查找技术的编程实现，掌握查找技术的编程实现，可以实现一种，也可以实现多种，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

6、排序技术的编程实现，掌握排序技术的编程实现，可以实现一种，也可以实现多种，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。 2、答疑和质疑

通过学生作业的情况了解学生对知识点的掌握情况，要求把每次作业的程序文本和运行结果存入到本人的用户目录下或其它方式供老师检查。通过学生作业的情况进行讲解和复习巩固所学的知识。

（三）考核方式

本课程考核包括笔试、平时成绩和上机编程三个部分。笔试占70%，由教研室统一命题或教师自行命题考核；平时成绩占20%，由任课教师负责考核；上机编程占10%，成绩由任课老师或实验室实验指导老师负责考核。

四 、与其他课程的联系与分工

《数据结构》的先修课主要是《C语言程序设计》和《离散数学》，本课程将以C语言作为算法描述和上机实践的工具，而理论基础有一部分在《离散数学》中有所体现。另外，本课程又是后续软件开发与设计等课程的基础。注意：高级语言中的结构体、指针、链表、递归、对象和离散数学中的集合论、关系论、图论、树等都构成了本课程的基础知识。