首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对( )个字符编码。
设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对( )个字符编码。
admin
2021-08-17
48
问题
设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对( )个字符编码。
选项
A、3
B、4
C、5
D、6
答案
B
解析
首先,赫夫曼编码遵循的原则为:一个编码不能是任何其他编码的前缀。比如1和10就不行,因为1是10的前缀。既然1和01已经使用了,所以1和01开头的码字不能再使用。又由于赫夫曼树的高度为5,故赫夫曼编码的长度不能超过4,只剩下0000、0001、0010、O011等4种编码(这种编码方式可得到最多),故选B选项。
注意:本题选的是最多还可以对多少个字符编码,所以不能选取001、000等编码。例如选取001,就意味着0010和0011不能使用,这样可编码的字符就少了1个。
总结:
(1)有n个叶子结点的赫夫曼树的结点总数为2n—1。
(2)高度为h的赫夫曼树中,至少有2h—1个结点,至多有2
h
—l个结点。
(3)赫夫曼树中一定没有度为1的结点。
(4)赫夫曼树中两个权值最小的结点一定是兄弟结点。
(5)树中任一非叶子结点的权值一定不小于下一层任一结点的权值。
补充例题:一棵赫夫曼树共有215个结点,对其进行赫夫曼编码,共能得到多少个码字?
解析:求多少个码字就是求有多少个叶结点,从(1)可以得到,叶结点的个数为108个,故可以得到108个码字。
转载请注明原文地址:https://kaotiyun.com/show/ZP3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
指令流水线将一条指令的执行过程分为四步,其中第1、2和4步的经过时间为△t,如下图5-1所示。若该流水线顺序执行,50条指令共用153At,并且不考虑相关问题,则该流水线的瓶颈第3步的时间是()。
某计算机采用16位定长指令字格式,其CPU中有一个标志寄存器,其中包含进位/借位标志CF、零标志zF和符号标志NF。假定为该机设计了条件转移指令,其格式如下:其中,00000为操作码OP;C、Z和N分别为CF、ZF和NF的对应检测位,某检测位为1时表示
HDLC协议对0111110001111110组帧后对应的比特串为
若某文件系统索引结点(inode)中有直接地址项和间接地址项,则下列选项中,与单个文件长度无关的因素是
用海明码对长度为8位的数据进行检/纠错时,若能纠正一位错,则校验位数至少为
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求:给出算法的基本设计思想。
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如表2-4所示。该模型机有8位和16位两种指令字长,采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型,16位字长指令为寄存器-存储器(R—M)二地址变址寻址类型(-128
以下有关拓扑排序的说法中,错误的是()。Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
对给定的关键字序列110,119,007,911,114,120,122进行基数排序,则第2趟分配收集后得到的关键字序列是_______。
随机试题
安装弧焊电源时,必须装有单独使用的电源开关。
美育的根本价值取向在于()
社会主义经济体制是指
国内外最常用的HIV确诊实验是
易发生幽门梗阻的溃疡是
女性,26岁。多血质外观,向心性肥胖,痤疮,下腹及大腿外侧见紫纹,血皮质醇明显升高。为进一步诊断病变部位,哪项检查最有意义
甲、乙合作投资开发一房地产项目,双方各出资1000万元,经营收益各按50%分成。到项目建成时投资刚好用完,销售费用也已预提。项目的总建筑面积10000m2,售价3000元/m2,销售费用为售价的7%。销售过程中,乙拿出一套建筑面积为100m2的房屋送给朋友
对于需要泵房直接挡水大型机组,为增大泵房的稳定性,一般建()。
下列关于外国投资者并购境内企业安全审查程序的说法,正确的是()。[2016年10月真题]
OneofthefeaturesofLondonisthenumberofbigstores,mostofwhicharetobefoundinorneartheWestEnd.Theyarevast
最新回复
(
0
)