首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
admin
2013-02-02
58
问题
若以{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)。
IEEE802.5令牌环网中,时延是由(36)决定的。要保证环网的正常运行,整个环网的时延必须大于(37)。设有一个令牌环网,长度为400m,环上有28个站,数据速率为4Mbit/s,信号传播速度为200m/μs,每个站点引入1位时延,则环网的最大和最小时
B类网络理论上可以有(24)台主机。
设某条指令中的操作数(地址)部分为x,地址为X的单元内容为Y,地址为Y的单元内容为z。如果用直接寻址方式,参与操作的数据为(8);如果用立接寻址方式,参与操作的数据为(9):如果用间接寻址方式,参与操作的数据为(10)。
现有的数据处理和声音通信的信息网一般采用(57)。
CSMA/CD的访问控制方式是IEEE的(33)标准中制定的,其中的CSMA是指(34),CD是(35),当侦听到冲突时,(36)标准采用的是(33)继续侦听,发现冲突后采用的退避算法是(37)。
X.25是CCITT关于分组交换网络的通信协议,其内容包括OSI参考模型(61);分组在X.25网中的传输方式,不含(62);两个X.25公用分组网之间互连时,采用的互连协议为(63);公用分组交换网的地址(编号)根据X.121建议编制,该地址中表示国别的
假设供应商S和供应情况SPJ的关系模式分别为:S(Sno,Sname,Status,City)和SPJ(Sno,Pno,Jno,Qty)。SQL语句(22)不能正确地查询出“零件号Pno等于‘P3’的供应商名Sname",而(23).能正确查询的关系代数表
阅读以下说明、Java代码和HTML文档,将应填入(n)处的字句写在对应栏内。[说明]当用户启动html浏览器并首次打开下面的html文档时,JavaApplet小程序在第一个显示面板上显示字符串"HelloWorld";在第二个显示面板上画一
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。[函数2.1说明]函数strcpy的功能是将字符串str2的内容复制到字符申str1。[函数2.1](1)strcpy(char*slr1,constchar*st
随机试题
作图分析垄断竞争厂商长期均衡状态。
数据库系统的主要作用是_______。
母乳喂养儿肠道主要的细菌是
幽门梗阻的典型特征是
朱镕基同志在2001年视察北京国家会计学院时,为北京国家会计学院题词的内容不包括( )。
货币市场基金是我国基金市场一类重要的产品类型,以“余额宝”为代表的货币市场基金近年来迅速发展,成为投资者现金管理的良好工具。但货币基金快速发展的同时,同样面临多方面的风险,如T+0赎回方式带来的流动性风险,期限错配问题带来的投资管理风险等。2016年12月
你今天的着装.根据着装学,我们觉得你这个人比较拘谨,你怎么解释?(2012年6月29日湖南省法检系统公务员面试真题)
下列关于编译系统对某高级语言进行翻译的叙述中,错误的是(10)。
重载的关系运算符和逻辑运算符的返回类型应当是_______。
Whatistherestaurantfamousfor?
最新回复
(
0
)