数据结构与算法题库
五、综合题
1．已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ。 (1) 画出这棵二叉树;
(2) 写出该二叉树的后序遍历序列;
(3) 画出这棵二叉树的中序线索二叉树的存储结构图。
2. 已知一棵二叉树的中根遍历序列为：2，4，1，5，3，7，6，8，后根遍历序列为：4，2，5，7，8，6，3，1。 (1)画出二叉树。
(2) 写出二叉树先根遍历序列。
(3) 画出该二叉树的先序线索二叉树。
3. 假设一颗二叉树的中序遍历序列为DCBGEAHFIJK和后序遍历序列为DCEGBFHKJIA.。 1） 请画出该二叉树。
2） 请画出该二叉树的后序序线索二叉树。 3） 写出该二叉树的先序遍历序列。
4. 已知一棵二叉树的先序遍历序列为ABCDEFGHIJK，中序遍历序列为CDBGFEAHJIK。 （1）请构造二叉树；
（2）画出先序线索二叉树。
（3）分别列出度为0、1和2的结点。
5.已知某通讯电文仅由a，b，c，d，e，f，g，h八个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。为这8中字母设计哈夫曼编码。
6. 假设用于通信的电文仅由5种字母ABCDE组成，每个字母出现的概率分别为0.12, 0.40, 0.15, 0.08, 0.25。
(1) 用5个概率值为权值设计Huffman(哈夫曼)树。 (2) 计算它的带权路径长度WPL。 (3) 设计这5种字符的Huffman编码
7.按下面要求转换森林和二叉树。 （1）将图-1的二叉树转换成森林。 （2）将图-2的树转换成二叉树。
A C B E D F I H J 图-1
A K J BC D E F G H I J K 图-2 8. 画出下列二叉树相应的森林，并写出中序遍历森林的序列。
9. 已知一个无向网如下图所示，试用普里姆算法计算出该图的最小生成树，最小生成树为权值之和最小的生成树。
A 6 B 1 5 C 3 6 E 6 4 F 2 5 5 D 10. 已知一个无向图G=(V,E),V={A,B,C,D,E,F,G,H}, E = {(A,B),(A,C),(B,D),(B,E),(C,F),(C,G),(D,H),(E,H),(F,G)}; (1)画出该无向图； (2)画出该图的邻接表存储结构； (3)根据存储结构，写出深度优先搜索遍历序列和广度优先搜索遍历序列。
11. 已知一个无向图G=(V,E),V={v1,v2,v3,v4,v5,v6,v7,v8}, E = {(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7),(v4,v8),(v5,v8),(v6,v7)}; (1)画出该无向图； (2)画出该图的邻接表存储结构； (3)根据存储结构，写出深度优先搜索遍历序列和广度优先搜索遍历序列。
12.已知一个有向图如下图所示： (1)画出该图的邻接表存储结构。 (2)画出该图的逆邻接表存储结构。 (3) 写出拓扑排序序列。 (4) 写出深度优先搜索遍历序列和广度优先搜索遍历序列。 A B C D E F
13.画出如下图所示的邻接表的表示，并以顶点V1为初始源点遍历所示的有向图所得到的深度优先遍历和广度优先遍历生成森林。
14. 已知一个连通网如下图所示，试用Prime（普里姆）算法计算下图的最小生成树，起始点为A。 16 B A 5 21 19 14 9 F C
26 11 6 D E
18
15 一个无向网如下图所示，试用普里姆算法计算出该图的最小生成树，起始点为A。
16. 请利用Prime（普里姆）算法计算下图的最小生成树。 A 5 6
B 1 5 C 3 6 E 6 4 F 2 5 D
17.已知一个AOE网如下图所示： (1) 写出下图的拓扑排序顺序序列；
(2) 试计算出该图从源点A出发到达汇点F的关键路径。
a5=3 B E
a3=2 a8=1 a1=3
a7=2 D A F
a4=4
a2=2 a6=3
C
18.已知一个AOE网如下图所示： (1) 找出AOE网源点和汇点； (2) 试计算出该图的关键路径。 V7 a4=1 a7=9 V5 a10=2 V9 a8=7 V8 a11=4 V2 a1=6 V1 a2=4 V3 a3=5 V4
a5=1 a9=4 a6=2 V6 19.已知一个AOE网如下图所示，其中V1为源点，V6为汇点。 (1) 写出拓扑排序序列； (2) 计算出从源点到汇点的关键路径。 a4=10
V3 V4 a7=6 a2=2 a6=19 V1 a3=4
a1=15 a8=5 V5 V2 a5=11
V6