??2021年10月自考02331數(shù)據(jù)結(jié)構(gòu)真題及答案

全國2021年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

課程代碼:02331

1.請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。

2.答題前,考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。

選擇題部分

注意事項(xiàng):每小題選出答案后,用2B鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng),用橡皮擦干凈后,再選涂其他答案標(biāo)號(hào)。不能答在試題卷上。

一、單項(xiàng)選擇題:本大題共15小題，每小題2分，共30分。在每小題列出的備選項(xiàng)中只有一項(xiàng)是最符合題目要求的，請將其選出。

1.下列關(guān)于數(shù)據(jù)項(xiàng)和數(shù)據(jù)元素的敘述中，正確的是

A.數(shù)據(jù)項(xiàng)只能是數(shù)值類型

B.數(shù)據(jù)項(xiàng)可以包含數(shù)據(jù)元素

C.數(shù)據(jù)元素是數(shù)據(jù)的基本單位

D.數(shù)據(jù)元素是由數(shù)據(jù)項(xiàng)組成的集合

2.下列關(guān)于抽象數(shù)據(jù)類型的敘述中，正確的是

A.抽象數(shù)據(jù)類型與具體實(shí)現(xiàn)相關(guān)

B.抽象數(shù)據(jù)類型是由C語言本身提供的

C.抽象數(shù)據(jù)類型是C語言提供的類型的邏輯描述

D.抽象數(shù)據(jù)類型將數(shù)據(jù)定義和數(shù)據(jù)操作封裝在一起

3.設(shè)有初始為空的棧S，入棧序列是f,e,d,c, b,a,出棧序列是d,e,a,b,c,f,則需要為S分配的空間大小至少是

A.2

B.3

C.4

D.5

4.指針head指向帶頭結(jié)點(diǎn)的單鏈表L的表頭，結(jié)點(diǎn)結(jié)構(gòu)為: ,其中，data為int型，next 是指向后繼結(jié)點(diǎn)的指針。指針p指向L中的首個(gè)數(shù)據(jù)結(jié)點(diǎn)，指針q指向p的后繼結(jié)點(diǎn)?，F(xiàn)要交換p. q所指向的兩結(jié)點(diǎn)中的data值，下列選項(xiàng)中，不能完成該任務(wù)的操作是

A. head->next=q; p->next=q->next; q->next= p;

B. p->next= q->next; head->next=q; q->next= p;

C. q->next- P; p->next= q->next; head->next = q;

D. int temp= p->data; p->data = q->data; q->data = temp;

5.采用行優(yōu)先壓縮存儲(chǔ)方式保存6行6列對(duì)稱矩陣A的上三角部分，每個(gè)元素占2個(gè)單元，若A中第一個(gè)元素a11的存儲(chǔ)地址是10,則元素a34的存儲(chǔ)地址是

A.22

B.26

C.34

D.40

6.已知廣義表L=((, i), h), (x,i,a,o))， 下列運(yùn)算中， 結(jié)果得到h的是

A. head( tail(L))

B. head( tail( head(L)))

C. head( head( tail(L)))

D. head( head( tail( tail(L))))

7. 下列關(guān)于二叉樹的敘述中，錯(cuò)誤的是

A.二叉樹可以為空

B.二叉樹可以保存在數(shù)組中

C.二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)多于度為1結(jié)點(diǎn)的個(gè)數(shù)

D.二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)多于度為2結(jié)點(diǎn)的個(gè)數(shù)

8.若二叉樹的前序遍歷序列是ABCD,中序遍歷序列是ACDB，則其后序遍歷序列是

A. ABDC

B. ACDB

C. CDBA

D. DCBA

9.對(duì)下圖進(jìn)行廣度優(yōu)先搜索遍歷，正確的遍歷序列是

A. bdeac

B. badce

C. acedb

D. abced

10.關(guān)于圖G的深度優(yōu)先生成樹T1與廣度優(yōu)先生成樹T2，下列敘述中正確的是

A.T1與T2一定相同

B.T1與T2可能相同

C.T1與T2一定不相同

D. T1與T2中所含邊數(shù)不相等

11. 對(duì)n個(gè)記錄進(jìn)行排序，最壞情況下，時(shí)間復(fù)雜度不是O(n2)的排序方法是

A.直接插入排序

B.冒泡排序

C.快速排序

D.堆排序

12.下 列排序方法中，不宜在鏈表上實(shí)現(xiàn)的是

A.直接插入排序

B.快速排序

C.歸并排序

D.基數(shù)排序

13.若元素序列11,13, 15,7,8, 9,23,2, 5是采用下列排序算法之一，得到的第2趟排序后的結(jié)果，則該排序算法是

A.直接插入排序

B.冒泡排序

C.選擇排序

D.二路歸并排序

14. 在長度為n (n≥100) 的有序線性表中進(jìn)行二分查找，查找成功時(shí)，查找長度不多于4的關(guān)鍵字個(gè)數(shù)是

A.4

B.7

C.15

D.100

15.將下列數(shù)據(jù)分別依次插入到初始為空的二叉排序樹中，能得到高度最低二叉排序樹的是

A.9,7,2,1,4, 10

B.6,4, 1,8, 10, 5

C. 5,1,2, 6,3, 4

D.2,4,7,5, 8, 10

非選擇題部分

注意事項(xiàng):用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上,不能答在試題卷上。

二、填空題:本大題共10小題，每小題2分，共20分。

16.非空的帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，終端結(jié)點(diǎn)的指針域指向的是鏈表的_______。

17.己知循環(huán)隊(duì)列存儲(chǔ)在- -維數(shù)組A[0..n-1]中，頭指針是front,尾指針是rear,初始時(shí)front的值和rear的值均是0，則第1個(gè)入隊(duì)元素存儲(chǔ)在數(shù)組中存儲(chǔ)位置的下標(biāo)是_______。

18.將中綴表達(dá)式9- (2+4*7)轉(zhuǎn)換為后綴表達(dá)式的結(jié)果是________。

19.廣義表G= (27, G)的深度是________。

20.具有n (n≥1)個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)，空指針域的個(gè)數(shù)是_______。

21.兩個(gè)無向連通圖均含有10 個(gè)頂點(diǎn)，它們之間的邊數(shù)差最大是________。

22.有向圖G存在拓?fù)湫蛄械臈l件是________。

23.若用C語言的數(shù)組A保存含n (n≥10) 個(gè)元素的大根堆，則第3大元素在A中的下標(biāo)最大是________。

24.分塊查找又稱為_______。

25.非空的3階B樹中，每個(gè)非根結(jié)點(diǎn)中含有的關(guān)鍵字個(gè)數(shù)最少是_

三、解答題:本大題共4小題，每小題5分，共20分。

26.鏈棧為什么不必設(shè)置頭結(jié)點(diǎn)?

27.已知字符集{ a,b,c, d,e }中各字符出現(xiàn)的頻次分別為2,3, 6, 8, 10,對(duì)字符集進(jìn)行哈夫曼編碼，字符a的編碼是000,字符e的編碼是11,則其余3個(gè)字符的編碼分別是什么?

28.設(shè)有向圖G如題28圖所示，給出圖G的鄰接矩陣。

題28圖

29.設(shè)有關(guān)鍵字16, 15,32, 11, 6, 30，將它們依次保存在哈希表(長度為7的一維數(shù)組)中，哈希函數(shù)為H(k) = k mod 7,采用線性探查法解決沖突。已知關(guān)鍵字16已放置在數(shù)組下標(biāo)為2的位置。請畫出哈希表。

四、算法閱讀題:本大題共4小題，每小題5分，共20分。

30.程序f30( )創(chuàng)建了一個(gè)帶頭結(jié)點(diǎn)的含n (n≥3)個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表L, L前兩個(gè)數(shù)據(jù)結(jié)點(diǎn)中的data值均為1,從第3個(gè)結(jié)點(diǎn)開始，結(jié)點(diǎn)的data值是其前兩個(gè)結(jié)點(diǎn)data值之和。請?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。

五、算法設(shè)計(jì)題:本題10分。

34.設(shè)n個(gè)整數(shù)存放在數(shù)組A中，請編寫函數(shù)f34(intA[],intn),將所有奇數(shù)調(diào)整到所有偶數(shù)之前。