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

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

1、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A、n

B、2n-1

C、2n

D、n-1

2、表长为1000的顺序存储的线性表，当在任何一个位置上插入一个元素的概率相等时，插入一个新元素所需移动元素的平均个数为（ ）。

A、1000

B、1001

C、500

D、499

3、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6，e7依次通过栈S，一个元素出栈后即进入队列Q，如果六个元素出队的序列为e2，e4，e3，e6，e5，e1，e7则栈S的容量至少是（ ）。

A、6

B、4

C、3

D、2

4、二维数组A[10..20,5..10]采用行序存储，每个数据元素占用4个存储单元，且A[10, 5]的存储地址是1000，则A[20, 9]的地址是（ ）。

A、1212

B、1256

C、1368

D、1364

5、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点个数为（ ）。

A、4

B、5

C、6.

D、7

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

A、EGFACDB

B、EACBDGF

C、EAGCFBD

D、EGAFCDB

7、有13个叶子节点的哈夫曼树总的节点个数为（ ）。

A、12

B、13

C、25

D、26

8、如果具有n个顶点的图是一个环，则它有（ ）棵生成树。

A、n

B、2n

C、n-1

D、n+1

1、试题答案：A

试题解析：

当第一个有序表中的元素均大于或均小于第二个有序表中的元素时，此时比较次数最少，为n。故本题选A。

2、试题答案：C

试题解析：

插入位置的范围是1~n+1。在第一个位置上插入一个元素需要移动1000个元素，在第二个位置上插入一个元素需要移动999个元素，以此类推，在第i个位置上插入一个元素需要移动1001-i个元素。因此，插入一个新元素所需移动元素的平均个数为((0+1000)×1001/2)/1001=500个。故本题选C。

3、试题答案：C

试题解析：

栈是限定仅在表尾进行插入或删除操作的线性表，又被称为后进先出的线性表。队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。因此六个元素的出栈顺序=六个元素的入队序列=六个元素的出队序列。
整个顺序栈的运行过程如下表所示。

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

4、试题答案：B

试题解析：

由于存储单元是一维的结构，而数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。对二维数组可有两种存储方式：一种以列序为主序的存储方式；一种是以行序为主序的存储方式。由题可知，每行有10-5+1=6个元素，一共有20-10+1=11行。A[10, 5]是第1行的第1个元素，A[20, 9]是第11行的第5个元素，因此[20, 9]的地址是1000+[(11-1)×6+(5-1)]×4=1256。故本题选B。

5、试题答案：C

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2+n3（结点数量）=n₁+2n₂+3n₃+1（边数量+1）。由此，代入数值可知，n₀=2n₃+n₂+1=4+1+1=6个。故本题选C。

6、试题答案：B

试题解析：

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

故本题选B。

7、试题答案：C

试题解析：

8、试题答案：A

试题解析：

第一个顶点和最后一个顶点相同的路径称为回路或环。具有n个顶点的环具有n条边，一棵有n个顶点的生成树有且仅有n-1条边。因此含有n个顶点的环去掉任意一条边可构成一棵生成树。故本题选A。