首页
登录
从业资格
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
练习题库
2022-08-02
65
问题
由权值为 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的主键为()。
随机试题
Whenyouopenyourelectronicmail,youmayfindinformationabouthowtobu
Ascientistwhodoesresearchineconomicpsychologyandwhowantstopredic
Streetsellers,particularlyindevelopingcountries,【C1】______largeamounts
OnFoodSafety,aLongListbutLittleMoneyA)Thissummer
慢性支气管炎最常见的并发症是A.支气管扩张症 B.肺脓肿 C.肺源性心脏病
女性,49岁,月经增多,周期缩短,经期延长,子宫正常大小,双附件(-)。服用甲基
患者男,28岁,主诉4d未解大便,伴头痛、腹痛、腹胀、乏力,触诊腹部较紧张,肛诊
股份公司股东可以查阅的是( )A.股东大会会议记录 B.董事会会议记录 C
钱先生2015年11月8日存入10000元,定期整存整取半年,假定年利率为2.7
甲公司委托证券公司发行股票2000万股,每股面值1元,每股发行价格是3元,支付手
最新回复
(
0
)