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

數(shù)據(jù)結構年月真題

0233120174

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

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

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

A:

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

B:

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

C:

答D:案：A

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

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

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

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

順序存儲時不一定相鄰，鏈式存儲時一定相鄰

順序存儲時不一定相鄰，鏈式存儲時也不一定相鄰

A:

順序存儲時一定相鄰，鏈式存儲時也一定相鄰

B:

順序存儲時一定相鄰，鏈式存儲時不一定相鄰

C:

答D:案：D

解析：線性表順序存儲的特點是邏輯關系上相鄰的兩個元素在物理位置上也是相鄰的，鏈

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

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

>next)。若指針p指向當前被遍歷結點，則判定遍歷過程結束的條件是

P==NULL

head==NULL

A:

P==head

B:

head！=P

C:

答D:案：C

解析：因為是單循環(huán)鏈表，P的指針指向頭結點時遍歷一遍，所以P=head。

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

列是

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

解析：棧的特點：后進先出。答案D正確。進出順序為：1進2進3進3出4進4出2出

1出5進5出。其他選項均違背了后進先出的原則。

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

存儲單元，則元素A[1][2]存儲地址是

10

12

A:

14

B:

15

C:

答D:案：D

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

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

解析：當表為非空時，稱第一個元素是表頭，其余元素組成的表稱為表尾，該題的表頭是

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

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

38

39

A:

40

B:

41

C:

答D:案：C

解析：由完全二叉樹定義可知，在完全二叉樹中除最下面一層外，各層結點都達到最大

值，每一層上結點個數(shù)恰好是上一層結點個數(shù)的2倍。所以答案為C。

8、【單選題】對下面的二叉樹進行中序線索化后，結點f的右指針指向的結點是

a

b

A:

c

B:

e

C:

答D:案：D

解析：中序遍歷的操作順序：左子樹，根結點，右子樹。答案為D。

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

n-1

n

A:

n*(n+1)/2

B:

n*(n+l)

C:

答D:案：B

解析：強連通圖是指一個有向圖中任意兩點v1、v2間存在v1到v2的路徑及v2到v1的

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

者逆時針，此時有n條邊。

10、【單選題】若從頂點a開始對下圖進行廣度優(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ā)點Vi，接著依次訪問Vi的所有未被訪問

接點Vi1，Vi2……，并標記為已經訪問，然后再按照Vi1，Vi2……的次序訪問每一個

頂點的所有未曾訪問的頂點半標記為訪問。答案的4個選項都以頂點a為出發(fā)點，b,c,e

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

點，接點是c,e,b,因為先訪問的C，那么下一步要先訪問f，才能再訪問d,這個順序不正

確，所以答案為C。

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

堆排序

直接選擇排序

A:

冒泡排序

B:

希爾排序

C:

答D:案：C

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

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

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

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

快速排序

直接選擇排序

A:

冒泡排序

B:

直接插入排序

C:

答D:案：B

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

關的排序方法是選擇排序。故答案選B。

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

前序遍歷

中序遍歷

A:

后序遍歷

B:

按層遍歷

C:

答D:案：B

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

的值，若它的左子樹為非空，則左子樹上所有結點的值均小于根結點的值，左、右子樹本

身又是一棵二叉排序樹。因為中序遍歷是先左子樹，再根結點，再右子樹，所以按中序遍

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

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

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

1

2

A:

3

B:

4

C:

答D:案：C

解析：散列地址為0的結點即是關鍵字可以整除11，記錄中，22，88，11都可以整除

11，所以結點數(shù)為3，答案為C。

15、【單選題】在下面3階B樹中插入關鍵字65后，其根結點內的關鍵字是

5390

53

A:

90

B:

65

C:

答D:案：D

解析：在B樹中插入一個結點的過程：先在最低層的某個非終端結點中添加一個關鍵字。

若該結點中關鍵字的個數(shù)不超過m-1，則插入完成，否則要產生結點“分裂”。“分裂”

結點時把結點分成兩個，將中間的一個關鍵字拿出來插入到該結點的雙親結點上，如果雙

親結點中已有m-1個關鍵字，則插入后將引起雙親結點的分裂，這一過程可能波及B樹的

根結點，引起根結點的分裂，從而使B樹長高一層。具體過程：因為65介于61和70之

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

同時61和70分成兩個結點，但這時53和90這個結點中因為插入了65，關鍵字超過了

3，也要分裂，65升為雙親結點，53和90分成兩個結點。所以該題答案為D。

16、【問答題】對題26圖所示的帶權無向圖G，試回答以下問題。

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

若用克魯斯卡爾(Kruskal)算法求最小生成樹，請按被選中的次序寫出最小生成樹上各條

邊的頂點和權值。

答案：

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

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

（E，F(xiàn)），因為前4條邊的權值最小，而且不在不形成回路，所以加入T中，接著考慮當

前的權值最小的邊(A,D),因為該邊的兩個端點在同一個回路上，故舍去，然后再選擇

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

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

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

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

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

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

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

3.

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

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

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

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

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

18、【問答題】試回答下列關于拓撲排序算法的問題。（1）算法中利用一個棧保存入度為

0的頂點，其目的是什么？（2）若在算法中將隊列改為棧，相應地將入、出棧及判?？詹僮?/p>

改為入、出隊列和判隊列空操作，其他部分不變，是否依然能夠得到拓撲排序時正確結果？

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

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

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

解析：教材164頁，拓撲排序實際就是對臨接表的遍歷，每次訪問一個入度為0的頂點。

設一個棧暫存所有入度為0的頂點，每次選擇入度為0的頂點時，只需要做出棧操作就可

以了，減少找入度為0的頂點的時間，提高排序的效率。棧或隊列的作用就是暫存所有入

度為零的頂點：在開始排序前，掃描對應的存儲空間，將入度為零的頂點均入棧(隊)。以

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

現(xiàn)。

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

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

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

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

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

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

無序區(qū)。排序開始，首先輸出堆頂元素（因為它是最值），將堆頂元素和最后一個元素交

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

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

找出關鍵字較大的若干項。

20、【問答題】設鏈表中結點類型定義如下，閱讀程序，回答下列問題。

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

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

答案：（1）88；（2）返回鏈表中各結點中值最大的。

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

21、【問答題】函數(shù)f31的功能是逆序輸出鏈表中所有結點的數(shù)據(jù)域值。請在空白處填充

適當?shù)膬热荩蛊渫瓿芍付üδ堋?/p>

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

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

前節(jié)點元素，這個遞歸就表明，總是先打印當前節(jié)點之后節(jié)點的值。

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

A表示。閱讀程序，并在空白處填入適當內容，使其完成指定功能。

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

解析：循環(huán)語句，從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頁例5.3原題，一顆二叉樹為空，則深度為0，否則它的深度等于其左右

子樹中的最大深度加1.

24、【問答題】已知二叉樹的結點類型定義如下：

請編寫函數(shù)SearchXNum，計

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

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

個數(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)}

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

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

算出來并返回值，最后返回結點的個數(shù)。

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

答案：存儲地址

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

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

26、【填空題】一個需要頻繁增刪的線性表宜選擇______存儲結構。

答案：鏈式

解析：線性表當需要做插入和刪除操作時，需要移動大量的元素，而鏈式存儲結避免這些

移動。

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

答案：962-8*+

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

送至輸出隊列，當讀到運算符時，將棧中所有優(yōu)先級高于或等于該運算符的運算符彈出，

再將當前運算符入棧，當讀入左括號時入棧，當讀到右括號時，將靠近棧頂?shù)牡谝粋€左括

號上面的運算符依次彈出，再刪除棧中左括號。本題中9彈出，“+”“（”入棧，6彈

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

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

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

n2等于____。

答案：n2=n0-1

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

為n2，則n0=n2+1。

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