本文提供2015年高級(jí)語(yǔ)言程序設(shè)計(jì)考研真題答案及解析，以下為具體內(nèi)容

1、以下數(shù)據(jù)結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是（ ）。

A、鏈表

B、棧

C、隊(duì)列

D、二叉樹(shù)

2、以下對(duì)線性表描述錯(cuò)誤的是（ ）。

A、順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)、存儲(chǔ)的時(shí)間復(fù)雜度為O(1)

B、鏈表是順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)的時(shí)間復(fù)雜度為O(n)

C、順序表的插入和刪除可能要移動(dòng)大量的元素

D、鏈表的插入和刪除可能要移動(dòng)大量的元素

3、已知p為指向帶頭結(jié)點(diǎn)的單鏈表的頭指針，以下表達(dá)式說(shuō)明該單鏈表為空的是（ ）。

A、

B、

C、

D、

4、設(shè)堆棧S和隊(duì)列Q的初始狀態(tài)為空，元素1，2，3，4，5，6依次入棧，一個(gè)元素退棧后即進(jìn)入隊(duì)列。若這6個(gè)元素出隊(duì)列的順序是3，2，6，5，4，1，則棧S的容量至少應(yīng)該是（ ）。

A、2

B、3

C、4

D、5

5、若從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)到達(dá)任一葉子結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹(shù)一定是（ ）。

A、二叉排序樹(shù)

B、哈夫曼樹(shù)

C、B-樹(shù)

D、堆

6、已知在一棵度為3的樹(shù)中，有4個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，2個(gè)度為3的結(jié)點(diǎn)，那么該樹(shù)中有葉子節(jié)點(diǎn)個(gè)數(shù)（ ）。

A、8

B、9

C、10

D、11

7、某哈弗曼樹(shù)的結(jié)點(diǎn)總數(shù)為2n-1，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中一共有多少個(gè)空指針域（ ）。

A、2n-1

B、2n

C、2n+1

D、4n

8、n個(gè)頂點(diǎn)組成的有向圖至少需要多少條弧才能構(gòu)成強(qiáng)連通圖（ ）。

A、n

B、2n

C、n(n-1)

D、n-1

9、設(shè)用鄰接矩陣M來(lái)表示有向圖G的存儲(chǔ)結(jié)構(gòu)，那么有向圖G的第i個(gè)頂點(diǎn)的入度為（ ）。

A、第i行非0元素的個(gè)數(shù)

B、第i列非0元素的個(gè)數(shù)

C、第i行非0元素的個(gè)數(shù)除以2

D、第i列非0元素的個(gè)數(shù)除以2