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

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

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

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

2、元素a，b，c，d，e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是（  ）。

A、 3

B、 4

C、 5

D、 6

3、已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A[0...n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是（  ）。

A、 0，0

B、 0，n-1

C、 n-1，0

D、 n-1，n-1

4、 若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是（  ）。

A、 257

B、 258

C、 384

D、 385

5、若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1，2，3，4和4，3，2，1，則該二叉樹的中序遍歷序列不會(huì)是（  ）。

A、 1，2，3，4

B、 2，3，4，1

C、 3，2，4，1

D、 4，3，2，1

6、已知一棵有2011個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)為116，該樹對(duì)應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)是（  ）。

A、 115

B、 116

C、 1895

D、 1896

7、對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是（  ）。

A、 95，22，91，24，94，71

B、 92，20，91，34，88，35

C、 21，89，77，29，36，38

D、 12，25，71，68，33，34

8、下列關(guān)于圖的敘述中，正確的是（ ）。Ⅰ.回路是簡單路徑Ⅱ.存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間Ⅲ.若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路

A、 僅Ⅱ

B、 僅Ⅰ、Ⅱ

C、 僅Ⅲ

D、 僅Ⅰ、Ⅲ

9、為提高散列（Hash）表的查找效率，可以采取的正確措施是（  ）。Ⅰ. 增大裝填（載）因子Ⅱ. 設(shè)計(jì)沖突（碰撞）少的散列函數(shù)Ⅲ. 處理沖突（碰撞）時(shí)避免產(chǎn)生聚集（堆積）現(xiàn)象

A、 僅Ⅰ

B、 僅Ⅱ

C、 僅Ⅰ、Ⅱ

D、 僅Ⅱ、Ⅲ

10、為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲(chǔ)方式是（  ）。

A、 順序存儲(chǔ)

B、 散列存儲(chǔ)

C、 鏈?zhǔn)酱鎯?chǔ)

D、 索引存儲(chǔ)