2019年计算机组成原理考研真题答案及解析

本文提供2019年计算机组成原理考研真题答案及解析，以下为具体内容

1、在多级存储体系中，“Cache-主存”结构的作用是解决（ ）的问题。

A、主存容量不足

B、主存与辅存速度不匹配

C、辅存与CPU速度不匹配

D、主存与CPU速度不匹配

2、在CPU执行指令的过程中，指令的地址由（ ）给出。

A、程序计数器PC

B、指令的地址码字段

C、操作系统

D、程序员

3、对n个关键字进行顺序查找，假设查找成功和查找不成功的概率相等，假设每个关键字的查找概率相等，计算平均查找长度ASL（ ）。

A、(n+1)/2

B、n/2

C、(n+1)/4

D、3(n+1)/4

4、在双向链表中，删除第i个结点的时间复杂度为（ ）。

A、O(1)

B、O(n)

C、

D、

5、以顺序方式表示和实现的循环队列中，计算队列中元素个数的语句为（ ）。

A、Q.rear-Q.front

B、Q.front-Q.rear

C、(Q.front-Q.rear+MaxSize)%MaxSize

D、(Q.rear-Q.front+MaxSize)%MaxSize

7、某一棵树，其中度为1的结点个数为10，度为2的结点个数为20，度为3的结点个数为30，度为4的结点个数为40，计算度为零的结点个数（ ）。

A、203

B、202

C、201

D、200

8、对关键字集合{5，4，3，2，1}进行快速排序（排为非递减序），第三趟排序的结果是（ ）。

A、{5，4，3，2，1}

B、{1，2，3，4，5}

C、{1，4，3，2，5}

D、{1，3，4，2，5}

9、给定事件个数及其事件概率（概率和为1），Huffman编码及其平均码长的唯一性为（ ）。

A、不唯一，不唯一

B、唯一，唯一

C、不唯一，唯一

D、唯一，不唯一

1、试题答案：D

试题解析：

Cache-主存层次主要解决CPU和主存速度不匹配的问题。由于Cache的速度比主存的速度高，只要将CPU近期要用的信息调入Cache，CPU便可以直接从Cache中获取信息，从而提高访存速度。但由于Cache的容量小，因此需不断地将主存的内容调入Cache，使Cache中原来的信息被替换掉。主存和Cache之间的数据调动是由硬件自动完成的，对程序员是透明的。故本题选D。

2、试题答案：A

试题解析：

程序计数器又称指令计数器，用来存放正在执行的指令地址或接着要执行的下条指令地址。故本题选A。

3、试题答案：D

试题解析：

在顺序查找中，当查找到第i个位置时，如果该位置上的关键字等于待查找的关键字，那么查找成功，查找长度为i，否则需要继续查找下一个位置，直到查找到最后一个位置，查找长度为n。由于每个关键字查找的概率相等，因此查找成功和查找不成功的概率也相等。因此平均查找长度ASL可以表示为：ASL = (成功的概率×成功时的查找长度+失败的概率×失败时的查找长度)=(1/2×1/n×(1+2+...+n)+1/2×(n+1))=3(n+1)/4。故本题选D。

4、试题答案：B

试题解析：

在双向链表中删除第i个结点需要先找到该结点，遍历链表的时间复杂度为O(n)，然后删除该结点需要对它前面和后面的结点进行链接操作，每个链接操作的时间复杂度都是O(1)，所以总的时间复杂度是O(n)。故本题选B。

5、试题答案：D

试题解析：

在循环队列中，队尾指针rear可能小于队头指针front，此时元素个数应为队尾指针到队头指针的距离加上循环部分长度，即(Q.rear-Q.front+MaxSize)%MaxSize。故本题选D。

7、试题答案：C

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2+n3+n4（结点数量）=n1+2n2+3n3+4n4+1（边数量+1）。则树T中的叶子结点n0的个数是n2+2n3+3n4+1=20+2×30+3×40+1=201。故本题选C。

8、试题答案：B

试题解析：

快速排序的基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。第一趟快速排序的结果是{1，4，3，2，5}；第二趟快速排序是{1，4，3，2，5}；第二趟快速排序是{1，2，3，4，5}。故本题选B。

9、试题答案：C

试题解析：

Huffman编码是一种将字符编码为二进制编码的算法，可以使得编码后的二进制串的长度最小化。在给定事件个数及其事件概率的情况下，可以使用Huffman编码来压缩数据。Huffman编码的唯一性与其平均码长有关。如果事件概率不同，那么Huffman编码一般是唯一的，并且与平均码长有关。但是，如果事件概率相同，那么Huffman编码可能不唯一。
具体来说，如果事件概率不同，那么Huffman编码的构造过程是唯一的，可以保证每个事件的编码长度最短，因此编码后的二进制串长度也是唯一的。此时Huffman编码的平均码长也是唯一的。但是，如果事件概率相同，那么Huffman编码可能不唯一，因为在构造编码时，可以任意交换权值相同的节点，这样可以得到不同的编码。但无论如何构造编码，平均码长始终相同。因此，Huffman编码的平均码长是唯一的，但具体的编码可能不唯一。故本题选C。