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

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

課程代碼:02331

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

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

選擇題部分

注意事項:每小題選出答案后,用2B鉛筆把答題紙上對應題目的答案標號涂黑。如需改動,用橡皮擦干凈后,再選涂其他答案標號。不能答在試題卷上。

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

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

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

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

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

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

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

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

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

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

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

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

A.2

B.3

C.4

D.5

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

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)先壓縮存儲方式保存6行6列對稱矩陣A的上三角部分，每個元素占2個單元，若A中第一個元素a11的存儲地址是10,則元素a34的存儲地址是

A.22

B.26

C.34

D.40

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

A. head( tail(L))

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

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

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

7. 下列關于二叉樹的敘述中，錯誤的是

A.二叉樹可以為空

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

C.二叉樹中葉結點的個數(shù)多于度為1結點的個數(shù)

D.二叉樹中葉結點的個數(shù)多于度為2結點的個數(shù)

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

A. ABDC

B. ACDB

C. CDBA

D. DCBA

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

A. bdeac

B. badce

C. acedb

D. abced

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

A.T1與T2一定相同

B.T1與T2可能相同

C.T1與T2一定不相同

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

11. 對n個記錄進行排序，最壞情況下，時間復雜度不是O(n2)的排序方法是

A.直接插入排序

B.冒泡排序

C.快速排序

D.堆排序

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

A.直接插入排序

B.快速排序

C.歸并排序

D.基數(shù)排序

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

A.直接插入排序

B.冒泡排序

C.選擇排序

D.二路歸并排序

14. 在長度為n (n≥100) 的有序線性表中進行二分查找，查找成功時，查找長度不多于4的關鍵字個數(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

非選擇題部分

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

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

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

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

18.將中綴表達式9- (2+4*7)轉換為后綴表達式的結果是________。

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

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

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

22.有向圖G存在拓撲序列的條件是________。

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

24.分塊查找又稱為_______。

25.非空的3階B樹中，每個非根結點中含有的關鍵字個數(shù)最少是_

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

26.鏈棧為什么不必設置頭結點?

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

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

題28圖

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

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

30.程序f30( )創(chuàng)建了一個帶頭結點的含n (n≥3)個數(shù)據(jù)結點的單鏈表L, L前兩個數(shù)據(jù)結點中的data值均為1,從第3個結點開始，結點的data值是其前兩個結點data值之和。請在空白處填上適當內容將算法補充完整。

五、算法設計題:本題10分。

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