您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 2010-2011-2数据结构课程教案
湖南科技经贸职业学院课程教案(章节备课)授课题目(章节)第六章树和二叉树授课类型理论课授课时间第9周至第11周共10学时教学目的要求:理解树与二叉树的基本概念,掌握二叉树的性质与存储结构;掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现教学要点:1树的概念和定义2树的特性及表示方式3树的相关术语4二叉树的定义和它的五种形态5二叉树的性质6二叉树的存储结构:顺序存储和二叉链表存储结构7遍历二叉树和线索二叉树8树的存储结构及与二叉树的转换9森林与二叉树的转换10树和森林的遍历11最优二叉树(哈夫曼树)的概念12赫夫曼树构造算法。13哈夫曼树的应用教学进程:1.讲授本章节的基本概念,先逻辑结构,后存储结构;2.讲授各存储结构下的实现的主要思想;3.计算机演示存储结构下的实现;4.例题讲解;5.作业教学重点:二叉树的性质、二叉树的存储结构;二叉树的遍历算法和二叉树遍历算法的应用;哈夫曼树在编码方面的应用方法。教学难点:二叉树的性质以及利用这些性质分析问题的方法;二叉树问题的遍历算法设计分析和实现。教学方法与手段辅助手段:多媒体演示,对于重点和难点,通过程序演示,作业来突出。思考题(讨论题)及作业(有单元课时教案的本项可不填):参考文献(含参考书、有关资料出处、相关课程网站网址等):1严蔚敏,吴伟民,米宁编著·数据结构题集·C语言版,北京,清华大学出版社,1999.62廖荣贵,许正宪,王龙发编著·数据结构算法,北京,清华大学出版社,2004.113李春葆编著·数据结构习题与解析·第二版,北京,清华大学版社,2004.24梁作娟,胡伟,唐瑞春编著·数据结构习题解答与考试指导,北京,清华大学出版社,2004.115张铭,刘晓丹译·数据结构与算法分析·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讲授二叉树的基本遍历方法,以直观的二叉树为例子,图示三种基本的遍历结果;2DLR,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语言版,北京,清华大学出版社,1999.62廖荣贵,许正宪,王龙发编著·数据结构算法,北京,清华大学出版社,2004.113李春葆编著·数据结构习题与解析·第二版,北京,清华大学版社,2004.24梁作娟,胡伟,唐瑞春编著·数据结构习题解答与考试指导,北京,清华大学出版社,2004.115张铭,刘晓丹译·数据结构与算法分析·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)。参考资料(含参考书、文献等,有章节教案的本项可不填):湖南科技经贸职业学院课程教案(课时单元备课)授课题目(或主题
本文标题:2010-2011-2数据结构课程教案
链接地址:https://www.777doc.com/doc-3065028 .html