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

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

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

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

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

A、 3

B、 4

C、 5

D、 6

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

A、 0，0

B、 0，n-1

C、 n-1，0

D、 n-1，n-1

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

A、 257

B、 258

C、 384

D、 385

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

A、 1，2，3，4

B、 2，3，4，1

C、 3，2，4，1

D、 4，3，2，1

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

A、 115

B、 116

C、 1895

D、 1896

7、對于下列關(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)于圖的敘述中，正確的是（ ）。Ⅰ.回路是簡單路徑Ⅱ.存儲稀疏圖，用鄰接矩陣比鄰接表更省空間Ⅲ.若有向圖中存在拓撲序列，則該圖不存在回路

A、 僅Ⅱ

B、 僅Ⅰ、Ⅱ

C、 僅Ⅲ

D、 僅Ⅰ、Ⅲ

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

A、 僅Ⅰ

B、 僅Ⅱ

C、 僅Ⅰ、Ⅱ

D、 僅Ⅱ、Ⅲ

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

A、 順序存儲

B、 散列存儲

C、 鏈式存儲

D、 索引存儲