《数据结构》期末复习题 答案

答案:二叉树形态

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)该散列表在等概率查找时查找成功的平均查找长度为多少? 答:

(1)对关键字35、20、33和48进行查找的比较次数为3、2、1、1; (2)平均查找长度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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4