聊城大学计算机学院数
据结构A答案
Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT
聊城大学计算机学院08—09学年第1学期期末考试2007级
《数据结构》试题（闭卷A）参考答案和评分标准
四、操作题（共2题，每题10分，共20分）
1.选择一种算法找出下面网络的最小生成树，要求给出构造过程。
解：用Prim算法生成最小生成树的过程为：
评分标准：可以用表的方式给出算法运行过程；生成过程不唯一，如可以选择其它初始点；只给出最终最小生成树，没有算法过程得6分；一个小步骤有错减1分。 或者用Kruskal 算法生成最小生成树过程为：
（2）
（1）2分
（5）
（4）
（3）
评分标准：生成过程不唯一，但必须从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个字符设计哈夫曼编码。要求画出所构造的哈夫曼树，计算树的带权路径长度，分别写出每个字符对应的编码。
（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和编码只要按照规则即可得步骤分。