课时计划(教案).pdf

《课时计划(教案).pdf》由会员分享，可在线阅读，更多相关《课时计划(教案).pdf（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 课时计划(教案)2 课时计划（教案）号 001 周次 第 1 周 日期 3 月 1 日 课时安排 2 课题 数据结构的基本概念 教材的重点、难点分析 1、引用参数的使用.2、new 与 delete 的正确使用 3、数据结构的形式化定义 教 学 目 标 1、为了方便实验，要求使用 C+编程环境（使用面向过程的程序设计方法）2、通过基本概念和术语的理解，为后续章节作好充分的准备 教学方法和 教学手段 教学方法：导入，讲解，提问 教学手段：PPT 课件，板书 1、课程介绍 3 教 学 过 程 2、教学安排：删除第 8 章、第 11 章、第 12 章和部分*章节 3、教学要求：4、补充介绍试验预备

2、知识 从 C 过渡到 C+（主要介绍以后实验中用到的一些主要差异）（1）注释行（2）引用类型的使用：&（3）流库：头文件 iostream.h 教 学 过 程 cout 一、基本概念和术语 1.数据(data)2.数据元素(data element)3.数据对象(data object)4.数据结构(data structure)形式化定义:例(P5)，补充例（提问）课后作业 教学 后记 4 课时计划（教案）号 002 周次 第 2 周 日期 3 月 5 日 课时安排 3 课题 算法分析 教材的重点、难点分析 1、抽象数据类型的引用及其描述方法（类 C 语言）2、算法时间复杂度的计算 教 学

3、目 标 1、熟悉个名词、术语的含义，掌握数据的逻辑结构和存储结构之间的关 系 2、了解抽象数据类型的定义、表示和实现方法，熟悉类 C 语言的书写规 范 3、掌握计算语句频度和估算算法时间复杂度的方法 教学方法和 教学手段 教学方法：讲解，提问 教学手段：PPT 课件，板书 教 5 学 过 程 Chapter1（续）5.逻辑结构(logical structure)6.存储结构（storage structure）7.数据类型(data type)8.抽象数据类型 ADT 的定义、表示 三元组来表示 补充例-复数的定义、表示及实现 教 学 过 程 9.类 C 语言（重点强调与 C 的一些差异，上

4、机时尤其注意）二、算法和算法分析 1.算法的定义、五个重要特性、算法和程序的区别 2.算法设计的原则(要求)3.算法效率的度量-时间效率 T(n)=O(f(n)的含义 语句频度的计算(补充一些例子)介绍选择排序和起泡排序算法 引入最坏时间复杂度和平均时间复杂度 4.算法存储空间的需求-空间效率 形式化定义:例(P5)，补充例（提问）课后作业 习题:1.3,1.8 思考题:1.4 1.6,1.7,1.19,1.20 教学 后记 6 课时计划（教案）号 003 周次 第 2 周 日期 3 月 8 日 课时安排 2 课题 顺序表 教材的重点、难点分析 1、顺序表的基本操作的实现算法 2、插入和删除算

5、法的时间性能分析 教 学 目 标 1、了解线性表的逻辑结构特性-线性关系 2、熟练掌握顺序结构的描述方法-一维数组 3、熟练掌握线性表在顺序存储结构上实现基本操作的算法(如查找、插入、删除)教学方法和 教学手段 教学方法：引入，讲解，提问 教学手段：PPT 课件，板书 教 学 过 程 1.补充关于程序时间复杂度计算的例题 2.解决 C+中输入输出宽度的使用方法 即 setw()、setprecision()、setfill()等等 用到的头文件为 iomanip.h 7 Chapter2 线性表 一、线性表的类型定义 重点介绍一下基本操作 InitList(&L),ListEmpty(L),L

6、istlength(L),教 学 过 程 GetElem(L,i,&e),LocateElem(L,e)ListInsert(&L,i,e),ListDelete&L,i,&e)二、线性表的顺序表示和实现 即顺序表 1.比较两种定义：typedef struct typedef struct ElemType*elem;ElemType elem50;int length;int length;Sqlist;动态数组 Sqlist;静态数组 两种定义的区别（提问）2.各种基本操作的实现 3.插入和删除算法的平均时间复卒读的分析 课后作业 习题:2.11,2.21 教学 后记 8 课时计划（教案

7、）号 004 周次 第 3 周 日期 3 月 12 日 课时安排 3 课题 链表 教材的重点、难点分析 1、链表中指针操作技术 2、单链表上查找、插入和删除算法的实现 教 学 目 标 1、熟练掌握链式存储结构的描述方法-指针操作和内存动态分配编程 技术 2、熟练掌握在各种链表结构中实现线性表操作的基本方法 教学方法和 教学手段 教学方法：讲解，提问 教学手段：PPT 课件，板书 教 学 过 程 Chapter2（续）4.顺序表中的几个例子 三、线性表的几个链式表示及其实现-链表 9 1 线性链表的.存储结构表述和示意图表示 LNode 和 LinkList 的含义有什么不同？（提问）2.单链表

8、的建立 方法一：头插法，方法二：尾插法 教 学 过 程 引入“头结点”的使用好处。3.查找运算 （1）按序号查找 GetElem()提问：书上算法中为什么 if(!p|ji)表示第 i 个元素不存在？什么情况下发生 p 为空和 ji？（2）定位查找 LocateElem()4.插入运算 5.删除运算 注意比较插入和删除的算法中 while 循环条件的不同！为什么？课后作业 习题:2.22,2.24 教学 后记 10 课时计划（教案）号 005 周次 第 3 周 日期 3 月 15 日 课时安排 2 课题 线性表的应用 教材的重点、难点分析 1、循环链表和双向链表的正确使用 2、用单链表实现稀疏

9、多项式的加法运算 教 学 目 标 1、能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不 同特点及其适用场合 2、掌握稀疏多项式的抽象数据类型的定义、表示和加法的实现 教学方法和 教学手段 教学方法：讲解 教学手段：PPT 课件，板书 教 Chapter2（续）11 学 过 程 6.两个有序链表的合并 7.循环链表 注意领会用尾指针表示的好处 例：将表(a1,a2,an)和(b1,b2,bm)链接成表（a1,a2,an，b1,b2,bm）注：用尾指针表示循环链表，其实间复杂度 O(1)教 学 过 程 8.双向链表 重点介绍插入运算和删除运算指针的变化 三、一元多项式的表示及相加 重点讨

10、论用单链表结构实现两个稀疏多项式的相加运算 课后作业 习题:2.31,2.32 思考题:2.6 2.7,2.8,2.9,2.10 教学 12 后记 13 课时计划（教 案）编号 006 周次 4 日期 课时安排 课题 栈及其应用 教材的重点、难点 1.栈类型的特点及其应用。2.栈满和栈空的条件及其描述方法。教 学 目 标 1.掌握栈类型的特点，并能在相应应用问题中正确运用。2.熟练掌握栈类型的两种实现方法，即顺序栈和链栈上 基本操作实现算法。教学 方法 和 教学 方法：讲解、导入、提问。手段：ppt 课件、板书。教 学 过 程 Chapter 3 栈和队列 一、栈的定义LIFO 结构 1.重点

11、分析几个基本操作的含义 InitStack（&S）StackEmpty（S）StackLength（S）GetTop（S，&e）Push(&S,e)Pop(&S,&e)2.顺序栈 注意：用 top=-1 表示空栈（与教材上不同）几个基本操作在顺序结构上实现细节，注意栈满和栈空的 14 教 学 判别。3.链栈 提问：为什么把 an作为表头，a1作为表尾处理？4.栈的应用 应用之一：数制转换 应用之二：括号匹配的检验 应用之三：行编辑程序 应用之四：表达式求值（算符优先法）中缀表达式、波兰符号法、逆波兰符号法 怎样由一个中缀表达式转化为后缀表达式（逆波兰 符号）？（提问）课后 作业 习题：3.15

12、 3.19 教学 后记 15 课时计划（教 案）编号 007 周次 4 日期 课时安排 2 课题 栈与递归的实现 教材的重点、难点 1.算符优先法的分析。2.递归算法到非递归算法的转化。教 学 目 标 1.掌握利用算符优先法对表达式求值方法过程。2.理解递归算法执行过程中栈的状态变化过程。教学 方法 和 教学 方法：讲解、提问。手段：ppt 课件、板书。教 学 过 程 表达式求值（续）算符优先算法的分析 结合例子讲解 OPTR 和 OPND 两个栈的变化情况。二、栈与递归的实现 1.递归的几个应用：递归函数、二叉树递归数据结构 16 教 学 Hanoi 塔求解等。2.布置一个递归程序写结果，考

13、察学生对递归的掌握情况。3.结合 hanoi 塔问题，分析递归工作栈的工作状态，及怎 样保留现场，可配合示意图加深理解。课后 作业 习题：3.21 3.22 教学 后记 17 课时计划（教 案）编号 008 周次 5 日期 课时安排 2 课题 队列 教材的重点、难点 1.循环队列的含义。2.队满和队空的表示方法。教 学 目 标 1.掌握队列类型的特点，并能在相应应用问题中正确选用。2.熟练掌握循环队列和链队列的基本操作实现算法。教学 方法 和 教学 方法:导入、讲解、提问。手段:PPT 课件、板书。教 学 过 程 三、队列FIFO 表 1.队列的定义。重点几个基本操作：InitQueue(&Q

14、)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e)DeQueue(&Q,&e)2.队列的顺序存储顺序队列或循环队列 空队列时，front=rear=0,注意 front 和 rear 的指向。为避免队列出现假满情况，使用循环队列，此时只凭 18 教 学 等式 front=rear 是无法判别队列是“空”，还是“满”？有两种处理方法：法一：（少用一个元素空间）P64-65 页教材上用此法实现。法二：（另设一个标志位 tag 区分）题集 3.29。3队列的链式存储链队列 注意 front、rear 的指向。出队操作中，if(Q.rear=p

15、)的处理（提问）4例题 课后 作业 习题：3.28，3.30 思考题：3.3 3.4 3.6 3.12 3.13 3.29 3.31 3.32 教学 后记 19 课时计划（教 案）编号 009 周次 5 日期 课时安排 2 课题 习题课 1 教材的重点、难点 教 学 目 标 教学 方法 和 教学 方法：讲解、提问。手段：PPT 课件、板书。教 学 过 程 一、第 1 章习题订正与讲解 1.习题 1.8 主要错误为、2.习题 1.6（先思考再讲解）3.习题 1.7（先思考再讲解）4.习题 1.19 20 教 学 5.习题 1.20 6.补充题的解答（用不多于 3/2n比较次数找向量 A 最大、最

16、小值）二、第 2 章部分习题的讲解 1.习题 2.11 2.习题 2.12 3.习题 2.19 4.习题 2.20 5.习题 2.21 6.习题 2.22 7.习题 2.24 课后 作业 教学 后记 21 课时计划（教 案）编号 010 周次 6 日期 课时安排 2 课题 串的概念及应用 教材的重点、难点 1.串的概念和基本操作的定义。2.串的两种存储结构上基本操作实现。教 学 目 标 1.熟悉串的 7 种基本操作的定义，并能利用这些基本操作 来实现串的其它操。2.熟练掌握串的定长顺序存储上各种操作实现。3掌握串的堆存储结构及其上串操作实现。教学 方法 和 教学 方法：导入、讲解。手段：PPT

17、 课件、板书。教 学 过 程 Chapter 4 串 一、串类型的定义 1.基本概念 如串、串长、空串、子串、主串。2C+的串库（Sting.h）中的常用函数。求串长 Strlen（S）串拷贝 Strcpy（S1，S2）串联接 Strcat（S1，S2）串比较 Strcmp（S1，S2）22 教 学 串定位 Strchr（S，c）串右定位 Strrchr（S，c）3串的抽象数据类型的定义 二、串的表示和实现。1定长顺序存储表示。2.堆分配存储表示。3.串的块链存储表示。课后 作业 习题 4.6 4.25 教学 后记 23 课时计划（教 案）编号 011 周次 6 日期 课时安排 2 课题 串的

18、模式匹配算法 教材的重点、难点 KMP 算法和 NEXT 函数的计算 教 学 目 标 1.理解串匹配的朴素匹配算法和 KMP 算法。2.熟悉 NEXT 函数的定义，能手工计算给定模式串的 NEXT 函数值和改进的 NEXT 函数值。教学 方法 和 教学 方法：讲解、提问。手段：PPT 课件、板书。教 学 过 程 Chapter 4 串（续）三、串的模式匹配算法 1朴素模式匹配算法（BruteForce 算法）S主串（目标）T子串（模式）2KMP 算法 注意 next 函数和 nextval 函数值的计算。24 教 学 3.其它方法 如 BM（BoyerMoore）算法 请同学们课后查阅。课后

19、作业 习题：4.8 4.28 思考题：4.7 4.9 4.18 4.23 4.29 4.30 教学 后记 25 课时计划（教案）号 012 周次 7 日期 4 月 9 日/4 月 10 日 课时安排 3 课题 数组的表示和短阵的压缩存储 教材的重点、难点分析 1、特殊矩阵压缩存储公式的计算 2、稀疏矩阵的两种存储方法 教学 目标 1、了解数组的两种存储表示方法 2、掌握对特殊矩阵压缩存储时下标变换公式 3、领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。教学方法和教学手段 教学方法：导入、讲解、提问 教学手段：PPT 课件、板书 26 教 学 过 程 Chapter 5 数组与广义表 一

20、、数组类型的定义 二、数组以行序表示和实现（1）以列序为主序存储方式（2）以行序为主序存储方式 注意其计算公式 三、短阵的压缩存储 1、特殊矩阵的压缩存储（1）对称矩阵（2）三角矩阵：上三角，下三角（3）三对角矩阵 2、稀疏矩阵，压缩存储（1）三天组顺序表：例：矩阵的转置运算（2）行逻辑链接的顺序表：例：矩阵的乘积运算（3）十字链表：例：矩阵相加运算 课后 作业 习题：5.17(2)(5)5.19 27 教学 后记 28 课时计划（教案）号 013 周次 7 日期 4 月 12 日/4 月 13 日 课时安排 2 课题 广义表 教材的重点、难点分析 广义表的特点及表头、表尾的分解方法 教学 目

21、标 1、掌握广义表的结构特点及其存储表示方法 2、学会对非空广义表进行分解的分析方法 教学方法和教学手段 教学方法：导入、讲解、提问 教学手段：PPT 课件、板书 教 学 过 程 Chapter 5 广义表 1、广义表定义及其相关术语 29 2、重点介绍表头、表尾、举例说明如何利用取表头 函数和取表尾函数从广义表中分离某原子的操作 3、广义表的图形表示，要求能根据某图形表示结果，还原为原来的广义表 4、广义表存储结构 头尾链表表示法 扩展线性链表表示法 课后 作业 习题：5.12，5.24 教学 后记 30 课时计划（教案）号 014 周次 8 日期 4 月 16 日/4 月 17 日 课时安

22、排 3 课题 树和二叉树的概念 教材的重点、难点分析 1、二叉树的性质及证明 2、二叉树的各种存储结构特点 教学 目标 1、理解树和二叉树的不同结构特性 2、熟练掌握二叉树的性质及其证明方法 3、熟悉二叉树的各种存储结构特点及适用范围 教学方法和教学手段 方法：导入、讲解、提问 手段：PPT 课件、板书 31 教 学 过 程 Chapter 6 树和二叉树 一、树定义 1、树悌归定义 2、树的表示方法：树形表示法、嵌套集合表示法、广义表表示法、凹入表表示法 3、树、相关术语和逻辑特征 二、二叉树 1、定义 注意二叉树与度为 2 的有序树的本质区别（准备提问）例子就是 3 个结点的树与 3 个结

23、点二叉树的不同形状 2、性质（5 个性质）要能灵活使用二叉树的性质 3、存储结构（1）顺序存储（利用完全二叉树的性质）（2）完全式存储（二叉链表，三叉链表）（3）二叉链表生成例 课后 作业 习题：6.33 6.34 教学 补充几个小例子灵活使用二叉树的性质 32 后记（1）已知二叉树中叶结点 61 个，度为 1 结点 40 个，问总结点数=？（2）完全二叉树第七层共 14 个叶子，问该二叉树最多结点数=？最少结点数=？33 课时计划（教案）号 015 周次 8 日期 4 月 16 日/4 月 17 日 课时安排 2 课题 二叉树的遍历和线索化 教材的重点、难点分析 1、各种遍历算法（递归和非递

24、归）2、二叉树的线索化过程 教学 目标 1、熟练掌握各种遍历策略的递归和非递归算法 2、灵活运用遍历算法实现二叉树的其它操作 3、熟练掌握二叉树的线索化过程及在中序线索化树上找给定结点的前驱和后继的方法 教学方法和教学手段 方法：讲解、提问 手段：PPT 课件、板书 教 学 过 程 Chapter 6 （读）三、遍历二叉树 1、先序遍历 申序遍历 34 后序遍历 递归算法，因离散教学上有此内容，找同学上黑板写三种遍历序列 2、表达式的叉树表示 3、遍历的非递归算法（重点介绍 3-4 个中序遍历非递归）先序非递归（作为习题）后序非递归（作为思考题）4、其它利用遍历算法的例子（1）求二叉树中树叶数

25、目推广为：求度为 1 结点数目，求度为 2结点数目（2）二叉树深度计算（3）二叉树的嵌套括号输出等等 课后 作业 习题：6.36,6.37,6.43,6.47 教学 后记 35 课时计划（教案）号 016 周次 第9周第1次 日期 课时安排 2 课题 树和森林 教材的重点、难点分析 树和森林与二叉树的转换方法 教 学 目 标 1、熟悉树的各种存储结构及其特点；2、掌握树和森林与二叉树的转换方法；3、学会编写实现树的各种操作的算法。教学方法和 教学手段 教学方法：讲授法：1）举例引导 2）提问 教学手段：利用多媒体投影仪和多媒体课件进行教学，减少板书，扩大课堂教学的信息量。教 学 过 程 Cha

26、pter6（续）四、线索二叉树 5、线索、线索化的含义；6、中序全序线索化、后序后继线索化等含义；7、中序线索链表的建立（重点是理解全局变量 pre 和参数 p 的含义及变化）；8、线索链表的应用（1）求中序后继、中序前驱；（2）求后序后继、后序前驱；36（3）求先序后继、先序前驱；（4）中序遍历等。教 学 过 程 五、树和森林 1、存储表示（1）双亲表示法；（2）孩子链表表示法；（3）孩子兄弟链表表示法。2、树、森林与二叉树的转换 3、树、森林的遍历 课后作业 习题：6.56 6.57 6.60 教学 后记 37 课时计划（教案）号 017 周次 第9周第2次 日期 课时安排 2 课题 哈夫

27、曼树及其应用 教材的重点、难点分析 哈夫曼树的构造及哈夫曼编码的方法 教 学 目 标 1、了解最优树的特性；2、掌握建立最优树和哈夫曼编码的方法。教学方法和 教学手段 教学方法：讲授法：1）举例引导 2）提问 教学手段：利用多媒体投影仪和多媒体课件进行教学，减少板书，扩大课堂教学的信息量。教 学 过 程 Chapter6（续）六、最优二叉树及其应用 1、最优二叉树的定义 路径长度、带权路径长度等概念 2、哈夫曼算法 3、前缀编码 4、使用的 DS 及算法分析 38 HT1HTn：叶子结点 HTn+1HTm：非终端结点 其中：m=2n-1，HTm为根结点 教 学 过 程 HC1HCn：为每个叶子

28、结点进行编码 步骤：（1）建树的过程；（2）编码（2 种方法）；（3）译码 上课时只讲解其实现原理，具体的实现由学生课后完成。课后作业 习题：6.49 6.69 教学 后记 布置实验五：二叉树的应用 实验内容：题集 149 页 5.2 哈夫曼编/译码器 要求：（1）用户界面为菜单式交互 （2）初始化建树读入的 n 及其字符与相应权值也从文件中读。39 课时计划（教案）号 018 周次 第 10 周第 1 次 日期 课时安排 2 课题 习题课 2 教材的重点、难点分析 教 学 目 标 教学方法和 教学手段 教学方法：讲授法：1）举例引导 2）提问 教学手段：利用多媒体投影仪和多媒体课件进行教学，

29、减少板书，扩大课堂教学的信息量。教 学 过 习题的订正与讲解：第二章：2.31 2.32 40 程 第三章：3.15 3.19 3.28 3.30 第四章：4.6 4.8 4.25 4.28 第五章：5.12 5.17 5.19 5.24 教 学 过 程 补充讲解：2.38 3.18 3.29 课后作业 教学 后记 41 课时计划（教案）号 019 周次 第 11 周第 1 次 日期 课时安排 2 课题 图的概念及其存储 教材的重点、难点分析 图的各种存储结构及其构造算法 教 学 目 标 1、熟悉图的定义和相关术语；2、熟悉图的各种存储结构及其构造算法。教学方法和 教学手段 教学方法：讲授法：

30、1）举例引导 2）提问 教学手段：利用多媒体投影仪和多媒体课件进行教学，减少板书，扩大课堂教学的信息量。42 教 学 过 程 Chapter7 图 一、图的定义和术语 1、有向图与无向图；2、子图与网；3、完全图、稀疏图、稠密图；4、邻接点、度、入度、出度：5、路径、路径长度、简单路径、简单回路：6、连通图、连通分量、强连通图、强连通分量：7、生成树、生成森林：8、抽象数据类型图的定义。教 学 过 程 二、图的存储结构 1、图的数组（邻接矩阵）存储表示：2、图的邻接表存储表示：3、有向图的十字链表存储表示：4、无向图的邻接多重表存储表示：课后作业 习题：7.14 7.15 7.16 注意这里图

31、的一些基本概念与离散数学里讲得有些不同：重点掌握邻接表、邻接矩阵，会对两种存储方法的特点进行比较。43 教学 后记 课时计划（教案）号 020 周次 第 11 周第 2 次 日期 课时安排 2 课题 图的遍历 教材的重点、难点分析 深度优先搜索算法和广度优先搜索算法的实现 教 学 目 标 1、熟练掌握图的遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法；2、理解图的遍历算法与树的遍历算法之间的类似和差异。教学教学方法：44 方法和 教学手段 讲授法：1）举例引导 2）提问 教学手段：利用多媒体投影仪和多媒体课件进行教学，减少板书，扩大课堂教学的信息量。教 学 过 程

32、Chapter7（续）三、图的遍历 1、深度优先搜索（DFS）；（1）以邻接矩阵作为存储结构介绍 DFS 算法：（2）以邻接表作为存储结构介绍 DFS 算法。教 学 过 程 2、广度优先搜索（BFS）；（1）以邻接矩阵作为存储结构介绍 BFS 算法：（2）以邻接表作为存储结构介绍 BFS 算法。45 课后作业 习题：7.22 7.23 教学 后记 注意：邻接矩阵与邻接表存储结构下，实现 LocateVex(G,V)、FirstAdjVex(G,V)、NextAdjVex(G,V,W)、要透彻理解。课时计划（教案）号 21 周次 12 日期 5 月 4 日 课时安排 3 课题 7.4 图的连通性

33、问题 教材的重点、难点分析 重点：图的连通分量的计算 难点：Prim 算法实现 教 学 目 1、掌握利用图的遍历算法计算图的连通分量方法。2、掌握最小生成数的两种算法实现方法。46 标 教学方法和 教学手段 教学方法：讲解、提问 教学手段：PPT 课件、板书 教 学 过 程 第 7 章 图（续）四、图的连通性问题 1、无向图的连通分量和生成树 DFS 生成树，DFS 生成森林 BFS 生成树，BFS 生成森林 2、生成树 最小生成树的 MST 性质 1）普里姆算法（Prim）2）克鲁斯卡尔算法（Kruskal）教 学 过 程 3、总结本次课程的主要内容；4、布置上机试验的内容；5、布置课后作业

34、。47 课后作业 习题：7.7，7.27 教学 后记 由于时间关系，以孩子兄弟链表存储森林的生成（深度优先生成森林）让学生课后自学 课时计划（教案）号 22 周次 12 日期 5 月 17 日5 月 18日 课时安排 2 课题 有向无环图及其应用 教材的重点、难点分析 有向无环图的两个重要应用：拓扑排序和关键路径 1.理解有向无环图的含义；48 教 学 目 标 2.掌握 AOV 网拓扑排序算法的实现；3.掌握 AOE 网关键路径算法的实现。教学方法和 教学手段 教学方法：讲解 教学手段：PPT 课件、板书 教 学 过 程 第 7 章 图（续）五、有向无环图应用 1、有向无环图的概念 2、拓扑排

35、序问题 AOV 网 提问：“课本上是用栈存储零入度顶点，然后想办法进行，得到其拓扑序列，如果该栈为队列，是否可以？为什么？”3、关键路径，最长路径（AOE 网）四个时间计算：vej，vlk，e，l等 教 学 过 49 程 课后作业 补充题 教学 后记 举一个关键路径的图例，用板书图示从左到右计算最早发生时间 vej，然后从右到左计算顶点最迟发生时间 vlk，进而得到每个活动最早开始与最迟开始时间。课时计划（教案）号 23 周次 13 日期 5 月 21 日5 月 22日 课时安排 3 课题 最短路径 教材的重点、难点Dijkstra 算法求最短路径的方法 50 分析 教 学 目 标 1、掌握最

36、短路径问题求解的 Dijkstra 算法的实现。2、掌握最短路径求解的 Floyd 算法的实现。教学方法和 教学手段 教学方法：讲解 教学手段：PPT 课件、板书 教 学 过 程 第 7 章 图（续）六、最短路径 1、Dijkstra 算法1 个源点到其余各点最短路径 2、Floyd 算法：计算所有顶点对之间最短路径 3、补充一个例子：设有 A、B、C、D 四个村庄，它们之间距离如下所示 要在四个村庄中选择一个作为俱乐部中心，使得其他村庄到俱乐部的最短距离最短。求 求各个村庄之间最短距离。哪个村庄作为俱乐部最合适，为什么？51 教 学 过 程 课后作业 思考题：7.5、7.7、7.9、7.10

37、、7.11、7.13 教学 后记 选择俱乐部中心，后面一句话省掉，即去掉“使得其他村庄到俱乐部的最短距离最短。”让学生选择哪个村庄作为俱乐部合适。52 课时计划（教案）号 25 周次 14 日期 课时安排 2 课题 静态查找表 教材的重点、难点分析 1、利用“监视哨”的方法实现顺序查找。2、折半查找的递归与非递归算法。教 学 目 标 1.掌握顺序查找的新实现方法，计算平均查找长度；2.掌握折半查找的算法，能利用判定数计算 ASL。教学方法和 教学手段 教学方法：导入、讲解、提问 教学手段：PPT 课件、板书 教 学 过 程 第 9 章 查找 查找表的定义、操作、分类 查找成功与查找不成功度量，

38、平均查找长度 ASL 一、静态查找表 1.顺序查找表 注意领会“监视哨”的含义 2.有序查找表 折半查找、判定树画法、ASL 计算 53 3.索引顺序表 分块查找 教 学 过 程 课后作业 习题 9.1 9.3 9.7 教学 后记 布置实验六：图的应用 实验内容：题集150 页 5.4“教学计划编制问题”要求：输入参数直接从键盘输入，最后存入一部分在文件中；课程尽可能集中在前几个学期。54 课时计划（教案）号 2 周次 14 日期 课时安排 2 课题 动态查找表二叉排序树和平衡二叉树 教材的重点、难点分析 平衡二叉树的建立即四种调整方案的使用 教 学 目 标 1.掌握二叉排序树的动态插入、删除

39、及其性能分析；2.掌握平衡二叉树的调整建立。教学方法和 教学手段 教学方法：导入、讲解、提问 教学手段：PPT 课件、板书 教 学 过 程 第 9 章 查找（续）二、动态查找树表 1.二叉排序树（二叉查找树）定义 查找算法 查找成功 查找不成功动态插入 插入算法 删除算法分三种情况 55 性能分析 2.平衡二叉树 教 学 过 程 平衡因子 插入（二叉排序树不断地进行调整，使其成为一棵平衡二叉树）课后作业 习题 9.9 9.10 教学 后记 56 课时计划（教案）号 027 周次 第 15 周 日期 课时安排 2 课题 动态查找表B-树等 教材的重点、难点分析 B-树的插入与删除 教 学 目 标

40、 1、理解 B-树的平衡多路查找树的特点；2、掌握B-树的插入与删除过程；3、理解 B+树与 B-树的区别。教学方法和 教学手段 教学方法：讲解 教学手段：PPT 课件、板书 57 教 学 过 程 Chapter9（续）三、B-树 1.定义平衡多路查找树 2.B-树的插入可能需要“分裂”结点 3.B-树的删除可能需合并结点 4.查找性能分析 四、B+树是 B-树的一种变型 注意：两种 B 树的定义与区别 课后作业 习题：9.13、9.14 教学 后记 58 课时计划（教案）号 028 周次 第 15 周 日期 6 月 7 日/6 月 8 日 课时安排 2 课题 哈希表 教材的重点、难点分析 哈

41、希表的建立与查找成功或不成功的平均查找长度的计算。教 学 目 标 4、理解理解哈希表的含义与哈希函数的构造方法 5、利用开放定址法处理冲突建立哈希表及其性能分析 6、掌握用链地址法处理冲突，建表与性能分析 教学方法和 教学方法：引入、讲解 教学手段：59 教学手段 PPT 课件、板书 教 学 过 程 Chapter9（续）五、哈希表 1哈希表是什么？2哈希表的构造方法 重点掌握除留余数法 3处理冲突办法 线性探测 （1）开放定址法 二次探测 随机探测（2）链地址法 ASL 成功 ASL 不成功 课后作业 习题：9.19、9.21 教学 后记 60 61 课时计划（教案）号 029 周次 第 1

42、6 周 日期 6 月 11 日/6 月 12 日 课时安排 3 课题 习题课 4 教材的重点、难点分析 教 学 目 标 7、理解理解哈希表的含义与哈希函数的构造方法 8、利用开放定址法处理冲突建立哈希表及其性能分析 9、掌握用链地址法处理冲突，建表与性能分析 教学方法和 教学方法：讲解、提问 教学手段：62 教学手段 PPT 课件、板书 教 学 过 程 习题讲解 第七章（1）7.14（2）7.15（3）7.16 注：图的基本操作中删除顶点的实现较复杂。（4）7.22（5）7.23 注：学生的习题中大面积出现相同的解法，是从网上下载的，几乎没有人能验证它的正确性，此解法均有一定的错误。课后作业

43、教学 后记 63 64 课时计划（教案）号 030 周次 第 16 周 日期 6 月 14 日/6 月 15 日 课时安排 2 课题 插入排序 教材的重点、难点分析 希尔排序的过程与性能分析 教 学 目 标 10、掌握直接插入排序的过程与分析 11、掌握希尔排序的过程 教学方法和 教学方法：讲解 教学手段：65 教学手段 PPT 课件、板书 教 学 过 程 Chapter 10 一、排序的概念及种类 内部排序与外部排序 稳定性与不稳定性 二、插入排序 1.直接插入排序稳定性 2.折半插入排序 3.希尔皮按需不稳定 课后作业 教学 后记 66 课时计划（教案）号 031 周次 第 17 周 日期

44、 6 月 18 日/6 月 19 日 课时安排 3 课题 交换排序 教材的重点、难点分析 快速排序的递归实现 教 学 目 标 12、掌握冒泡排序的过程与分析 13、掌握快速尔排序的过程（一趟排序）与时空效率 教学方法和 教学方法：讲解 教学手段：67 教学手段 PPT 课件、板书 教 学 过 程 Chapter 10（续）三、交换排序 1.冒泡排序稳定性 2.快速排序（1）基准选择（2）递归实现（3）时空效率（4）不稳定性 课后作业 教学 后记 68 课时计划（教案）号 032 周次 第 18 周 日期 6 月 21 日/6 月 22 日 课时安排 2 课题 选择排序 教材的重点、难点分析 堆

45、排序的过程 教 学 目 标 14、掌握简单选择排序排序的过程 15、理解堆排序的定义及堆的建立 16、掌握堆排序的过程（即堆的调整与筛选）教学方法和 教学方法：讲解 教学手段：69 教学手段 PPT 课件、板书 教 学 过 程 Chapter 10（续）三、选择排序 1.简单选择排序 2.树型选择排序 3.堆排序 大顶堆 小顶堆（1）堆的定义（2）堆的建立（3）堆的调整与筛选 课后作业 教学 后记 70 71 课时计划（教案）号 033 周次 第 18 周 日期 课时安排 课题 归并与基数排序 教材的重点、难点分析 重点：1、基数排序的原理；.难点：1、基数排序算法的实现 教 学 目 标 1、掌握归并排序过程与性能分析；2、理解多关键字排序的两种方法；3、掌握基数排序的过程；4、理解各种内排序的原理、时空效率、稳定性；教学方法和 教学手段 教学方法：讲授法：1）举例引导 2）提问 教学手段：利用多媒体投影仪和多媒体课件进行教学，减少板书，扩大课堂教学的信息量。教 学 过 程 四、归并与基数排序 1、归并排序（二路归并）需要较大的辅助空间，稳定 2、基数排序（1）多关键字排序的思想 （2）性能分析 稳定的、空间复杂度 72 3、各种排序方法比较 时间复杂度 空间复杂度 稳定性等 教 学 过 程 课后作业 教学 后记 73