2. 从业资格
  3. 由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为（请作答此空），其带

由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为（请作答此空），其带

练习题库2022-08-02  58
问题 由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为（请作答此空），其带权路径长度为（ ）。
选项
答案 A
解析 本题考察最优二叉树（哈夫曼树）的构造和带权路径长度的计算。构造最优二叉树的哈夫曼算法如下：（1）、根据给定的n个权值{w1, w2, …，wn}， 构成n棵二叉树的集合F= {T1, T2, …Tn}，其中，每棵树Ti中只有一个带权为wi的根结点，其左、右子树均空。（2）、在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。（3）、从F中删除这两棵树，同时将新得到的二叉树加入到F中。（4）、重复（2）、（3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树(哈夫曼树)。所以由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为（红色圈内填写的数字为构造的新节点，在选项中没有体现出来，用空白圆圈进行了替代）：结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积，而树的带权路径长度为树中所有叶子结点的带权路径长度之和。所以构造的哈夫曼树的带权路径长度为9*1+6*2+4*3+（1+2）*4=9+12+12+12=45。
转载请注明原文地址:https://tihaiku.com/congyezige/2416838.html
本试题收录于： 中级 软件评测师题库软件水平考试初中高级分类

中级 软件评测师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)