数据结构课后答案 - 北邮

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