问题
单项选择题
对于给出的一组权W=9、13、16、20、30，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为( )。
A．88
B．188
C．98
D．198
答案
参考答案：D
解析： 霍夫曼给出了求具有最小带权外部路径长度的扩充二叉树的方法：首先找出两个最小的W值，设为W，和W2，然后对m-1个权W1+W2，W3，W4，…，Wn来求解这个问题，如此进行下去直到所有的w都成为外部结点的权。
根据条件可以构造以下的霍夫曼树：
[*]
因此该树的带权路径长度为L=30*2+(9+13)*3+(16+20)*2=198
