2015年10月自考02331數(shù)據(jù)結(jié)構(gòu)試題及答案含解析

數(shù)據(jù)結(jié)構(gòu)年月真題

02331201510

1、【單選題】1.下列選項(xiàng)中，不屬于線性結(jié)構(gòu)的是

網(wǎng)

棧

A:

隊(duì)列

B:

線性表

C:

答D:案：A

解析：線性表、棧和隊(duì)列所表達(dá)和處理的數(shù)據(jù)都以線性結(jié)構(gòu)為組織形式。

2、【單選題】2.長度為n的順序表，刪除位置i上的元素(0≤i≤n一1)，需要移動(dòng)的元素

個(gè)數(shù)為

n—i

n—i—l

A:

i

B:

i+1

C:

答D:案：B

解析：當(dāng)i=0時(shí)，代表第一個(gè)元素，此時(shí)刪除刪除位置i上的元素，那么i=n-1，所以移

動(dòng)次數(shù)為n-i-1

3、【單選題】3.棧采用不同的存儲(chǔ)方式時(shí)，下列關(guān)于出棧過程的敘述中，正確的是

順序棧需要判定?？?，鏈棧也需要判定

順序棧需要判定棧空，而鏈棧不需要判定

A:

順序棧不需要判定?？?，而鏈棧需要判定

B:

順序棧不需要判定?？?，鏈棧也不需要判定

C:

答D:案：A

解析：出棧時(shí)，如果棧中的元素個(gè)數(shù)為0則不能繼續(xù)出棧，所以需要判斷當(dāng)前棧是否為

空。在鏈隊(duì)列中進(jìn)行入隊(duì)操作時(shí)要判斷隊(duì)列是否為空，因?yàn)樵阪滉?duì)列中，即使不設(shè)置尾指

針也能進(jìn)行入隊(duì)操作。

4、【單選題】4.若一個(gè)棧以數(shù)組V[0..n-1]存儲(chǔ)，初始棧頂指針top為n，則x入棧的正確

操作是

top=top+1；V[top]=x

V[top]=x；top=top+1

A:

top=top一1；V[mp]=x

B:

V[top]=x；top=top—l

C:

答D:案：C

解析：棧式運(yùn)算受限的線性表，只允許在棧頂進(jìn)行插入和刪除操作。題中棧頂指針為n該

數(shù)組將棧頂放在了下標(biāo)大的一端，所以在進(jìn)行入棧操作時(shí)top指針應(yīng)該進(jìn)行減1操作。通

常元素進(jìn)棧的操作為:先移動(dòng)棧頂指針后存入元素。

5、【單選題】5.在二維數(shù)組a[9][10]中：每個(gè)數(shù)組元素占用3個(gè)存儲(chǔ)空間，從首地址SA開

始按行優(yōu)先連續(xù)存放，則元素a[8][5]的起始地址是

SA+141

SA+144

A:

SA+222

B:

SA+255

C:

答D:案：D

解析：

6、【單選題】6.廣義表A=(x，((y)，((a))，A))的深度是

2

3

A:

4

B:

∞

C:

答D:案：D

解析：廣義表長度是數(shù)第一層括號內(nèi)的逗號數(shù)目，深度是數(shù)括號數(shù)目，所以深度是∞

7、【單選題】7.一棵左子樹為空的二叉樹在前序線索化后，其空指針域個(gè)數(shù)為

0

1

A:

2

B:

不確定

C:

答D:案：C

解析：左子樹為空的二叉樹的根結(jié)點(diǎn)的左線索為空（無前驅(qū)），先序序列的最后結(jié)點(diǎn)的右

線索為空（無后繼），共2個(gè)空鏈域。

8、【單選題】8.下列關(guān)于哈夫曼樹的敘述中，錯(cuò)誤的是

用n個(gè)結(jié)點(diǎn)構(gòu)造的哈夫曼樹是唯一的

哈夫曼樹中只有度為0或度為2的結(jié)點(diǎn)

A:

樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)可能是兄弟結(jié)點(diǎn)

B:

同一結(jié)點(diǎn)集構(gòu)造的二叉樹中，哈夫曼樹的WPL最小

C:

答D:案：A

解析：結(jié)構(gòu)不一定唯一，一旦構(gòu)造過程中間出現(xiàn)某兩個(gè)結(jié)點(diǎn)權(quán)值一樣，并且只能選擇一個(gè)

時(shí)，此時(shí)形態(tài)不唯一。

9、【單選題】9.6個(gè)頂點(diǎn)的強(qiáng)連通圖中，含有的邊數(shù)至少是

4

5

A:

6

B:

7

C:

答D:案：C

解析：在有向圖中任意兩個(gè)頂點(diǎn)都連通，則稱該圖是強(qiáng)連通圖，這樣的有向圖的形狀是環(huán)

狀，因而至少應(yīng)有n條邊。

10、【單選題】12.有向圖采用鄰接矩陣存儲(chǔ)，某一行中非零元素的個(gè)數(shù)等于

對應(yīng)頂點(diǎn)v的度

對應(yīng)頂點(diǎn)v的出度

A:

對應(yīng)頂點(diǎn)v的入度

B:

依附于對應(yīng)頂點(diǎn)v的邊數(shù)

C:

答D:案：B

解析：因?yàn)猷徑泳仃嚨摹緄】【j】代表的是頂點(diǎn)到頂點(diǎn)有無弧，因此行上非零元素個(gè)數(shù)為

vi的出度。

11、【單選題】13.下列選項(xiàng)中，符合堆定義的是

{102，24，55，60，89，93}

{24，89，55，60，93，102}

A:

{102，93，55，60，89，24}

B:

C:

{102，60。89，93，55，24}

答D:案：C

解析：堆是一種經(jīng)過排序的樹形數(shù)據(jù)結(jié)構(gòu)，每一個(gè)結(jié)點(diǎn)都有一個(gè)值，堆的特點(diǎn)是根結(jié)點(diǎn)的

值最小（或最大），且根結(jié)點(diǎn)的兩個(gè)子樹也是一個(gè)堆。

12、【單選題】14.已知關(guān)鍵字序列為{66，82，25，51，98，108}，利用快速排序方法，以

第一個(gè)元素為基準(zhǔn)得到的一趟排序結(jié)果為

{25，51，66，82，98，108}

{25，51，66，98，82，108}

A:

{51，25，66，108，98，82}

B:

{51，25，66，82，98，108}

C:

答D:案：D

解析：根據(jù)快速排序法定義，以66為基準(zhǔn)數(shù)把比它大的放在右邊，小的放在左邊，所以

第一趟排序結(jié)果是（51，25，66，82，98，108｝

13、【單選題】15.下列選項(xiàng)中，其平均查找性能與基于二叉排序樹的查找相當(dāng)?shù)氖?/p>

二分查找

順序查找

A:

分塊查找

B:

索引順序查找

C:

答D:案：A

解析：就平均查找性能而言，二叉排序樹上的查找和二分查找差不多。并且二叉排序樹插

入和刪除結(jié)點(diǎn)十分方便，無須大量移動(dòng)結(jié)點(diǎn)。

14、【填空題】16.線性表(a1，a2，…，an)中，除____外，每個(gè)元素都有唯一的直接前

趨。

答案：a1

15、【填空題】17.指針P指向單鏈表中某個(gè)結(jié)點(diǎn)，在P所指結(jié)點(diǎn)后插入指針s所指的結(jié)

點(diǎn)，正確的操作序列是____。

答案：?

16、【填空題】18.設(shè)Push，、Pop分別表示人棧和出棧操作，x=10，y=20，z=30。依次進(jìn)

行下列操作：Push(y)、Push(z)、Push(z)、X=Pop()、Y=Pop()，x,y的值分別是____。

答案：30,30

17、【填空題】19.廣義表L=(a，(b，e，(e，f，g，h)))，head(L)=____。

答案：a

18、【填空題】20.設(shè)樹T的度為3，其中度為1、2和3的結(jié)點(diǎn)個(gè)數(shù)分別為3、2和1，則T

中葉子結(jié)點(diǎn)的個(gè)數(shù)為____。

答案：5

19、【填空題】21.由一棵二叉樹的后序遍歷序列和____遍歷序列可以唯一確定該二叉樹。

答案：中序

20、【填空題】22.在有n個(gè)頂點(diǎn)的無向圖中，任一頂點(diǎn)的度不大于____。

答案：n-1

21、【填空題】23.借助于一