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

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

1、若某线性表最常用的操作是存取第i个元素及其前驱的值，则采用（ ）存储方式更节省操作时间。

A、单链表

B、双链表

C、单循环链表

D、顺序表

2、设有两个指针p和q分别指向某单链表中的两个元素，若p所指向元素为q所指向元素的前驱，则（ ）成立。

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

B、q->next==p

C、p->next==q

D、p==q

3、在长度为10的顺序表中删除元素可能需要移动若干元素，最坏情况下的删除需要移动的元素个数是（ ）。

A、10

B、9

C、8

D、7

4、为了防止队列发生假溢出，应该（ ）。

A、定义足够大的存储空间

B、及时进行出队操作

C、及时进行入队操作

D、采用循环队列

5、设一个栈的输入序列为a、b、c、d，则借助该栈所得到的输出序列不可能是（ ）。

A、a、b、c、d

B、d、a、b、c

C、a、c、d、b

D、d、c、b、a

6、一个三对角矩阵An×n按行压缩存储到一维数组B中，则B的长度至少是（ ）。

A、3n+1

B、3n

C、3n-1

D、3n-2

7、一棵二叉树结点的（ ）可唯一确定一棵二叉树。

A、前序序列和中序序列

B、前序序列和后序序列

C、中序序列

D、后序序列

8、在下列算法中，用以生成最短路径的算法是（ ）。

A、Prim算法

B、Kruskal算法

C、Dijkstra算法

D、Huffman算法

9、某无向连通图具有n个顶点，则其生成树的边数为（ ）。

A、n-1

B、n-2

C、n/2

D、1

10、对二叉查找树（Binary Search Tree）进行（ ）可得到关键字升序序列。

A、中序遍历

B、先序遍历

C、层次遍历

D、后序遍历

1、试题答案：D

试题解析：

选项A、B和C中的三个存储结构在存取第i个元素及其前驱的值，都需遍历数组，时间复杂度为O(n)。故本题选D。

2、试题答案：C

试题解析：

p所指向元素为q所指向元素的前驱，那么q所指向元素的后继为p所指向的元素。故本题选C。

3、试题答案：B

试题解析：

顺序表中第一个位置上删除一个元素时，需将后面第2个元素至第n个元素均向前移动一位。故本题选B。

4、试题答案：D

试题解析：

在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。假溢出是指不可再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破坏，然而队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列臆造为一个环状的空间，即采用循环队列，充分利用数组空间。故本题选D。

5、试题答案：B

试题解析：

栈是限定仅在表尾进行插入或删除操作的线性表。选项A中栈的操作过程是：a入栈、a出栈、b入栈、b出栈、c入栈、c出栈、d入栈、d出栈；选项C中栈的操作过程是：a入栈、a出栈、b入栈、c入栈、c出栈、d入栈、d出栈、b出栈；选项D中栈的操作过程是：a入栈、b入栈、c入栈、d入栈、d出栈、c出栈、b出栈、a出栈；选项B中栈在d出栈后，栈顶的元素是c，此时a需要c、b出栈之后再出栈。故本题选B。

6、试题答案：D

试题解析：

在三对角矩阵中，除了主对角线上和直接在对角线，上、下方两条对角线上的元之外，所有其他的元素皆为零。因此第一行需要存储的元素为2，第n行需要存储的元素为2，其他行每行需要存储的元素为3，因此B的长度至少是3n-2。故本题选D。

7、试题答案：A

试题解析：

前序遍历的遍历规则是根左右，中序遍历的遍历规则是左根右，后序遍历的遍历规则是左右根。一棵二叉树结点的前序序列和中序序列或后序序列和中序序列可唯一确定一棵二叉树。故本题选A。

8、试题答案：C

试题解析：

Prim算法和Kruskal算法用以生成最小生成树，Huffman算法用以生成带权路径长度最短的树。故本题选C。

9、试题答案：A

试题解析：

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

10、试题答案：A

试题解析：

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