首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
admin
2013-02-02
60
问题
若以{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
程序员上午基础知识考试
软考初级
相关试题推荐
中继器对应ISO/OSI开放系统参考模型的物理层,它不转换或过滤数据包,因而要求连接的两个网络(26)。
局域网中应用最广泛的差错控制方法是(47)校验。在CRC校验中,假设采用的生成多项式为4阶多项式,它产生的校验码为(48)位。在接收端,若发现错误,则将采取(49)措施。
Windows系列操作系统在配置网络时应该遵循的基本顺序为(55)。
关于WindowsNT中域和工作组的描述,下面表述(39)是正确的。
计算机中存放当前指令地址的寄存器称为(11),在顺序执行程序时,当指令长度为32位,存储器按字节编址,每执行一条指令该寄存器自动加(12)。在数据传输过程中经常增加一位来检验传送的正确性,该位称为(13)位。
操作系统具有进程管理、存储管理、文件管理和设备管理的功能,在以下有关的描述中,(15)是错误的。
在层次网络体系结构中,第N层协议利用(28)提供的服务向(29)提供服务,称(29)是N服务的(30),(30)是利用(31)通过(32)调用N层协议的服务的。
以下关于VLAN配置的描述中,正确的是(55)________________。①通过创建VLAN,会同时进入VLAN视图②通过umdoVLAN,VLAN会处于停用状态③可以对VLAN配置描述字符串,字符串长度不限④通过displayVLAN命
阅读以下说明、Java代码和HTML文档,将应填入(n)处的字句写在答题纸的对应栏内。【说明】当用户启动html浏览器并首次打开下面的HTML文档时,JavaApplet小程序在显示面板上显示字符串“Welcome!”;当html页面被其他窗口
随机试题
压力变送器是根据力平衡原理来测量的。
寒、热、痰、湿、瘀、郁,犯及冲任导致冲任阻滞,治宜疏通冲任,代表方有
对重度休克病人纠正代谢性酸中毒时,下列哪项不宜使用:
钢筋混凝土水处理构筑物的浇筑层高度一般为振捣器作用部分长度的1.25倍,最大不超过()mm。
“备案号”栏应填:“原产国”栏应填:
费率是指利率以外的银行提供信贷服务的价格,一般以信贷产品金额为基数,按一定比率计算。()(2010年上半年)
法是一种社会规范,同道德规范、职业规范相比,具有以下特点()。
班主任对一个班集体的发展起()。
下列VisualBasic变量名中,正确的是()。
描述计算机内存容量的参数,正确的是()。
最新回复
(
0
)