数据结构(第二版)-电子教案全书课程设计1-9章全.doc

教 案（理论课）
第 1 次课 2 学时
章 节
第一章 绪论
1.1 数据结构的发展
1.2 数据结构的意义
1.3 数据结构的基本概念和术语
讲授主要内 容
介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语。
重 点
难 点
重点：
数据结构及相关概念；
数据的逻辑结构、存储结构及运算之间的关系；
难点：
数据元素；逻辑关系；抽象数据类型
要求掌握知识点和分析方法
l 了解数据结构的发展
l 理解数据结构中的基本概念
l 理解抽象数据类型的概念、记法和用法
教学设计
1. 从数据在计算机中的处理过程入手，介绍课程
2. 介绍数据结构课程的意义及其在教学计划中的核心地位
3. 介绍教材整体结构
4. 提出学习方法及要求：强调课后练习及实验的重要性，介绍配套网络教学平台
5. 讲授数据结构的基本概念
6. 通过实例辅助分析数据结构的三个方面：逻辑结构、存储结构及运算，重点结束逻辑关系，强调存储结构如何表示逻辑关系。注意引申三者之间的关系
7. 在理解数据类型和抽象的基础上，给出抽象数据类型的定义。分析：为什么对数据结构仅定义基本操作
作业布置
习题1
一．1~3 二．1~6 三．1,2
教学后记

教 案（理论课）
第 2 次课 2 学时
章 节
第一章 绪论
1.4 算法及其分析

讲授主要内 容
介绍算法的定义，算法的基本特性，算法的描述方法，讲授算法复杂度的分析方法。
重 点
难 点
重点：
算法的定义及基本特性；
算法复杂度的分析方法。
难点：
算法复杂度的分析方法。
要求掌握知识点和分析方法
l 理解算法的定义及基本特性
l 理解算法的描述方法
l 理解算法与程序的关系
l 掌握算法复杂度的分析方法
教学设计
1. 以实例引入算法定义
2. 从使用的角度分析算法的特性
3. 介绍算法的描述方法：自然语言、流程图、程序设计语言等
4. 分析算法与程序的关系，指出：程序设计的核心是算法设计
5. 给出算法分析的意义，介绍事前分析法和事后统计法
6. 给出问题规模、语句频度、大O记号的概念
7. 结合例题，讲授常用的几种时间复杂度
作业布置
习题1
一．4 二．7~9 三．3 四．
教学后记

教 案（理论课）
第 3 次课 2 学时
章 节
第二章 线性表
2.1 线性表的逻辑结构
2.2 线性表的顺序存储结构

讲授主要内 容
举例讲解线性表，分析其逻辑结构。介绍线性表的抽象数据类型。讲授顺序表的存储结构及特点，分析讲授顺序表的各种基本运算。
重 点
难 点
重点：
线性表的定义及其逻辑结构
顺序表的存储结构及特点
顺序表的基本运算及其性能分析
难点：
顺序表的基本运算及其性能分析

要求掌握知识点和分析方法
l 掌握线性表的定义及其逻辑结构
l 理解线性表的抽象数据类型
l 掌握顺序表的存储结构及特点
l 掌握顺序表的基本运算：插入、删除及查找运算及其性能分析
教学设计
8. 给出线性表的定义，注意强调要点，分析其逻辑结构
9. 给出线性表的抽象数据类型
10. 给出顺序表的存储结构示意图，强调存储要点，总结存储特点
11. 给出顺序表的建表算法
12. 利用算法动画演示，分析顺序表的插入运算执行过程，写出插入算法并分析
13. 利用算法动画演示，分析顺序表的删除运算执行过程，写出删除算法并分析
14. 利用算法动画演示，分析顺序表的查找运算执行过程，写出查找算法及分析
作业布置
习题2
一．1~6 二．1,2,4,5,6 三．1,2
教学后记

教 案（实验课）
第 4 次课 2 学时
章 节
第二章 线性表
线性表的顺序存储结构
重 点
难 点
重点：
顺序表的基本运算及其性能分析
难点：
顺序表的基本运算及其性能分析

要求掌握知识点和分析方法
l 掌握顺序表的存储结构及特点
l 掌握顺序表的基本运算：插入、删除及查找运算及其性能分析
教学内容
实现在顺序表上的基本运算。
要求：
1. 实现顺序表的建立，采用给定的数组做输入和从键盘输入两种方式实现
2. 实现顺序表的插入
3. 实现顺序表的删除
4. 实现顺序表的查找：按值查找和按位置查找
5. 实现顺序表的逆置
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 5 次课 2 学时
章 节
第二章 线性表
2.3 线性表的链式存储结构

讲授主要内 容
举例讲解链表，分析其逻辑结构。讲授单链表上实现的基本运算。
重 点
难 点
重点：
链表的结构。
单链表上实现的基本运算：头插法
难点：
单链表上实现的基本运算
要求掌握知识点和分析方法
l 理解链表的含义及其逻辑结构
l 掌握单链表的基本运算及其性能分析
教学设计
1. 给出单链表的存储结构示意图，强调存储要点，总结存储特点
2. 利用算法动画演示，分析单链表的头插法、尾插法建表运算执行过程，写出算法并分析
3. 利用算法动画演示，分析单链表的插入运算执行过程，写出插入算法并分析
4. 利用算法动画演示，分析单链表的删除运算执行过程，写出删除算法并分析
5. 利用算法动画演示，分析单链表的查找运算执行过程，写出查找算法及分析
作业布置
习题2
一．7~10 二．3,7 三．3,4,5
教学后记

教 案（理论课）
第 6 次课 2 学时
章 节
第二章 线性表
2.4 顺序表与链表的比较
2.5 案例实现
讲授主要内 容
讲授单循环链表、双链表。分析顺序表与链表的差异。分析本章案例。
重 点
难 点
重点：
单循环链表与双链表的逻辑结构与基本操作。
顺序表与链表的比较
难点：
单循环链表的基本操作
双链表的基本操作
要求掌握知识点和分析方法
l 掌握循环链表、双链表的存储结构
l 熟练掌握循环链表的基本操作
l 掌握双链表的基本操作
l 掌握顺序表与链表的比较
教学设计
1. 通过在单链表中查找前驱结点的问题，引入单循环链表。分析单循环链表的逻辑结构及其与单链表的区别。解决“求循环链表中任意一个结点的前驱结点”的问题
2. 分析双链表的逻辑结构及其特点，通过图示讲解在双链表上实现的基本查找
3. 分析解析顺序表与链表在时间、空间、程序设计语言三方面的区别与联系。
4. 通过顺序表、链表两种方式实现本章案例：通讯录管理系统。
作业布置
习题2
一．11~14 二．8,9,10 三．6,7
教学后记

教 案（实验课）
第 7 次课 2 学时
章 节
第二章 线性表
线性表的链式存储结构
重 点
难 点
重点：
链表的基本运算及其性能分析
难点：
链表的基本运算及其性能分析

要求掌握知识点和分析方法
l 掌握链表的存储结构及特点
l 熟练掌握链表的基本运算：插入、删除及查找运算及其性能分析
l 掌握单循环链表、双链表的基本操作
教学内容
实现在顺序表上的基本运算。
要求：
1. 实现链表的建立，选用头插法或尾插法实现
2. 实现链表的插入
3. 实现链表的删除
4. 实现链表的查找：按值查找和按位置查找
5. 实现单链表中查找任意顶点前驱的操作
6. 实现双链表中的插入运算：在值为x的结点前插入值为2x的结点
7. 实现单链表的逆置
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 8 次课 2 学时
章 节
第三章 栈和队列
3.1 栈

讲授主要内 容
分析栈的逻辑结构，讲述顺序栈与链栈的存储特点及分别在顺序栈和链栈上实现的运算。介绍“顺序栈和链栈的比较”，以所学的知识实现“栈的应用”。
重 点
难 点
重点：
6. 栈的类型定义。
7. 栈的顺序存储和链接存储的表示。
8. 在栈的顺序存储和链接存储上进行各种栈操作的算法。
难点：
1. 栈的顺序存储和链接存储的表示。
2. 在栈的顺序存储和链接存储上进行各种栈操作的算法。
要求掌握知识点和分析方法
l 掌握栈的定义及其逻辑结构
l 理解栈的抽象数据类型
l 掌握顺序栈和链栈的实现方法
l 了解双栈共享空间
教学设计
1. 以汉诺塔游戏引入栈，分析其逻辑结构及其“后进先出”的特性
2. 给出栈的抽象数据类型
3. 分析顺序栈的工作原理，介绍“上溢”和“下溢”
4. 利用算法动画演示，分析顺序栈的进栈、出栈过程，给出相应算法并分析
5. 利用例题，分析链栈的进栈、出栈过程，给出相应算法并分析
6. 介绍顺序栈和链栈的比较：从时间性能和空间性能两个角度
7. 简单介绍双栈的原理
8. 介绍栈的应用：递归
作业布置
习题3
一．1,2,7~10 二．2,4,5,6 三．1,2,3,4 四 五. 1~4
教学后记

教 案（实验课）
第 9 次课 2 学时
章 节
第三章 栈和队列
3.1 栈
重 点
难 点
重点：
1. 栈的类型定义。
2. 栈的顺序存储和链接存储的表示。
3. 在栈的顺序存储和链接存储上进行各种栈操作的算法。
难点：
1. 栈的顺序存储和链接存储的表示。
2. 在栈的顺序存储和链接存储上进行各种栈操作的算法。
要求掌握知识点和分析方法
l 掌握栈的定义及其逻辑结构
l 理解栈的抽象数据类型
l 掌握顺序栈和链栈的实现方法
l 了解双栈共享空间
教学内容
一、 讲授：
1. 介绍栈的应用：表达式求值
2. 利用算法动画演示，分析括号匹配算法
二、上机完成案例。
要求：
1. 实现算数表达式的求值
2. 实现判定表达式是否为“回文”
3. 实现本章案例：汉诺塔
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 10 次课 2 学时
章 节
第三章 栈和队列
3.2 队列

讲授主要内 容
讲解队列并分析其逻辑结构。讲授队列上实现的基本运算。
重 点
难 点
重点：
1、队列的类型定义。
2、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。
难点：
1、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

要求掌握知识点和分析方法
l 理解顺序队列、循环队列、链队列的类型定义及其逻辑结构
l 掌握顺序队列、循环队列、链队列的基本运算及其性能分析
l 了解双端队列
教学设计
9. 给出队列的存储结构示意图，强调存储要点，总结存储特点
10. 利用算法动画演示，分析顺序队列的入队、出队过程
11. 由例题引出顺序队列的“假溢出”现象
12. 分析“假溢出”的解决方案，引入循环队列的教学。
13. 讲授循环队列的基本操作，注意分析队空和队满的判定条件
14. 讲授链队列的基本操作
15. 介绍双端队列
16. 分析循环队列与链队列的对比

作业布置
习题3
一．3,11~16 二．1,3,7 三．5~8 五.5,6,7
教学后记

教 案（实验课）
第 11 次课 2 学时
章 节
第三章 栈和队列
3.3队列
重 点
难 点
重点：
1、队列的类型定义。
2、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。
难点：
1、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

要求掌握知识点和分析方法
l 掌握链表的存储结构及特点
l 熟练掌握链表的基本运算：插入、删除及查找运算及其性能分析
l 掌握单循环链表、双链表的基本操作
教学内容
一、 讲授：
1. 介绍队列的应用：舞伴问题
2. 利用算法动画演示，杨辉三角问题
二、上机完成案例。
要求：
1. 实现本章案例：键盘缓冲区
2. 实现本章案例：杨辉三角问题
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 12 次课 2 学时
章 节
第四章 串

讲授主要内 容
串的定义及基本操作；串的存储结构；串的模式匹配算法。
重 点
难 点
重点：
1、“串”类型定义中各基本操作。
2、 串的模式匹配算法：BF算法。
难点：
串的模式匹配算法。
要求掌握知识点和分析方法
l 掌握串的定义及其基本概念
l 理解串的抽象数据类型
l 掌握串的基本操作
l 理解串的存储结构
l 掌握BF算法
l 了解KMP算法
教学设计
9. 由案例给出串的定义，总结串的特性。注意区分空串与空白串的不同。
10. 介绍串的抽象数据类型
11. 举例分析串的基本操作
12. 分析串与普通线性表的不同，引出串的三种存储结构
13. 利用算法动画演示，分析模式匹配的基本过程，给出相应算法并分析
14. 分析BF算法，找出其效率低下的原因，引出KMP算法。对KMP算法的基本思想做简单介绍，具体分析及算法实现可以根据情况由学生课后完成。

作业布置
习题4
教学后记

教 案（理论课）
第 13 次课 2 学时
章 节
第五章 数组和广义表
5.1 多维数组
5.2 矩阵的压缩存储
讲授主要内 容
数组的定义；数组的存储结构与寻址；
特殊矩阵的压缩存储；稀疏矩阵的压缩存储
重 点
难 点
重点：
掌握二维数组的存储方式和矩阵的压缩方式
难点：
特殊矩阵的压缩存储；稀疏矩阵的压缩存储
要求掌握知识点和分析方法
l 掌握数组的定义
l 熟练掌握二维数组的存储方法及寻址
l 掌握矩阵压缩存储的思想
l 掌握特殊矩阵的压缩存储方法及寻址
l 掌握稀疏矩阵的压缩存储方法及寻址：三元组表
教学设计
17. 给出数组的定义
18. 提出问题：多维数组如何存储在内存中呢？引入二维数组的存储方法：行优先和列优先存储方法
19. 给出练习，加强学生对二维数组存储方法及寻址方式的理解
20. 给出一个对称矩阵的例子，分析一下采用普通存储方式的缺陷，提出矩阵压缩存储。
21. 介绍对称矩阵、三角矩阵、对角矩阵的存储方式
22. 给出一个稀疏矩阵的例子，引出稀疏矩阵的压缩存储。
23. 介绍三元组表示法，并以三元组为存储结构分析稀疏矩阵转置算法。
作业布置
习题5
一．1~3 二．1~5 三．1,2,3 四.1,2 五.1
教学后记

教 案（理论课）
第 14 次课 2 学时
章 节
第五章 数组和广义表
5.2 矩阵的压缩存储
5.3 广义表
5.4案例实现
讲授主要内 容
稀疏矩阵的十字链表表示法；广义表
重 点
难 点
重点：
掌握广义表的基本概念。
难点：
十字链表、广义表的存储结构和操作。

要求掌握知识点和分析方法
l 掌握稀疏矩阵的压缩存储方法及寻址：十字链表
l 掌握广义表的定义及基本性质和基本运算
l 理解广义表的存储结构
教学设计
8. 由三元组顺序表的缺点引出十字链表，画出存储示意图
9. 分析十字链表的建立算法
10. 给出广义表的定义，分析广义表的性质，指出与线性表、数组的区别联系
11. 讲授广义表的基本运算，通过课堂练习加深学生的理解
12. 介绍广义表的存储结构
13. 根据本章的理论知识，引导学生学习本章的案例实现
作业布置
习题5
一．4~6 二．6 三．4,5 四．3,4 五.2,3
教学后记

教 案（理论课）
第 15 次课 2 学时
章 节
第六章 树
6.1 树
6.2 二叉树
讲授主要内 容
树的定义和基本术语；树的抽象数据类型定义；树的存储结构；二叉树的定义；二叉树的基本性质；二叉树的抽象数据类型定义
重 点
难 点
重点：
1．树的定义和基本术语
2．树的存储结构
3．二叉树的定义
4．二叉树的性质
难点：
1． 二叉树的定义
2． 二叉树的性质
要求掌握知识点和分析方法
l 掌握树的定义和基本术语
l 理解树的抽象数据类型
l 掌握树的四种存储结构
l 掌握二叉树的定义和基本性质
l 理解二叉树的抽象数据类型
教学设计
15. 分析“团委的人事管理系统”组织图，给出树的定义，深刻理解树的逻辑结构。
16. 结合实例分析讲授树的基本术语
17. 给出树的抽象数据类型
18. 提出问题：如何实现树的存储，引出树的各种存储结构。分别从双亲、孩子多个角度引出解决方案，并分析各种存储结构的优缺点
19. 给出二叉树的定义，分析根据二叉树的定义得出的二叉树的基本形态
20. 给出两种特殊形态的二叉树——满二叉树和完全二叉树的定义，说明其特点
21. 推导、证明二叉树的基本性质
22. 介绍二叉树的抽象数据类型
作业布置
习题6
一．1,2,7~10 二．2,4,5,6 三．1,2,3,4 四 五. 1~4
教学后记

教 案（理论课）
第 16 次课 2 学时
章 节
第六章 树
6.2 二叉树
讲授主要内 容
二叉树的存储结构；二叉树的遍历；二叉树遍历的应用
重 点
难 点
重点：
二叉树的遍历
难点：
二叉树的遍历；二叉树遍历的应用
要求掌握知识点和分析方法
l 熟练掌握二叉树的遍历操作
l 掌握二叉树遍历的应用

教学设计
1. 分析二叉树的三种存储结构：顺序存储、二叉链表、三叉链表
2. 由二叉树的组成得到三种遍历次序：前序遍历、中序遍历、后序遍历
通过算法演示分析各种遍历的过程，给出递归算法及其分析
3. 由树的层次特征得到层次遍历
4. 给出二叉树的建立算法
5. 以案例形式给出二叉树遍历的应用实例（教材内容可选讲）
作业布置
习题6
一．1,2,7~10 二．2,4,5,6 三．1,2,3,4 四 五.
教学后记

教 案（实验课）
第 17 次课 2 学时
章 节
第六章 树
6.2 二叉树
重 点
难 点
重点：
二叉树的遍历
难点：
二叉树的遍历；二叉树遍历的应用
要求掌握知识点和分析方法
l 熟练掌握二叉树的遍历操作
l 掌握二叉树遍历的应用

教学内容
上机完成案例。
要求：
1. 设计一个程序，利用递归算法完成二叉树的建立、前序遍历、中序遍历、后序遍历和层次遍历
2. 仿照案例6-3,6-4,6-5，编写程序实现习题6 五大题中的3个小题
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 18 次课 2 学时
章 节
第六章 树
6.3 树、森林与二叉树
6.4 线索二叉树
6.6 案例实现——团委人事管理系统
讲授主要内 容
树与二叉树的转换；森林与二叉树的转换；树与森林的遍历
线索二叉树的定义
重 点
难 点
重点：
1．树、森林与二叉树之间的转换
2．树与森林的遍历
3. 线索二叉树的定义
难点：
1． 树、森林与二叉树之间的转换
2． 线索二叉树的定义
要求掌握知识点和分析方法
l 掌握树、森林与二叉树之间的转换
l 熟练掌握树与森林的遍历
l 理解线索二叉树的定义
教学设计
24. 从应用的角度分析树、森林和二叉树转换的意义
25. 分析树、森林和二叉树转换中的几个特点：树的孩子兄弟表示法与二叉树的二叉链表表示法的相似之处，引入转换方法。利用算法动态演示，形象展示转换方法。
26. 从树的组成得到树的遍历方法：前序和后序，层次遍历
27. 分析森林与树的关系，得到森林的遍历方法
28. 由“保存二叉树的遍历序列的方法”，分析二叉链表的构造，引入线索链表
29. 给出线索链表的存储思想，说明结点结构，根据实例画出一棵二叉树的线索链表
30. 根据教学情况，选讲线索链表的操作

作业布置
习题6
一．8,9 三．3,4,9,10 四.5,6,7,8
教学后记

教 案（理论课）
第 19 次课 2 学时
章 节
第六章 树
6.5 哈夫曼树及其应用

讲授主要内 容
哈夫曼树的基本概念；哈夫曼树的构造方法；哈夫曼编码
重 点
难 点
重点：
1．哈夫曼树的基本概念
2．哈夫曼树的构造方法
3．哈夫曼编码
难点：
1．哈夫曼树的构造方法
2．哈夫曼编码
要求掌握知识点和分析方法
l 理解哈夫曼树的定义及基本概念
l 熟练掌握哈夫曼树的构造方法
l 理解哈夫曼树的构造算法
l 理解哈夫曼编码
l 了解哈夫曼编码和译码算法
教学设计
1. 以几棵不同的二叉树为例，讲授哈夫曼树的定义及基本概念，重点分析其权值、WPL
2. 利用算法动态演示，分析、展示哈夫曼树的构造方法
3. 给出哈夫曼树的构造算法
4. 介绍等长和不等长编码，引出前缀编码
5. 利用哈夫曼树构造不等长编码的方法，通过案例讲解编码、译码的过程
6. 根据教学情况，选讲编码和译码算法
作业布置
习题6
一．10,11,12 二．14 三．8 四11,12
教学后记

教 案（实验课）
第 20 次课 2 学时
章 节
第六章 树
6.5 哈夫曼树及其应
重 点
难 点
重点：
1．哈夫曼树的基本概念
2．哈夫曼树的构造方法
3．哈夫曼编码
难点：
1．哈夫曼树的构造方法
2．哈夫曼编码
要求掌握知识点和分析方法
l 理解哈夫曼树的定义及基本概念
l 熟练掌握哈夫曼树的构造方法
l 理解哈夫曼树的构造算法
l 理解哈夫曼编码
l 了解哈夫曼编码和译码算法
教学内容
一、分析本章案例，由学生课后完成
二、上机完成案例。
要求：
利用所学的哈夫曼树知识，构建一棵哈夫曼树，并实现编码功能。
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 21 次课 2 学时
章 节
第七章 图
7.1 图的逻辑结构
7.2 图的存储结构
讲授主要内 容
图的定义和基本术语；图的抽象数据类型定义；
图的存储结构：邻接矩阵
重 点
难 点
重点：
1．图的定义和基本术语
2．邻接矩阵
3．邻接表

难点：
1．图的定义和基本术语
2．邻接矩阵

要求掌握知识点和分析方法
l 熟练掌握图的定义和基本术语
l 理解图的抽象数据类型
l 掌握图的邻接矩阵
教学设计
7. 由案例引入图的教学。
8. 给出图的定义，结合实例分析讲授图的基本术语
9. 给出图的抽象数据类型
10. 由存储图要解决的关键问题引出图的各种存储结构
11. 给出图的邻接矩阵存储结构，分析有向图、无向图、有向网、无向网的邻接矩阵表示方法。分析图的邻接矩阵存储结构的特点，采用算法动态演示，以有向图为例给出邻接矩阵建立算法
作业布置
习题7
一．1,2,3,4,7 二．1,2,3,5,6,7,9,10 三. 2,4
教学后记

教 案（理论课）
第 22 次课 2 学时
章 节
第七章 图
7.2 图的存储结构

讲授主要内 容
图的存储结构：邻接表、十字链表、邻接多重表、边集数组
重 点
难 点
重点：
1．邻接表
2．边集数组
难点：
1．邻接表
要求掌握知识点和分析方法
l 掌握图的邻接表
l 理解图的十字链表、邻接多重表、边集数组
教学设计
1. 给出图的邻接表存储结构，分析有向图、无向图、有向网、无向网的邻接矩阵表示方法。分析图的邻接表存储结构的特点，采用算法动态演示，以有向图为例给出邻接表建立算法
2. 介绍图的十字链表、邻接多重表、边集数组
3. 讲授图的各种存储结构的比较
4. 当堂练习
作业布置
习题7
二．10,11 四.1
教学后记

教 案（理论课）
第 23 次课 2 学时
章 节
第七章 图
7.3 图的遍历
7.4 图的连通性

讲授主要内 容
图的深度优先搜索；图的广度优先搜索；
图的连通性：无向图、有向图；
重 点
难 点
重点：
1. 图的深度优先搜索
2. 图的广度优先搜索
3. 图的连通性：无向图、有向图
4. 生成树和最小生成树：生成树的概念；普里姆（Prim）算法；克鲁斯卡尔（Kruskal）算法
难点：
1．图的深度优先搜索
2．图的广度优先搜索
3．普里姆（Prim）算法
4．克鲁斯卡尔（Kruskal）算法
要求掌握知识点和分析方法
l 掌握图的深度优先搜索、广度优先搜索
l 理解图的连通性
l 理解生成树、最小生成树的概念
l 掌握普里姆（Prim）算法
l 掌握克鲁斯卡尔（Kruskal）算法
教学设计
6. 利用算法动态演示，讲解图的深度优先搜索，并分析算法
7. 利用算法动态演示，讲解图的广度优先搜索，并分析算法
8. 讲授图的连通性，通过举例的方式，分别分析无向图和有向图
9. 分析生成树和最小生成树的概念
10. 利用算法动态演示，讲解普里姆（Prim）算法
11. 利用算法动态演示，讲解克鲁斯卡尔（Kruskal）算法
作业布置
习题7
一．9,10,11 二． 4,8,12 三．3 四.2,3
教学后记

教 案（理论课）
第 24 次课 2 学时
章 节
第七章 图
7.5 图的应用
讲授主要内 容
拓扑排序；关键路径
重 点
难 点
重点：
1．拓扑排序
2．关键路径
难点：
1．拓扑排序
2．关键路径
要求掌握知识点和分析方法
l 理解AOV网的含义及特点
l 掌握拓扑排序的方法
l 掌握关键路径的求解思想
教学设计
31. 给出AOV网的定义，通过实例说明AOV网的建模意义，分析其性质
32. 给出拓扑序列定义和拓扑排序的方法
33. 利用算法动态演示，分析拓扑排序的方法
34. 课堂练习：给出一个AOV网，由学生完成拓扑排序
35. 给出AOE网的定义，通过实例说明AOE网的性质
36. 结合实例分析关键路径和关键活动的概念
37. 利用算法动态演示，给出求解关键路径的方法和步骤。注意分析多条关键路径同时存在时的情况。
38. 课堂练习：给出一个AOE网，由学生完成关键路径的求解和关键活动分析
作业布置
习题7
一．8,9 三．3,4,9,10 四.4
教学后记

教 案（理论课）
第 25 次课 2 学时
章 节
第七章 图
7.5 图的应用
7.6 案例实现
讲授主要内 容
最短路径；图的综合操作
重 点
难 点
重点：
1． 最短路径的思想
2． 迪杰斯特拉(Dijkstra)算法
难点：
迪杰斯特拉(Dijkstra)算法

要求掌握知识点和分析方法
l 理解最短路径的思想
l 掌握迪杰斯特拉(Dijkstra)算法求解思想及过程

教学设计
12. 举例说明在网中最短路径的含义
13. 利用算法动态演示，分析、展示迪杰斯特拉(Dijkstra)算法求解思想及过程
14. 根据教学情况，选讲弗洛伊德（Floyd）算法
15. 课堂练习：给出一网图，分析从某点出发的最短路径。
16. 结合整章的教学内容，整理、分析图的综合案例
作业布置
习题7
四.11,12
教学后记

教 案（实验课）
第 26 次课 2 学时
章 节
第七章 图

重 点
难 点
重点：
1． 图的存储结构：邻接矩阵、邻接表的实现
2． 图的遍历算法
难点：
1. 图的存储结构：邻接矩阵、邻接表的实现
2. 图的遍历算法

要求掌握知识点和分析方法
l 熟练掌握图的存储结构的实现
l 熟练掌握图的遍历算法

教学内容
上机完成案例。
要求：
完成本章案例。有能力的同学可以在此基础上完成拓扑排序。
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 27 次课 2 学时
章 节
第八章 查找
8.1 查找的基本概念
8.2 线性表的查找
讲授主要内 容
查找的基本概念；顺序查找；二分查找；分块查找

重 点
难 点
重点：
1．查找的基本概念
2．顺序查找
3．二分查找
4. 分块查找

难点：
1．顺序查找
2．二分查找

要求掌握知识点和分析方法
l 理解查找的基本概念：查找、关键字、ASL等
l 熟练掌握顺序查找
l 熟练掌握二分查找
l 掌握折半查找判定树
l 理解分块查找
教学设计
17. 结合实例分析查找的操作，给出查找的相关基本概念：查找、关键字、静态查找、动态查找、ASL。
18. 利用算法动态演示，讲解顺序查找：分析“监视哨”的设置及作用；给出算法；分析算法的优缺点及特性
19. 从“顺序查找”引入“二分查找”。利用算法动态演示，讲解二分查找：分析二分查找的基本思想，举例分析查找成功和查找不成功的案例；给出算法；分析算法的优缺点及特性；强调二分查找的前提（有序的顺序表）
20. 给出折半查找判定树的定义及构造方法，分析查找成功和查找不成功时的查找性能
21. 分析分块查找。强调“块间有序，块内无序”，分析两步的查找性能
22. 比较三种线性表的查找性能
作业布置
习题8
一．1~9,11,12 二．2,3,5,6,7,9,10 三. (教师指定) 四.(教师指定)
教学后记

教 案（理论课）
第 28 次课 2 学时
章 节
第八章 查找
8.3.1二叉排序树

讲授主要内 容
二叉排序树的定义；二叉排序树的查找； 二叉排序树的插入和生成；二叉排序树的删除
重 点
难 点
重点：
1．二叉排序树的定义
2．二叉排序树的查找
3．二叉排序树的插入和生成
4．二叉排序树的删除
难点：
1．二叉排序树的定义
2．二叉排序树的查找
3．二叉排序树的插入和生成
4．二叉排序树的删除
要求掌握知识点和分析方法
l 掌握二叉排序树的定义、查找
l 理解二叉排序树的插入和生成
l 了解二叉排序树的删除
教学设计
5. 通过二叉树的中序遍历引出二叉排序树
6. 讲解二叉排序树的定义及查找方法，举例分析并给出算法
7. 利用算法动画演示，说明二叉排序树的插入和生成方法，给出算法
8. 利用算法动画演示，说明二叉排序树的删除方法，给出算法
9. 分析、演示：二叉排序树的综合应用案例
10. 当堂练习
作业布置
习题8
一．10,13,14,15 二．2 三. (教师指定) 四.(教师指定)
教学后记

教 案（理论课）
第 29 次课 2 学时
章 节
第八章 查找
8.3.2平衡二叉树
8.3.3 B-树

讲授主要内 容
平衡二叉树；B-树及其查找；B-树查找分析；B-树的插入和删除
重 点
难 点
重点：
5. 平衡二叉树
6. B-树及其查找
7. B-树查找分析
8. B-树的插入
难点：
1. 平衡二叉树
2. B-树及其查找
3. B-树查找分析
4. B-树的插入
要求掌握知识点和分析方法
l 理解平衡二叉树的定义和平衡因子BF
l 了解平衡二叉树的调整思想及方法
l 理解B-树的插入操作
l 了解B-树的删除操作
教学设计
12. 由二叉排序树的查找性能引出平衡二叉树
13. 给出平衡二叉树和平衡因子的概念，理解平衡的含义
14. 给出构造平衡二叉树的基本思想，介绍平衡调整的四种情况
15. 介绍B-树的定义，以4阶B-