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

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

1、含有m個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中空指針的個(gè)數(shù)為（ ）。

A、2m

B、m-1

C、m+1

D、m

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

A、快速排序

B、插入排序

C、選擇排序

D、希爾排序

E、無(wú)正確答案

3、一個(gè)棧的進(jìn)棧序列是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、哈希表的平均查找長(zhǎng)度說(shuō)法錯(cuò)誤的是（ ）。

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

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

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

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

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

A、O（n+e）

B、

C、O（n+2e）

D、O（n*e）

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

A、3

B、4

C、5

D、6

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

A、1500

B、1501

C、1000

D、1001

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

A、46

B、28

C、19

D、17