填空题
对于给出的一组权w={5，6，8，12}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为{{U}} 【4】 {{/U}}。
- 1、
【正确答案】
1、61
【答案解析】
[解析] 霍夫曼算法给出了求扩充二叉树的具有最小带权外部路径的方法：首先找出两个最小的wi值，不妨设为w1、w2，然后对m-1个权(w1+w2，w3，…)来求解这个问题，并且将这个解中的结点(w1+w2)用图1所示来代替，如此下去，直到所有的w都成为外
部结点。对本题的w={5，6，8，12}，我们不妨写出其序列：
{{U}}5{{/U}} {{U}}6{{/U}} 8 12
{{U}}8{{/U}} 12 {{U}}11{{/U}}
{{U}}12{{/U}} {{U}}19{{/U}}
31
因此其扩展二叉树参见图2。
[解析] 霍夫曼算法给出了求扩充二叉树的具有最小带权外部路径的方法：首先找出两个最小的wi值，不妨设为w1、w2，然后对m-1个权(w1+w2，w3，…)来求解这个问题，并且将这个解中的结点(w1+w2)用图1所示来代替，如此下去，直到所有的w都成为外
部结点。对本题的w={5，6，8，12}，我们不妨写出其序列：
{{U}}5{{/U}} {{U}}6{{/U}} 8 12
{{U}}8{{/U}} 12 {{U}}11{{/U}}
{{U}}12{{/U}} {{U}}19{{/U}}
31
因此其扩展二叉树参见图2。