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

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

0233120224

1、【單選題】下列數(shù)據(jù)結(jié)構(gòu)中，與存儲(chǔ)結(jié)構(gòu)相關(guān)的是

線性表

棧

A:

鏈隊(duì)列

B:

二叉樹(shù)

C:

答D:案：C

解析：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈隊(duì)列。它是一種限制在表頭刪除和表尾插入操作的單鏈

表。顯然，僅看單鏈表的頭指針是不便在表尾作插入操作的,為此再增加一個(gè)尾指針，使

其指向鏈表上的最后一個(gè)結(jié)點(diǎn)，于是，二個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一確

定。P77

2、【單選題】將20個(gè)數(shù)據(jù)元素的線性表存儲(chǔ)在數(shù)組中，若第9個(gè)元素的存儲(chǔ)地址是1000，

第11個(gè)元素的存儲(chǔ)地址是1040，則最后一個(gè)元素的存儲(chǔ)地址是

1200

1210

A:

1215

B:

1220

C:

答D:案：D

3、【單選題】設(shè)棧的初始狀態(tài)為空，元素1,3,5,2,4依次入棧，不能得到的出棧序列是

5,1,3,2,4

4,2,5,3,1

A:

2,4,5,3,1

B:

1,3,5,2,4

C:

答D:案：A

4、【單選題】設(shè)指針變量p指向非空單鏈表中的結(jié)點(diǎn)，next是結(jié)點(diǎn)的指針域，現(xiàn)要?jiǎng)h除p

所指結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)，則下列語(yǔ)句中正確的是

while(p!NULL){q=p;p=p->next;free(q);}

while(p!NULL){q=p->next=p->next->next;free(q);}

A:

while(p->next!=NULL){q=p->next;p=p->next;free(q);}

B:

while(p->next!=NULL{q=p->next;p->next=p->next->next;free(q);}

C:

D:

答案：D

5、【單選題】已知廣義表LS=(((a,b),(c,d)),(e,f,(g,h,i))),LS的深度是

2

3

A:

4

B:

5

C:

答D:案：B

6、【單選題】已知一棵高度為4的完全二叉樹(shù)T的第4層上共有3個(gè)葉子結(jié)點(diǎn)，則T中葉子

結(jié)點(diǎn)的個(gè)數(shù)是

4

5

A:

6

B:

7

C:

答D:案：B

7、【單選題】已知二叉樹(shù)T的前序遍歷序列為a,b,c,d,e,則前序遍歷序列與T相同的不同

二叉樹(shù)個(gè)數(shù)（不包含T)是

11

12

A:

13

B:

14

C:

答D:案：C

8、【單選題】采用鄰接矩陣存儲(chǔ)含n個(gè)頂點(diǎn)和e條邊的有向圖G,鄰接矩陣中0的個(gè)數(shù)是

nxn-e

nxn-2e

A:

n(n-1)/2-e

B:

n(n-1)/2-2e

C:

答D:案：A

9、【單選題】無(wú)向圖中所有頂點(diǎn)的度數(shù)之和是10，則頂點(diǎn)的最大度數(shù)是

5

6

A:

7

B:

C:

10

答D:案：A

10、【單選題】設(shè)有向圖G含有n個(gè)頂點(diǎn)、e條邊，使用鄰接矩陣存儲(chǔ)。對(duì)G求拓?fù)湫蛄兴?/p>

法的時(shí)間復(fù)雜度是

O(n)

O(e)

A:

O(n2)

B:

O(nxe)

C:

答D:案：C

11、【單選題】對(duì)數(shù)據(jù)序列(15,12,13,12,8,4,5)采用冒泡排序進(jìn)行升序排序，兩趟排序后

得到的排序結(jié)果是

12,13,12,8,4,5,15

12,12,8,4,5,13,15

A:

5,4,8,12,12,13,15

B:

4,5,8,12,12,13,15

C:

答D:案：B

12、【單選題】下列選項(xiàng)中，穩(wěn)定的排序方法是

直接插入排序

直接選擇排序

A:

希爾排序

B:

堆排序

C:

答D:案：A

解析：直接插入排序是一種比較簡(jiǎn)單的排序方法，它的基本操作是：假設(shè)待排序的記錄存

儲(chǔ)在數(shù)組R[l..n]中，在排序過(guò)程的某一時(shí)刻，R被劃分成兩個(gè)子區(qū)間，和R[i..n],其中

前一個(gè)為已排好序的有序區(qū)，而后一個(gè)為無(wú)序區(qū)，開(kāi)始時(shí)有序區(qū)中只含有一個(gè)元素R[l],

無(wú)序區(qū)為R[2..n]。排序過(guò)程中，只需要每次從無(wú)序區(qū)中取出第一個(gè)元素，把它插入到有

序區(qū)的適當(dāng)位置，使之成為新的有序區(qū)，依次這樣經(jīng)過(guò)?-1次插入后，無(wú)序區(qū)為空，有序

區(qū)中包含了全部〃個(gè)元素，至此排序完畢。P170

13、【單選題】關(guān)鍵碼序列為30,77,57,12,25,86，建立的初始大根堆是

77,30,57,12,25,86

86,77,57,12,25,30

A:

86,77,57,30,25,12

B:

C:

86,57,77,25,30,12

答D:案：B

14、【單選題】在一棵二叉排序樹(shù)中，關(guān)鍵字所在結(jié)點(diǎn)是關(guān)鍵字m所在結(jié)點(diǎn)的孩子結(jié)點(diǎn)，則

n一定大于m

n一定小于m

A:

n一定等于m

B:

n與m的大小關(guān)系不確定

C:

答D:案：D

15、【單選題】設(shè)散列表長(zhǎng)m=14,散列函數(shù)H(key)=key%13。采用線性探測(cè)法處理沖突。表

中已按散列地址保存了3個(gè)關(guān)鍵字16,30,18，此時(shí)存儲(chǔ)關(guān)鍵字29的探查次數(shù)是

1

2

A:

3

B:

4

C:

答D:案：D

16、【問(wèn)答題】設(shè)電文字符集是{e?,e?,e?,e4,e5,e6},各字符出現(xiàn)的頻次分別為

{20,21,1,15,22,3}?，F(xiàn)要為該字符集設(shè)計(jì)哈夫曼編碼。請(qǐng)回答下列問(wèn)題。(1)給出構(gòu)造的

哈夫曼樹(shù)。(2)給出各字符的哈夫曼編碼。

答案：

17、【問(wèn)答題】已知圖G采用鄰接矩陣存儲(chǔ)，鄰接矩陣如題27圖所示。

(1)根據(jù)鄰接矩陣畫(huà)出圖G。

(2)寫(xiě)出圖G的從頂點(diǎn)A開(kāi)始的1個(gè)拓?fù)湫蛄小?/p>

答案：

18、【問(wèn)答題】有數(shù)據(jù)序列(15,16,04,12,21,23,43,31,16,13)，使用希爾排序方法將其排

成升序序列。請(qǐng)回答下列問(wèn)題。(1)分別寫(xiě)出增量序列的取值依次為4,1的希爾排序結(jié)果。

(2)計(jì)算增量為4時(shí)希爾排序中數(shù)據(jù)元素之間的總交換次數(shù)（兩個(gè)元素之間的交換記1次)。

答案：(1)原始值：15,16,04,12,21,23,43,31,16,13增量為4：

15,13,04,12,16,16,43,31,21,23增量為1：04,12,13,15,16,16,21,23,31,43

(2)1+2+0+0=3次

19、【問(wèn)答題】設(shè)二叉排序樹(shù)T如題29圖所示。現(xiàn)需在T中刪除結(jié)點(diǎn)22。請(qǐng)回答下列問(wèn)

題。

(1)刪除結(jié)點(diǎn)22有幾種不同的方法？

(2)分別畫(huà)出對(duì)應(yīng)于(1)中不同方法刪除結(jié)點(diǎn)22后的二叉排序樹(shù)。

答案：

20、【問(wèn)答題】順序表類(lèi)型定義如下：

#defineListSize100

typedefstruct{

intdata[ListSize]

intlength;

}SeqList;

閱讀程序，并回答下列問(wèn)題。

(1)若SL1->data中的數(shù)據(jù)為(13,12,23,7，-27,36,123,52,31)，SLl->length=9,SL2-

>data中的數(shù)據(jù)為(-7,17，-23,18,37,22,41,15)，SL2->length=8則調(diào)用函數(shù)

f30(&SL1;,&SL2;)后的返回值是什么？

(2)函數(shù)f30()的功能是什么？

答案：(1)30(2)分別計(jì)算兩個(gè)順序表中元素的平均值，輸出最大的平均值。

21、【問(wèn)答題】二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)類(lèi)型定義如下：

(1)設(shè)二叉樹(shù)T如題31圖所示，給出執(zhí)行f31(T)的輸出結(jié)果。

(2)給出該算法的時(shí)間復(fù)雜度。

答案：(1)ACDEB(2)O(n)

22、【問(wèn)答題】待排序記錄的數(shù)據(jù)類(lèi)型定義如下：

下列函數(shù)f32()的功能是用直接插入排序?qū)樞虮戆瓷蜻M(jìn)行排序，請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)

內(nèi)容使算法完整。

答案：(1)j=i(2)temp.key<R[j-1].key(3)j--

23、【問(wèn)答題】二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)類(lèi)型定義如下：

閱讀程序，并回答下列問(wèn)題。

(1)設(shè)二叉樹(shù)T如題33圖所示，bt是指向根結(jié)點(diǎn)的指針。給出執(zhí)行f33(bt,15,25)的輸出

結(jié)果。

(2)給出函數(shù)f33()的功能。

答案：(1)181617(2)在按RNL(右子樹(shù)，根節(jié)點(diǎn)，左子樹(shù))次序遍歷二叉樹(shù)時(shí)，輸出大

于等于left且小于right的元素值。

24、【問(wèn)答題】設(shè)順序表L按升序排列，請(qǐng)編寫(xiě)函數(shù)f34(),要求用二分查找確定插入位置，

將元素x插入到L中，使L保持有序。函數(shù)f34()的原型為：void

f34(SeqList*L,DataTypex)

答案：

25、【填空題】鏈棧、順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)不同，數(shù)據(jù)的運(yùn)算也不同，它們的_____結(jié)構(gòu)相

同。

答案：邏輯

26、【填空題】若指針p和q分別指向單鏈表L中的兩個(gè)相鄰結(jié)點(diǎn)，且q指向的是終端結(jié)

點(diǎn)。則在p所指結(jié)點(diǎn)之后插入指針r所指結(jié)點(diǎn)的語(yǔ)句是r->next=q;_______;。

答案：p->next=r

27、【填空題】實(shí)現(xiàn)遞歸函數(shù)調(diào)用和返回的數(shù)據(jù)結(jié)構(gòu)是_____。

答案：棧

28、【填空題】廣義表（(a,b),(c,d),(e,f),(g,h))的表尾是______。

答案：((c,d),(e,f),(g,h))

29、【填空題】已知完全二叉樹(shù)的按層遍歷序列存儲(chǔ)在一維數(shù)組A[0..n-1]中，則

A[i](1≤i≤n-1)的父結(jié)點(diǎn)是_______。

答案：A[(i-1)/2]

30、【填空題】如果有向無(wú)環(huán)圖G中至少有兩個(gè)頂點(diǎn)的入度為0，則G中至少有____個(gè)不同

的拓?fù)湫蛄小?/p>

答案：2

31、【填空題】將森林T轉(zhuǎn)換為一棵二叉樹(shù)T1,則T中葉子結(jié)點(diǎn)在T1中滿足