发布时间 : 星期一 文章数据结构课后答案 - 北邮更新完毕开始阅读
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