首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对( )个字符编码。
设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对( )个字符编码。
admin
2021-08-17
49
问题
设某赫夫曼树的高度为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
学硕统考专业
相关试题推荐
假定某计算机的CPU主频为80MHz,CPI为4,并且平均每条指令访存1.5次,主存与cache之间交换的块大小为16B,Caehe的命中率为99%,存储器总线宽度为32位。请回答下列问题。为了提高性能,主存采用4体交叉存储模式,工作时每1/4个存储周
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
设有6个有序表A、B、c、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。请回答下列问题。给出完整的合并过程,并求出最坏情
若用户1与用户2之间发送和接收电子邮件的过程如下图所示,则图中①、②、③阶段分别使用的应用层协议可以是
下列关于IP路由器功能的描述中,正确的是I.运行路由协议,设置路由表Ⅱ.监测到拥塞时,合理丢弃IP分组Ⅲ.对收到的IP分组头进行差错校验,确保传输的IP分组不丢失Ⅳ.根据收到的IP分组的目的IP地址,将其转发到合适的输出线路上
用户程序发出磁盘I/O请求后,系统的处理流程是:用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中,计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
关于Hash查找说法不正确的有()个。Ⅰ.采用链地址法解决冲突时,查找一个元素的时间是相同的Ⅱ.采用链地址法解决冲突时,若插入操作规定总是在链首,则插入任一个元素的时间是相同的Ⅲ.用链地址法解决冲突易引起聚集(堆积)现象
在一个段式存储管理系统中,逻辑地址为32位,其中高16位为段号,低16位为段内偏移,以下是段表(其中的数据均为十六进制,如表7-1所示)。以下是代码段的内容:试问:causin指令的执行过程:先将当前PC值入栈,然后在PC内装入目标PC
某数采用IEEE754单精度浮点数格式表示为C6400000H,则该数的值是
随机试题
在Word中,()是文档中标题的列表,可以通过它来浏览文档中讨论了哪些主题。
人身保险合同中由投保人指定的,在保险事故发生后享有保险赔偿与保险金请求权的人是()。
某机场场道施工结束后,按竣工验收程序,施工单位进行了自检自验。问题:自检自验包括哪些内容?
现金预算的组成部分包括()。
不适用旅行社质量保证金赔偿的情形有哪些?
《学记》中提出的“道而弗牵,强而弗抑,开而弗达”,体现了教学的()。
下列词语中加下划线的字和词,字形、解释全都正确的一组是:
某商场的部门、员工和商品三个实体之间的关系如下图所示。假设每个部门有若干名员工,每种商品只能由一个部门负责销售,那么部门到员工、部门到商品之间分别存在着(33)的联系。如果用户要求得到表4所示的结果,需要(34),并增加关系模式(35)。如果查询某部门负责
某单位网络拓扑如下图所示。路由器AR2路由表内容如下所示路由器AR2接口GE0/0/0地址为_____________。
ReformingtheSocialSecurityretirementprogramisanissueofenormouspracticalimportance.Yetitremainsthemissingpiece
最新回复
(
0
)