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

1、求整數n （n≥0）階乘的算法如下，其時間復雜度是

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

2、已知操作符包括‘+’、‘-’、‘*’、 ‘/’、‘（’ 和‘）’。將中綴表達式a+b- a*（（c+d）/e-f）+g轉換為等價的后綴表達式ab+acd+e/f-*-g+時，用棧來存放暫時還不能確定運算次序的操作符，若棧初始時為空，則轉換過程中同時保存在棧中的操作符的最大個數是（  ）。

A、 5

B、 7

C、 8

D、 11

3、 若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結點的孩子結點（  ）。

A、 只有e

B、 有e、b

C、 有e、c

D、 無法確定

4、若平衡二叉樹的高度為6，且所有非葉結點的平衡因子均為1，則該平衡二叉樹的結點總數為（  ）。

A、 10

B、 20

C、 32

D、 33

5、對有n個結點、e條邊且使用鄰接表存儲的有向圖進行廣度優先遍歷，其算法時間復雜度是（  ）。

A、 O（n）

B、 O（e）

C、 O（n+e）

D、 O（ne）

6、若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該圖拓撲序列的結論是（  ）。

A、 存在，且唯一

B、 存在，且不唯一

C、 存在，可能不唯一

D、 無法確定是否存在

7、如圖所示的有向帶權圖，若采用迪杰斯特拉（Dijkstra）算法求從源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標頂點是b，第二條最短路徑的目標頂點是c，后續得到的其余各最短路徑的目標頂點依次是（  ）。

A、 d，e，f

B、 e，d，f

C、 f，d，e

D、 f，e，d

8、下列關于最小生成樹的敘述中，正確的是（  ）。I. 最小生成樹的代價唯一II. 所有權值最小的邊一定會出現在所有的最小生成樹中III. 使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同IV. 使用普里姆算法和克魯斯卡爾（Kruskal） 算法得到的最小生成樹總不相同

A、僅I

B、僅II

C、僅I、III

D、僅II、IV