二叉树的遍历（前序 中序 后序） 树、森林和二叉树的转换（树森林到二叉树的转换， 二叉树到树、森林的转换）
第八章图 图的基本概念（有向图、无向图 特点） 图的基本存储结构（邻接矩阵、邻接表） 生成树与最小生成树（prim算法、Kruskal算法） 最短路径（单源最短路径：Dijkstra算法）
第九章 检索 检索的基本概念（平均查找长度） 顺序检索（思想、查找成功和失败的平均查找长度 ）
（五）、对于如图所示的有向网，用Dijkstra 方法 求从顶点A 到图中其他顶点的最短路径，并写出执 行算法过程中距离向量d 与路径向量p 的状态变化 情况。
10E B4Fra bibliotek2 15
A
18
13
F
D
28 8
4
C
0
1
2
3
4
5
0
1
2
3
4
5
上图的最短路径和长度为：
（六）、假设通讯电文中只用到A，B，C，D，E， F 六个字母，它们在电文中出现的相对频率分别为： 8，3，16，10，5，20，试为它们设计Huffman 编 码，并求出这些字符的平均编码长度。
图
（三)、已知一棵二叉树的中序遍历的结果为 ABCEFGHD ，后序遍历的结果为ABFHGEDC， 试画出此二叉树。
(四)、 对如图所示的连通图，分别用Prim 和 Kruskal算法构造其最小生成树。
（1）prim算法
（2）采用Kruskal 算法求解最小生成树时首先要对边进行由小到大 进行排序，本题对边进行排序的结果是：（D,F）1、（C,F）2、 （A,F）3、（A,C）4、（F,G）4、（D,E）4、（D,B）4、（C,D） 5、（E,G）5、（A,D）6、（D,G）6、（A,B）7 。
查找成功时的平均查找长度计算方法： 查找成功时比较的总次数/关键字的个数
线性探测法构造的散列表如下：
查找成功时的平均查找长度为: (1+1+3+4+1+1+2+8)/8=21/8
四、考试复习提纲
第一章 概论 数据结构的基本概念与术语（逻辑结构、存储结构、运 算集合） 算法和算法分析（算法的基本特征、算法的空间复杂度 和时间复杂度） 第二章线性表及其顺序存储 顺序表的实现（插入和删除） 栈和队列的基本特征及操作 循环队列特点（队空、队满等）
复习课
• 期末考试题型及分数分布
• 程序填空题
• 重点习题讲解
• 考试复习提纲
• 考试注意事项
一、期末考试题型及分数分布：
填空题（20分， 每空2分） 选择题（10题 ，每题2分 ，共20分） 程序填空题（2题，每空2.5分，共20分） 论述分析题（3题，共40分） 考试时间：第10周
二、程序填空题
第三章 线性表及其链式存储 链式存储特点 单链表 及带头结点的单链表（插入、 删除） 循环单链表（结点特征）
第六章 树型结构 树的基本概念（度、深度、终端结点、路径长度等） 存储结构（双亲表示法 孩子表示法 孩子兄弟表示法） 树的遍历（前序 后序 层次） 第七章二叉树 二叉树的基本概念、性质、满二叉树、完全二叉树（ 性质）等。
二分检索（检索基本过程） 二叉排序树（二叉树满足的性质、平均查找长 度） 最佳二叉排序树和Huffman树（Huffman树 （ Huffman编码）） 冲突处理（开放定址法：线性探测再散列） 第十章内排序 排序的基本概念 插入排序（直接插入排序 二分法插入排序） 选择 排序（直接选择排序） 交换排序（冒泡排序 快速排序）
算法2.7、算法2.8 算法3.4、算法3.5、 算法3.9、 算法3.10、 算法9.2 、 算法9.3、 算法10.1、算法10.8
三、重点习题讲解
1、邻接矩阵 2、邻接表
（一）、求下图的邻接矩阵和邻接表
（二）、已知一棵二叉树如图所示，试求：
（1）该二叉树前序、中序和后序遍 历的结果； 前序：abdgecfh；中序： dgbeafhc；后序：gdebhfca （2）该二叉树是否是满二叉树？是 否是完全二叉树？ 该二叉树不是满二叉树，也不 是完全二叉树。 （3）将它转换成对应的树或森林 （4）这棵二叉树的深度为多少？ 该二叉树的深度为4
Huffman 编码 A：001 B：0000 C：10 D：01 E：0001 F：11
第一种情况
第二种情况：
Huffman 编码 A：001 B：0000 C：11 D：10 E：0001 F：01
字符的平均编码长度：
((3+5) ×4+8×3+(20+10+16) ×2)/62=2.3
（七）、设散列表长度为11，散列函数 H(x)=x % 11，给定的关键字序列为：1，13 ，12，34，38，33，27，22。试画出用线性 探测法解决冲突时所构造的散列表，并求出 在等概率的情况下，这 种方法查找成功时的 平均查找长度。
五、考试注意事项
复习资料邮箱
用户名： guet_sjjg2012@ 密码：sjjg2012