2020年操作系統(tǒng)考研真題答案及解析（一）

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

1、含有m個結點的二叉樹鏈式存儲結構中空指針的個數為（ ）。

A、2m

B、m-1

C、m+1

D、m

2、下列排序算法中元素的移動次數和關鍵字的初始排列次序無關的是（ ）。

A、快速排序

B、插入排序

C、選擇排序

D、希爾排序

E、無正確答案

3、一個棧的進棧序列是a b c d e，則棧的輸出序列不可能的是（ ）。

A、a b c d e

B、e d c b a

C、d e c b a

D、d c e a b

4、需要的輔助空間最多的排序算法為（ ）。

A、歸并排序

B、快速排序

C、基數排序

D、堆排序

5、哈希表的平均查找長度說法錯誤的是（ ）。

A、與處理沖突方法有關而與表的長度無關

B、與選用的哈希函數有關

C、與哈希表的飽和程度有關

D、與表中填入的記錄數有關

6、有n個頂點、e條邊且使用了鄰接表存儲的有向圖進行深度優(yōu)先遍歷，其算法的時間復雜度是（ ）。

A、O（n+e）

B、

C、O（n+2e）

D、O（n*e）

7、已知一個長度為11的順序表，其元素按關鍵字有序排列，若采用折半查找查找一個其中不存在的元素，則關鍵字的比較次數最多是（ ）。

A、3

B、4

C、5

D、6

8、一棵完全二叉樹上有3001個結點，其中葉子結點的個數是（ ）。

A、1500

B、1501

C、1000

D、1001

9、若一棵二叉樹度為2的結點有18個，度為1的結點有10個，則度為0的結點個數是（ ）。

A、46

B、28

C、19

D、17