给定5个字符a~f,它们的权值集合W={2,3,4,7,8,9},试构造关于W的一棵哈夫曼树,求其带权路径长度WPL和各个字符的哈夫曼树编码。

第1题：

参考答案：

第2题：

第3题：

第4题：

第5题：

答案：D

解析：

第6题：

若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。
69
略

第7题：

以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。

2  0000
3  0001
4  001
7  10
8  11
9  01
略

第8题：

下面关于哈夫曼树的说法，不正确的是（）

• A、对应于一组权值构造出的哈夫曼树一般不是唯一的
• B、哈夫曼树具有最小带权路径长度
• C、哈夫曼树中没有度为1的结点
• D、哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点

第9题：

对哈夫曼树，下列说法错误的是（）。

• A、哈夫曼树是一类带树路径长度最短的树
• B、给出一组数，构造的哈夫曼树唯一
• C、给出一组数，构造的哈夫曼树的带树路径长度不变
• D、哈夫曼树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和

第10题：

设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）

• A、20
• B、30
• C、40
• D、45

第11题：

第12题：

第13题：

第14题：

正确答案：C
解析：根据哈夫曼算法，由权值为5，9，2，6的 4个叶子构造一棵哈夫曼树，如图4-9所示。

图4-9哈夫曼树的权W(T)=(2+5)×3+6×2+9×1=42。

第15题：

最优二叉树(或哈夫曼树)是指权值为w1，w2，…，wn的n个叶结点的二叉树中带权路径长度最小的二叉树。( )是哈夫曼树(叶结点中的数字为其权值)。

答案：A

解析：

本题考查数据结构基础知识。
哈夫曼树又称为最优二叉树，是一类带权路径长度最短的树。
树的带权路径长度(WPL)为树中所有叶子结点的带权路径长度之和，记为

其中n为带权叶子结点数目，wk为叶子结点的权值，lk为根到叶子结点的路径长度。
选项A所示二叉树的WPL=(2+4)*3+5*2+7*1=35
选项B所示二叉树的WPL=(2+4+5+7)*2=36
选项C所示二叉树的WPL=(5+7)*3+4*2+2*1=46
选项D所示二叉树的WPL=(4+5)*3+7*2+2*1=43

第16题：

第17题：

哈夫曼树又称为（），它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL（）。
最优二叉树；最小的二叉树
略

第18题：

对给定权值2，1，3，3，4，5构造两棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。
（1）wpl1=45

（2）wpl2=45

略

第19题：

用5个权值{3，2，4，5，1}构造的哈夫曼（Huffman）树的带权路径长度是（）

第20题：

哈夫曼树是带权路径长度（）的树，通常权值较大的结点离根（）

第21题：

设一组权值集合W=（15，3，14，2，6，9，16，17），要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）

• A、129
• B、219
• C、189
• D、229

第22题：

给定权值2，10，12，4，8，5，构造相应的哈夫曼树并求出带权路径长度WPL。

第23题：