Problem B: 哈夫曼树练习题

 哈夫曼树练习题

1. 现有4个权值：2、3、5、6。请写出哈夫曼树的合并顺序，画出这棵哈夫曼树，并写出最终的根结点数值。

答：合并顺序：_______________________________________           画树:

根结点数值：__________

2. 小红有3个礼物盒，重量分别是1kg、2kg、3kg。每次只能把2个盒子打包成1个大包裹（新包裹重量=两个旧包裹重量之和）。按照最省力的哈夫曼规则：

① 一共需要打包几次？  ② 最后一次打包的重量是多少？

答：① __________   ② __________

3.  观察下方的小树：

① 这棵树是由哪几个初始权值构成的？② 它是不是哈夫曼树？（填“是”或“否”）

答：① __________   ② __________

4. 给定权值集合{4 2 5 7}：

① 画出对应的哈夫曼树；                （画图区）

② 计算该树的带权路径长度（WPL）。

答：WPL = __________

5. 小明投篮得分的频率（权值）如下表，请构造哈夫曼树并计算WPL：

答：WPL = __________

6. 快递点要运送5种包裹，重量分别为1kg、3kg、5kg、7kg、9kg。每次只能两两合并包裹，运输费用=每次合并后的包裹总重量。请设计最省钱的合并方案，算出最低总费用。

答：合并步骤：________________________________________________

      最低总费用：__________

7. 已知字符 A B C D 的频率（权值）分别为 {5 9 12 13}。请推断字符 A 的哈夫曼编码长度是多少？

答：A 的哈夫曼编码长度是: __________

8. 某段电文只包含字符 X Y Z，它们的哈夫曼编码分别为 0、10、11。请问这三个字符中，出现频率最高的是哪一个？

答：出现频率最高的是: __________