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

1、將長度分別為n（n>0）和n2+n 的兩條升序單鏈表合并成長度為n2+2n 的降序單鏈表，則最壞時(shí)間復(fù)雜度是（ ）。

A、O(n)

B、O(n²)

C、O(n²+n)

D、O(n³)

2、字母a，b，c，d，e，f，g依次入棧（stack），最后全部出棧。出棧和入棧可以交替進(jìn)行，但連續(xù)出棧的操作次數(shù)不得超過上次連續(xù)入棧的次數(shù)，除最后的出棧操作外。比如：入棧、出棧、入棧、入棧、入棧、出棧、出棧、入棧…的順序滿足條件，但入棧、入棧、出棧、入棧、入棧、出棧、出棧、出棧…有誤。下面的出棧順序哪些有誤（ ）。I.a，c，f，e，g，d，bII.b，e，d，f，g，c，aIII.c，b，d，a，f，e，gIV.a，b，d，c，f，g，eV.d，c，e，b，g，f，a

A、I，II和V

B、僅III

C、II和IV

D、III和V

3、順序隊(duì)列最多可記錄n個(gè)元素。如果只通過比較front和rear指針的位置來判斷元素的數(shù)量以及隊(duì)列是否為空，則順序隊(duì)列的數(shù)組長度至少是（ ）。

A、n+1

B、2n

C、n

D、nlogn

4、初始為空的二叉檢索樹BST里依次插入值為17，8，12，29，11，13，6，19的結(jié)點(diǎn)。刪除值為8的結(jié)點(diǎn)后得到的 BST，其前序遍歷結(jié)點(diǎn)的值序列是（ ）。I.17，6，12，11，13，29，19II.17，13，6，12，11，29，19III.17，11，6，12，13，29，19IV.17，12，6，11，13，29，19

A、僅I

B、II或III

C、I或III

D、I，II或IV

5、Huffman 編碼樹中所有節(jié)點(diǎn)（含葉節(jié)點(diǎn)）的權(quán)重分別為：0.05，0.15，0.18，0.2，0.26，0.36，0.38，0.62，1.0。則該Huffman 編碼的平均編碼長度是（ ）。

A、3.2

B、2.8

C、3.4

D、3.6

6、對(duì)如下無向圖進(jìn)行廣度優(yōu)先遍歷，結(jié)點(diǎn)序列錯(cuò)誤的是（ ）。

A、a，b，d，c，f，e

B、b，a，c，f，d，e

C、d，a，e，c，f，b

D、d，a，b，e，c，f

7、使用Dijkstra算法計(jì)算如下有向帶權(quán)圖中從源結(jié)點(diǎn)b到達(dá)各結(jié)點(diǎn)的最短路徑，則求得最短路徑的結(jié)點(diǎn)（b除外）依次是（ ）。

A、c，a，d，e，f

B、c，a，e，f，d

C、c，e，a，d，f

D、a，c，e，f，d

8、最大堆中最大的元素在第1層（設(shè)根為第1層），則第二大和第三大的元素所在的位置是（ ）。

A、都在第2層

B、第二大元素在第2層、第三大在第3層

C、第二大元素在第2層、第三大在第2或第3層

D、都不確定

9、對(duì)已排好序的序列進(jìn)行排序，最壞時(shí)間復(fù)雜度為O(n)的排序算法有（ ）。I.選擇排序II.快速排序III.插入排序IV.堆排序V.合并排序I.選擇排序

A、僅IV

B、II和III

C、I和V

D、僅III