首页
登录
从业资格
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
练习题库
2022-08-02
72
问题
由权值为 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的主键为()。
随机试题
Withthepossibleexceptionofequalrights,perhapsthemost【C1】______issu
Itisdesirablethatyou_____somefamiliaritywithcomputers.A、shouldhaveB、h
粪链球菌引起的尿路感染,有临床诊断意义的最低菌落计数为()。A.清洁中段尿培养
1岁3个月小儿,多汗,烦躁,前囟门未闭,方颅,鸡胸,"()"形腿,血钙低,血
患者,女,36岁,已婚。近3个月来,月经提前6~7天,量少、色红,每于经期鼻衄,
补体替代途径的激活物是A:C反应蛋白B:内毒素C:抗原抗体复合物D:MBL
某厂有五种产品:甲、乙、丙、丁、戊。它们的年销售额之间的关系为:丙没有丁高,甲没
磺胺类药物的抑菌机制是( )。A.不可逆性抑制 B.竞争性抑制 C.非竞争
(2021年真题)有限合伙人参与选择会计所,视为执行事务()。
按成本组成,施工成本分解为( )。A.企业管理费 B.材料费 C.暂估价
最新回复
(
0
)