首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某计算机有14条指令,其使用频度分别如表1-2所示。 这14条指令的指令操作码用等长码方式编码,其编码的码长至少为(20)位。若只用两种码长的扩展操作码编码,其平均码长至少为(21)位。
某计算机有14条指令,其使用频度分别如表1-2所示。 这14条指令的指令操作码用等长码方式编码,其编码的码长至少为(20)位。若只用两种码长的扩展操作码编码,其平均码长至少为(21)位。
admin
2019-03-04
51
问题
某计算机有14条指令,其使用频度分别如表1-2所示。
这14条指令的指令操作码用等长码方式编码,其编码的码长至少为(20)位。若只用两种码长的扩展操作码编码,其平均码长至少为(21)位。
选项
A、2.8
B、3.4
C、3.8
D、4.2
答案
B
解析
本题要考查的知识点是指令格式的优化问题。优化就是以较少的格式,以尽可能短的码长来实现各种指令编码。我们知道,指令字包括操作码和地址码,所以对这两部分都要采取优化措施。
这要用到哈夫曼(Huffman)压缩的概念,哈夫曼压缩法是一种频率相关的编码方法,即出现频率高的字符编码短,频率低的字符编码长,这样可以缩短平均码长。
考生要掌握的是用哈夫曼树实现哈夫曼编码。其方法很简单,可以分为建树和编码两个步骤:
(1)建树:根据所给的各种指令使用频率,把它们从小到大依次排好作为叶结点(相同的频率可任取一个排在前),然后把最小的两个结点值(频率)相加,形成一个新结点,以这个结点的值与其他叶结点的值比较大小,仍旧取最小的两个结点值合并产生新结点,直到最终合并为一个根(通常这个值是1或100)。
(2)编码:从根结点开始向下,凡左边分支都编为“1”,右边分支都编为“0”(也可取反),则从根结点到叶结点的一条路径上的编码组合就是该指令的哈夫曼编码。
注意,哈夫曼树不是唯一的(因为相同的频率可以任取一个在前,且编码时又可任取左1或左0),但所得的平均码长应该是一样的。由于哈夫曼编码得到的码长很不规整,所以有时候要采用哈夫曼扩展编码,就是在哈夫曼码的基础上对码长加以限制(取几个确定的长度如2位、4位等),对编码做适当改变。
如果使用等长编码方式,则由于2
3
=8,2
4
=16,所以至少要4位的编码长度才能将这14条指令编码。
接下来我们分析两种长度的编码。由于题目中给出了指令的执行频度,且要求计算平均码长的最小值,抛开“两种码长”这个限制,我们应毫不犹豫地选哈夫曼编码,先构造一棵哈夫曼树,如图1-3所示。
因为题目规定只能使用两种码长,所以还需要对已建好的哈夫曼树进行一些调整。从哈夫曼树的结点分布可以看出,树中深度为3和5的结点是最多的,还有一个深度为 4的结点,以及两个深度为6的结点。我们可以对它们做如图1-4所示的调整。
调整以后得到的树如图1-5所示。
图1-5的树中所有结点的深度都为3或5。我们现在可以按照码长乘以频度,然后再累加的方法来计算平均码长:
(0.15+0.15+0.14+0.13+0.12+0.11)×3+(0.04+ 0.04+0.03+0.03+0.02+0.02+0.01+0.01)×5=3.4
转载请注明原文地址:https://kaotiyun.com/show/UJTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
在规划质量中,()是一种统计分析技术,可用来帮助人们识别并找出哪些变量对项目结果的影响最大。
当评估项目的成本绩效数据时,根据数据与基线的偏差程度将做出不同的反应。例如,10%的偏差可能不需要做出反应,而100%的偏差将需要进行调查,对成本偏差大的判断必须使用到的是()。
甲向乙发送其数字签名,要验证该签名,乙可使用()对该签名进行解密。
下列有关项目分解结构(PBS)与工作分解结构(WBS)的描述中,正确的是()。
有八种物品A、B、C、D、E、F、G、H要装箱运输,虽然量不大,仅装1箱也装不满,但出于安全考虑,有些物品不能同装一箱。在下表中,符号“×”表示相应的两种物品不能同装一箱。运输这八种物品至少需要装(67)箱。
某软件的工作量是20000行,由4人组成的开发小组开发,每个程序员的生产效率是5000行/(人月),每对程序员的沟通成本是250行/(人月),则该软件需要开发盟月。
已知网络图各段路线所需费用如下图所示,图中甲线和乙线上的数字分别代表相应点的有关费用。从甲线到乙线的最小费用路线有___________(66)条,最小费用为___________(67)。(66)
在1号楼办公的小李希望在本地计算机上通过远程登录的方式访问放置在2号楼的服务器,为此将会使用到TCP/IP协议族中的___________协议。
(2010下架构)某公司欲对其内部的信息系统进行集成,需要实现在系统之间快速传递可定制格式的数据包,并且当有新的数据包到达时,接收系统会自动得到通知。另外还要求支持数据重传,以确保传输的成功。针对这些集成需求,应该采用______的集成方式。
(2009上系分)极限编程是一种重要的敏捷开发方法,包含策划、设计、编码和测试四个框架活动的规则和实践。下面关于极限编程的叙述,错误的是______。
随机试题
商品是_______、_______。
下列不属于学科课程特点的是()
A.由雌激素、糖皮质激素、卤素等所致B.接触石油、焦油等C.痤疮突然显著加重,伴有发热等全身症状D.表现为严重的结节、囊肿、窦道、瘢痕E.与月经密切相关药物性痤疮
发包人应在不迟于约定开工日期前()天预付工程款,承包人在预付时间到期后()天内,向发包人发出预付通知,发包人在收到预付通知后仍不能按照要求支付,承包人可在发出通知()天后,停止施工。
内在稳定器可以抵消经济的不稳定。()
商业银行开展个人理财业务.应遵守()。
AfterWorldWarIItheglorificationofanever-largerGNPformedthebasisofanewmaterialism,whichbecameasacredobligati
在计算机的硬件技术中,构成存储器的最小单位是
Dependingonyourageandmemory,itwasaweekofradicallyneworreassuringlyolddevelopmentsintheadvertisingindustry.T
A、Hedresseddecently.B、Hedressedimproperly.C、Hewastoopoortobuyclothes.D、Hewasparticularaboutclothes.B
最新回复
(
0
)