考研408計(jì)算機(jī)統(tǒng)考分兩部分，80分單項(xiàng)選擇題和70分大題，滿分150分。單項(xiàng)選擇題總共80分，每小題2分，40小題。單項(xiàng)選擇題，1-10題是數(shù)據(jù)結(jié)構(gòu)部分；11-22題是計(jì)算機(jī)組成原理部分；23-32題是操作系統(tǒng)部分；33-40題是計(jì)算機(jī)網(wǎng)絡(luò)部分。綜合應(yīng)用題70分，共7小題，41和42題是數(shù)據(jù)結(jié)構(gòu)題，分值各為10分和15分；43和44題是計(jì)算機(jī)組成原理題，各占8分和13分；45和46題是操作系統(tǒng)題，各占7分和8分；47題是計(jì)算機(jī)網(wǎng)絡(luò)題，分值為9分。為了方便大家更好的來(lái)備考，小編為大家整理了“2019年408計(jì)算機(jī)考研真題”，希望可以幫助大家更好的復(fù)習(xí)408計(jì)算機(jī)考研內(nèi)容。

2019年考研408計(jì)算機(jī)統(tǒng)考考研真題

一、單項(xiàng)選擇題（第1～40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)最符合試題要求）

1、設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下列程序段的時(shí)間復(fù)雜度是（  ）。

x=0;

while(n>=(x+1)*(x+1))

x=x+1

A.O(logn)

B.O(n1/2)

C.O(n)

D.O(n2)

2、若將一棵樹(shù)T轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)BT，則下列對(duì)BT的遍歷中，其遍歷序列與T的后根遍歷序列相同的是（  ）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

3、對(duì)n個(gè)互不相同的符號(hào)進(jìn)行哈夫曼編碼。若生成的哈夫曼樹(shù)共有115個(gè)結(jié)點(diǎn)，則n的值是（  ）。

A.56

B.57

C.58

D.60

4、在任意一棵非空平衡二叉樹(shù)（AVL樹(shù)）T1中，刪除某結(jié)點(diǎn)v之后形成平衡二叉樹(shù)T2，再將v插入T2形成平衡二叉樹(shù)T3。下列關(guān)于T1與T3的敘述中，正確的是（  ）。

I.若v是T1的葉結(jié)點(diǎn)，則T1與T3可能不相同

II.若v不是T1的葉結(jié)點(diǎn)，則T1與T3一定不相同

III.若v不是T1的葉結(jié)點(diǎn)，則T1與T3一定相同

A.僅I

B.僅II

C.僅I、II

D.僅I、III

5、下圖所示的AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程?；顒?dòng)d的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間分別是（  ）。

A.3和7

B.12和12

C.12和14

D.15和15

6、用有向無(wú)環(huán)圖描述表達(dá)式(x+y)((x+y)/x)，需要的頂點(diǎn)個(gè)數(shù)至少是（  ）。

A.5

B.6

C.8

D.9

7、選擇一個(gè)排序算法時(shí)，除算法的時(shí)空效率，下列因素中，還需要考慮的是（  ）。

I.數(shù)據(jù)的規(guī)模

II.數(shù)據(jù)的存儲(chǔ)方式

III.算法的穩(wěn)定性

IV.數(shù)據(jù)的初始狀態(tài)

A.僅III

B.僅I、II

C.僅II、III、IV

D.I、II、III、IV

8、現(xiàn)有長(zhǎng)度為11且初始為空的散列表HT，散列函數(shù)是H(key)=key%7，采用線性探查(線性探測(cè)再散列)法解決沖突。將關(guān)鍵字序列87，40，30，6，11，22，98，20依次插入HT后，HT查找失敗的平均查找長(zhǎng)度是（  ）。

A.4

B.5.25

C.6

D.6.29

9、設(shè)主串T="abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法進(jìn)行模式匹配，到匹配成功時(shí)為止，在匹配過(guò)程中進(jìn)行的單個(gè)字符間的比較次數(shù)是（  ）。

A.9

B.10

C.12

D.15

10、排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一“趟”。下列序列中，不可能是快速排序第二趟結(jié)果的是（  ）。

A.5，2，16，12，28，60，32，72

B.2，16，5，28，12，60，32，72

C.2，12，16，5，28，32，72，60

D.5，2，12，28，16，32，72，60