聊城大学计算机学院数据结构A答案.docVIP

聊城大学计算机学院08—09学年第1学期期末考试2007级 《数据结构》试题（闭卷A）参考答案和评分标准 四、操作题（共2题，每题10分，共20分） 选择一种算法找出下面网络的最小生成树，要求给出构造过程。 解：用Prim算法生成最小生成树的过程为： 评分标准：可以用表的方式给出算法运行过程；生成过程不唯一，如可以选择其它初始点；只给出最终最小生成树，没有算法过程得6分；一个小步骤有错减1分。 或者用Kruskal算法生成最小生成树过程为： 6 6 评分标准：生成过程不唯一，但必须从V={A,B,C,D,E,F,G},E={}开始；只给出最终最小生成树，没有算法过程得6分；一个小步骤有错减1分。 假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。要求画出所构造的哈夫曼树，计算树的带权路径长度，分别写出每个字符对应的编码。 （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和编码只要按照规则即可得步骤分。 2 A E 6 4 D E 4 A 5 B 6 4 D 5 B 6 E A 4 D E A G 6 6 G 5 B 6 4 D E A C 5 F 7 5 （1）2分 C 6 G 5 B 6 4 D E A （2） （3） （4） （5）2分 （6）6分 （1）2分 F 4 C F G （2） B C G D E A 4 F （3） 5 C G B B D E 4 A F D E A （4） 5 C G B D E A 5 5 4 F （5） 5 C G B D E A 6 6 5 4 F （6）2分 5 C G B D E A 6 6 6 5 4 F （6）6分 5 C G B D E A 7 100 59 41 34 25 12 13 8 5 23 18