（ 4 ）霍夫曼算法是求具有最 【 4 】 带权外部路径长度的扩充二叉树的算法。

正确答案：112
112 解析：首先选出7和11构造为内部结点，权值为18，再与18构造一个内部结点36，最后与22构造根结点58。带权外部路径长度为(7+11)*3+18*2+22=112。

正确答案：小
小 解析：霍夫曼算法是用来求具有最小带权外部路径长度的扩充二叉树的算法。

正确答案：61
（5+6）*3+8*2+12=61.

正确答案：61
61 解析：霍夫曼算法给出了求扩充二叉树的具有最小带权外部路经的方法：首先找出两个最小的wi值，不妨设为w1、w2，然后对m-1个权(w1+w2，w3，…)来求解这个问题，并且将这个解中的结点(w1+w2)用下图来代替，如此下去，直到所有的w都成为外部结点。

对本题中的W={5，6，8，12}，我们不妨写出其序列：

因此其扩展二叉树参见下图。

因此我们可以计算出扩充二叉树的具有最小带权外部路长度12*1+8*2+5*3+6*3=61。

正确答案：80
80 解析：用霍夫曼算法求具有最小带权外部路径长度的扩充二叉树的办法是：首先找出两个最小的wi值，不妨设为w1和w2，然后对m-1个权w1+w2，w3，…，wm来求解这个问题，并且将这个解中的结点用权值代替，如此进行下去，直到所有的w都成为外部结点的权。根据条件构造哈夫曼树如下：树的带权路径长度为WPL=7×2+8×2+4×3+2×4+3×4+9×2=80。