问题 单项选择题

对于给出的一组权w={10,12,16,21,30

答案

参考答案:C

解析: 霍夫曼算法给出了求扩充二叉树的具有最小带权外部路经的方法:首先找出两个最小的wi值,不妨设为w1、w2,然后对 m-1个权(W1+W2,w3,…)来求解这个问题,并且将这个解中的结点(W1+W2)用下图来代替,如此下去,直到所有的w都成为外部结点。
[*]
对本题中的W={10、12、16、21、30},我们不妨写出其序列:
[*]
因此其扩展二叉树参见下图。
[*]
我们可以计算出扩充二叉树的具有最小带权外部路径长度为:
10*3+12*3+16*2+21*2+30*2=200
本题正确答案为选项C。

单项选择题
单项选择题