6. 已知一个森林如图所示：
(1) 分别写出该森林的先序和中序遍历序列 (2) 将该森林转换为一棵二叉树
AH B C D I E F G J L K
7. 设用于通信的电文由8个字母A—H组成。字母在电文中出现的频率分别为0.06, 0.20,
0.01, 0.07, 0.33, 0.02, 0.22, 0.09。试构造相应的哈夫曼树，为这8个字母设计哈夫曼编码。，求平均的码长WPL值，使用0－7的二进制表示形式是另一种编码方案，试比较两种方案的优缺点。 答案
1. 设度为k的结点数为
则有K×
nk，叶子结点数为
n
0nnn＋0＝kk 解得
n0?n(k?1)?1n?1?n?
kkn=n－1
2. （b）
3. (1)先序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA
(2)先序和中序相反的二叉树为
F H D 后序和中序相反的二叉树为 G
(3)
0 1 0 A 0 0 B 1 0 C 0 1 D 0 1 E 1 0 F 1 1 G 1 1 H 1
(4)
(5)
A A B C D E F NIL G H B C D E F G H (6)
A C F
B E H D G
4. 孩子表示法；双亲表示法；孩子兄弟表示法 5. （1）先序：ABEFCDH 后序：EFBCHDA
(2) (3)双亲表示法 A -1 0 A B 0 1 C 0 0 B 2 D E 1 C 3 F 1 3 D 4 H 5 E 6 F H
孩子兄弟表示法 A ∧ B ∧ E ∧ C D ∧ ∧ F ∧ ∧ H ∧
6. (1)先序：ABCEGDGHIJKL 中序：BEFCGDAIJHLK
(2) A H B C I K D J L E G F 7.
第七章作业
1. 常用的又向图的存储结构有______,_______和_______。
常用的无向图的存储结构有______和_______。 2.
V1 V2 (1)分别画出该图的邻接矩阵，邻接表，逆邻接表和十字链表.
(2)求出ID（V5）OD（V5）TD（V2）OD（V3）ID（V3）的值。 V3(3)判断其是否为一强连通图？
V4 V5
V6 3. V1 （1）分别对该图进行深度优先搜索＆广度优 先搜索，并写出遍历序列。
V2 V3 （2）分别画出其深度优先生成树＆广度优先 生成树。
V4V8 V7
V5 V6 V9
4. 从A,G,J分别画出该图的深度优先生成森林及广度优先生成森林。
A J B
G C
E
G I K D
F 5.已知一图的邻接表分别画出从A出发该图的深度优先生成树和广度优先生成树。
A 3 1 ∧
4 2 0 ∧ B
4 1 ∧ 3
C
0 ∧ 2
D
1 ∧ 2
