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

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

0233120174

1、【單選題】下列敘述中，不正確的是

算法解決的只能是數(shù)值計(jì)算問題

同一問題可以有多種不同算法

A:

算法的每一步操作都必須明確無歧義

B:

算法必須在執(zhí)行有限步后結(jié)束

C:

答D:案：A

解析：本題可以用排除法，算法的5個(gè)準(zhǔn)則：有窮性，即算法中每一條指令的執(zhí)行次數(shù)都

是有限的。確定性：算法中每一條指令的含義都必須明確，無二義性。同一個(gè)問題可以用

多種算法。B、C、D都是正確的，答案是A。

2、【單選題】下列關(guān)于棧中邏輯上相鄰的兩個(gè)數(shù)據(jù)元素的敘述中，正確的是

順序存儲(chǔ)時(shí)不一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)一定相鄰

順序存儲(chǔ)時(shí)不一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)也不一定相鄰

A:

順序存儲(chǔ)時(shí)一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)也一定相鄰

B:

順序存儲(chǔ)時(shí)一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)不一定相鄰

C:

答D:案：D

解析：線性表順序存儲(chǔ)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也是相鄰的，鏈

式存儲(chǔ)結(jié)構(gòu)存儲(chǔ)線性表數(shù)據(jù)元素的空間可能連續(xù)，也可能不連續(xù)。

3、【單選題】對(duì)帶頭結(jié)點(diǎn)的單循環(huán)鏈表從頭結(jié)點(diǎn)開始遍歷(head為頭指針，p=head-

>next)。若指針p指向當(dāng)前被遍歷結(jié)點(diǎn)，則判定遍歷過程結(jié)束的條件是

P==NULL

head==NULL

A:

P==head

B:

head！=P

C:

答D:案：C

解析：因?yàn)槭菃窝h(huán)鏈表，P的指針指向頭結(jié)點(diǎn)時(shí)遍歷一遍，所以P=head。

4、【單選題】設(shè)棧的入棧序列為1，2，3，4，5，經(jīng)過入、出棧操作后，可能得到的出棧序

列是

2,3,5,1,4

4,2,1,3,5

A:

3,4,1,2,5

B:

3,4,2,1,5

C:

答D:案：D

解析：棧的特點(diǎn)：后進(jìn)先出。答案D正確。進(jìn)出順序?yàn)椋?進(jìn)2進(jìn)3進(jìn)3出4進(jìn)4出2出

1出5進(jìn)5出。其他選項(xiàng)均違背了后進(jìn)先出的原則。

5、【單選題】數(shù)組A[2][3]按行優(yōu)先順序存放，A的首地址為10。若A中每個(gè)元素占用一個(gè)

存儲(chǔ)單元，則元素A[1][2]存儲(chǔ)地址是

10

12

A:

14

B:

15

C:

答D:案：D

解析：數(shù)組元素aij的地址計(jì)算函數(shù)為：LOC（aij）=LOC（a00）+(i*n+j)*d,因?yàn)?/p>

i=1,j=2,n=3,根據(jù)公式得：LOC（a12）=10+（1*3+2）=15，答案為D。

6、【單選題】廣義表（（a，b），（c，d））的表尾是

b

d

A:

（c，d）

B:

（（c，d））

C:

答D:案：D

解析：當(dāng)表為非空時(shí)，稱第一個(gè)元素是表頭，其余元素組成的表稱為表尾，該題的表頭是

（a,b）,表尾是（（c,d））,答案為D。

7、【單選題】若完全二叉樹T包含20個(gè)終端結(jié)點(diǎn)，則T的結(jié)點(diǎn)數(shù)最多是

38

39

A:

40

B:

41

C:

答D:案：C

解析：由完全二叉樹定義可知，在完全二叉樹中除最下面一層外，各層結(jié)點(diǎn)都達(dá)到最大

值，每一層上結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié)點(diǎn)個(gè)數(shù)的2倍。所以答案為C。

8、【單選題】對(duì)下面的二叉樹進(jìn)行中序線索化后，結(jié)點(diǎn)f的右指針指向的結(jié)點(diǎn)是

a

b

A:

c

B:

e

C:

答D:案：D

解析：中序遍歷的操作順序：左子樹，根結(jié)點(diǎn)，右子樹。答案為D。

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

n-1

n

A:

n*(n+1)/2

B:

n*(n+l)

C:

答D:案：B

解析：強(qiáng)連通圖是指一個(gè)有向圖中任意兩點(diǎn)v1、v2間存在v1到v2的路徑及v2到v1的

路徑的圖。最少的情況：即n個(gè)頂點(diǎn)圍成一個(gè)圈，且圈上各邊方向一致，即均為順時(shí)針或

者逆時(shí)針，此時(shí)有n條邊。

10、【單選題】若從頂點(diǎn)a開始對(duì)下圖進(jìn)行廣度優(yōu)先遍歷，則不可能得到的遍歷序列是

a，b，c，e，f，d

a，c，b，e，f，d

A:

a，c，e，b，d，f

B:

a，e，b，c，f，d

C:

答D:案：C

解析：廣度優(yōu)先搜索的基本思想：先訪問出發(fā)點(diǎn)Vi，接著依次訪問Vi的所有未被訪問

接點(diǎn)Vi1，Vi2……，并標(biāo)記為已經(jīng)訪問，然后再按照Vi1，Vi2……的次序訪問每一個(gè)

頂點(diǎn)的所有未曾訪問的頂點(diǎn)半標(biāo)記為訪問。答案的4個(gè)選項(xiàng)都以頂點(diǎn)a為出發(fā)點(diǎn)，b,c,e

的順序可以任意，但d,f的順序受e,c被訪問的先后順序影響，答案C中，以a為出發(fā)

點(diǎn)，接點(diǎn)是c,e,b,因?yàn)橄仍L問的C，那么下一步要先訪問f，才能再訪問d,這個(gè)順序不正

確，所以答案為C。

11、【單選題】下列排序算法中，穩(wěn)定的是

堆排序

直接選擇排序

A:

冒泡排序

B:

希爾排序

C:

答D:案：C

解析：這個(gè)題考查各種排序方法的穩(wěn)定性，教材190頁(yè)內(nèi)部排序方法的分析與比較中總結(jié)

到，直接插入、冒泡、歸并、基數(shù)排序算法是穩(wěn)定的，直接選擇、希爾、快速、堆排序算

法是不穩(wěn)定的，所以答案為C。

12、【單選題】下列排序算法中，比較操作的次數(shù)與待排序序列初始排列狀態(tài)無關(guān)的是

快速排序

直接選擇排序

A:

冒泡排序

B:

直接插入排序

C:

答D:案：B

解析：教材191頁(yè)排序方法的選取一節(jié)中講到，關(guān)鍵字比較次數(shù)與記錄的初始排列順序無

關(guān)的排序方法是選擇排序。故答案選B。

13、【單選題】若對(duì)二叉排序樹進(jìn)行遍歷，則下列遍歷方式中，其遍歷結(jié)果為遞增有序的是

前序遍歷

中序遍歷

A:

后序遍歷

B:

按層遍歷

C:

答D:案：B

解析：根據(jù)二叉排序樹的定義它的右子樹非空，則右子樹上的所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)

的值，若它的左子樹為非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值，左、右子樹本

身又是一棵二叉排序樹。因?yàn)橹行虮闅v是先左子樹，再根結(jié)點(diǎn)，再右子樹，所以按中序遍

歷二叉排序樹所得到的遍歷序列是一個(gè)遞增有序序列。

14、【單選題】設(shè)一組記錄的關(guān)鍵字為{12，22，10，20，88，27，54，11}，散列函數(shù)為

H(key)=key%11，用拉鏈法解決沖突，則散列地址為0的鏈中結(jié)點(diǎn)數(shù)是

1

2

A:

3

B:

4

C:

答D:案：C

解析：散列地址為0的結(jié)點(diǎn)即是關(guān)鍵字可以整除11，記錄中，22，88，11都可以整除

11，所以結(jié)點(diǎn)數(shù)為3，答案為C。

15、【單選題】在下面3階B樹中插入關(guān)鍵字65后，其根結(jié)點(diǎn)內(nèi)的關(guān)鍵字是

5390

53

A:

90

B:

65

C:

答D:案：D

解析：在B樹中插入一個(gè)結(jié)點(diǎn)的過程：先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字。

若該結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不超過m-1，則插入完成，否則要產(chǎn)生結(jié)點(diǎn)“分裂”。“分裂”

結(jié)點(diǎn)時(shí)把結(jié)點(diǎn)分成兩個(gè)，將中間的一個(gè)關(guān)鍵字拿出來插入到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)上，如果雙

親結(jié)點(diǎn)中已有m-1個(gè)關(guān)鍵字，則插入后將引起雙親結(jié)點(diǎn)的分裂，這一過程可能波及B樹的

根結(jié)點(diǎn)，引起根結(jié)點(diǎn)的分裂，從而使B樹長(zhǎng)高一層。具體過程：因?yàn)?5介于61和70之

間，所以插到該節(jié)點(diǎn)中，但插入后節(jié)點(diǎn)數(shù)超過了2，所以要分裂，把65拿到雙新結(jié)點(diǎn)中，

同時(shí)61和70分成兩個(gè)結(jié)點(diǎn)，但這時(shí)53和90這個(gè)結(jié)點(diǎn)中因?yàn)椴迦肓?5，關(guān)鍵字超過了

3，也要分裂，65升為雙親結(jié)點(diǎn)，53和90分成兩個(gè)結(jié)點(diǎn)。所以該題答案為D。

16、【問答題】對(duì)題26圖所示的帶權(quán)無向圖G，試回答以下問題。

(1)畫出G的最小生成樹：(2)

若用克魯斯卡爾(Kruskal)算法求最小生成樹，請(qǐng)按被選中的次序?qū)懗鲎钚∩蓸渖细鳁l

邊的頂點(diǎn)和權(quán)值。

答案：

解析：本題是教材上P156例6.3原題?？唆斔箍?Kruskal)算法按權(quán)值遞增順序考慮邊

（A,C）,（D,F,（B,E）,（C,F）,（A，D）,（B,C），（C，D），（A,B）,(C,E),

（E，F(xiàn)），因?yàn)榍?條邊的權(quán)值最小，而且不在不形成回路，所以加入T中，接著考慮當(dāng)

前的權(quán)值最小的邊(A,D),因?yàn)樵撨叺膬蓚€(gè)端點(diǎn)在同一個(gè)回路上，故舍去，然后再選擇

（B,C）加入T，便得到要求一最小生成樹了。

17、【問答題】已知散列表的長(zhǎng)度為11，散列函數(shù)為H(key)=key%11，散列表的當(dāng)前狀

態(tài)如下：現(xiàn)要插入關(guān)鍵字

38，回答下列問題。（1）若用線性探查法解決沖突，則38所在位置的下標(biāo)是什么？

（2）若用二次探查法解決沖突，則38所在位置的下標(biāo)是什么？（3）以上兩種方法中，

各需要多少次探查次數(shù)？

答案：（1）插入位置的下標(biāo)是8；（2）插入位置的下標(biāo)是4；（3）探查次數(shù)分別為4和

3.

解析：（1）h(38)=5,散列地址5已經(jīng)被占，因些探查h1=(5+1)%11=6,但散列地址6也已

經(jīng)被占，再探查h2=(6+1)%11=7,散列地址7也被占了，再探查h3=(7+1)%11=8,此地址是

開放的，可將38插入。（2）h(38)=5,散列地址5已經(jīng)被占，因些探查h1=(5+12)%11=6,

但散列地址6也已經(jīng)被占，再探查h2=(5-12)%11=4，此地址是開放的，可將38插入。

（3）根據(jù)第1和2題的探查次數(shù)可得知為4次和3次。

18、【問答題】試回答下列關(guān)于拓?fù)渑判蛩惴ǖ膯栴}。（1）算法中利用一個(gè)棧保存入度為

0的頂點(diǎn)，其目的是什么？（2）若在算法中將隊(duì)列改為棧，相應(yīng)地將入、出棧及判棧空操作

改為入、出隊(duì)列和判隊(duì)列空操作，其他部分不變，是否依然能夠得到拓?fù)渑判驎r(shí)正確結(jié)果？

答案：（1）每次選擇入度為0的頂點(diǎn)時(shí)，只需要做出棧操作就可以了，減少找入度為0

的頂點(diǎn)的時(shí)間，提高排序的效率。（2）每次選人度為零的頂點(diǎn)時(shí)，只需做出棧(隊(duì))操作

即可。所以把棧換成隊(duì)列同樣可以實(shí)現(xiàn)。

解析：教材164頁(yè)，拓?fù)渑判驅(qū)嶋H就是對(duì)臨接表的遍歷，每次訪問一個(gè)入度為0的頂點(diǎn)。

設(shè)一個(gè)棧暫存所有入度為0的頂點(diǎn)，每次選擇入度為0的頂點(diǎn)時(shí)，只需要做出棧操作就可

以了，減少找入度為0的頂點(diǎn)的時(shí)間，提高排序的效率。?；蜿?duì)列的作用就是暫存所有入

度為零的頂點(diǎn)：在開始排序前，掃描對(duì)應(yīng)的存儲(chǔ)空間，將入度為零的頂點(diǎn)均入棧(隊(duì))。以

后每次選入度為零的頂點(diǎn)時(shí)，只需做出棧(隊(duì))操作即可。所以把棧換成隊(duì)列同樣可以實(shí)

現(xiàn)。

19、【問答題】考慮用快速排序、堆排序和歸并排序3種排序方法對(duì)數(shù)據(jù)序列進(jìn)行排序，針

對(duì)下列不同情況，宜分別選擇哪種排序方法？（1）使用盡量少的存儲(chǔ)空間；（2）要求排序

結(jié)果是穩(wěn)定的；（3）快速找出數(shù)據(jù)序列中關(guān)鍵字值較大的若干項(xiàng)。

答案：（1）堆排序（2）歸并排序（3）堆排序

解析：根據(jù)教材190頁(yè)內(nèi)部排序方法的比較分析得出這三種排序方法中，堆排序是要求空

間最小的O（1），歸并排序是最穩(wěn)定的。堆排序是一種選擇排序。建立的初始堆為初始的

無序區(qū)。排序開始，首先輸出堆頂元素（因?yàn)樗亲钪担?，將堆頂元素和最后一個(gè)元素交

換，這樣，第n個(gè)位置（即最后一個(gè)位置）作為有序區(qū)，前n-1個(gè)位置仍是無序區(qū)，對(duì)無

序區(qū)進(jìn)行調(diào)整，得到堆之后，再交換堆頂和最后一個(gè)元素。如果建的最大化堆，就能快速

找出關(guān)鍵字較大的若干項(xiàng)。

20、【問答題】設(shè)鏈表中結(jié)點(diǎn)類型定義如下，閱讀程序，回答下列問題。

（1）若鏈表L={2，12，16，

88，5，10}，寫出調(diào)用f30(L)的輸出結(jié)果；（2）函數(shù)f30的功能是什么？

答案：（1）88；（2）返回鏈表中各結(jié)點(diǎn)中值最大的。

解析：max(head->data,f30(head->next),鏈表中的兩個(gè)結(jié)點(diǎn)值比較，輸出值大的那個(gè)。

21、【問答題】函數(shù)f31的功能是逆序輸出鏈表中所有結(jié)點(diǎn)的數(shù)據(jù)域值。請(qǐng)?jiān)诳瞻滋幪畛?/p>

適當(dāng)?shù)膬?nèi)容，使其完成指定功能。

答案：（1）return;(2)head->data

解析：如果節(jié)點(diǎn)為空，則不打印，直接返回，否則逆向打印后面節(jié)點(diǎn)的元素，最后打印當(dāng)

前節(jié)點(diǎn)元素，這個(gè)遞歸就表明，總是先打印當(dāng)前節(jié)點(diǎn)之后節(jié)點(diǎn)的值。

22、【問答題】函數(shù)f32的功能是統(tǒng)計(jì)N個(gè)頂點(diǎn)的有向圖中邊的數(shù)量，有向圖用鄰接矩陣

A表示。閱讀程序，并在空白處填入適當(dāng)內(nèi)容，使其完成指定功能。

答案：(1)i++;(2)j=0;(3)A[i][j]>0

解析：循環(huán)語(yǔ)句，從i=0開始,一直循環(huán)到i=n-1,從j=0開始，循環(huán)到J=n-1.如果

A[i][j]>0，sum就加1，最后返回總值。

23、【問答題】己知二叉樹的二叉鏈表類型定義如下：

答案：（1）bt==null；(2)hl>hr；（3）return(hr+1)

解析：教材120頁(yè)例5.3原題，一顆二叉樹為空，則深度為0，否則它的深度等于其左右

子樹中的最大深度加1.

24、【問答題】已知二叉樹的結(jié)點(diǎn)類型定義如下：

請(qǐng)編寫函數(shù)SearchXNum，計(jì)

算任意二叉樹T中其數(shù)據(jù)域的值大于或等于x的結(jié)點(diǎn)的個(gè)數(shù)并返回該值。函數(shù)原型如下：

SearchXNum（BinTree*T，intx）；∥返回二叉樹T中數(shù)據(jù)域的值大于或等于x的結(jié)點(diǎn)的

個(gè)數(shù)。

答案：intLTXNum(BinTree*t,intx){intn;if(T==null)return0;if(T-

>data>=x)n=1;elsen=0;returnn+LTXNum(T->lchild,x)+LTXNum(T->rchild,x)}

解析：算法的思想是根結(jié)點(diǎn)如果為空，表示該二叉為空樹，返回0。如果根結(jié)點(diǎn)值大于或

等X，n=1,并返回結(jié)點(diǎn)的值。然后用遞歸算法，分別把左子樹和右子樹大于X的結(jié)點(diǎn)個(gè)數(shù)

算出來并返回值，最后返回結(jié)點(diǎn)的個(gè)數(shù)。

25、【填空題】散列方法的基本思想是根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的_______。

答案：存儲(chǔ)地址

解析：散列存儲(chǔ)的基本思想：以線性表中的每個(gè)元素的關(guān)鍵字為自變量，通過一種函數(shù)H

（key）計(jì)算出函數(shù)值，把這個(gè)函數(shù)值解釋為一塊連續(xù)存儲(chǔ)空間的單元地址。

26、【填空題】一個(gè)需要頻繁增刪的線性表宜選擇______存儲(chǔ)結(jié)構(gòu)。

答案：鏈?zhǔn)?/p>

解析：線性表當(dāng)需要做插入和刪除操作時(shí)，需要移動(dòng)大量的元素，而鏈?zhǔn)酱鎯?chǔ)結(jié)避免這些

移動(dòng)。

27、【填空題】若中綴表達(dá)式為9+(6-2)*8，則相應(yīng)的后綴表達(dá)式是_______。

答案：962-8*+

解析：中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式的思想：順序掃描中綴表達(dá)式，當(dāng)讀到數(shù)字時(shí)，直接

送至輸出隊(duì)列，當(dāng)讀到運(yùn)算符時(shí)，將棧中所有優(yōu)先級(jí)高于或等于該運(yùn)算符的運(yùn)算符彈出，

再將當(dāng)前運(yùn)算符入棧，當(dāng)讀入左括號(hào)時(shí)入棧，當(dāng)讀到右括號(hào)時(shí)，將靠近棧頂?shù)牡谝粋€(gè)左括

號(hào)上面的運(yùn)算符依次彈出，再刪除棧中左括號(hào)。本題中9彈出，“+”“（”入棧，6彈

出，“-”入棧，2彈出，遇到右括號(hào)了，把“-”彈出，刪除左括號(hào)，“*”入棧，8彈

出，“*”彈出，最后“+”彈出。

28、【填空題】對(duì)任何一棵二叉樹T，若其葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則

n2等于____。

答案：n2=n0-1

解析：根據(jù)二叉樹性質(zhì)3，對(duì)任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)

為n2，則n0=n2+1。

29、【填空題】若某二叉樹