首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于给定的一组权值{2,3,4,1 1),用其构造Huffman树,则其WPL为(52),根节点的权值为(53)。
对于给定的一组权值{2,3,4,1 1),用其构造Huffman树,则其WPL为(52),根节点的权值为(53)。
admin
2014-11-11
44
问题
对于给定的一组权值{2,3,4,1 1),用其构造Huffman树,则其WPL为(52),根节点的权值为(53)。
选项
A、53
B、40
C、34
D、20
答案
C、D
解析
Huffman树又称为最优树,是一类带权路径长度最短的树。路径是指从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径,路径上的分支数目就称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。树的路径长度为树中所有节点的带权路径长度之和,记为
,其中n为带权叶子节点数目,W
R
为叶子节点的权值,l
k
为叶子节点到根的路径长度。Huffman树是指权值为w
1
、w
2
、…、w
n
的n个叶子节点的二叉树中带权路径长度最小的二叉树。构造Huffman树的算法如下:(1)给定n个节点的集合,每个节点都带权值。(2)选两个权值最小的节点构造一棵新的二叉树,新的二叉树的根节点的权值就是两个子节点权值之和。(3)从n个节点中删除刚才使用的两个节点,同时将新产生的二叉树的根节点放在节点集合中。(4)重复(b)(c),直到只有一棵树为止。本题构造出的Huffman树如下:
根节点的权值为20,对应的WPL为:11×1+4×2+(2+3)×3=34。
转载请注明原文地址:https://kaotiyun.com/show/rXRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在IEEE802.11标准中使用了扩频通信技术,下面选项中有关扩频通信的说法中正确的是______。
Linux系统中,为某一个文件在另外一个位置建立一个文件链接的命令为______。
ISO/IEC9126软件质量模型中第一层定义了6个质量特性,并为各质量特性定义了相应的质量子特性。子特性__________属于可靠性质量特性。(2008年下半年试题)
某单位架设了域名服务器来进行本地域名解析,在客户机上运行nslookup查询某服务器名称时能解析出IP地址,查询IP地址时却不能解析出服务器名称,解决这一问题的方法是(34)。
在Kerberos系统中,使用一次性密钥和__________来防止重放攻击。(2009年下半年试题)
利用结构化分析模型进行接口设计时,应以__________为依据。(2011年下半年试题)
SNMP是一个异步请求/响应协议,它的请求与响应没有必定的时间顺序关系,它是一个(1)的协议。SNMP的管理进程和管理代理之间的关系是共同体,它们是(2)。SNMP的设计独立于具体的传输网络,所以它(3)传输层协议支持下工作。SNMP的PDU有多种不同的结
TraditionalIPpacketforwardinganalyzesthe(1)IPaddresscontainedinthenetworklayerheaderofeachpacketasthepacke
语言信号是模拟信号,其标准频谱范围为__________。
设有一个空栈,栈顶指针为1000H(十六进制,下同),现有输入序列为1,2,3,4,5,经过PUSH, PUSH,POP,PUSH,POP,PUSH,PUSH后,输出序列是(27),栈顶指针是(28)。设一数列的顺序为1,2,3,4,5,6,通过栈结构可以
随机试题
已知则f(x)
A.经蝶窦切除垂体微腺瘤B.一侧肾上腺全切+另侧肾上腺大部切除,术后作垂体放疗C.一侧肾上腺肿瘤摘除D.开颅手术+垂体放疗垂体手术未发现肿瘤而临床症状严重的Cushing病
周围血管疾病用测定双侧肢体皮肤温差的方法判断动脉血流减少情况,温度相差至少应大于()
根据《建设工程质量管理条例》,具有法定最低保修期限的有()。
下面是对社会公德的几种看法。观点一:社会公德维护公共利益,但会损害个人利益。观点二:社会公德很重要,但它与我没有多大关系。观点三:对熟悉的人,应该讲公德,对那些不认识的人没必要讲公德。观点四:社会公德可有可无,讲不讲公德无所谓。运用社会公德知识对
关于网孔电流法,下列叙述正确的有()。
下列名胜属于“东方四大奇观”的是()。
通知(文种)用于()。
(上海理工大学2006年试题)Inatelephonesurveyofmorethan2,000adults,21%saidtheybelievedthesunrevolved(旋转)aroundtheearth
HowtoSucceedinYourLiteratureClassCollegeliteratureclassmayseemdifficulttobeginners,especiallywiththeirlan
最新回复
(
0
)