2021年操作系统考研真题答案及解析

考研希赛网 2023-07-07 浏览 464 来源：希赛网

考研真题，是用来研究考试规律的。考生可通过真题，来确定自己的复习范围，来研究考试的重点、难点是哪些内容。希赛网为大家整理2021年操作系统考研真题答案及解析，供大家参考!

本文提供2021年操作系统考研真题答案及解析，以下为具体内容

1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A、单链表

B、仅有头指针的单向循环链表

C、双链表

D、仅有尾指针的单向循环链表

2、一个栈的输入序列为1，2，3，...，n，若输出序列的第一个元素是n，那么输出第i（1<=i<=n）个元素是（）。

A、n-i

B、i

C、n-i+1

D、不确定

3、若一颗二叉树具有15个度为2的结点，10个度为1的结点，则度为0的结点个数是（）。

A、16

B、25

C、40

D、不确定

4、根据使用频率，为5个字符设计的哈夫曼编码不可能是（）。

A、000，001，010，011，1

B、000，001，01，10，11

C、00，100，101，110，111

D、0000，0001，001，01，1

5、设a，b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（）。

A、a在b的右方

B、a在b的左方

C、a是b的祖先

D、a是b的子孙

6、对一棵二叉排序树按（）遍历，可得到结点值从小到大的排序序列。

A、先序

B、中序

C、后序

D、层次

7、已知一个有序表为（5，13，19，21，37，56，64，75，80，88，92），则折半查找64需要比较（）次。

A、1

B、2

C、3

D、4

8、在一个图中，所有顶点的度数之和等于所有边数的（）倍。

A、1/2

B、1

C、2

D、3

9、一个序列中有100000个元素，若只想得到其中前10个最大元素，则最好采用（）方法。

A、快速排序

B、堆排序

C、插入排序

D、归并排序

10、下列四个序列中，哪一个是堆（）。

A、70，60，40，10，30，25，20，15

B、70，60，30，15，25，40，20，10

C、70，40，60，10，25，30，20，15

D、70，40，60，30，15，25，20，10

1、试题答案：D

试题解析：

【考点】本题考查线性表的链式存储结构。
【解析】四个存储方式在最后一个元素之后插入一个元素和删除第一个元素这两种操作的时间复杂度如下表所示。由表可知，虽然选项C和D的时间复杂度均是O(1)，但相比之下，双链表多了一个结点前驱和后继指针的修改。故本题选D。

2、试题答案：C

试题解析：

【考点】本题考查栈的基本概念。
【解析】由于输出序列的第一个元素是n，表明此时序列1至n-1均已入栈，后续只能依次输出。第二个输出的是n-1，第三个输出的是n-2……以此类推，第i个输出的是n-i+1。故本题选C。

3、试题答案：A

试题解析：

【考点】本题考查二叉树的主要特征。
【解析】根据完全二叉树的性质，根据二叉树的性质，结点个数n=n0+n1+n2（结点数量）=n1+2n2+1（边数量+1）。由此，代入数值可知，n0=n2+1=16。故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查哈夫曼树和哈夫曼编码。
【解析】根据哈夫曼树的构造思想可知，哈夫曼树仅存在度为2的结点和度为0的叶子结点。根据左0右1，四个选项对应的哈夫曼树如下图所示。由图可知，选项C中出现了度为1的结点。故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历。
【解析】二叉树中序遍历的算法思想是左根右。根据排除法，当选项A、C、D出现下图所示情况时，a在b后面。故本题选B。

6、试题答案：B

试题解析：

【考点】本题考查二叉排序树的性质。
【解析】一棵非空的二叉排序树具有以下性质：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；
（3）它的左、右子树也分别为二叉排序树。
因此，通过对比中序遍历的算法思想，易知中序遍历二叉排序树可得到一个关键字的有序序列。故本题选B。

7、试题答案：C

试题解析：

【考点】本题考查折半查找法。
【解析】折半查找的具体过程如下表所示。故本题选C。