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

Question

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

A．89

B．189

C．200

D．300

Answer 1

正确答案：C
解析：根据条件构造哈夫曼树如下：

树的带权路径长度为WPL=10×3+12×3+16×2+21×2+30×2=200。