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

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

1、在下列选项中，使用顺序表比链表好的运算是（ ）。

A、插入

B、删除

C、根据序号查找

D、根据元素值查找

2、栈和队列的共同点是（ ）。

A、都是先进先出

B、都是先进后出

C、只允许在端点处插入和删除元素

D、没有共同点

3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入a结点，则执行（ ）。

A、p->next=a;a->next=q;

B、p->next=a->next;a->next=p;

C、q->next=a;a->next=p;

D、a->next=p->next;p->next=a;

4、二叉树第i层上最多有（ ）个结点。

A、2ⁱ

B、2ⁱ-1

C、2^i-1

D、不可确定。

5、某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列为（ ）。

A、EGFACDB

B、EACBDGF

C、EAGCFBD

D、EGAFCDB

6、以中序遍历一棵二叉排序树，得到的序列是（ ）。

A、升序

B、降序

C、分块有序

D、无序

7、一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。

A、极小连通子图

B、极小子图

C、极大连通子图

D、极大子图

8、一个有n个顶点的有向图最多有（ ）条弧。

A、n

B、n(n-1)

C、n(n-1)/2

D、2n

1、试题答案：C

试题解析：

长度为n的顺序表的插入、删除和根据元素值查找这三个操作的时间复杂度均为O(n)，根据序号查找操作的时间复杂度均为O(1)，长度为n的链表的插入和删除这两个操作的时间复杂度均为O(1)，根据元素值查找和根据序号查找操作的时间复杂度均为O(n)。故本题选C。

2、试题答案：C

试题解析：

栈是限定仅在表尾进行插入或删除操作的线性表，又被称为后进先出的线性表。队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。两者均只允许在端点处插入和删除元素。故本题选C。

3、试题答案：C

试题解析：

由题目可知，p所指结点是q所指结点的后继结点。在未插入a结点之前，q->next=p。若想在q和p之间插入a结点，需将q所指结点的后继结点修改为a，a所指结点的后继结点修改为p。故本题选C。

4、试题答案：C

试题解析：

利用归纳法容易证得此性质。
i=1时，只有一个根结点。显然，2^i-1=2⁰=1是对的。
现在假定对所有的j，1≤j<i，命题成立，即第j层上至多有2^i-1个结点。那么，可以证明j=i时命题也成立。
由归纳假设：第i-1层上至多有2^i-2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2×2^i-2=2^i-1。
故本题选C。

5、试题答案：B

试题解析：

根据中序和后序遍历的结果确定二叉树的过程如下图所示。此后根据先序遍历的算法思想可获得先序遍历序列。

故本题选B。

6、试题答案：A

试题解析：

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

7、试题答案：A

试题解析：

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。故本题选A。

8、试题答案：B

试题解析：

对于无向图，边的取值范围是0到n(n-1)/2。有n(n-1)/2条边的无向图称为完全图。对于有向图，e的取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。故本题选B。