2020年操作系统考研真题答案及解析（一）

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

1、含有m个结点的二叉树链式存储结构中空指针的个数为（ ）。

A、2m

B、m-1

C、m+1

D、m

2、下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。

A、快速排序

B、插入排序

C、选择排序

D、希尔排序

E、无正确答案

3、一个栈的进栈序列是a b c d e，则栈的输出序列不可能的是（ ）。

A、a b c d e

B、e d c b a

C、d e c b a

D、d c e a b

4、需要的辅助空间最多的排序算法为（ ）。

A、归并排序

B、快速排序

C、基数排序

D、堆排序

5、哈希表的平均查找长度说法错误的是（ ）。

A、与处理冲突方法有关而与表的长度无关

B、与选用的哈希函数有关

C、与哈希表的饱和程度有关

D、与表中填入的记录数有关

6、有n个顶点、e条边且使用了邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是（ ）。

A、O（n+e）

B、

C、O（n+2e）

D、O（n*e）

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

A、3

B、4

C、5

D、6

8、一棵完全二叉树上有3001个结点，其中叶子结点的个数是（ ）。

A、1500

B、1501

C、1000

D、1001

9、若一棵二叉树度为2的结点有18个，度为1的结点有10个，则度为0的结点个数是（ ）。

A、46

B、28

C、19

D、17

1、试题答案：C

试题解析：

【考点】本题考查二叉树的链式存储结构的定义。
【解析】链式存储结构下的m个结点的二叉树共有2m个指针。其中有m-1条边，即有m-1个非空指针，故空指针数=2m-(m-1)=m+1。简单画图亦可获得结果，如下图所示，4个结点的二叉树链式存储结构中的空指针的个数为5。故本题选C。

2、试题答案：E

试题解析：

无正确答案。在相对有序的序列中，一些元素可能就在其最终位置上不需要移动，快速排序、插入排序、选择排序和希尔排序都可能在比较过程中不移动这些元素。但是基数排序，每个元素都要先到顶堆，然后再到相应位置上，所以不论原来序列是否有序，都要变更元素的位置，所以和初始排列顺序无关。因此本题的正确选项是基数排序。
【考点】本题考查各种内部排序算法的比较。

3、试题答案：D

试题解析：

【考点】本题考查栈的基本概念。
【解析】根据栈“后进先出”的特点，可知选项D中dce均出栈后，栈中仅剩下ab两个元素。但由于a比b先进栈，故a只能在b出栈之后出栈，因此输出序列不可能是dceab。故本题选D。

4、试题答案：A

试题解析：

5、试题答案：D

试题解析：

【考点】本题考查散列（Hash）表及其查找。
【解析】哈希表的平均查找长度取决于下列三个因素：哈希函数，处理冲突的方法和哈希表的装填因子（即饱和程度）。故选项A、B、C正确。哈希表的平均查找长度是装填因子的函数，而不是记录数的函数。由此，不管记录数多大，总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围内。故本题选D。

6、试题答案：A

试题解析：

【考点】本题考查深度优先搜索。
【解析】深度遍历图的过程实质上是对每个顶点的查找其邻接点的过程。其耗费的时间则与所采用的存储结构有关。以邻接表存储时，找邻接点所需的时间为O(e)，因此时间复杂度为O(n+e)。故本题选A。

7、试题答案：B

试题解析：

8、试题答案：B

试题解析：

【考点】本题考查二叉树的主要特征。
【解析】根据完全二叉树的性质，最后一个度不为0的结点是最后一个结点的父节点。由此，序号为3001结点的父结点序号是3001/2=1500，叶子结点个数等于3001-1500=1501。故本题选B。

9、试题答案：C

试题解析：