首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于给定的一组权值{2,3,4,1 1),用其构造Huffman树,则其WPL为(52),根节点的权值为(53)。
对于给定的一组权值{2,3,4,1 1),用其构造Huffman树,则其WPL为(52),根节点的权值为(53)。
admin
2014-11-11
52
问题
对于给定的一组权值{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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在MIB-II中,IP组对象。iplnReceives为接收的数据包总数,其数据类型为__________类型。(2013年上半年试题)
在单指令流多数据流计算机(SIMD)中,各处理单元必须(5)。
内存按字节编址,地址从90000H~CFFFFH,若用存储容量为16K×8b的存储器芯片构成该内存,至少需要__________片。(2008年上半年试题)
SCSI是一种通用的系统级标准输入/输出接口,其中(65)标准的数据宽度16位,数据传送率达20MB/s。大容量的辅助存储器常采用RAID磁盘阵列。RAID的工业标准共有六级。其中,(66)是镜像磁盘阵列,具有最高的安全性;(67)是无独立校验盘的奇偶校验
ATM(异步传输模式)网络是一种使用信元作为传输数据的单位的网络,并且信元大小是固定的53字节。信元传输采用(273)。当信元从用户端进入网络中第一个交换机后,信元头中修改的部分是(274)。当进行VP交换时,VPI和VCI的变化情况是(275)。当需要传
构造LAN时,一般不采用的方案是(41)。采用粗细电缆混接的条件下,若用100m细电缆,则在没有中继器时网络的最大可延伸距离为(42)。在光纤通信中,单模光纤一般比多模光纤的直径(43)。光纤采用SDH传输方式时,其基本速率可达到(44),在光纤上采用AT
TraditionalIPpacketforwardinganalyzesthe(1)IPaddresscontainedinthenetworklayerheaderofeachpacketasthepacke
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】C++语言本身不提供对数组下标越界的判断。为了解决这一问题,在程序6中定义了相应的类模板,使得对厂任意类型的二维数组,可以在访问数组元素的同时,对行下标和列下标进行越
设有一个空栈,栈顶指针为1000H(十六进制,下同),现有输入序列为1,2,3,4,5,经过PUSH, PUSH,POP,PUSH,POP,PUSH,PUSH后,输出序列是(27),栈顶指针是(28)。设一数列的顺序为1,2,3,4,5,6,通过栈结构可以
栈和队列都是(2)。若进栈序列为1,2,3,4,则(3)不可能是一个出栈序列。若进队列的序列为1,2,3,4,则(4)是一个进队列序列。
随机试题
Researchonfriendshiphasestablishedanumberoffacts,someinteresting,someevenuseful.Didyouknowthattheaveragestud
设y1(x),y2(x是二阶常系数线性微分方程yˊˊ+Pyˊ+qy=0的两个线性无关的解,则它的通解为________.
干姜的主治病证有
高血压危急症的处理原则最主要的是()
小儿,阵发性痉挛性咳嗽1个半月,经治疗咳嗽减轻,但痰粘难以咳出,伴低热,烦躁盗汗,舌红苔少,脉细数。治疗应首选方剂
狭义的金融犯罪是指金融业务活动本身的犯罪,主要是指“破坏金融管理秩序罪”及“金融诈骗罪”;广义的金融犯罪还包括金融机构工作人员的职务犯罪,如贪污、受贿、挪用公款罪等。()
初次见面握手时间应控制在3秒钟内,切记不可戴手套。()
国际足联总部位于()。
简述赫尔巴特的教学理论。【2012年-天津师大】【2015年-北师大】【2019年-苏州大学】
TheemploymentdiscriminationlawsuitagainstWal-Mart,whichtheSupremeCourtheardlastweek,isthelargestinAmericanhist
最新回复
(
0
)