首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
admin
2013-02-02
56
问题
若以{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
程序员上午基础知识考试
软考初级
相关试题推荐
在某个学校,在办公室需要连接相同的两个局域网,可选用(39),其成本是最低的。
在文件系统中,用户数据的访问通常以(37)为单位。
下面有关FFP的描述正确的是(20)。
FTP命令集因系统、版本而异,常用的命令如下。(54)有ASCII和二进制模式。(55)改变计算机的当前目录。(56)open建立同远程计算机的连接,close关闭连接。(57)put传送一个文件到远程计算机,put传送多个文件到远程计算机。(58)get
设某条指令中的操作数(地址)部分为x,地址为X的单元内容为Y,地址为Y的单元内容为z。如果用直接寻址方式,参与操作的数据为(8);如果用立接寻址方式,参与操作的数据为(9):如果用间接寻址方式,参与操作的数据为(10)。
操作系统具有进程管理、存储管理、文件管理和设备管理的功能,在以下有关的描述中,(15)是错误的。
计算机中,具有先进后出特点的(14)称为存储器堆栈。
Excel单列表格(14)可以根据“分隔符号”分列成多列表格。如果选中某单元格并输入2000,按Enter键后此单元格的显示内容为¥2000,那么应将此单元格的格式设置成(15)。
假设供应商S和供应情况SPJ的关系模式分别为:S(Sno,Sname,Status,City)和SPJ(Sno,Pno,Jno,Qty)。SQL语句(22)不能正确地查询出“零件号Pno等于‘P3’的供应商名Sname",而(23).能正确查询的关系代数表
阅读以下说明和C语言函数,将应填入(n)。【说明】已知包含头结点(不存储元素)的单链表的元素已经按照非递减方式排序,函数compress(NODE*head)的功能是去掉其中重复的元素,使得链表中的元素互不相同。处理过程中,当元素重复出
随机试题
可燃、难燃物品的高架仓库和高层仓库,应设自动喷水灭火系统。()
在板材对接平位气焊过程中,如发生烧穿,不能采取()的措施。
下列叙述正确的是()。
企业用来进行长期投资决策经济评价的基本方法是
我国伟大的音乐家聂耳创作的《义勇军进行曲》是影片______的主题歌,该曲后来被定为中华人民共和国国歌。
CT扫描中,边缘增强滤过的作用是
切牙乳突作为无牙颌解剖标志的作用是
案情:2007年2月10日,甲公司与乙公司签订一份购买1000台A型微波炉的合同,约定由乙公司3月10日前办理托运手续,货到付款。乙公司如期办理了托运手续,但装货时多装了50台B型微波炉。甲公司于3月13日与丙公司签订合同,将处于运输途中的
将城市工程管线按弯曲程度分类,下列()管线属于可弯曲管线。
A,B,C,D四个队举行足球循环赛(即每两个队都要赛一场),胜一场得3分,平一场得1分,负一场得0分。已知:(1)比赛结束后四个队的得分都是奇数;(2)A队总分第一;(3)B队恰有两场平局,并且其中一场是与C队平局。问:D队得几分?
最新回复
(
0
)