《数据结构》教案

安庆师范学院

.

教案（课时计划）

课程名称：数据结构 授课班级： 授课地点： 主讲教师：程玉胜

2015----2016 学年第 2学期

.

目 录

01、数据结构的概念及相关术语

02、抽象数据类型的表示与实现、算法和算法分析 03、线性表的类型定义、线性表的顺序表示和实现 04、线性表的链式表示和实现（线性链表）

05、循环链表、双向链表、一元多项式的表示及相加 06、栈、栈应用举例（数制转换、括号匹配、行编辑） 07、迷宫求解、表达式求值、栈与递归的实现 08、队列 09、机动 10、习题课

11、串类型的定义、串的表示和实现

12、串的模式匹配算法、串操作应用举例

13、数组的定义、顺序表示和实现、矩阵的压缩存储 14、稀疏矩阵的存储结构、广义表

15、树的定义和基本术语、二叉树的定义 16、二叉树的性质、二叉树的存储结构 17、遍历二叉树和线索二叉树 18、树和森林

19、赫夫曼树及其应用 20、习题课

21、图的定义和术语、图的存储结构 22、十字链表、邻接多重表、图的遍历 23、图的连通性问题 24、有向无环图及其应用 25、最短路径 26、静态查找表

27、二叉排序树和平衡二叉树 28、B-树和B+树 29、哈希表

30、排序概述、插入排序 31、快速排序、选择排序 32、归并排序、基数排序

33、外部排序、各种排序方法的比较 34、文件

.

.

编号 周次 课题 1 1 日期 9.3 课时安排 2 数据结构的概念及相关术语 教材重点：(1)数据结构的逻辑结构 的重(2)数据结构的存储结构 点 、(3)抽象数据类型的概念 难点分析 掌握数据、数据元素、数据对象的概念 熟练掌握数据结构的概念及其逻辑结构和物理结构的分类 教 学 目 标 掌握抽象数据类型的定义方法 教学方法和 教学手段 讲授法 多媒体 教学内容安排与板书设计： 第一章 绪论 教 学 过 程 1．1 什么是数据结构 非数值计算问题举例 《数据结构》产生的背景 《数据结构》在计算机科学中的地位和作用 .

.

1．2 基本概念和术语 数据 数据元素 数据对象 数据结构 教 学 过 程 数据结构的形式定义 Data-Structure = (D, S) 数据的逻辑结构及分类：集合、线性、树形、图形结构 数据的物理结构：顺序存储结构与链式存储结构 数据类型 抽象数据类型 抽象数据类型的形式定义 ADT = (D, S, P) 抽象数据类型定义举例—Triplet 师生双边活动： 提问：什么是数据类型？ 举例： 演示实验： 教具准备： 课后1.2,1.19 作业 教材： [1]严蔚敏 吴伟民编著：数据结构（C语言版），清华大学出版社，1997年 教学后记 参考书目： [1]Wirth N：Algorithms+Data Structures=Programs，Prentice-Hall Inc.，1976 [2][美]S 巴斯：计算机算法：设计和分析引论，复旦大学出版社，1985 .

.

编号 周次 课题 教材的重点 、难点分析 1 2 日期 9.6 课时安排 2 抽象数据类型的表示与实现、算法和算法分析 重点：(1)算法复杂度的分析方法 难点：(1)算法复杂度的分析方法 (1)理解数据抽象的意义 教 学 目 标 (2)熟悉类C语言 (3)掌握抽象数据类型的表示和实现方法 (4)掌握算法描述和算法分析的方法 教学方法和 教学手段 教学内容安与排板书设计： 1．3 抽象数据类型的表示和实现 教 学 过 程 数据抽象的意义 类C语言 抽象数据类型的表示和实现举例 .

.

1．4 算法和算法分析 算法 算法的定义 算法的特性：有穷性、确定性、可行性、输入、输出 算法设计的要求 教 学 过 程 正确性、可读性、健壮性、效率与低存储量需求 算法效率的度量 时间度量的方法分析 时间复杂度 T(n) = O(f(n)) 时间复杂度的计算 算法的存储空间需求 S(n) = O(f(n)) 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后1.4,1.20 作业 教学 后记 .

.

编号 周次 课题 2 3 日期 9.10 课时安排 2 线性表的类型定义、线性表的顺序表示和实现 教材重点：(1)顺序表的基本运算 的重(2)顺序表上实现的各种算法的时间性能分析 点 、难点 分析 (1)理解线性表的逻辑结构特征 教 学 目 标 (2)熟练掌握顺序表的描述方法、特点及有关概念 (3)熟练掌握顺序表的基本运算 教学方法和 教学手段 教学内容安排与板书设计： 第二章 线性表 教 学 过 程 线性结构的特点 2．1 线性表的类型定义 线性表的定义及其表示 线性表的类型定义 线性表操作举例：用线性表表示集合、线性表的合并 .

.

2．2 线性表的顺序表示和实现 线索性表的顺序表示 线性表的顺序存储结构的定义及其特征 顺序表的基本运算 顺序表的初始化 教 学 过 程 顺序表的插入操作 顺序表的删除操作 顺序表的合并 顺序表基本操作的时间复杂度计算 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后2.12 作业 教学 后记 .

.

编号 周次 课题 2 4 日期 9.13 课时安排 2 线性表的链式表示和实现（线性链表） 教材重点：(1)链表的基本运算 的重(2)链表上实现的各种算法的时间性能分析 点 、难点 分析 (1)熟练掌握链表的描述方法、特点及有关概念 教 学 目 标 (2)掌握链表的基本运算 (3)掌握静态链表的构造方法 教学方法和 教学手段 教学内容安排与板书设计： 2．3 线性表的链式表示和实现 教 学 过 程 2．3．1 线性链表 单链表的定义 单链表的存储结构特征 单链表的基本操作： 插入 .

.

删除 有序链表的合并 静态链表 静态链表的定义 静态链表的操作举例 教 学 过 程 师生双边活动： 提问：malloc() free() 举例： 演示实验： 教具准备： 课后2.17,2.25 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 难点：(1)循环链表 (1)掌握循环链表的特点 3 5 日期 9.17 课时安排 2 循环链表、双向链表、一元多项式的表示及相加 教 学 目 标 (2)掌握双向链表的特点 (3)从时空角度综合比较顺序表和链表的不同特点及使用场合 (4)能应用线性表解决一些实际问题 教学方法和 教学手段 教学内容安排与板书设计： 2．3．2 循环链表 教 学 过 程 循环链表的定义 循环链表的操作 .

.

2．3．3 双向链表 双向链表的定义 双向链表的操作特点 线性链表的类型定义 2．4 一元多项式的表示及相加 教 学 过 程 一元多项式的表示 一元多项式的相加 一元多项式的类型定义 多项式的相加算法 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后2.32 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 3 6 日期 9.20 课时安排 2 栈、栈应用举例（数制转换、括号匹配、行编辑） 重点：(1)栈在两种存储结构上实现的基本运算。 难点：栈满栈空的条件及它们的描述 (1)掌握栈这种数据结构的特点 教 学 目 标 (2)熟悉栈与线性表的关系 (3)重点掌握顺序栈和链式栈的五种基本运算 (4)掌握栈的应用方法 教学方法和 教学手段 教学内容安排与板书设计： 第三章 栈与队列 教 学 过 程 3．1 栈 3．1．1 抽象数据类型栈的定义 栈及其与线性表的关系 栈的类型定义 .

.

3．1．2 栈的表示和实现 顺序栈的定义 链栈的定义 3．2 栈的应用举例 教 学 过 程 3．2．1 数制转换 3．2．2 括号匹配的检验 3．2．3 行编辑程序 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后3.15 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 (1)能应用栈解决一些实际问题 7 4 日期 9.24 课时安排 2 迷宫求解、表达式求值、栈与递归的实现 教 学 目 标 (2)了解递归算法执行过程中栈的变化过程 教学方法和 教学手段 教学内容安排与板书设计： 3．2．4 迷宫求解 教 学 过 程 3．2．5 表达式求值 3．3 栈与递归的实现 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后3.19,3.25 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 4 8 日期 9.27 队列 课时安排 2 重点：(1)队列在两种存储结构上实现的基本运算。 难点：(1)循环队列（注意队满队空的条件及它们的描述） (1) 掌握队列这种数据结构的特点 教 学 目 标 (2)熟悉队列与线性表的关系 (3)掌握循环队列和链式队列的五种基本运算 (4)能应用队列解决一些实际问题 教学方法和 教学手段 教学内容安排与板书设计： 3．4 队列 教 学 过 程 3．4．1 抽象数据类型队列的定义 队列的定义(FIFO) 队列的类型定义 .

.

3．4．2 链队列—队列的链式表示和实现 单链队列的定义 单链队列的操作 3．4．3 循环队列—队列的顺序表示和实现 队列的顺序存储结构 教 学 过 程 循环队列的基本操作 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后3.29 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 9 5 日期 10.1 机动 课时安排 2 教 学 目 标 教学方法和 教学手段 教学内容安排与板书设计： 教 学 过 程 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 10 5 日期 10.4 习题课 课时安排 2 教 学 目 标 教学方法和 教学手段 讲授法 教学内容安排与板书设计： 教 学 过 程 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 6 日期 11 10.8 课时安排 2 串类型的定义、串的表示和实现 重点：(1)串的基本运算 难点：(1)串的动态存储结构 (1)熟悉串的有关概念，串与线性表的关系 教 学 目 标 (2)掌握串的静态存储结构与动态存储结构和它们的优缺点 (3)熟练掌握串的基本运算 教学方法和 教学手段 教学内容安排与板书设计： 第四章 串 教 学 过 程 4．1 串类型的定义 串的概念 串类型的定义 .

.

4．2 串的表示和实现 4．2．1 定长顺序存储表示 串的定长顺序存储表示 串联接 求子串 教 学 过 程 4．2．2 堆分配存储表示 串的堆分配存储表示 堆的基本操作 4．2．3 串的块链存储表示 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后4.17,4.22/4.24 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 (1)理解串的模式匹配算法 12 6 日期 10.11 课时安排 2 串的模式匹配算法、串操作应用举例 教 学 目 标 (2)了解串的应用 教学方法和 教学手段 教学内容安排与板书设计： 4．3 串的模式匹配算法 教 学 过 程 4．3．1 求子串位置的定位函数 4．3．2 模式匹配的一种改进算法 KMP算法 .

.

4．4 串操作应用举例 4．4．1 文本编辑 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后4.8 作业 教学 后记 .

.

编号 周次 课题 7 日期 13 10.15 课时安排 2 数组的定义、顺序表示和实现、矩阵的压缩存储 教材重点：(1)多维数组的存储方式 的重(2)矩阵的压缩存储方式 点 、难点 分析 难点：(1)稀疏矩阵的压缩存储表示下实现的算法 (1)熟悉数组的按行（列）优先顺序的存储结构中的地址计算方法 教 学 目 标 (2)熟悉特殊矩阵在压缩存储时的下标变换 (3)理解稀疏矩阵的三元组和十字链表两种压缩存储表示 教学方法和 教学手段 教学内容安排与板书设计： 第五章 数组和广义表 教 学 过 程 5．1 数组的定义 数组的类型定义 二维数组 .

.

5．2 数组的顺序表示和实现 二维数组的存储方式 数组的顺序存储表示和实现 5．3 矩阵的压缩存储 教 学 过 程 5．3．1 特殊矩阵 对称矩阵 对角矩阵 5．3．2 稀疏矩阵 稀疏矩阵的类型定义 1、三元组顺序表 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后5.21 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 7 日期 14 10.18 课时安排 2 稀疏矩阵的存储结构、广义表的定义和存储结构 重点：(1)广义表的定义及其运算 (1)掌握稀疏矩阵的存储结构 教 学 目 标 (2)熟悉广义表的有关概念和运算 (3)掌握广义表的两种存储结构 教学方法和 教学手段 教学内容安排与板书设计： 2、行逻辑链接的顺序表 教 学 过 程 3、十字链表 5．4 广义表的定义 .

.

广义表的类型定义 广义表举例 广义表的特点 5．5 广义表的存储结构 教 学 过 程 讨论： M元多项式的表示 广义表的递归算法 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后5.26,5.12 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 8 日期 15 10.22 课时安排 2 树的定义和基本术语、二叉树的定义 重点：(1)树的基本术语 (2)二叉树的定义 (1)掌握树的定义和有关术语 教 学 目 标 (2)熟悉二叉树的递归定义，有关术语及基本概念 教学方法和 教学手段 教学内容安排与板书设计： 第六章 树和二叉树 教 学 过 程 6．1 树的定义和基本术语 树的类型定义 基本术语 .

.

6．2 二叉树 6．2．1 二叉树的定义 二叉树的类型定义 二叉树的基本形态 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后6.2 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 8 日期 16 10.25 课时安排 2 二叉树的性质和和存储结构 重点：(1)二叉树的存储结构 难点：(1)二叉树的性质 (1)熟练掌握二叉树的性质及证明方法 教 学 目 标 (2)熟练掌握二叉树的顺序和链式存储结构及特点 教学方法和 教学手段 讲授法 教学内容安排与板书设计： 6．2．2 二叉树的性质 教 学 过 程 性质1 性质2 性质3 性质4 性质5 .

.

6．2．3 二叉树的存储结构 顺序存储结构 链式存储结构 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后6.6,6.11 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 9 日期 17 10.29 课时安排 2 遍历二叉树和线索二叉树 重点：(1)二叉树的遍历算法及其相关应用 难点：(1)二叉树的非递归遍历算法 (1)熟练掌握二叉树的各种遍历 教 学 目 标 (2)能灵活运用遍历算法实现二叉树的基本运算 (3)掌握二叉树的线索化及相应算法 教学方法和 教学手段 教学内容安排与板书设计： 6．3 遍历二叉树和线索二叉树 教 学 过 程 6．3．1 遍历二叉树 遍历二叉树的递归算法 先序遍历 中序遍历 后序遍历 .

.

遍历二叉树的非递归算法 遍历二叉树的其他算法 二叉树的其他操作 6．3．2 线索二叉树 线索二叉树及其存储结构 教 学 过 程 二叉树的线索化 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后6.43,6.47,6.56 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 重点：(1)树的存储结构 18 9 日期 11.1 树和森林 课时安排 2 难点：(1) 森林、树与二叉树之间的转换 (1)掌握树的存储结构及其特点 教 学 目 标 (2)熟练掌握森林、树与二叉树之间的转换方法 (3)掌握森林和树的遍历 教学方法和 教学手段 教学内容安排与板书设计： 6．4 树和森林 教 学 过 程 6．4．1 树的存储结构 双亲表示法 孩子表示法 孩子兄弟表示法 .

.

6．4．2 森林与二叉树的转换 森林与二叉树的对应关系 二叉树与森林的对应关系 6．4．3 树和森林的遍历 先序遍历森林 教 学 过 程 中序遍历森林 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后6.60,6.66 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 重点：(1)赫夫曼编码 难点：(1)赫夫曼编码 19 10 日期 11.5 赫夫曼树及其应用 课时安排 2 (1)掌握最优化二叉树的特性、熟练掌握建立最优二叉树的方法 教 学 目 标 (2)熟练掌握哈夫曼编码的方法 教学方法和 教学手段 讲授法 教学内容安排与板书设计： 6．6 赫夫曼树 教 学 过 程 6．6．1 最优二叉树 最优二叉树的概念 构造赫夫曼树 最优判定算法 6．6．2 赫夫曼编码 .

.

求赫夫曼编码 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后6.26 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 20 10 日期 11.8 习题课 课时安排 2 教 学 目 标 教学方法和 教学手段 讲授法 教学内容安排与板书设计： 教 学 过 程 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 11 日期 21 11.12 课时安排 2 图的定义和术语、图的存储结构 重点：(1)图的存储 (1)熟悉图的有关术语和概念 教 学 目 标 (2)熟练掌握图的四种存储结构和建立算法 教学方法和 教学手段 教学内容安排与板书设计： 第七章 图 教 学 过 程 7．1 图的定义和术语 图的类型定义 图的分类 连通图、连通分量、生成树 .

.

7．2 图的存储结构 7．2．1 数组表示法 图的邻接矩阵 网及其邻接矩阵 7．2．2 邻接表 教 学 过 程 图的邻接表存储表示 邻接表和逆邻接表 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后7.14,7.15 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 11 日期 22 11.15 课时安排 2 十字链表、邻接多重表、图的遍历 重点：(1)图的遍历 难点：(1)图的遍历非递归算法 (1)熟练掌握图的四种存储结构和建立算法 教 学 目 标 (2)熟练掌握图的深度优先遍历和广度优先遍历 教学方法和 教学手段 教学内容安排与板书设计： 7．2．3 十字链表 教 学 过 程 有向图的十字链表存储表示 构造有向图 7．2．4 邻接多重表 无向图的邻接多重表 .

.

7．3 图的遍历 7．3．1 深度优先搜索 7．3．2 广度优先搜索 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后7.22,7.28 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 12 日期 23 11.19 图的连通性问题 课时安排 2 重点：(1)最小生成树的构造 掌握最小生成树的两种构造方法 教 学 目 标 教学方法和 教学手段 教学内容安排与板书设计： 7．4 图的连通性问题 教 学 过 程 7．4．1 无向图的连通分量和生成树 7．4．2 有向图的强连通分量 .

.

7．4．3 最小生成树 Prim算法 Kruskal算法 7．4．3 关节点和重连通分量 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后7.32 作业 教学 后记 .

.

编号 周次 课题 12 日期 24 11.22 有向无环图及其应用 课时安排 2 教材重点：(1)拓扑排序 的重(2)求关键路径 点 、难点 分析 难点：(1)求关键路径 (1)掌握拓扑排序的方法 教 学 目 标 (2)掌握关键路径的求法 教学方法和 教学手段 教学内容安排与板书设计： 7．5 有向无环图及其应用 教 学 过 程 DAG 7．5．1 拓扑排序 7．5．2 关键路径 AOE网 关键路径 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后7.36 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 重点：(1)求最短路径 25 13 日期 11.26 最短路径 课时安排 2 难点：(1)求每一对顶点之间的最短路径 熟练掌握从某个源点到其余各顶点的最短路径的求法 掌握求每一对顶点之间的最短路径的求法 教 学 目 标 教学方法和 教学手段 教学内容安排与板书设计： 7．6 最短路径 教 学 过 程 7．6．1 从某个源点到其余各顶点的最短路径 Dijkstra算法 7．6．2 每一对顶点之间的最短路径 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后7.42 作业 教学 后记 .

.

编号 周次 课题 教材重点：(1)顺序查找 的重(2)折半查找 点 、难点 分析 13 日期 26 11.29 静态查找表 课时安排 2 (1)熟练掌握静态查找的各种方法 教 学 目 标 教学方法和 教学手段 教学内容安排与板书设计： 第八章 查找 教 学 过 程 查找表与静态查找表和动态查找表 关键字与主关键字和次关键字 查找与成功和不成功 .

.

8．1 静态查找表 静态查找表的类型定义 8．1．1 顺序表的查找 顺序查找 平均查找长度 教 学 过 程 8．1．2 有序表的查找 折半查找 折半查找的性能分析 8．1．3 静态树表的查找 8．1．4 索引顺序表的查找 表其索引表 分块查找 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后9.29 作业 教学 后记 .

.

编号 周次 课题 14 日期 27 12.3 课时安排 2 二叉排序树和平衡二叉树 教材重点：(1)动态查找表及查找算法 的重(2)二叉排序树 点 、难点 分析 难点：(1)二叉排序树 (1)熟练掌握二叉排序树的构造方法及查找过程 教 学 目 标 (2)掌握AVL树的构造 教学方法和 教学手段 教学内容安排与板书设计： 8．2 动态查找表 教 学 过 程 动态查找表的类型定义 8．2．1 二叉排序树和平衡二叉树 1、二叉排序树及其查找过程 二叉排序树 .

.

2、二叉排序树的插入和删除 二叉排序树的构造 二叉排序树的删除 3、二叉排序树的查找分析 教 学 过 程 4、平衡二叉树 平衡二叉树与不平衡的二叉树 平衡树的生成过程 二叉排序树的平衡旋转 二叉排序树的类型定义 5、平衡树查找的分析 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后9.33 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 28 14 日期 12.6 B-树和B+树 课时安排 2 (1)掌握B-树和B+树的构造和查找 教 学 目 标 (2)了解键树的构造方法 教学方法和 教学手段 教学内容安排与板书设计： 8．2．2 B-树和B+树 教 学 过 程 1、B-树及其查找 2、B-树查找分析 .

.

3、B-树的插入和删除 4、B+树 8．2．3 键树 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 难点：(1)哈希表及查找算法 29 15 日期 12.10 哈希表 课时安排 2 (1)熟练掌握哈希表的建表方法、冲突的处理及查找过程 教 学 目 标 (2)理解哈希表与其它存储结构的表的本质区别 (3)熟练掌握哈希表的平均查找长度的计算（等概率） 教学方法和 教学手段 教学内容安排与板书设计： 8．3 哈希表 教 学 过 程 8．3．1 什么是哈希表 哈希函数 冲突 散列 .

.

8．3．2 哈希函数的构造方法 1、直接定址法 2、数字分析法 3、平方取中法 4、折叠法 教 学 过 程 5、除留余数法 6、随机数法 8．3．3 处理冲突的方法 1、开放定址法 2、再哈希法 3、链地址法 4、建立一个公共溢出区 8．3．4 哈希表的查找及其分析 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后9.46 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 重点：(1)希尔排序 30 15 日期 12.13 排序概述、插入排序 课时安排 2 (1)深刻理解插入排序的基本思想及其特点 教 学 目 标 (2)熟练掌握插入排序方法的排序过程 (3)掌握插入排序算法时间复杂度的分析方法并熟记其分析结论 教学方法和 教学手段 教学内容安排与板书设计： 第九章 排序 教 学 过 程 9．1 排序概述 排序 排序方法的稳定性 内部排序与外部排序 .

.

9．2 插入排序 9．2．1 直接插入排序 9．2．2 其他插入排序 1、折半插入排序 教 学 过 程 2、2-路插入排序 3、表插入排序 9．2．3 希尔排序 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后10.25 作业 教学 后记 .

.

编号 周次 课题 16 日期 31 12.17 快速排序、选择排序 课时安排 2 教材重点：(1)快速排序 的重(2)堆排序 点 、难点 分析 难点：(1)快速排序 (2)堆排序 (1)深刻理解快速排序的基本思想及其特点 教 学 目 标 (2)熟练掌握快速排序方法的排序过程 (3)掌握快速排序算法时间复杂度的分析方法并熟记其分析结论 (4)深刻理解选择排序的基本思想及其特点 (5)熟练掌握选择排序方法的排序过程 (6)掌握选择排序算法时间复杂度的分析方法并熟记其分析结论 教学方法和 教学手段 教学内容安排与板书设计： 9．3 快速排序 教 学 过 程 起泡排序的过程 起泡排序算法 快速排序的时间性能分析 .

.

9．4 选择排序 9．4．1 简单选择排序 排序过程 9．4．2 树形选择排序 教 学 过 程 9．4．3 堆排序 堆 堆排序算法 建堆 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后10.30,10.34 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 重点：(1)归并排序 32 16 日期 12.20 归并排序、基数排序 课时安排 2 (1)深刻理解归并排序的基本思想及其特点 教 学 目 标 (2)熟练掌握归并排序方法的排序过程 (3)掌握归并排序算法时间复杂度的分析方法并熟记其分析结论 (4)深刻理解基数排序的基本思想及其特点 (5)熟练掌握基数排序方法的排序过程 (6)掌握基数排序算法时间复杂度的分析方法并熟记其分析结论 教学方法和 教学手段 教学内容安排与板书设计： 9．5 归并排序 教 学 过 程 2-路归并排序 9．6 基数排序 9．6．1 多关键字的排序 9．6．2 链式基数排序 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后10.38,10.43 作业 教学 后记 .

.

编号 周次 课题 教材的重点 、难点分析 17 日期 33 12.24 课时安排 2 外部排序、各种排序方法的比较 重点：(1)各种排序算法的性能比较 (1)掌握各种内部排序方法的优缺点及排序方法的选择 教 学 目 标 (2)了解外部排序的基本思想及其特点 教学方法和 教学手段 教学内容安排与板书设计： 9．7 各种内部排序方法的比较讨论 教 学 过 程 9．8 外部排序 外部排序特点 多路平衡归并 置换-选择排序 .

.

教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后 作业 教学 后记 .

.

编号 周次 课题 17 日期 34 12.27 文件 课时安排 2 教材重点：(1)索引文件 的重(2)直接存取文件 点 、难点 分析 难点：(1)ISAM文件和VSAM文件 (1)了解文件在外存储器中的表示方法 教 学 目 标 (2)了解文件各种运算的实现方法 教学方法和 教学手段 教学内容安排与板书设计： 第十章 文件 教 学 过 程 10．1 文件的基本概念 10．2 顺序文件 10．3 索引文件 10．4 ISAM文件和VSAM文件 .

.

10．5 直接存取文件 10．6 多关键字文件 教 学 过 程 师生双边活动： 提问： 举例： 演示实验： 教具准备： 课后 作业 教学 后记 .