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

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

1、已知一个长度为20的顺序表L，其元素按键值有序排列。若采用折半查找法查找L中不存在的元素，则关键字的比较次数最多是（ ）。

A、4

B、5

C、6

D、7

2、将森林F转换为对应的二叉树T，F中叶结点个数为（）。

A、T中叶结点个数

B、T中左孩子指针为空的结点个数

C、T中度为1结点个数

D、T中右孩子指针为空的结点个数

3、表达式a*(b-c)+d的后缀表达式是（）。

A、abcd*-+

B、abc-*d+

C、abc*-d+

D、+-*abcd

4、若用A[0…m-1]存放循环队列的元素值，front和rear分别表示队头和队尾，则当前队列中的元素个数是（）。

A、(rear-front+m)%m

B、rear-front+1

C、rear-front

D、rear-front-1

5、若一棵二叉树的先序遍历序列为a，e，b，d，c；后序遍历序列为b，c，d，e，a；则根结点的孩子结点是（）。

A、有e，c

B、有e，b

C、只有e

D、无法确定

7、对邻接表的叙述中，（）是正确的。

A、无向图的邻接表中，第i个顶点的度为第i个链表中结点数的二倍

B、邻接表比邻接矩阵操作简单

C、邻接矩阵比邻接表操作简单

D、求有向图顶点的度，必须遍历整个邻接表

8、在下列给出的四种排序方法中，关键字的比较次数与记录初始排列无关的是（）。

A、简单选择排序

B、快速排序

C、直接插入

D、起泡排序

9、设树T的度为4，其中度为1，2，3，4的结点个数分别为4，3，2，1，则T中的叶结点个数为（ ）。

A、9

B、10

C、11

D、12

1、试题答案：B

试题解析：

2、试题答案：B

试题解析：

将如下图所示的森林转换成对应的二叉树：

由图可知，F中叶子结点个数为6。对于A，T中叶子结点个数是3，因此A错误。对于B，T中左孩子指针为空的结点个数是6，因此B正确。对于C，T中度为1结点个数是5，因此C错误。对于D，T中右孩子指针为空的结点个数是5，因此D错误。故本题选B。

3、试题答案：B

试题解析：

使用加括号的方法求解后缀表达式的步骤如下：
① 对题干所示的中缀表达式按照运算的优先顺序加上括号：((a*(b-c))+d)；
② 将括号中的运算符移到括号外：((a(bc)-)*d)+；
③ 将括号去掉后的后缀表达式：abc-*d+。故本题选B。

4、试题答案：A

试题解析：

将顺序队列首尾相接成环状空间即为循环队列。在本题中，rear表示队尾元素的下一个位置，若rear>front，则队列的元素个数=rear-front；若rear>front，则队列的元素个数=rear-front+m。因此正确答案应当为：(rear-front+m)%m。故本题选A。

5、试题答案：C

试题解析：

根据二叉树的先序遍历和后序遍历是无法唯一确定一棵二叉树的，但本题只问了根结点的孩子结点，则本题可解。根据先序遍历可知，根结点为a，若左孩子根结点为e，则根据后序序列可知该树无右孩子，因此根结点的孩子结点只有e。若右孩子的根结点为e，则根据先序遍历可知该树无左孩子，因此根结点的孩子结点只有e。故本题选C。

7、试题答案：D

试题解析：

对于A，无向图第i个顶点的度为第i个链表中结点数而非二倍，因此A错误。对于B和C，邻接表和邻接矩阵对于处理不同的问题各有优势，邻接表更适用于稀疏图，邻接矩阵更适用于稠密图，因此B和C错误。对于D，有向图顶点Vi的出度仅需要遍历以Vi为顶点数组的边链表，但是求Vi的入度则需要遍历整个链表，因此D正确。故本题选D。

8、试题答案：A

试题解析：

9、试题答案：C

试题解析：