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

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

1、从一个具有n个结点的单链表中检索其值等于x的结点时，在检索成功的情况下，需平均比较的结点个数是（ ）。

A、n/2

B、n

C、(n+1)/2

D、(n-1)/2

2、设双向循环链表中结点的结构为(data,lLink,rLink)，且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行的操作是（ ）。

A、p->rLink=s;s->lLink=p;p->rLink->lLink=s;s->rLink=p->rLink;

B、p->rLink=s;p->rLink->lLink=s;s->lLink=p;s->rLink=p->rLink;

C、s->lLink=p;s->rLink=p->rLink;p->rLink=s;p->rLink->lLink=s;

D、s->lLink=p;s->rLink=p->rLink;p->rLink->lLink=s;p->rLink=s;

3、单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（ ）。

A、O(n)

B、O(1)

C、O(n²)

D、O(nlogn)

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，后序序列为ACBEDGF，则前序序列为（ ）。

A、FGDBACE

B、FDEBACG

C、FDBACEG

D、FDBCAEG

7、有5个字符，根据其使用频率设计对应的赫夫曼编码，则不可能的赫夫曼编码是（ ）。

A、000，001，010，011，1

B、0000，0001，001，01，1

C、000，001，01，10，11

D、00，100，101，110，111

8、在一个具有8个顶点的有向图中，若所有顶点的出度之和为10， 则所有顶点的入度之和为（ ）。

A、7

B、8

C、9

D、10

1、试题答案：C

试题解析：

检索位置的范围是1~n。在检索成功的情况下，检索第1个结点时需比较的结点个数是1，检索第2个结点时需比较的结点个数是2，以此类推，检索第i个结点时需比较的结点个数是i，检索第n个结点时需比较的结点个数是n。因此需平均比较的结点个数是[n×(n+1)/2]/n=(n+1)/2。故本题选C。

2、试题答案：D

试题解析：

假设未插入s前p的后继结点为q，选项A和选项B第一步都实现了p的后继节点修改为s，因此失去了与q的联系，无法修改q的相关指针。故选项A、B错误。选项C中执行完第一步至第三步，已经成功修改p的后继指针，s的前驱和后继指针，第四步中由于p的后继节点修改为s，因此无法指向q结点。故选项C错误。故本题选D。

3、试题答案：A

试题解析：

需要遍历长度为n的单循环链表，该操作的时间复杂度为O(n)；获取该队列的尾结点之后，将元素插入在该尾结点之后即可，该操作的时间复杂度为O(1)。故本题选A。

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

试题解析：

6、试题答案：C

试题解析：

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

7、试题答案：D

试题解析：

根据哈夫曼树的构造思想可知，哈夫曼树仅存在度为2的结点和度为0的叶子结点。根据左0右1，四个选项对应的哈夫曼树如下图所示。由图可知，选项D中出现了度为1的结点。故本题选D。

8、试题答案：D

试题解析：

顶点的度是指和顶点相关联的边的数目。对于无向图而言，每条边都与两个顶点相关联，所有顶点的度数之和等于所有边数的两倍。对于有向图而言，每条边都对应着一个顶点的一个入度和另一个顶点的一个出度，所有顶点的入度之和等于出度之和，等于所有边数的两倍。故本题选D。