首页
登录
从业资格
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
练习题库
2022-08-02
46
问题
由权值为 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.30,0.25,0.25,0.12,0.08}构造的哈夫曼树中
对下图所示的二叉树进行中序遍历(左子树,根结点,右子树)的结果是( )。 A
在面向对象的系统中,对象是运行时的基本实体,对象之间通过传递(请作答此空)进行通
如图所示的UML类图中,Shop和Magazine之间为(请作答此空)关系,Ma
DHCP协议的功能是();FTP使用的传输层协议为(请作答此空)。A.TC
DHCP协议的功能是(请作答此空);FTP使用的传输层协议为()。A.WI
从下列名词中区分类和对象。其中,(请作答此空)全部是类,()全部是对象。A.课
从下列名词中区分类和对象。其中,()全部是类,(请作答此空)全部是对象。A.课
在一系统中,不同类对象之间的通信的一种构造称为(请作答此空),一个对象具有多种形
通过(请作答此空)关系运算,可以从表1和表2获得表3;表3的主键为()。
随机试题
Howdidthemanspendhislastweekend?[originaltext]W:Didyouhaveagoodtime
TheAmericanwarondrugshasgottenallthetypeinrecentyears,butalcoh
恩格尔系数是食品支出总额与居民人均可支配收入之比。()
如图5,该作品所属的艺术流派是()。 图5A.现代主义 B.后现代
下列关于膜剂概述叙述错误的是A:膜剂系指药物与适宜成膜材料经加工成的薄膜制剂
对高度怀疑肠结核的病例中,下列最有利于临床诊断的是A.PPD试验阳性 B.有
增资发行B股时,承销协议应在报送中国证监会前签署。()
下列薪酬形式中,适用于个人激励的有()。A.绩效奖金 B.员工持股制度
根据反垄断法律制度的规定,下列选项中,不属于纵向垄断协议的是()。A.维持转售
从生产到使用过程中无毒,无公害,无污染,无腐蚀,无残留,无需布置管道的灭火系统是
最新回复
(
0
)