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

1、設n是描述問題規模的非負整數，下面程序片段的時間復雜度是（ ）。

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

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

A、 3

B、 4

C、 5

D、 6

3、已知循環隊列存儲在一維數組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個結點，則該二叉樹中葉結點的個數是（  ）。

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個結點的樹，其葉結點個數為116，該樹對應的二叉樹中無右孩子的結點個數是（  ）。

A、 115

B、 116

C、 1895

D、 1896

7、對于下列關鍵字序列，不可能構成某二叉排序樹中一條查找路徑的序列是（  ）。

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

A、 僅Ⅱ

B、 僅Ⅰ、Ⅱ

C、 僅Ⅲ

D、 僅Ⅰ、Ⅲ

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

A、 僅Ⅰ

B、 僅Ⅱ

C、 僅Ⅰ、Ⅱ

D、 僅Ⅱ、Ⅲ

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

A、 順序存儲

B、 散列存儲

C、 鏈式存儲

D、 索引存儲