数据结构课后答案 - 北邮 下载本文

abcdefgh

7.请将图5-42所示树T转换为二叉树T′。

KAEI答案:

BFCGJDH

KABEIJFGH

8. 对于图5-43所示的二叉树,该树的三种遍历分别是什么?

CD-+abc答案:

/*-d

ef前序 -+a*b-cd/ef

中序 a+b*c-d-e/f 后序 abcd-*+ef/-

9. 对于图5-44所示的二叉树,请画出和其对应的森林。

ABCDEFGHIJKM

答案:

ABDHKECFIGJM

10. 假设用于通信的电文仅由9个字符组成,并且出现概率为0.07(A)、0.19(B)、0.02(C)、0.06(D)、0.32(E)、0.03(F)、0.21(G)、0.10(H): (1)画出哈夫曼树; 答案:

10.600.400.28EBG0.110.170.05DAHCF

(2)每个字符的哈夫曼编码; 答案: A 0010 B 10 C 00000 D 0001 E 01 F 00001 G 11 H 0011

(3)计算其带权路径长度;

答案:WPL=0.07*4+0.19*2+0.02*5+0.06*4+0.32*2+0.03*5+0.21*2+0.10*4=2.61

(4)如果电文是“ABCDEFGH”压缩前每个字符使用8bit的ASCII编码,则采用上面的哈夫曼编码,其压缩比是多少? 答案:??4?2?5?4?2?5?2?48?8?0.4375