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

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

1、下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是（ ）。

A、程序的功能都通过中央处理器执行指令实现

B、指令和数据都用二进制数表示，形式上无差别

C、指令按地址访问，数据都在指令中直接给出

D、程序执行前，指令和数据需预先存放在存储器中

2、相对于微程序控制器，硬布线控制器的特点是（ ）。

A、指令执行速度慢，指令功能的修改和扩展容易

B、指令执行速度慢，指令功能的修改和扩展难

C、指令执行速度快，指令功能的修改和扩展容易

D、指令执行速度快，指令功能的修改和扩展难

3、在循环链表中删除第一个结点，时间复杂度为（）。

A、O(1)

B、O(n)

C、

D、

4、顺序存储的循环队列Q假设队列头为front，队列尾为rear，队列长度为MaxSize，则判断队列Q是否为满的语句为（）。

A、return(Q.rear-Q.front+MaxSize)%MaxSize;

B、return(Q.rear+1)%MaxSize=front;

C、return(Q.front!=Q.rear);

D、return(Q.front==Q.rear);

6、若一棵二叉树的中序序列和后序序列相同，则该二叉树必满足条件（）。

A、不存在满足条件的二叉树；

B、空树或任一结点仅有一个孩子的非空二叉树；

C、空树或任一结点无左孩子的非空二叉树；

D、空树或任一结点无右孩子的非空二叉树；

7、Huffman树共有399个结点，其叶子结点个数为（）。

A、149

B、199

C、200

D、300

8、假设网有n+1个顶点，e条边，则其克鲁斯卡尔最小生成树有（）条边。

A、e

B、e-1

C、n

D、n+1

9、使用邻接表作为无向图的存储结构，设n为顶点数，e为边数，图的广度优先搜索遍历（BFS）的时间复杂度为（ ）。

A、O(n²)

B、O(e²)

C、O(n+e)

D、O(n*e)

10、顺序查找，查找成功的平均查找长度为（）。

A、n/2

B、n+1

C、(n+1)/2

D、log n²

1、试题答案：C

试题解析：

【考点】本题考查计算机组成原理--计算机系统概述--计算机的硬件--冯·诺依曼结构--冯·诺依曼结构的设计思想。
【解析】数据不是直接在指令中给出。在冯·诺依曼结构中，指令按照其地址被访问，而数据则是通过指令中的地址进行访问的，指令中并不直接给出数据。故本题选C。

2、试题答案：D

试题解析：

组合逻辑控制器或硬连线控制器是采用组合逻辑技术来实现的，其控制单元是由门电路组成的复杂树形网络。组合逻辑控制器的最大优点是速度快。但是控制单元的结构不规整，使得设计、调试、维修较困难，难以实现设计自动化。微程序控制器的设计思想和组合逻辑设计思想截然不同。它具有设计规整、调试、维修以及更改、扩充指令方便的优点，易于实现自动化设计，但是，由于它增加了一级控制存储器，所以指令的执行速度比组合逻辑控制器慢。故本题选D。

3、试题答案：B

试题解析：

在循环链表中删除第一个结点，需要先找到最后一个结点，将其指向原本第二个结点，然后再删除第一个结点，这个过程需要遍历整个链表，因此时间复杂度为O(n)。故本题选B。

4、试题答案：B

试题解析：

顺序存储的循环队列Q为了区分队列是空还是满，需要浪费一个存储空间。因此，当队列满时，队列元素个数为MaxSize-1。判断队列Q是否为满的语句应该为：return(Q.rear+1)%MaxSize=front;。故本题选B。

6、试题答案：B

试题解析：

如果一棵二叉树的中序序列和后序序列相同，那么它必然满足以下条件：
（1）只有一个根节点。
（2）根节点的左子树或右子树为空或仅有一个节点。
如果不满足以上条件，那么中序序列和后序序列就不可能相同。因此，该二叉树必须是空树或任一结点仅有一个孩子的非空二叉树。故本题选B。

7、试题答案：C

试题解析：

根据二叉树的特性可知，结点个数n=n0+n1+n2（结点数量）=n1+2n2+1（边数量+1）。由于哈夫曼树中不存在度为1的结点，因此Huffman树中叶子结点比度为2的结点多一个，叶子结点个数为200，度为2的结点个数为199。故本题选C。

8、试题答案：C

试题解析：

在Kruskal算法中，将所有的边按权值从小到大排序，然后依次选取权值最小的边加入到生成树中，直到生成树中含有 n 个顶点为止。同时，保证所选取的边不会构成环。因此，对于n+1个顶点，最小生成树中边的数量应该为n条，即所有顶点之间有且仅有n条边，而不会出现额外的边。故本题选C。

9、试题答案：C

试题解析：

在广度优先搜索遍历有向图时，需要遍历图中所有的n个结点和e条边，因为对于每一个结点，需要遍历其所有出边，才能确定其相邻的结点，并将这些相邻结点加入到队列中等待遍历。因此，算法的时间复杂度与n和e的数量有关。在广度优先搜索遍历时，需要将每个结点遍历一次，将其所有的出边都访问一次，将其相邻结点加入队列中一次，因此总共需要遍历n个结点，访问e条边，时间复杂度为O(n+e)。故本题选C。

10、试题答案：C

试题解析：

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