本文提供2013年操作系統(tǒng)考研真題答案及解析，以下為具體內(nèi)容

1、從一個具有n個結(jié)點(diǎn)的單鏈表中檢索其值等于x的結(jié)點(diǎn)時(shí)，在檢索成功的情況下，需平均比較的結(jié)點(diǎn)個數(shù)是（ ）。

A、n/2

B、n

C、(n+1)/2

D、(n-1)/2

2、設(shè)雙向循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,lLink,rLink)，且不帶表頭結(jié)點(diǎn)。若想在指針p所指結(jié)點(diǎn)之后插入指針s所指結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作是（ ）。

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、單循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針，則入隊(duì)的時(shí)間復(fù)雜度為（ ）。

A、O(n)

B、O(1)

C、O(n²)

D、O(nlogn)

4、二維數(shù)組A[10..20,5..10]采用行序存儲，每個數(shù)據(jù)元素占用4個存儲單元，且A[10, 5]的存儲地址是1000，則A[20, 9]的地址是（ ）。

A、1212

B、1256

C、1368

D、1364

5、在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個，則度為0的結(jié)點(diǎn)個數(shù)為（ ）。

A、4

B、5

C、6.

D、7

6、某二叉樹中序序列為ABCDEFG，后序序列為ACBEDGF，則前序序列為（ ）。

A、FGDBACE

B、FDEBACG

C、FDBACEG

D、FDBCAEG

7、有5個字符，根據(jù)其使用頻率設(shè)計(jì)對應(yīng)的赫夫曼編碼，則不可能的赫夫曼編碼是（ ）。

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個頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為10， 則所有頂點(diǎn)的入度之和為（ ）。

A、7

B、8

C、9

D、10