答案：二叉树形态
ABCEDFGH
2.
如图请给出邻接表、邻接矩阵及逆邻接表。
V1 V3
参考答案如下：
V2 V4
（1）邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next
（2）逆邻接表：
（3）
6
3.
由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。
答案：原来的电文为：eatst
4.
请画出下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历。
1 2 3 4 6 8
答案：
5 7
1 2 3 4 6
先序遍历为：12345687 中序遍历为：34867521
5 8 7 7
5. 设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。
答案：
使用散列函数 H(key) = key mod 13，有
利用线性探查法造表： 0 78 (1)
1
2 15 (1)
3 03 (1)
4
5 57 (1)
6 45 (1)
7 20 (1)
8 31 (4)
9
10 23 (1)
11 36 (2)
12 12 (1)
H(12) = 12, H(20) = 7, H(15) = 2,
H(23) = 10,
H(45) = 6,
H(57) = 5,
H(03) = 3, H(36) = 10.
H(78) = 0, H(31) = 5,
搜索成功的平均搜索长度为
ASLsucc =
1(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14 1010 6.
已知带权图G如图所示，画出图G的一棵最小生成树。
答：
7.
假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，请为这8个字母设计哈夫曼编码。
8
哈夫曼编码为：a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000 注意：答案不唯一
8.
试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。
301218743125116
WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
9.
画出与如图所示森林对应的二叉树。
答：
9
10. 已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12
其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+i*h1(key))%m 其中： h1(key)=key+1 回答下列问题：
（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ （2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 答：
（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１； （２）平均查找长度ASL?i=0,1,?，m-1
3?2?1?1?29?55
11.
请画出与下列二叉树对应的森林。
答： 12.
对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}，
（1）试构造一棵二叉排序树；
（2）求等概率情况下的平均查找长度ASL。 答：
10