内容发布更新时间 : 2024/5/12 13:52:03星期一 下面是文章的全部内容请认真阅读。

答案：二叉树形态

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