参考答案
一、选择题 1. C 2. D 3. B 4. C 5. A
二、填空题 1. 如图
2. 352 232 3. n2+1 4. 2k-1 2k-1 5. 99 6. n-1 7. T -> lchild, key, T, p T -> rchild, key , T, p 三、简答题 1.
EBACDGFHIKJ
2. 1）根据邻接表给出的有向图如下：
V1 V2 V5V4 V3
2）从顶点V1出发，按照深度优先遍历算法给出的顶点序列为：V1, V3, V4, V5, V2
3. 生成树如下：
v1
1 v2
5 v3 v4
3 v5
4 v6
2
生成步骤如下列图a-e所示：
v1
v1
v1
v3
v3
v4
v6
v3
v6
图a 图b 图c
v1
v1
v2
v3 v4
v2
v3 v4
v5
v6
v6
图d 图e
4. 1）其赫夫曼树如下图所示：
35
19 10 16 92 57 28 15 29 14 9 4 6 7 8 2）各个字符的赫夫曼编码为：
A（6）：0011， B（14）：111， C（4）：0010， D（7）：1100 E（9）：000， F（16）：01， G（28）：10， H（8）：1101
3）带权路径长度为：
WPL=4*（4+6+7+8）+3*（9+14）+2*（16+28）=257 5.
顶点(事件) V1 V2 V3 V4 V5 V6 V7 V8 V9 ve 0 6 4 5 7 7 16 14 18 vl 0 6 6 8 7 10 16 14 18 活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e 0 0 0 6 4 5 7 7 7 16 14 l 0 2 3 6 6 8 7 7 10 16 14 l-e 0 2 3 0 2 3 0 0 3 0 0
关键活动为：a1，a4，a7，a8，a10，a11。
关键路径有两条：（V1,V2,V5,V7,V9）和(V1,V2,V5,V8,V9)
6. 依题意，得：
H（87）=87 ％ 13=9
H（25）=25 ％ 13=12 H(310) =310％13=11 H（08）=08 ％ 13=8 H（27）=27 ％13=1 H（132）=132=2 H（68）= 68 ％13= 3 H（95）=95 ％13=4 H（187）=187 ％13=5 H（123）=123 ％13=6 H（70）=70 ％13=5 H（63）=63 ％13=11 H（47）=47 ％13=8
采用链地址法处理冲突，所得链接表如右上图所示。 成功查找的平均查找长度：ASL=(1*10+2*3)/13=16/13 7.（1）
先序遍历森林序列为：EIJGBKACFD
（2）
1 2 3 4 6 8 5 7 8 2 对应二叉树
3 4 6 1 5
7