首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
admin
2019-05-10
41
问题
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
选项
A、23
B、37
C、44
D、46
答案
C
解析
由权值为9、2、5、7的四个叶子构造的哈夫曼树可如下图所示。
该树的带权路径长度=9×1+7×2+2×3+5×3=44。
[归纳总结]对哈夫曼树特征的总结:
(1)用n个权值(对应n个叶子结点)构造哈夫曼树,共需要n-1次合并,即哈夫曼树中非叶子结点的总数为n-1,总结点个数为2n-1。
(2)哈夫曼树中没有度为1的结点,因为非叶子结点都是通过两个结点合并而来。但是,没有度为1的二叉树并不一定是哈夫曼树。
(3)用n个权值(对应n个叶子结点)构造的哈夫曼树,形态并不是唯一的。
建立哈夫曼树的过程中有以下三种常见的错误:
(1)在合并中不是选取根结点权值最小的两棵二叉树(包括已合并的和未合并的),而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并。
(2)每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。
(3)有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树,但那只是巧合,没有规律性,而没有规律性的解法不利于用计算机进行处理。
转载请注明原文地址:https://www.kaotiyun.com/show/L2Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第三次科技革命对社会经济结构的影响是()。
材料一材科二(戈尔巴乔夫政府)在制定改革政策方针中存在三个严重问题:第一,仍然以优先发展重工业和机器制造业为主的“加速发展战略”作为发展资本密集型产业的主要战略,已不符合时代潮流。现代经济结构已由资本密集型向技术密集型发展……苏联的经济改革对
试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。
下列关于马略军事改革的叙述,不正确的是()。
对阿拉伯半岛的统一起了促进作用的宗教是()。
到1869年为止,人类已发现了多少种化学元素()。
顽固派破坏百日维新的手段有()①对变法诏令阳奉阴违托词抗命②把京津地区的兵权都抓在手中③改总理衙门为外务部讨好列强④慈禧太后直接控制人事任免权
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
设有一个带头结点的循环单链表,其结点值均为正整数。试设计一个算法,反复找出单链表中结点值最小的结点,并输出之,然后将该结点从中删除,直到单链表空为止,最后再删除表头结点。
四位运算器框图如下图所示,ALU为算术逻辑单元,A和B为三选一多路开关,预先已通过多路开关A的SW门向寄存器R1,R2送入数据如下:R1=0101,R2=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下:(1)R1
随机试题
下列涎腺疾病中有自愈倾向的是
新生儿的呼吸频率是()。
在房地产贷款的主要参与者中,为客户代办房地产贷款、房地产抵押登记等手续的机构一般是()。
在古希腊建筑中,柱式象征人体的比例,()希腊柱式分别仿男性和女性的人体比例。
如果组合中包括了全部股票,则投资人()。
浣花溪记钟惺出成都南门,左为万里桥。西折纤秀长曲,所见如连环、如玦,如带,如规,如钩;色如鉴、如琅圩,如绿沉瓜,窈然深碧,潆回城下者,皆浣花溪委也。然必至草堂,而后浣花有专名,则以少陵浣花居
【2015年吉林辽源.判断】“拔苗助长”违背了循序渐进原则。()
治安管理处罚中,处罚是目的,教育是手段。()
“法之必行”的真正动力来自哪里?有人说靠监督,有人说靠激励,也有人寄希望于惩戒。这些都不无道理,但还有一点往往被人忽视,那就是法治精神的作用。常见媒体有这样的报道,一些考试尽管监考人员众多,监考规则严格,技术手段先进,却依然难以杜绝各种作弊行为。所谓“破山
执行以下程序段后,输出结果不为2的是
最新回复
(
0
)