《数据结构(Python语言描述)》教学教案.docxVIP

教学单元：数据结构（本科）课程概述（2学时） 授课班级: 教学内容提要: 1课程简介：地位（考研、软件开发岗位必考），在专业知识体系中的位置，就 业岗位等；2课程主要内容及学时分配； 3课程考核方式；4课程学习方法； 5算法的基本概念和术语；6 Java语言编程回顾。 教学目的： 了解该课程所研究的内容、作用和发展状况，就业岗位，可以考取的证书等；了解算法基本概念和术语； 3在Eclipse环境下编辑一个简单的求最大公约数的程序。 教学重点、难点： 1数据结构、算法、算法复杂度的基本概念；2如何把现实的问题抽象出来，建立模型，设计算法，再分析算法的复杂度，并 选取合适的语言编码实现。 教学方法： 通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。 教学过程设计： 1、利用CC网，介绍课程的资源：老师搭建的hustoj在线评测网站、几本教材的 PPT、Java软件等供他们下载，自学，要求他们主动学习，提供参考资料给他们； 2、介绍学习方法，课堂及作业要求、纪律要求、考核方式等；3、了解学生：有多少人数准备继续深造（出国，考研等），多少人准备从事软件 开发，自己创业等； 4、介绍课程的作用，在专业课程中的地位，对个人提升的重要性等，特别强调所 4）二叉树的层次遍历层次遍历的定义、层次遍历的算法实现和层次遍历的应用 教学目的： 了解树和二叉树的定义；2 了解二叉树的性质和存储结构； 3掌握二叉树的几种遍历；4掌握利用前序和中序遍历构建二叉树的递归算法 教学重点、难点： 1二叉树二叉链式存储实现2二叉树遍历的应用 3利用前序和中序遍历构建二叉树教学方法： 通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。 教学过程设计： 1、介绍树和二叉树的基本概念；2、介绍树和二叉树的顺序存储和链式存储的实现，并画出示意图（黑板）； 3、讲解完全二叉树的存储原理和实现细节（为后面堆的知识做铺垫）；4、介绍二叉树常用的三种遍历 讨论二叉树的遍历能否确定一棵二叉树？ 举出前序和后序遍历不能确定二叉树的反例给出利用前序和中序遍历构建二叉树的递归算法，作业题9 5、讲解二叉树的层次遍历；讨论二叉树的层次遍历，要怎么存储层次和父子信息 课堂提问： 提问1:如何判定完全二叉树？ 提问2：能不能给出前序和后序遍历不能确定二叉树的反例？ 提问3：老师给出的利用前序和中序遍历构建二叉树的算法，为什么要用递 归？使用递归有什么优点？ 小结： 介绍二叉树基本概念和术语；介绍二叉树常用的三种遍历和层次遍历; 3)掌握利用前序和中序遍历构建二叉树的算法。 作业： 预习：常用二叉树复习：队列 教学单元：《数据结构》哈夫曼树（2时） 授课班级： 教学内容提要： 5哈夫曼树1哈夫曼树构造方法 1. 1最优二叉树概念 .路径和路径长度 .结点的权和带权路径长度 .树的带权路径长度WPL = ^W^\ 1=1 哈夫曼树构造的步骤如下： （1）用给定的n个权值{wl, w2,…，wn}对应的n个结点构成n棵二叉树的森 林F={T1, T2,…，Tn},其中每一棵二叉树Ti （1 Wi Wn）都只有一个权值为wi的 根结点，其左、右子树为空。 （2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、 右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。（3）从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。 （4）重复（2）、（3）操作，直到森林中只含有一棵二叉树为止，此时得 到的这棵二叉树就是赫夫曼树。 2哈夫曼编码 前缀编码：任一个字符的编码都不是另一个字符编码的前缀，可利用二叉树 设计前缀编码。 3哈夫曼编码的编码方法 二叉树指向左孩子的边编码为1,指向右孩子的边编码为0。每个叶子节点代 表字符（单词）的编码，为从根节点到该节点所经边的编码串。 教学目的： 了解哈夫曼树和哈夫曼编码的定义；了解哈夫曼树的性质和构造方法； 3掌握哈夫曼树的编码方法；教学重点、难点： 1哈夫曼树存储实现2哈夫曼树构造方法的编码实现 3哈夫曼树编码的编码实现教学方法： 通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。 教学过程设计： 1、介绍哈夫曼树和哈夫曼编码的基本概念；2、介绍哈夫曼树构造方法，并画出示意图(黑板)； 3、讲解哈夫曼树构造方法的代码实现(为后面哈夫曼编码做铺垫)；4、讲解哈夫曼编码的代码实现； 讨论：采用链式存储好还是顺序存储好？ 课堂提问: 有一电文共使用五种字符a, b, c, d, e,其出现频率依次为4, 7, 5, 2, 9。 (1)试画出对应的编码赫夫曼树(要求左子树根结点的权小于等于右子树根结 点的权)。 (2)求出每个字符的赫夫曼编码。 小结： 介绍哈夫曼树和哈夫曼编码的基本概念；掌握哈夫曼