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

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

1、含有m個結(jié)點的二叉樹鏈式存儲結(jié)構(gòu)中空指針的個數(shù)為（ ）。

A、2m

B、m-1

C、m+1

D、m

2、下列排序算法中元素的移動次數(shù)和關(guān)鍵字的初始排列次序無關(guān)的是（ ）。

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、基數(shù)排序

D、堆排序

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

A、與處理沖突方法有關(guān)而與表的長度無關(guān)

B、與選用的哈希函數(shù)有關(guān)

C、與哈希表的飽和程度有關(guān)

D、與表中填入的記錄數(shù)有關(guān)

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

A、O（n+e）

B、

C、O（n+2e）

D、O（n*e）

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

A、3

B、4

C、5

D、6

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

A、1500

B、1501

C、1000

D、1001

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

A、46

B、28

C、19

D、17