问题 单项选择题


对于给出的一组权w={10,12,16,21,30},通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为

A.89

B.189

C.200

D.300

答案

参考答案: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。

单项选择题
单项选择题