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

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

0233120194

1、【單選題】線性表是一種由n個(gè)數(shù)據(jù)元素組成的數(shù)據(jù)結(jié)構(gòu),n的取值是

0或者任意一個(gè)正整數(shù)或者∞

非負(fù)整數(shù)

A:

任意一個(gè)正整數(shù)或者∞

B:

某個(gè)正整數(shù)

C:

答D:案：B

解析：線性表是一種由n個(gè)數(shù)據(jù)元素組成的數(shù)據(jù)結(jié)構(gòu),n的取值是非負(fù)整數(shù)。

2、【單選題】在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn),若在p和q之間插

入s所指結(jié)點(diǎn),則正確的操作是

s->next=p->next;p->next=s;

s->next=q;p->next=s->next;

A:

q->next=s;s->next=p;

B:

p->next=s;s->next=p;

C:

答D:案：A

3、【單選題】下列選項(xiàng)中,不宜通過棧求解的問題是

判斷字符串是否是回文

檢驗(yàn)圓括號是否匹配

A:

不同數(shù)制之間進(jìn)行轉(zhuǎn)換

B:

圖的廣度優(yōu)先搜索遍歷

C:

答D:案：D

4、【單選題】設(shè)棧S的輸入序列為1,2,3,4,5,則下列選項(xiàng)中不可能是S的輸出序列的是

2,3,4,1,5

5,4,1,3,2

A:

2,3,1,4,5

B:

1,5,4,3,2

C:

答D:案：B

5、【單選題】使用一個(gè)大小為6的數(shù)組保存循環(huán)隊(duì)列Q。若從Q中出隊(duì)兩個(gè)元素,并入隊(duì)一

個(gè)元素,此時(shí)隊(duì)尾rear和隊(duì)頭front的值分別為2和4。則在執(zhí)行這三個(gè)操作之前rear和

front的值分別是

0和3

1和2

A:

2和5

B:

4和5

C:

答D:案：B

6、【單選題】設(shè)二維數(shù)組M有3行4列,按行優(yōu)先的方式存儲,每個(gè)元素占6個(gè)存儲單元。第

1個(gè)元素的存儲地址為100,則M[2][2]的存儲地址為A

135

153

A:

160

B:

165

C:

答D:案：C

7、【單選題】設(shè)n階方陣M是對稱矩陣,采用壓縮存儲方式將M中的元素保存在一維數(shù)組B

中,則下列選項(xiàng)中,正確的是

保存M中的主對角線中的元素,B的元素個(gè)數(shù)是n

保存M中上三角部分的元素,B的元素個(gè)數(shù)是n(n-1)/2

A:

保存M中上三角部分的元素,B的元素個(gè)數(shù)是n(n+1)/2

B:

保存M中的全部元素,B的元素個(gè)數(shù)是n2

C:

答D:案：C

8、【單選題】已知完全二叉樹T的第4層有5個(gè)葉結(jié)點(diǎn),則T的結(jié)點(diǎn)個(gè)數(shù)最多是

12

20

A:

21

B:

36

C:

答D:案：C

9、【單選題】在一棵非空二叉樹的后序遍歷序列中,所有列在根結(jié)點(diǎn)前面的是

左子樹中的部分結(jié)點(diǎn)

右子樹中的全部結(jié)點(diǎn)

A:

左右子樹中的部分結(jié)點(diǎn)

B:

左右子樹中的全部結(jié)點(diǎn)

C:

D:

答案：D

10、【單選題】若對題10圖所示的無向圖進(jìn)行深度優(yōu)先搜索遍歷,則下列選項(xiàng)中正確的遍

歷序列是

h,c,a,b,d,e,g,f

e,a,f,g,b,h,c,d

A:

d,b,c,a,h,e,f,g

B:

a,b,c,d,h,e,f,g

C:

答D:案：D

11、【單選題】對題11圖所示的有向圖進(jìn)行拓?fù)渑判?。下列選項(xiàng)中能夠得到的拓?fù)湫蛄?/p>

是

3,1,2,4,5,6

3,1,2,4,6,5

A:

3,1.4,2,5,6

B:

3,1,4,2,6,5

C:

答D:案：D

12、【單選題】已知數(shù)據(jù)序列(8,9.10,4,5.6,20,1,2)是某種排序算法第一趟排序后得到的

結(jié)果,則該算法可能是

選擇排序

起泡排序

A:

直接插入排序

B:

快速排序

C:

答D:案：C

13、【單選題】下列選項(xiàng)中,每一趟都能選出一個(gè)元素放在其最終位置上,且不穩(wěn)定的排序算

法是

起泡排序

希爾排序

A:

歸并排序

B:

快速排序

C:

D:

答案：D

解析：對于每一趟都能選出一個(gè)元素放在其最終位置上的排序算法，我們可以考慮冒泡排

序和插入排序。這兩種排序算法都是穩(wěn)定的排序算法?？焖倥判蚴且环N不穩(wěn)定的排序算

法。在快速排序中，我們選擇一個(gè)基準(zhǔn)元素，將數(shù)組分成兩個(gè)子數(shù)組，一個(gè)子數(shù)組中的元

素都小于基準(zhǔn)元素，另一個(gè)子數(shù)組中的元素都大于基準(zhǔn)元素。然后遞歸地對這兩個(gè)子數(shù)組

進(jìn)行排序。在快速排序的過程中，我們會(huì)通過交換元素的位置來實(shí)現(xiàn)元素的分區(qū)。這個(gè)過

程可能會(huì)導(dǎo)致相同元素之間的相對順序發(fā)生改變，從而使快速排序成為不穩(wěn)定的排序算

法。舉個(gè)例子，考慮以下數(shù)組：[5,2,5,1,3]。在快速排序中，我們選擇基準(zhǔn)元素為

3，將數(shù)組分成[2,1]和[5,5]兩個(gè)子數(shù)組。然后對這兩個(gè)子數(shù)組進(jìn)行排序，得到[1,2]和

[5,5]。最后將基準(zhǔn)元素3放置在正確的位置上，得到[1,2,3,5,5]?？梢钥吹?，原

數(shù)組中的兩個(gè)相同的5在排序后的結(jié)果中位置發(fā)生了變化，因此快速排序是不穩(wěn)定的排序

算法。

14、【單選題】對有序表(1,9,12,41,62,77,82,95,100)采用二分查找方法查找值82,查找過

程中關(guān)鍵字的比較次數(shù)是

1

2

A:

4

B:

7

C:

答D:案：B

15、【單選題】將下列數(shù)據(jù)依次插入到初始為空的二叉排序樹中能得到高度最小的二叉排序

樹的序列是

2,4,7.5,8,10

5.1,2,6,3,4

A:

6,4,1,8,10,5

B:

9,7,2,1,4,0

C:

答D:案：C

16、【問答題】設(shè)細(xì)數(shù)矩陣M如下所示。矩陣的行列下標(biāo)均從1開始，請畫出M按行優(yōu)先

存儲的三元組表。

答案：

17、【問答題】已知二樹T的前序遍歷序列是A,B.C,D,E.L,M,O,N序遍歷序列是

C,B,E,D,A,M,O,L,N請畫出T。

答案：

18、【問答題】已知有向帶權(quán)圖G如題28圖所示。請回答下列問題。(1)給出圖G的

鄰接矩陣。(2)求出G中從源點(diǎn)A到其余各頂點(diǎn)的最短路徑。要求根據(jù)迪杰斯特拉算法

的求解過程依次給出各條路徑,包括路徑上經(jīng)過的頂點(diǎn)及其長度。

答案：

19、【問答題】設(shè)有關(guān)鍵字序列(65,23,31,26,7,91,53,15,72,52),散列函數(shù)為

H(key)=key%11,將關(guān)鍵字依次放入表長為11的散列表H中,采用線性探測法處理沖突。請回

答下列問題。(1)畫出構(gòu)造的散列表,并給出查找每個(gè)關(guān)鍵字的探查次數(shù)。(2)求散列表的平均

查找長度ASL。

答案：

20、【問答題】

答案：

21、【問答題】

答案：

22、【問答題】

答案：(1)high=mid-1(2)mid(3)i>=inspace

23、【問答題】

答案：(1)R中的值是{30,14,-38,-9,52,256,128,258,64}(2)該算法選擇第一個(gè)元素作

為基準(zhǔn),實(shí)現(xiàn)對數(shù)組的一次劃分。(或?qū)崿F(xiàn)快速排序的一次劃分。)

24、【問答題】

答案：

25、【填空題】線性表的存儲方式中，能夠隨機(jī)存取表中任一元素的存儲結(jié)構(gòu)是____。

答案：順序存儲結(jié)構(gòu)

26、【填空題】用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234，為了得到

1342的出棧順序，相應(yīng)的S、X操作串為____。

答案：SXSSXSXX

27、【填空題】若廣義表L的深度是∞，則L一定是____。

答案：遞歸表

28、【填空題】廣義表（（a,b）,（c,d）,e）的表尾是____。

答案：(（c,d),e）

29、【填空題】利用二叉樹中的空指針域，使之指向結(jié)點(diǎn)在某種遍歷次序下的前趨或后繼結(jié)

點(diǎn)，此時(shí)域中的內(nèi)容稱為____。

答案：線索

30、【填空題】若用n個(gè)帶權(quán)字符構(gòu)造哈夫曼樹T，則T中結(jié)點(diǎn)的總數(shù)是____。

答案：2n-1

31、【填空題】設(shè)連通帶權(quán)圖G中有n個(gè)頂點(diǎn)，使用普里姆算法構(gòu)造G的最小生成樹T，T

中含有的邊數(shù)是____。

答案：n-1

32、【填空題】要使n個(gè)記錄的關(guān)