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