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

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

1、在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数是（ ）。

A、n

B、n/2

C、(n-1)/2

D、(n+1)/2

2、一个队列的入队序列是1、2、3、4，则队列的输出序列是（ ）。

A、4、3、2、1

B、1、2、3、4

C、1、4、3、2

D、3、2、4、1

3、有一顺序栈，元素S1、S2、S3、S4、S5、S6依次入栈，如果6个元素出栈的顺序是S2、S3、S4、S6、S5、S1，则栈的容量至少应该是（ ）。

A、2

B、3

C、5

D、6

4、下面二叉树中，一定是完全二叉树的是（ ）。

A、平衡二叉树

B、满二叉树

C、单枝二叉树

D、二叉排序树

5、已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，其前序遍历序列是（ ）。

A、acbed

B、baedc

C、dceab

D、cedba

6、在有n个叶子结点的赫夫曼树中，其结点总数是（ ）。

A、不确定

B、2n

C、2n+1

D、2n-1

7、含有n个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。

A、1

B、n/2

C、n-1

D、n

8、设哈希表长m=14，哈希函数H(key)=key % 11，表中已有4个结点，其存放地址分别是4、5、6、7，其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点地址应是（ ）。

A、3

B、8

C、9

D、10

1、试题答案：C

试题解析：

删除位置的范围是1~n。删除第1个结点时所需移动结点的次数是n-1，删除第2个结点时需比较的结点个数是n-2，以此类推，删除第i个结点时需比较的结点个数是n-i，删除第n个结点时需比较的结点个数是0。因此需平均比较的结点个数是[n×(n-1+0)/2]/n=(n-1)/2。故本题选C。

2、试题答案：B

试题解析：

队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。因此元素的入队序列等于元素的出队序列。故本题选B。

3、试题答案：B

试题解析：

栈是限定仅在表尾进行插入或删除操作的线性表，又被称为后进先出的线性表。整个顺序栈的运行过程如下表所示。

整个运行过程中栈中元素最多的时候有3个，S的容量至少为3。故本题选B。

4、试题答案：B

试题解析：

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。完全二叉树是指深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。故满二叉树是一种特殊的完全二叉树。故本题选B。

5、试题答案：B

试题解析：

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

6、试题答案：D

试题解析：

7、试题答案：C

试题解析：

在无向图G中，如果从某个顶点到另一个顶点有路径，则称这两个定点是连通的。如果对于图中任意两个顶点都是连通的，则称G是连通图。序列中顶点不重复出现的路称为简单路径。因此含有n个顶点的连通图中的任意一条简单路径，其长度不可能超过n-1。故本题选C。

8、试题答案：D

试题解析：