首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
admin
2013-02-02
44
问题
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
选项
A、55
B、68
C、59
D、28
答案
C
解析
本题考查带权哈夫曼树的构造及求带权路径长度。树的路径长度是从树根到树中每一结点的路径长度之和,结点到树根之间的路径长度与该结点上权的乘积,称为结点的带权路径长度。树中所有叶结点的带权路径长度之和,称为树的带权路径长度。在权为w1,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,…, wn,则哈夫曼树的构造规则为:(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点);(2)在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3)从森林中删除选取的两棵树,并将新树加入森林。重复第(2)步和第(3)步,直到森林中只剩一棵树为止,该树即为所求的哈夫曼树。根据哈夫曼树的构造规则,不难得到题目中给出叶子结点对应的哈夫曼树,得到哈夫曼树后我们再计算带权路径长度=3×(3+4)+2×(5+6+8)=59。
转载请注明原文地址:https://kaotiyun.com/show/nGVZ777K
本试题收录于:
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
ATM提供一种和应用独立的服务,主要表现在(41)。
ISO的常务领导机构是理事会,下设政策指定委员会。政策指定委员会管理4个专门委员会。负责研究协调各国和地区产品质量的合格认证的是(61),负责维护消费者利益的是(62),负责研究发展中国家对标准化要求的是(63),负责研究标准化情报交流方法与措施的是(64
在ISDN系统结构中,用于家庭的配置,在符合ISDN标准的用户设备和ISDN交换系统之间(52)。
FTP命令集因系统、版本而异,常用的命令如下。(54)有ASCII和二进制模式。(55)改变计算机的当前目录。(56)open建立同远程计算机的连接,close关闭连接。(57)put传送一个文件到远程计算机,put传送多个文件到远程计算机。(58)get
FTP命令集因系统、版本而异,常用的命令如下。(54)有ASCII和二进制模式。(55)改变计算机的当前目录。(56)open建立同远程计算机的连接,close关闭连接。(57)put传送一个文件到远程计算机,put传送多个文件到远程计算机。(58)get
下面是一些Internet上常见的文件类型,(49)文件类型一般代表WWW页面文件。
X.25是CCITT关于分组交换网络的通信协议,其内容包括OSI参考模型(61);分组在X.25网中的传输方式,不含(62);两个X.25公用分组网之间互连时,采用的互连协议为(63);公用分组交换网的地址(编号)根据X.121建议编制,该地址中表示国别的
某操作系统中,有以下四个作业:在单道方式下,采用短作业优先算法时作业调度的顺序是(20),一种综合兼顾短作业和长作业的作业调度算法是(21)。
数字通信的主要特点是(19),模拟信号数字化最基本的方法有三个过程,其正确的顺序是(20)。
阅读以下程序说明和C程序,将应填入(n)处的子句,写在对应栏内。【程序说明】函数intcommstr(char*str1,char*str2,int*sublen)从两已知字符串str1和str2中,找出它们的所有最长的公共子串。如
随机试题
In______,CanadawasformallydeclaredtobepartnernationswithBritainandbecameamemberoftheCommonwealthofNations.(
男,6岁。浮肿、尿色红2天入院。查体:颜面眼睑浮肿,心肺听诊无异常,尿常规有红细胞(+++),蛋白(+),半月前患过扁桃体炎。若患儿在病程中出现精神萎靡,水肿加重,尿量减少,氮质血症,血钾增高和代谢性酸中毒,BP120/80mmHg。应首先考虑发生
关于注册咨询工程师(投资)的权利,下列说法正确的是()。
下列关于企业的股份支付,表述正确的有()。
甲公司适用的所得税税率为25%。甲公司2×18年发生的与或有事项相关的交易如下:(1)3月1日,向其特定客户销售A产品50万件,总价款为1500万元,产品成本为1150万元。甲公司对该产品实行三包政策,18个月内如发现质量问题,可以向公司提出书面申请要
教师在检索和使用各种教学资源时,需要特别注意版权保护的问题。下列关于知识版权问题的描述,正确的是()。
下面属于以语言为主的教学方法有()。
某省报警电话达到11万个。其中有一些是打错了,不属于警察的服务范围。有一些是故意错打,恶意骚扰电话。求助类服务电话和交通报警明显增多,请谈谈你的看法。
某医药为降低对患者的误诊率,花巨资买了一批操作简单、精确度高的先进的辅助诊断设备,使用一年后,统计发现对患者的误诊率不但没有下降,反而有上升的趋势。以下哪项最能解释上述看来矛盾的断定?
Sportingactivitiesareessentiallymodifiedformsofhuntingbehavior.Viewedbiologically,themodernfoot-ballerisinrealit
最新回复
(
0
)