2016年操作系統(tǒng)考研真題答案及解析

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

1、下列程序段的時(shí)間復(fù)雜度是（ ）。sum=0;for(i=0;i<n;i*=2)     for(j=0;j<n;j++)         sum++;

A、O(1)

B、O(n)

C、O(nlogn)

D、O(n²)

2、若某鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則該鏈表最節(jié)省時(shí)間的存儲(chǔ)方式是（ ）。

A、單鏈表

B、單循環(huán)鏈表

C、帶尾指針的單循環(huán)鏈表

D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

3、元素?cái)?shù)a，b，c，d，e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可以停留、可出棧，直到所有元素出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是（ ）。

A、3

B、4

C、5

D、6

4、在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹T的葉結(jié)點(diǎn)個(gè)數(shù)是（ ）。

A、41

B、82

C、113

D、122

5、已知某二叉樹的前序遍歷序列為 ABCDEFGH，中序遍歷序列為CBEDFAGH，則后序遍歷序列為（ ）。

A、HGFEDACB

B、GHEDFCBA

C、CEFDBHGA

D、HGAFDEBC

6、某有向圖G是具有10個(gè)頂點(diǎn)的強(qiáng)連通圖，則G含有邊的數(shù)目至少是（ ）。

A、45

B、90

C、10

D、9

7、

A、2

B、3

C、4

D、5

8、某無(wú)向圖G有n個(gè)頂點(diǎn)，則G的鄰接表中的邊結(jié)點(diǎn)最多有（ ）。

A、n²

B、n(n-1)

C、n(n+1)

D、n(n-1)/2

9、折半查找有序表（2，5，7，10，14，15，18，23，35，41，52）查找關(guān)鍵字14需做的比較次數(shù)為（ ）。

A、2

B、3

C、4

D、5

10、下列選項(xiàng)中，不可能是快速排序第2趟排序結(jié)果的是（ ）。

A、2，3，5，4，6，7，9

B、2，7，5，6，4，3，9

C、3，2，5，4，7，6，9

D、4，2，3，5，7，6，9