首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
admin
2019-08-10
22
问题
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
选项
A、23
B、37
C、44
D、46
答案
C
解析
由权值为9、2、5、7的四个叶子构造的哈夫曼树可如图2—5所示。
(1)该树的带权路径长度=9×1+7×2+2×3+5×3=44。中非叶子结点的总数为n-1,总结点个数为2n-1。
(2)哈夫曼树中没有度为1的结点,因为非叶予结点都是通过两个结点合并而来。但是,没有度为1的二叉树并不一定是哈夫曼树。
(3)用n个权值(对应n个叶子结点)构造的哈夫曼树,形态并不是唯一的。
建立哈夫曼树的过程中有以下三种常见的错误:
(1)在合并中不是选取根结点权值最小的两棵二叉树(包括已合并的和未合并的),而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并。
(2)每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。
(3)有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树,但那只是巧合,没有规律性,而没有规律性的解法不利于用计算机进行处理。
转载请注明原文地址:https://kaotiyun.com/show/syCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
建国以来,根据我国民族状况自身特点,民族自治地方人民代表大会依据全国人民代表大会制定的有关法律,先后制定了若干自治条例和单行条例;全国依法建立了155个民族自治地方,少数民族当家作主的权利得到充分保障。同时,国家采取一系列措施,加大支持力度,促进了民族自治
【第三次浪潮】苏州大学2015年世界史专业基础综合真题
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
虚拟存储器技术是基于程序的()特性。
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
假设计算机系统采用CSCAN(循环扫描)磁盘调度策略,使用2KB的内存空间记录16384个磁盘块的空闲状态。如果将磁盘替换为随机访问的Flash半导体存储器(如u盘、SSD等),是否有比CSCAN更高效的磁盘调度策略?若有,给出磁盘调度策略的名称并说明
随机试题
把邓小平理论确定为中国共产党指导思想并写入党章的会议是( )
真核生物的启动子结构是
设备基础验收时,提供的移交资料包括()。
铁路工程施工工期控制方法有()。
企业期末“本年利润”的借方余额为7万元,“利润分配”和“应付股利”账户贷方余额分别为18万元和12万元,则当期资产负债表中“未分配利润”项目金额应为()万元。
地区发展模式比较符合中国的文化传统,因此,这一模式可以有效地解决社区中的所有问题。()
下列行业属于特种行业的有()以及出租车。
Scrapsoffoodcouldsoonbehelpingpoweryourhome,thankstoanultra-cheapbacteria-drivenbattery.Itsdevelopershopethat
若有以下程序段:structst{intn;int*m;};inta=2,b=3,c=5;stmctsts[3]=({101,&a},{102,&c},{103,&b}};main(
Iliketohaveyoubecomingwellgroundedintheliteratureandphilosophyofothercenturiesandofothercountries______ourow
最新回复
(
0
)