计算机科学与技术(本科)
若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。
题目
若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。
相似问题和答案
第1题：
带权为9，2，4，6的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为______。
A．21
B．41
C．36
D．39
解析：本题考查哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的长度与该结点权的乘积。哈夫曼是指含有n个权值分别为w1，w2，…，wn的n个叶子结点的二叉树中带权路径长度最小的那棵树。所以应该将权重最大的叶子结点距离根结点最近，权重次小的距离根结点次远，依次类推。所以WPL=9+6*2+(2+4)*3=39。
第2题：
由值为29、12、15、6、23的五个叶子结点构造的哈夫曼树为(64)，其带权路径长度为(65)。
A．
B．
C．
D．
第3题：
第4题：
下列关于哈夫曼树的叙述错误的是
A．一棵哈夫曼树是带权路径长度最短的二叉树
B．一棵哈夫曼树中叶结点的个数比非叶结点的个数大1
C．一棵哈夫曼树结点的度要么是0，要么是2
D．哈夫曼树的根结点的权值等于各个叶子结点的权值之和
解析：哈夫曼树中结点的度可以是0，1，2。
第5题：
以下关于哈夫曼树的叙述，正确的是（60）。
A.哈夫曼树一定是满二叉树，其每层结点数都达到最大值
B.哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为-1、0或1
C.哈夫曼树中左孩子结点的权值小于父节点、右孩子节点的权值大于父节点
D.哈夫曼树中叶子节点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。所以D选项的说法正确。
第6题：
A.16
B.30
C.12
D.18
第7题：
● 由权值为 29、12、15、6、23 的五个叶子结点构造的哈夫曼树为（64)，其带权路径长度为 （65） 。
第8题：
由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为(50)。
A．23
B．37
C．44
D．46
解析：根据哈夫曼算法，由权值为9，2，5，7的四个叶子结点构造的一棵哈夫曼树如下图所示。
第9题：
若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是(33)。
A．55
B．68
C．59
D．28
解析：本题考查带权哈夫曼树的构造及求带权路径长度。树的路径长度是从树根到树中每一结点的路径长度之和，结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度。树中所有叶结点的带权路径长度之和，称为树的带权路径长度。在权为w1，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1，w2，…，wn，则哈夫曼树的构造规则为：(1)将w1，w2，…，wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林。重复第(2)步和第(3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。根据哈夫曼树的构造规则，不难得到题目中给出叶子结点对应的哈夫曼树，得到哈夫曼树后我们再计算带权路径长度=3×(3+4)+2×(5+6+8)=59。
第10题：
B.在哈夫曼树中，权值较大的叶子结点一般离根结点较远
C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近
D.在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理