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