资源描述
湖南科技经贸职业学院课程教案(章节备课)授课题目（章节） 第六章 树和二叉树授课类型理论课授课时间第 9 周 至第 11 周 共10学时教学目的要求：理解树与二叉树的基本概念，掌握二叉树的性质与存储结构；掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现教学要点：1 树的概念和定义2 树的特性及表示方式3 树的相关术语 4 二叉树的定义和它的五种形态5 二叉树的性质6 二叉树的存储结构：顺序存储和二叉链表存储结构7 遍历二叉树和线索二叉树 8 树的存储结构及与二叉树的转换 9 森林与二叉树的转换10 树和森林的遍历11 最优二叉树（哈夫曼树）的概念12 赫夫曼树构造算法。13 哈夫曼树的应用教学进程：1讲授本章节的基本概念，先逻辑结构，后存储结构；2讲授各存储结构下的实现的主要思想；3计算机演示存储结构下的实现；4例题讲解；5作业教学重点：二叉树的性质、二叉树的存储结构；二叉树的遍历算法和二叉树遍历算法的应用；哈夫曼树在编码方面的应用方法。教学难点：二叉树的性质以及利用这些性质分析问题的方法；二叉树问题的遍历算法设计分析和实现。教学方法与手段辅助手段：多媒体演示，对于重点和难点，通过程序演示，作业来突出。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析本间讲述了树、二叉树、哈夫曼树的定义、性质、算法。讲述了一个新的数据结构，算法相对简单，学生理解尚可，但由于本章涉及较多的递归，学生对递归算法的实现不太理解。以后在教学中可以压缩树的定义、二叉权的性质讲解内容，增加树的遍历算法及哈夫曼树的应用讲解内容，并增加习题课湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）：树的定义、基本术语，二叉树的定义及五条性质、顺序、链式存储结构授课类型理论课授课时间第9周第2节教学目标或要求：掌握树的定义，了解树的基本术语，了解树的基本操作；掌握二叉树的概念和性质，掌握二叉树的存储结构。教学要点：1树的定义及树的基本术语、二叉树，满二叉树，完全二叉树； 2二叉树的性质3二叉树的链式存储结构的实现4二叉树的顺序存储结构和链式存储结构教学进程：1先讲授概念：二叉树，满二叉树，完全二叉树，图示一些图结构，提问互动，加强对概念的理解。2讲授二叉树的5条性质，证明其中的（1），(3)，(4)。用例子说明这些性质，加强理解3分析链式存储结构的特点，比较线形结构与树结构的不同，体现在实现上的不同有哪些？讲授链式存储的实现，演示程序。教学重点：二叉树的五个性质，二叉树的链式存储结构的实现教学难点：二叉树的链式存储结构的实现教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。思考题、讨论题、作业：一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点上都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：（1）各层的结点数目是多少？（2）编号为p的结点的父结点（若存在）的编号是多少？（3）编号为p的结点的第i个儿子结点（若存在）的编号是多少？（4）编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 遍历二叉树的递归及非递归算法授课类型理论课授课时间第10周第1节教学目标或要求：掌握二叉树遍历的基本方法（DLR，LDR，LRD），二叉树链式存储结构下遍历的递归、非递归算法教学要点：1二叉树遍历的基本方法（DLR，LDR，LRD）2二叉树链式存储结构下遍历的递归、非递归算法教学进程：1讲授二叉树的基本遍历方法，以直观的二叉树为例子，图示三种基本的遍历结果；2 DLR，LDR 或LRD，LDR的组合可以唯一确定一颗二叉树，而DLR，LRD的组合不唯一，多媒体动态演示LRD，LDR唯一确定一颗二叉树的过程。3 边讲解边演示二叉树链式存储结构下遍历的递归算法的实现。 4 演示二叉树遍历的应用，强调遍历算法是本章很多算法的基础，比较重要。5 讨论如何将遍历的算法变为非递归的算法-重要的工具：堆栈。教授非递归算法的实现的思想，以例子说明堆栈的变化及遍历结果。教学重点：二叉树链式存储结构下的递归算法教学难点： 二叉树链式存储结构下的非递归算法教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。思考题、讨论题、作业：统计二叉树中叶子结点的个数(先序遍历)求二叉树的深度(后序遍历)复制二叉树(后序遍历)参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 线索二叉树树的存储结构、森林与二叉树的转换及森林的遍历授课类型理论课授课时间第10周第2节教学目标或要求：了解线索二叉树和二叉树的线索化。掌握树的存储结构，掌握二叉树、树和森林的转换。教学要点：1 线索二叉树2 二叉树的线索化3树的三种主要表示方法4 树的抽象数据类型5 树的常用存储结构的构造方法6 树与二叉树的转换；树的遍历。7 森林与二叉树的转换；森林的遍历。教学进程：1 介绍线索二叉树2 介绍树的存储结构的构造方法，分别举例；3 介绍转换的一般原则，先讲授树转换为二叉树的步骤，举例说明，在讲授二叉树转换为树的步骤,举例说明。4 树的遍历（先根和后根）5先讲授森林转换为二叉树的步骤，举例说明，在讲授二叉树转换为森林的步骤,举例说明。6 森林的遍历教学进程：1 回顾二叉树的链式存储表示及遍历方法2 链式存储表示的二叉树的遍历不方便之处3提问指针的个数4 讲授线索二叉树的遍历5讲授二叉树的线索化教学重点： 线索二叉树和二叉树的线索化.。树的三种主要表示方法、树与二叉树的转换；树的遍历、森林与二叉树的转换；森林的遍历教学难点： 二叉树的线索化。树与二叉树的转换、树的遍历教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。思考题、讨论题、作业：将下列二叉链表改为先序线索链表（不画出树的形态）。 分别画出和下列树对应的各个二叉树假设在二叉链表中增加两个域：双亲域（parent）以指示其双亲结点；标志域（mark取值0.2）以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 赫夫曼树及赫夫曼编码授课类型理论课授课时间第11周第1节教学目标或要求：掌握哈夫曼树的建立、哈夫曼编码。了解树的计数问题。教学要点：1 概念： 路径，路径长度，二叉树的路径长度，二叉树的带权路径长度；2哈夫曼树的构造算法3哈夫曼编码4 哈夫曼编码问题的设计和实现教学进程：1讲授概念： 路径，路径长度，二叉树的路径长度，二叉树的带权路径长度；举例说明；2哈夫曼树的含义，什么是哈夫曼编码，讲授哈夫曼树的构造算法，举例说明如何构造哈夫曼树和哈夫曼树编码。3 讲解哈夫曼编码的实现。教学重点：哈夫曼树的构造算法，哈夫曼编码，教学难点：哈夫曼编码问题的设计和实现教学手段与方法：多媒体为辅助手段，以提问设计师生互动思考题、讨论题、作业：假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树6.11 假设用于通信的电文仅由八个字母组成，字母在电文中的出现频率分别为0.07, 0.19, 0.02, 0.06, 0.32,0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制是另一种编码方案。对于上述实例，比较两种方案的优缺点。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案(章节备课)授课题目（章节） 第七章 图授课类型理论课授课时间第 11 周 至第 13 周 共10学时教学目的要求：了解图的基本概念和术语；掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；理解图的深度和广度遍历方法和算法设计方法；理解最小生成树的概念、普里姆算法和克鲁斯卡尔算法；了解最短路径问题的基本概念和从一个结点到其余各结点最短路径的算法。教学要点：1 概念和术语2 图的基本运算的定义3 图的存储结构4 图的遍历算法5 如何得到图的最小生成树6 构造最小生成树的算法7 拓扑排序和AOV网（顶点表示活动的有向网）8 关键路径问题和AOE网（边表示活动的有向网）9 单源最短路径迪杰斯特拉(Dijkstra)算法10 每对顶点间的最短路径弗洛伊德（Floyd）算法教学进程：1 介绍图的定义和术语2 讲授图的两种存储结构和两种遍历方法3 介绍图的连通性问题，重点是最小生成树4讲授图的拓扑排序并介绍关键路径5 介绍最短路径每次下课前布置若干思考题，待下次上新课前进行提问。根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。教学重点：图的邻接矩阵和图的邻接表存储结构；图的深度和广度遍历方法；普里姆算法和克鲁斯卡尔算法。教学难点：操作的实现方法。教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，图中的概念很多，采取先讲实例应用，再总结概念定义的方法学习效果会好些。对重点和难点算法的核心部分通过板书进行详细讲解。对算法的实现要求采用VC+开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 图的定义和术语及图的邻接矩阵表示授课类型理论课授课时间第11周第2节教学目标或要求：掌握图的概念和表示，掌握图的顺序存储结构及描述。教学要点：1图的基本概念、定义、特性2图的邻接矩阵表示教学进程：1 回顾第一章提出的信号灯问题，引出图结构2 画一个图，讲解图的基本概念、定义、术语和性质，3 讲授图的邻接矩阵表示方法4重点讲授图的数组存储表示5 画一图，讲授邻接矩阵表示的图的构造方法教学重点：图的邻接矩阵表示教学难点：图操作的实现方法。教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，图中的概念很多，采取先讲实例应用，再总结概念定义的方法学习效果会好些。对重点和难点算法的核心部分通过板书进行详细讲解。对算法的实现要求采用VC+开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。思考题、讨论题、作业：已知如右图所示的有向图，请给出该图的 1）每个顶点的入/出度；2）邻接矩阵；试在邻接矩阵存储结构上实现图的基本操作：InsertVex(G,v),InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 图的邻接表表示、邻接多重表、图的遍历及最小生成树授课类型理论课授课时间第12周第1节教学目标或要求：掌握图的链表存储结构及描述，了解十字链表和邻接多重表，掌握图的两种遍历方式，了解图的连通性问题。教学要点：1 图的邻接表存储表示2 十字链表邻接多重表3 图的深度优先遍历4 图的广度优先遍历5 无向图的连通分量和生成树6 有向图的强连通分量教学进程：1 回顾图的邻接矩阵表示2 讲授图的邻接表存储表示、逆邻接表，各自的优缺点3 介绍十字链表和邻接多重表4 利用图示法重点讲授图的深度优先遍历和广度优先遍历5介绍无向图的连通分量和生成树和有向图的强连通分量教学重点：图的邻接表存储表示、逆邻接表、图的深度优先遍历和广度优先遍历教学难点：图的深度和广度遍历算法的程序实现教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。对算法的实现要求采用VC+ 开发环境进行调试运行，配合大屏幕投影演示，增强学生对算法的设计方法的理解和提高学生的学习兴趣。思考题、讨论题、作业：已知如左下图所示的有向图，请给出该图的1）邻接表；2）逆邻接表。 画出上右图所示的无向图的邻接多重表，使得其中每个无向边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。列出深度优先和广度优先搜索遍历该图所得到顶点序列和边的序列。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 普里姆算法授课类型理论课授课时间第12周第2节教学目标或要求：了解图的连通性问题，理解最小生成树的概念以及普里姆算法和克鲁斯卡尔算法，掌握最小生成树的创建。教学要点：1 利用普里姆算法构造图的最小生成树2 普里姆算法的实现3 利用克鲁斯卡尔算法构造图的最小生成树4 关键点和重连通分量教学进程：1 讲授图的最小生成树的定义2 图示法讲授利用普里姆算法构造图的最小生成树3 重点讲解普里姆算法的实现4 图示法讲授利用克鲁斯卡尔算法构造图的最小生成树5 介绍关键点和重连通分量教学重点：普里姆算法和克鲁斯卡尔算法教学难点：普里姆算法和克鲁斯卡尔算法的程序实现。教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法核心部分通过板书进行详细讲解。对算法的实现要求采用VC+ 开发环境进行调试运行，配合大屏幕投影演示，增强学生对算法的设计方法的理解和提高学生的学习兴趣。思考题、讨论题、作业：对无向带权图，1）写出它的邻接矩阵，并按普里姆算法求其最小生成树； 2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树；参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 拓朴排序授课类型理论课授课时间第13周第1节教学目标或要求：掌握拓扑排序的方法和步骤，了解关键路径的创建方法，了解最短路径。教学要点：1 拓扑排序2 关键路径3 最短路径教学进程：1 讲授拓扑排序概念和作用2 图示法讲授如何得到一个图的拓扑排序3 重点讲授拓扑排序算法4 介绍关键路径及其求法5 介绍最短路径及其求法教学重点： 拓扑排序、关键路径、最短路径教学难点： 拓扑排序算法实现，关键路径和最短路径的实现教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量。对算法的实现要求采用VC+ 开发环境进行调试运行，配合大屏幕投影演示，增强学生对算法的设计方法的理解和提高学生的学习兴趣。思考题、讨论题、作业：对下左图所示的AOE-网，计算各活动弧的e(ai)和l(aj)函数值、各事件（顶点）的ve(vi)和vl(vj)函数值；列出各条关键路径。 利用Dijkstra算法求下右图中从顶点a到其它各顶点间的最短路径，写出执行算法过程中各步的状态。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案(章节备课)授课题目（章节） 第九章 查找授课类型理论课授课时间第 13 周 至第 14 周 共8学时教学目的要求：1 查找的基本概念；2 顺序表的查找；3 树表的查找；4 哈希表查找。教学要点：1 顺序查找、二分查找、索引顺序查找算法；2 二叉排序树的查找、插入与删除算法；3 B-树的定义以及B-树的查找、插入与删除算法思想。4 常用的哈希函数的设计方法：除留余数法、直接定址法、数字分析法；5 哈希冲突解决方法：开放地址法、链表法。6 哈希表的完整设计过程，包括：哈希表的构建、元素的插入与删除、哈希表查找。7 分析方法：结合具体实例，通过示意图分析算法的设计方法，并在VC环境下实际运行。教学进程：1 介绍查找、查找表的基本概念2 首先讲授静态查找表，主要讲顺序查找的思想和算法实现、折半查找的思想和算法实现，理解静态树表的查找算法和举例，掌握索引查找的算法思想和算法性能分析3 接着讲授动态查找表，主要讲二叉排序树的构造、结点的插入和删除算法及查找分析4 图示法介绍平衡二叉树的构造方法5 介绍B-树、B+树、键树6 分析查找的时间复杂度，提出哈希表的概念、术语7 讲授哈希函数的构造方法、处理冲突的方法，介绍哈希表的查找算法及算法分析板书设计：以文字描述为主，要点及关键词用不同颜色标注；对查找、插入与删除等算法通过示意图描述；对于实例，通过链接到VC环境下实际运行。重点突出：通过课堂强调与透彻分析，课后练习进行。难点解决：通过不同类型的实例讲解，使学生理解并掌握常用的哈希函数设计方法以及哈希冲突的解决方法，并总结其优、缺点。师生互动设计：实例分析中引导学生参与算法设计；提问：在每一种哈希函数的设计方法及哈希冲突的解决方法讲解后，引导并提问学生此类方法的优、缺点及解决途径。教学重点：1 二分查找；2 二叉排序树的查找；3 哈希表查找。教学难点：哈希表中哈希函数的设计与哈希冲突解决方法。教学方法与手段以课堂多媒体教学为主，辅助以黑板进行绘图分析；课后做习题，并上机实验，练习二分查找、二叉排序树查找及哈希表查找的算法设计，以巩固课堂所学知识点。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 顺序查找及折半查找、静态树表的查找及索引顺序表的查找授课类型理论课授课时间第13周第2节教学目标或要求：要求掌握：查找的基本概念；顺序查找、二分查找、索引顺序查找算法；分析方法：从介绍算法的基本思想，然后结合具体实例在VC环境下实际运行。教学要点：1 概念：查找表、静态查找表、动态查找表、关键字、查找成功、查找不成功2 顺序表的查找算法思想、算法实现、平均查找长度分析3 折半查找算法思想、算法实现、平均查找长度分析4 次优查找树、静态树表的查找算法思想、算法实现、平均查找长度分析5 索引查找表的查找算法、平均查找长度分析教学进程：1 由现实生活中的查找入手介绍本章概念2 讲授顺序表的查找算法思想，图示查找过程，分析后得出顺序查找算法。3 分析顺序查找平均查找长度4 从有序表入手折半讲授折半查找的算法思想，演示查找过程，分析算法思想后得出算法5分析折半查找平均查找长度6 由不等查找概率的情况分析折半查找平均查找长度，引出次优查找树，演示构造过程、查找过程，分析得出算法。7 介绍索引顺序表的查找、分析平均查找长度教学重点：1 有序顺序表的查找；2 索引顺序表的查找。教学难点：索引顺序表的查找。教学手段与方法：以课堂多媒体教学为主，辅助以黑板进行绘图分析；课后做习题，并上机实验，练习顺序查找、二分查找、索引顺序查找算法，以巩固课堂所学知识点。思考题、讨论题、作业：已知含12个关键字的有序表及其相应的权值为：1) 试按次优查找树的构造算法并加恰当调整画出由这12个关键字构造所得的次优查找树，并计算它的PH值。2）画出对以上有序表进行折半查找的判定树，并计算它的PH值。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 二叉排序树及查找及分析、平衡二叉树的介绍授课类型理论课授课时间第14周第1节教学目标或要求：了解动态查找的思想，掌握二叉排序树的构造方法，理解平衡二叉树的构造方法，了解B+树和B-树。教学要点：1 二叉排序树及查找过程2 二叉排序树的插入和删除3 二叉排序树的查找分析4 平衡二叉树5 B-树+B+树教学进程：1 由静态查找表：折半查找引申到动态查找表：二叉排序树2 讲授二叉排序树的定义、性质3 图示法讲授二叉排序树的构造方法4 重点讲解二叉排序树中的插入和删除5分析二叉排序树的平均查找长度 6 由二叉排序树的极端情况引出平衡二叉树 7 讲授平衡二叉树的构造方法 8 介绍平衡二叉树的实现算法 9 介绍B-树和B+树教学重点：二叉排序树的查找、插入与删除算法教学难点：二叉排序树的删除算法教学手段与方法：以课堂多媒体教学为主，辅助以黑板进行绘图分析；课后做习题，练习二叉排序树及B-树的查找、插入与删除算法，并上机实验B-树的查找、插入与删除算法设计，以巩固课堂所学知识点。思考题、讨论题、作业：已知一组关键字为25，18，46，2，53，39，32，4，74，67，60，11。（1）试求在顺序表上顺序查找时，在等概率的情况下查找成功的平均查找长度。（2）若对表中的元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。（3）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。（4）按表中元素的顺序构造一棵平衡二叉树，并求其在等概率的情况下查找成功的平均查找长度。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 哈希表授课类型理论课授课时间第14周第2节教学目标或要求：掌握哈希表的基本概念、哈希函数的构造方法、哈希冲突解决方法、哈希表设计举例。教学要点：1 哈希表的基本概念；2 常用的哈希函数的设计方法：除留余数法、直接定址法、数字分析法；3 哈希冲突解决方法：开放地址法、链表法。4 哈希表的完整设计过程，包括：哈希表的构建、元素的插入与删除、哈希表查找。5 分析方法：结合具体实例，分析介绍各种哈希函数的设计方法及哈希冲突的解决方法。教学进程：1 由各种查找算法的平均查找长度引出哈希表2 讲授哈希表的的基本概念：哈希函数、冲突、同义词、哈面表、哈希地址3 举例讲解哈希函数的构造方法4 讲授处理冲突的方法，对开放定址法、链地址法分别举例说明5 介绍哈希表的查找算法6 分析哈希表的平均查找长度教学重点：1 哈希函数的构造方法；2 哈希冲突解决方法。教学难点：哈希冲突解决方法。教学手段与方法：以课堂多媒体教学为主，辅助以黑板推导有关计算、绘图分析；课后做习题，并上机实验，练习哈希函数的设计方法、哈希冲突的解决方法及哈希表的查找，以巩固课堂所学知识点。思考题、讨论题、作业：设给定的哈希表地址空间为HT0.10，关键字的集合为key=24, 38, 56, 70, 23, 53, 43, 64, 75，哈希函数使用“除留余数法”，冲突解决分别采用“线性探测再散列”和“链地址”法，试画出两种情况下的哈希表，并求出等概率查找时的查找成功的平均查找长度和查找不成功的平均查找长度。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案(章节备课)授课题目（章节） 第十章 内部排序授课类型理论课授课时间第 15 周 至第 16 周 共7学时教学目的要求：掌握排序的基本概念和排序算法的评判标准；掌握直接插入排序、希尔排序、直接选择排序、堆排序、快速排序、二路归并排序、基数排序的算法思想。教学要点：讨论比较各种内部排序方法，插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。在每类排序方法中，从简单方法如手，重点讨论性能先进的高效方法（如，插入排序类中的希尔排序、交换排序类中的快速排序、选择排序类的堆排序）。1 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。2 了解各种方法的排序过程及其依据的原则。3 掌握各种排序算法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(n*logn)的高效排序方法和O(d*n)的基数排序方法。4 理解排序方法稳定和不稳定的含义弄清楚在什么情况下要求的排序方法必须是稳定的。5 希尔排序、快速排序、堆排序和归并排序等高效方法是本章学习的重点和难点。教学进程：1 讲授本章节的基本概念，先逻辑结构，后存储结构；2 讲授各存储结构下的实现的主要思想；3 计算机演示存储结构下的实现；4 例题讲解；5 作业教学重点：希尔排序、堆排序、快速排序、二路归并排序和基数排序的算法思想教学难点：堆排序、快速排序、二路归并排序和基数排序的算法设计方法教学方法与手段以课堂多媒体教学为主，辅助以黑板进行绘图分析；课后做习题，并上机实验，练习插入排序、交换排序、选择排序的算法设计，以巩固课堂所学知识点。思考题（讨论题）及作业（有单元课时教案的本项可不填）：参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）：排序的基本概念、插入排序授课类型理论课授课时间第15周第1节教学目标或要求：掌握直接插入排序、折半插入排序、希尔排序的思想和算法描述，理解2-路插入排序，掌握排序算法的时间和空间复杂度。教学要点：1 概念：排序，主（次）关键字，内部（外部）排序，比较排序算法的技术指标、排序方法是稳定的和不稳定的2 插入排序的基本思想；3 直接插入排序的思想、实现、算法分析4 折半插入排序的思想、实现、算法分析5 二路插入排序的思想6 希尔排序的思想，实现，算法分析。教学进程：1介绍基本概念：什么是排序，按什么排序，需有主关键字，什么是内部排序，外部排序2 介绍比较排序算法的技术指标，举例说明排序的稳定性。3 直接插入排序的基本思想-举例说明-算法的实现-算法分析-算法的程序演示。4 折半插入排序的基本思想-举例说明-算法的实现-算法分析-算法的程序演示。5 介绍二路插入排序的算法思想6 希尔插入排序的基本思想-举例说明-算法的实现-算法分析-算法的程序演示。教学重点：各种插入排序算法的算法思想、程序实现、算法分析教学难点： 各种插入排序算法的程序实现教学手段与方法：以课堂多媒体教学为主，辅助以黑板进行绘图分析；课后做习题，练习直接插入排序、折半插入排序、希尔排序算法，并上机实验直接插入排序、折半插入排序、希尔排序算法设计，以巩固课堂所学知识点。思考题、讨论题、作业：理解排序方法稳定和不稳定的含义，弄清楚在什么情况下要求的排序方法必须是稳定的。讨论比较各种内部排序方法，插入排序、的基本思想、算法特点、排序过程以及它们的时间复杂度分析。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 快速排序及选择排序授课类型理论课授课时间第15周第2节教学目标或要求：掌握冒泡排序、快速排序、选择排序、堆排序等排序算法的思想和算法实现，掌握排序算法的时间和空间复杂度。教学要点：1 冒泡排序的思想、实现、算法分析2 快速排序的思想、实现、算法分析3 简单选择排序的思想、实现、算法分析4 堆排序的思想、实现、算法分析教学进程：1 讲授冒泡排序的基本思想-算法实现-程序演示性能分析。2 讲授快速排序的基本思想-算法实现-程序演示性能分析。3 简单选择排序的思想-算法实现-程序演示性能分析；4 扼要介绍推排序的思想，相关概念：堆，最大堆，最小堆；5 堆的创建；6 堆排序算法与性能分析。教学重点：各种排序算法的基本思想与算法实现及算法分析教学难点： 各种排序算法的算法实现教学手段与方法：以课堂多媒体教学为主，辅助以黑板进行绘图分析；课后做习题，练习冒泡排序、快速排序、选择排序算法，并上机实验冒泡排序、快速排序、选择排序算法设计，以巩固课堂所学知识点。思考题、讨论题、作业：讨论比较各种内部排序方法，插入排序、交换排序、选择排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案（课时单元备课）授课题目（或主题）： 归并排序、基数排序及排序方法比较授课类型理论课授课时间第16周第1节教学目标或要求：了解归并排序、基数排序的算法思想；掌握对各种排序算法的时间和空间复杂度进行比较的方法。教学要点：1 归并排序的算法思想、实现、算法分析2 基数排序的算法思想3 链数基数排序的算法思想4 各种排序算法的时间和空间复杂度进行比较教学进程：1归并排序的思想-算法实现-程序演示-性能分析；2基数排序的概念，要借助队列来实现，不同的存储结构，不同的实现方法，不同的算法性能。3 链式基数排序的思想4本章小结：各种排序算法的性能比较教学重点：归并排序 ，基数排序的基本思想与算法实现、算法分析教学难点： 归并排序 ，基数排序的算法实现教学手段与方法：课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量。对算法的实现要求采用VC+ 开发环境进行调试运行，配合大屏幕投影演示，增强学生对算法的设计方法的理解和提高学生的学习兴趣。思考题、讨论题、作业：讨论比较各种内部排序方法归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。参考资料（含参考书、文献等，有章节教案的本项可不填）： 湖南科技经贸职业学院课程教案(章节备课)授课题目（章节） 第十一、十二章 外部排序和文件、总复习授课类型理论课授课时间第 16 周 至第 16 周 共3学时教学目的要求：了解外部排序的方法，多路平衡归并的实现，理解置换-选择排序算法，了解文件、顺序文件、索引文件、ISAM文件、VASM文件、直接存取文件、多关键字文件等概念。教学要点：1 外排原因2 读取一个数据块的时间3 外排方法及其外排所用的时间分析4 多路平衡归并的实现5 置换-选择排序6 文件的概念教学进程：1 外部排序问题的提出2 外部排序的基本过程3 分析外排所用的时间4 简单介绍多路平衡归并的实现5 介绍置换-选择排序的算法思想6 简单介绍文件有关的基本概念教学重点：外排方法及外部排序所用时间分析，置换-选择排序教学难点：外部排序所用时间分析，置换-选择排序教学方法与手段课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量。思考题（讨论题）及作业（有单元课时教案的本项可不填）：讨论外部排序所用时间分析。参考文献（含参考书、有关资料出处、相关课程网站网址等）：1 严蔚敏，吴伟民，米宁编著数据结构题集C语言版，北京，清华大学出版社，199962 廖荣贵，许正宪，王龙发编著数据结构算法，北京，清华大学出版社，2004113 李春葆编著数据结构习题与解析第二版，北京，清华大学版社，200424 梁作娟，胡伟，唐瑞春编著数据结构习题解答与考试指导，北京，清华大学出版社，2004115 张铭，刘晓丹译数据结构与算法分析C+版，电子工业出版社课 后 自 我 总 结 分 析
展开阅读全文