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

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

1、x为树T的非根结点，bt为x所在的二叉树。在bt中，x是双亲节点的右孩子，则在树T中x（ ）。

A、一定是叶子结点

B、一定有左兄弟

C、一定没有右兄弟

D、一定没有左兄弟

2、在平衡二叉树中，A是最小不平衡子树，它的左孩子平衡因子为1，右孩子平衡因子为0，其中平衡因子为左子树高度-右子树高度，问需要对失衡子树做（ ）调整？

A、LR

B、RR

C、RL

D、LL

3、使用Dijkstra算法求下图从顶点3到其它各顶点的最短路径，先后求得的最短路径顶点顺序为（ ）。

A、5，1，2，6，4

B、5，2，1，6，4

C、5，4，6，2，1

D、5，3，6，1，4

4、下列哪一项为稳定排序（ ）。

A、快速排序

B、堆排序

C、归并排序

D、选择排序

5、C（n）表示二叉排序树有n个结点时可以出现的形态数量，则C（1）、C（2）、C（3）、C（4）分别为（ ）？

A、1，2，4，14

B、1，2，5，14

C、1，2，4，8

D、1，2，5，8

1、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--树转换为二叉树。
【解析】举例分析，下图中树转换为二叉树满足题干所给的条件。但是，在树中x不是叶子结点，有左兄弟，也有右兄弟。因此，可以排除选项A、C和D。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查数据结构--查找--动态查找表--平衡二叉树--平衡二叉树的应用。
【解析】下图满足题干条件，其中h代表子树的高度。由此可知是在A的左孩子的左子树中插入结点导致A这棵子树不平衡的，所以应该进行LL型调整。故本题选D。

3、试题答案：A

试题解析：

【考点】本题考查数据结构--图--最短路径--从某顶点到其余各顶点的最短路径--Dijkstra算法。
【解析】用迪杰斯特拉算法分析顶点3到各个顶点的最短路径如下所示，由此知，先后求得的最短路径顶点顺序为5，1，2，6，4。故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查数据结构--排序--内部排序。
【解析】由下表知，归并排序为稳定排序。故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查数据结构--查找--动态查找表--二叉排序树。
【解析】
（1）C（1）= 1毋庸置疑；
（2）C（2）固定根结点，剩下一个结点可以是左孩子，可以是右孩子，C（2）=C（1）+ C（1）=2；
（3）C（3）固定根结点，剩下两个结点可以左0右2、左1右1、左2右0组合，因此C（3）=C（0）× C（2）+ C（1）× C（1）+ C（2）× C（0）=5；
（4）C（4）固定根结点，剩下三个结点可以左0右3、左1右2、左2右1、左3右0，C（4）=C（0）× C（3）+ C（1）×C（2）+ C（2）× C（1）+ C（3）× C（0）=14。
因此，C（1）、C（2）、C（3）、C（4）分别为1，2，5，14。故本题选B。