内容发布更新时间 : 2024/12/23 11:14:47星期一 下面是文章的全部内容请认真阅读。
答案:二叉树形态
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