实用数据结构基础参考答案

+ ˉ + ˉ 0 A BC D 后缀表达式：0 A – B + C – D +

（11）画出表达式：（A+B/C-D）*（E*（F+G））的标识符树，并求它们的后缀表达式。 解： * ˉ * + + E D

G F / A B C

后缀表达式：A B C / + D – E F G + * *

（12）对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。 解：

+

* *

+ E FG

A *

B / C D

后缀表达式：A B C D / * + E * F G * +

（13）给定一个权集W={4,5,7,8,6,12,18}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。

49

解：4 5 6 7 8 12 18 60

9 13 2535

12 13 17 18 17 25 9 6 7 8

35 5 4

60

WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159

（14）给定一个权集W={3,15,17,14,6,16,9,2}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。 解：

82 2 3 6 9 14 15 16 17

3349

5 29 33 16 17 29 20

11 9 11 1415

20 6 5

49

82

WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229

（15）假设用于通信的电文仅由A、B、C、D、E、F、G 8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：（左子为0，右子为1。） 1000 1

字母编号 对应编码 出现频率

A 1010 7 40 600 1 1 B 00 19 0

C 10000 2 21 19 28 32 0 D 1001 6 1

E 11 32 11 17 1 0 0 D 10001 3 1 E 01 21 5 6 7 100 F 1011 10 1 2 3

六．算法设计题

2 3 50