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

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

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

A、1000

B、1001

C、500

D、499

2、将长度为n的单链表链接在长度为m的单链表之后算法时间复杂度为（ ）。

A、O(1)

B、O(n)

C、O(m)

D、O(n+m)

3、没有一个栈，元素进栈的顺序为a、b、c、d、e，下列出栈序列中不可能的是（ ）。

A、a、b、c、d、e

B、b、c、d、e、a

C、e、a、b、c、d

D、e、d、c、b、a

4、设二维数组A[m][n]，A[0][0]存放位置为644，A[2][2]存放位置在676，每个元素占一个空间，则A[4][5]的地址是（ ）。

A、692

B、626

C、709

D、724

5、广义表A((a),a)的表头和表尾是（ ）。

A、(a),(a)

B、(a),a

C、a,(a)

D、(a),((a))

6、高度为h的二叉树上只有度为0和度为2的节点，则此类二义树中所包含的节点数至少为（ ）。

A、2h

B、2h-1

C、2h+1

D、h+1

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

A、EGFACDB

B、EACBDGF

C、EAGCFBD

D、EGAFCDB

8、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ）。

A、29

B、37

C、46

D、44

1、试题答案：C

试题解析：

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

2、试题答案：C

试题解析：

题目中要求将长度为n的单链表链接在长度为m的单链表之后，因此需要遍历长度为m的单链表，该操作的时间复杂度为O(m)；获取该链表的尾结点之后，将长度为n的单链表的头结点接在该尾结点之后即可，该操作的时间复杂度为O(1)。故本题选C。

3、试题答案：C

试题解析：

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

4、试题答案：C

试题解析：

由于存储单元是一维的结构，而数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。对二维数组可有两种存储方式：一种以列序为主序的存储方式；一种是以行序为主序的存储方式。由于题中未明确说明存储方式，因此需对两种情况都进行求解。当二维数组以行序为主序存储时，A[0][0]作为第1个元素的存放位置为644，A[2][2]作为第676-644+1=33个元素存放在676，由公式2×n+2=33-1解得n=15，表明该数组每行有15个元素，因此A[4][5]的地址=4×15+5+644=709。选项C正确。依此类推，当二维数组以列序为主序存储时，该数组每列有15个元素，因此A[4][5]的地址=5×15+4+644=723，选项中无此答案。故本题选C。

5、试题答案：A

试题解析：

6、试题答案：B

试题解析：

当高度为1，由于二叉树中只有度为0和度为2的节点，二叉树中只有一个结点，因此可以排除选项A、C、D。故本题选B。

7、试题答案：B

试题解析：

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

故本题选B。

8、试题答案：D

试题解析：

由题中四个结点构造的哈夫曼树如下图所示。

因此带权路径长度WPL=9×1+7×2+2×3+5×3=44，故本题选D。