首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于给定的一组权值{2,3,4,1 1),用其构造Huffman树,则其WPL为(52),根节点的权值为(53)。
对于给定的一组权值{2,3,4,1 1),用其构造Huffman树,则其WPL为(52),根节点的权值为(53)。
admin
2014-11-11
54
问题
对于给定的一组权值{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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在Linux操作系统中,采用()来搭建DNS服务器。
~WindowsSetter2003操作系统中,IIs6.0不提供下列()服务。
WindOWSServer2003中配置SNMP服务时,必须以__________身份登录才能完成SNMP服务的配置功能。(2012年下半年试题)
在输入输出控制方法中,采用__________可以使得设备与主存间的数据块传送无需CPU干预。(2010年下半年试题)
内存按字节编址,地址从90000H~CFFFFH,若用存储容量为16K×8b的存储器芯片构成该内存,至少需要__________片。(2008年上半年试题)
运行RIPv2协议的3台路由器按照如下图所示的方式连接,路由表项最少需经过__________可达到收敛状态。
Routingincircuit-switchingnetworkshastraditionallyinvolvedastaticroutingstrategywiththeuseof(1)pathstorespond
N-ISDN是在(33)基础上建立起来的网络,能够提供的最高速率是(34)。网络提供基本接口速率时,传输声音需要使用(35),一路话音占用的数据传输数率是(36),占用户实际可用带宽的比例是(37)。
IEEE802.11定义了无线局域网的两种工作模式,其中的(208)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,它通过把一组需要互相通讯的无线网卡的ESSID设为同值来组网。IEEE802.11的物理层规定了三种传输技术,即红外技术、直接
随机试题
急性胰腺炎的非手术治疗有哪些?
患者男,46岁。脊髓损伤,双上肢肩关节可自主活动,手关节不能自主活动,双下肢迟缓性瘫痪一级护理。患者可能损伤的脊髓节段为
根据干扰素的性质,可将干扰素分成两种类型:Ⅰ型和Ⅱ型。Ⅱ型干扰素的主要功能是()
案情:位于某市甲区的天南公司与位于乙区的海北公司签订合同,约定海北公司承建天南公司位于丙区的新办公楼,合同中未约定仲裁条款。新办公楼施工过程中,天南公司与海北公司因工程增加工作量、工程进度款等问题发生争议。双方在交涉过程中通过电子邮件约定将争议提交某仲裁委
某企业本月营业收入为1515000元,营业外收入为100000元,投资收益为60000元,营业成本为760000元,营业税金及附加为30000元,营业外支出为80000元,管理费用为40000元,销售费用为30000元,财务费用为15000元,所得税费用为
青藏高原有“世界屋脊”之称,它的形成是由()碰撞引起的。
Americannolongerexpectpublicfigures,whetherinspeechorinwriting,tocommandtheEnglishlanguagewithskillandgift.
[*]
在计算机领域中通常用MIPS来描述
Althoughmostdreamsapparentlyhappen______,dreamactivitymaybeprovokedbyexternalinfluence.
最新回复
(
0
)