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

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

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

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

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

A、 5

B、 7

C、 8

D、 11

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

A、 只有e

B、 有e、b

C、 有e、c

D、 無法確定

4、若平衡二叉樹的高度為6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為（  ）。

A、 10

B、 20

C、 32

D、 33

5、對(duì)有n個(gè)結(jié)點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是（  ）。

A、 O（n）

B、 O（e）

C、 O（n+e）

D、 O（ne）

6、若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（  ）。

A、 存在，且唯一

B、 存在，且不唯一

C、 存在，可能不唯一

D、 無法確定是否存在

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

A、 d，e，f

B、 e，d，f

C、 f，d，e

D、 f，e，d

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

A、僅I

B、僅II

C、僅I、III

D、僅II、IV