2. 计算机
  3. 某计算机有14条指令，其使用频度分别如表1-2所示。 这14条指令的指令操作码用等长码方式编码，其编码的码长至少为(20)位。若只用两种码长的扩展操作码编码，其平均码长至少为(21)位。

某计算机有14条指令，其使用频度分别如表1-2所示。 这14条指令的指令操作码用等长码方式编码，其编码的码长至少为(20)位。若只用两种码长的扩展操作码编码，其平均码长至少为(21)位。

admin2019-03-04  17
问题 某计算机有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位等)，对编码做适当改变。
   如果使用等长编码方式，则由于23=8，24=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

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)