2019年408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)考研真題答案及解析

本文提供2019年408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)考研真題答案及解析，以下為具體內(nèi)容

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

A、

B、

C、

D、

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