2013年408計算機學科專業(yè)基礎考研真題答案及解析

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

1、已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則“最壞情況”下的時間復雜度是（  ）。

A、 O（n）

B、 O（m*n）

C、 O（min（m，n））

D、 O（max（m，n））

2、一個棧的入棧序列為1，2，3… n，其出棧序列是p1，p2，p3...pn。若p2=3，則p3可能取值的個數(shù)是（  ）。

A、 n-3

B、 n-2

C、 n-1

D、 無法確定

3、若將關鍵字1， 2， 3， 4， 5， 6， 7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結點的個數(shù)是（  ）。

A、 0

B、 1

C、 2

D、 3

4、已知三叉樹T中6個葉結點的權分別是2，3， 4，5， 6， 7， T的帶權（外部）路徑長度最小是（  ）。

A、 27

B、 46

C、 54

D、 56

5、若X是后序線索二叉樹中的葉結點，且X存在左兄弟結點Y，則X的右線索指向的是（  ）。

A、 X的父結點

B、 以Y為根的子樹的最左下結點

C、 X的左兄弟結點Y

D、 以Y為根的子樹的最右下結點

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

A、 僅I、III

B、 僅I、IV

C、 僅II、III

D、 僅II、IV

7、設圖的鄰接矩陣A如下所示。各頂點的度依次是：

A、 1，2，1，2

B、 2，2，1，1

C、 3，4，2，3

D、 4，4，2，2

8、若對如下無向圖進行遍歷，則下列選項中，不是廣度優(yōu)先遍歷序列的是（  ）。

A、 h，c，a，b，d，e，g，f

B、 e，a，f，g，b，h，c，d

C、 d，b，c，a，h，e，f，g

D、 a，b，c，d，h，e，f，g

9、下列AOE網表示一項包含8個活動的工程。通過同時加快若干活動的進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短工程工期的是（  ）。

A、 c和e

B、 d和e

C、 f和d

D、 f和h

10、在一株高度為2的5階B樹中，所含關鍵字的個數(shù)最少是（  ）。

A、 5

B、 7

C、 8

D、 14