首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某计算机有14条指令,其使用频度分别如表1-2所示。 这14条指令的指令操作码用等长码方式编码,其编码的码长至少为(20)位。若只用两种码长的扩展操作码编码,其平均码长至少为(21)位。
某计算机有14条指令,其使用频度分别如表1-2所示。 这14条指令的指令操作码用等长码方式编码,其编码的码长至少为(20)位。若只用两种码长的扩展操作码编码,其平均码长至少为(21)位。
admin
2019-03-04
50
问题
某计算机有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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
某项目在执行过程中,在软件的需求基线已经确定后,客户需要增加新的功能,但该需求变更会对已经完成系统的稳定性有较大影响。作为项目负责人处理这些需求变更,下列()做法是不合适的。
关于入侵检测系统(IDS),下面说法不正确的是()。
很多银行网站在用户输入密码时要求使用软键盘,这是为了()。
WindowsNT和Windows2000系统能设置为在若干次无效登录后锁定账号,此技术可以防止()。
WBS是一种以()为导向的分析方法,用于分析项目所涉及的工作。
某系统集成项目的目标是使人们能在各地书报零售店购买到彩票,A公司负责开发该项目适用的软件,但需要向其他公司购买硬件设备。A公司外包管理员首先应准备的文件被称为()。
某承诺文件超过要约规定时间到达要约人。依据邮寄文件收函邮局戳记标明的时间,受要约人是在要求的时间内投邮,由于邮局错递而错过了规定时间。对此情况,该承诺文件(28)。
煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连,位置如下图所示,节点代表各住宅楼和主管道位置,线上数字代表两节点间距离(单位:百米)。则煤气公司铺设的管道总长最短为()米。
在沟通管理中不仅要“用别人喜欢被对待的方式来对待他们”,而且还需要根据自身面临的情况,灵活采取适当的沟通措施。如重复对方的话,让对方确认,以真正了解对方的意图时,一般采用()。
随机试题
预防子宫内膜异位症的发生错误的是
男,24岁,心悸气促10年,常咯血,梨形心,心尖区舒张期隆隆样杂音,P2亢进,S1亢进,有开瓣音。首选治疗方法是
男,25岁。反复腹痛、腹泻、便血10个月。近日加重伴发热,体温39℃,1天前因腹痛肌注阿托品治疗6小时后腹胀明显。查体:70/50mmHg,心率120次/分。最可能出现的情况是
下列有关鉴定人和证人的区别的表述正确的是:()
项目建议书阶段的投资估算允许误差是:[2000-46]
美术教学备课的主要内容是()。
当中断发生后,进入中断处理的程序属于()。
被关押的罪犯在脱逃中使用暴力致使狱警死亡的行为,应当以()
Softwareisdividedintotwocategories,systemsoftwareandapplicationsoftware.Pleasechooseonewhichisdifferfromotherth
如表1所示,在某dhcp客户机上捕获了5条报文,并对第5条报文进行了解析,表2是在该客户机捕获上述报文后执行ipconfig/all命令后得到的部分信息。分析表中的报文和信息,并补全表中空白处的信息。
最新回复
(
0
)