首页
登录
从业资格
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
练习题库
2022-08-02
100
问题
由权值为 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的主键为()。
随机试题
[originaltext]Expertsinthefoodindustryarethinkingalotabouttrasht
[originaltext]W:Ihaveplentyofgoodideas,ProfessorJohnson,buthaven’tbe
人际关系的形成与变化,取决于交往双方()A.修养和处世方法 B.身份和地位
下列关于防烟分区划分的说法中,错误的是()。A.防烟分区可采用防火隔墙划分
下列关于靶向制剂的概念正确的描述是A.靶向制剂是指进入体内的载药微粒被巨噬细胞摄
在委托指令中,不管是采用填写委托单还是自助委托方式,都需要反映客户买卖证券的基本
某商业银行为增值税一般纳税人,2019年第二季度经营情况如下: (1)提供
送风温度低于室温,出风速度较低,送风气流与室内气流掺混量最小,且能够保存分层流态
最先提出“不伤害原则”的西方医学家是( )。A.希波克拉底 B.盖伦 C.
女性,18岁,因反复低热,伴皮肤出血点2周入院,体查:轻度贫血貌,全身皮肤散在出
最新回复
(
0
)