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

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

1、广度优先搜索的时间复杂度（ ）。

A、

B、

C、

D、

2、下列说法正确的是（ ）。I.邻接矩阵适用于稠密图II.邻接表适用于稀疏矩阵III. Prim适用于稀疏图IV. Kruskal适用于稠密图

A、I，II

B、I，III

C、II，IV

D、III，IV

3、以3，1，2建成的AVL树，如何平衡（ ）。

A、单左旋

B、单右旋

C、先左旋后双右旋

D、先右旋后双左旋

4、冒泡排序最坏情况下的移动次数（ ）。

A、n（n-1）/2

B、3n（n-1）/2

C、n（n+1）/2

D、3n（n+1）/2

5、以下排序算法不稳定的是（ ）。

A、直接插入排序

B、简单选择排序

C、二路归并

D、基数排序

1、试题答案：D

试题解析：

【考点】本题考查数据结构--图--图的遍历--图的广度优先遍历/搜索。
【解析】在广度优先搜索中，我们按照层次的方式逐步遍历图中的顶点。假设有n个顶点和e条边，那么在最坏情况下，需要遍历所有的顶点和边，所以广度优先搜索的时间复杂度为O(n+e)。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查
1、数据结构--图--图的存储--图的邻接矩阵；
2、数据结构--图--图的存储--图的邻接表；
3、数据结构--图--最小代价生成树--构造最小生成树--Prim算法；
4、数据结构--图--最小代价生成树--构造最小生成树--Kruskal算法。
【解析】Prim适用于稠密图，Kruskal适用于稀疏图，所以III，IV说法错误。故本题选A。

3、试题答案：C

试题解析：

【考点】本题考查数据结构--查找--动态查找表--平衡二叉树--平衡二叉树的应用--平衡二叉树的构造。
【解析】由3，1，2画出的树如下所示，其最小不平衡结点是3，这是因为在其的左孩子的右子树位置插入元素2所导致的，所以需要进行LR型调整，先左旋后双右旋。故本题选C。

4、试题答案：A

试题解析：

【考点】本题考查数据结构--排序--内部排序--起/冒泡排序。
【解析】在冒泡排序的最坏情况下，即待排序序列完全逆序排列时，需要执行n-1趟排序才能将最大元素移动到正确的位置。在每一趟排序中，都会进行相邻元素的比较和可能的交换操作。每次比较都会产生一次移动操作。在第一趟排序中，需要比较n-1对相邻元素，并可能进行n-1次交换。在第二趟排序中，需要比较n-2对相邻元素，并可能进行n-2次交换。依此类推，直到最后一趟排序只需要比较1对相邻元素，并可能进行1次交换。因此，冒泡排序最坏情况下的移动次数可移动次数 = (n-1) + (n-2) + ... + 1 = n(n-1)/2。故本题选A。

5、试题答案：B

试题解析：

【考点】本题考查数据结构--排序--内部排序。
【解析】简单选择排序是一种选择排序算法，其基本思想是每次从待排序的元素中选择最小（或最大）的元素，放到已排序部分的末尾。在选择最小（或最大）元素的过程中，可能会改变具有相同关键字的元素的相对位置，因此简单选择排序是不稳定的排序算法。故本题选B。