聊城大学计算机学院08—09学年第1学期期末考试2007级 《数据结构》试题（闭卷A）参考答案和评分标准 四、操作题（共2题，每题10分，共20分）

1. 选择一种算法找出下面网络的最小生成树，要求给出构造过程。 解：用Prim算法生成最小生成树的过程为：

4 A E A 4 E 6 A B 6 D 4 E D （1）2分 4 A （2） 5 4 A （3）

E E 6 6 B B 6 D G 6 D C 5 G 5 5 （4） 4 A E （5）2

6 G B 6 D C 5 5 F 7 （6）6

评分标准：可以用表的方式给出算法运行过程；生成过程不唯一，如可以选择其它初始点；只给出最终最小生成树，没有算法过程得6分；一个小步骤有错减1分。 或者用Kruskal算法生成最小生成树过程为：

A E B C G D F （1）2

6

4 A E B C G D F 4 A E B C 5 G D F 4 A E B C 5 G 5 D F 4 A E B 6 C 5 G 5 D F 2）3）4）5）（

（

（

（

6

4 A E 6 G B 6 C 5 5 D F （6）2

4 A E 6 G B 6 C 5 7 5 D F （6）6

评分标准：生成过程不唯一，但必须从V={A,B,C,D,E,F,G},E={}开始；只给出最终最小生成树，没有算法过程得6分；一个小步骤有错减1分。

2. 假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：34，5，12，23，8，

18，试为这6个字符设计哈夫曼编码。要求画出所构造的哈夫曼树，计算树的带权路径长度，分别写出每个字符对应的编码。

1059 41 25 34 18 23 13 12 5 8 （4分）

WPL=5×4＋8×4＋12×3＋34×2＋18×2＋23×2＝238 （3分） 字符集的哈夫曼编码分别为：01，0000，001，11，0001，10。 （3分）

评分标准：哈夫曼树的形态有很多，但是WPL是固定的值，编码规则必须为左0右1.如果树错误，WPL和编