本文提供2019年408計算機學科專業基礎考研真題答案及解析，以下為具體內容

1、設 n 是描述問題規模的非負整數，下列程序段的時間復雜度是（ ）。

A、

B、

C、

D、

2、若將一棵樹 T 轉化為對應的二叉樹 BT，則下列對 BT 的遍歷中，其遍歷序列與 T 的后根遍歷序列相同的是（ ）。

A、 先序遍歷

B、 中序遍歷

C、 后序遍歷

D、 按層遍歷

3、對 n 個互不相同的符號進行哈夫曼編碼。若生成的哈夫曼樹共有 115 個結點，則 n 的值是（ ）。

A、 56

B、 57

C、 58

D、 60

4、在任意一棵非空平衡二叉樹（AVL 樹）T1 中，刪除某結點 v 之后形成平衡二叉樹T2，再將v插入T2形成平衡二叉樹T3。下列關于T1與T3的敘述中，正確的是（ ）。I. 若v是T1的葉結點，則T1與T3可能不相同II. 若v不是T1的葉結點，則T1與T3一定不相同III. 若v不是T1的葉結點，則T1與T3一定相同

A、 僅I

B、 僅II

C、 僅I、II

D、 僅I、III

5、下圖所示的 AOE 網表示一項包含 8 個活動的工程。活動 d 的最早開始時間和最遲開始時間分別是（ ）。

A、 3和7

B、 12和12

C、 12和14

D、 15和15

6、用有向無環圖描述表達式(x+ y)((x+y)/x)，需要的頂點個數至少是（ ）。

A、 5

B、 6

C、 8

D、 9

7、選擇一個排序算法時，除算法的時空效率，下列因素中，還需要考慮的是（ ）。I. 數據的規模II. 數據的存儲方式 III. 算法的穩定性 IV. 數據的初始狀態

A、 僅III

B、 僅I、II

C、 僅II、III、IV

D、 I、II、III、IV

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

A、 4

B、 5.25

C、 6

D、 6.29

9、設主串T = "abaabaabcabaabc"，模式串S = "abaabc"，采用KMP算法進行模式匹配，到匹配成功時為止，在匹配過程中進行的單個字符間的比較次數是（ ）。

A、 9

B、 10

C、 12

D、 15

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

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