本文提供2016年操作系統考研真題答案及解析，以下為具體內容

1、下列程序段的時間復雜度是（ ）。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、若某鏈表最常用的操作是在末尾插入結點和刪除尾結點，則該鏈表最節省時間的存儲方式是（ ）。

A、單鏈表

B、單循環鏈表

C、帶尾指針的單循環鏈表

D、帶頭結點的雙循環鏈表

3、元素數a，b，c，d，e依次進入初始為空的棧中，若元素進棧后可以停留、可出棧，直到所有元素出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數是（ ）。

A、3

B、4

C、5

D、6

4、在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉結點個數是（ ）。

A、41

B、82

C、113

D、122

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

A、HGFEDACB

B、GHEDFCBA

C、CEFDBHGA

D、HGAFDEBC

6、某有向圖G是具有10個頂點的強連通圖，則G含有邊的數目至少是（ ）。

A、45

B、90

C、10

D、9

7、

A、2

B、3

C、4

D、5

8、某無向圖G有n個頂點，則G的鄰接表中的邊結點最多有（ ）。

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）查找關鍵字14需做的比較次數為（ ）。

A、2

B、3

C、4

D、5

10、下列選項中，不可能是快速排序第2趟排序結果的是（ ）。

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