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

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

0214220234

1、【單選題】與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的

存儲結(jié)構(gòu)

邏輯結(jié)構(gòu)

A:

類型

B:

運算實現(xiàn)

C:

答D:案：B

2、【單選題】在單鏈表中，釋放已移出結(jié)點p的空間使用語句

malloc(p)

sizeof(p)

A:

free(p)

B:

p=NULL

C:

答D:案：C

3、【單選題】在表長為n的順序表上做插入運算，平均要移動的結(jié)點數(shù)為

n/4

n/3

A:

n/2

B:

n

C:

答D:案：C

4、【單選題】線性表實現(xiàn)順序存儲使用

棧

隊列

A:

鏈表

B:

數(shù)組

C:

答D:案：D

5、【單選題】棧可以實現(xiàn)

函數(shù)的嵌套調(diào)用和操作系統(tǒng)中進程調(diào)度

函數(shù)的嵌套調(diào)用和程序遞歸的處理

A:

程序遞歸的處理和操作系統(tǒng)中進程調(diào)度

B:

C:

操作系統(tǒng)中進程調(diào)度和網(wǎng)絡(luò)管理中的打印服務(wù)

答D:案：B

6、【單選題】順序隊列結(jié)構(gòu)類型中，data為

一維數(shù)組

二維數(shù)組

A:

單鏈表

B:

循環(huán)鏈表

C:

答D:案：A

7、【單選題】下列關(guān)于樹的描述，正確的是

樹形結(jié)構(gòu)不可以表示具有層次結(jié)構(gòu)的數(shù)據(jù)

樹是n(n≥0)個結(jié)點的有限集合

A:

任何只含一個結(jié)點的集合不是一棵樹

B:

樹形結(jié)構(gòu)的定義是非遞歸的

C:

答D:案：B

8、【單選題】葉子的度為

-1

0

A:

1

B:

2

C:

答D:案：B

9、【單選題】樹的遍歷有三種，為

先序、中序和后序遍歷

先序、中序和層次遍歷

A:

先序、后序和層次遍歷

B:

中序、后序和層次遍歷

C:

答D:案：A

10、【單選題】二叉樹的中序序列中，結(jié)點P排在結(jié)點Q之前的條件是：在二叉樹中

P在Q的左邊

P在Q的右邊

A:

P是Q的祖先

B:

P是Q的子孫

C:

D:

答案：A

11、【單選題】無向圖中一個頂點的度是指圖中

通過該頂點的簡單路徑數(shù)

與該頂點連通的頂點數(shù)

A:

通過該頂點的回路數(shù)

B:

與該頂點相鄰接的頂點數(shù)

C:

答D:案：D

12、【單選題】下列序列中，符合堆定義的是

(100,80,55,60,50,40,58,35,20)

(100,80,55,60,50,40,35,58,20)

A:

(100,80,55,58,50,40,60,35,20)

B:

(100,70,55,60,50,40,58,35,20)

C:

答D:案：B

13、【單選題】下列有關(guān)解決沖突的幾種方法，描述正確的是

線性探測法生成后繼散列地址計算復(fù)雜

二次探測法生成的后繼散列地址是連續(xù)的

A:

鏈地址法是挑選部分同義詞建單鏈表來解決沖突

B:

多重散列法不易產(chǎn)生“堆積”

C:

答D:案：D

14、【單選題】雙向循環(huán)鏈表的對稱性可以表示為

p=p->prior->next=p->next->prior

p=p->next=p->prior

A:

p=p->next->next=p->prior->prior

B:

p=p->next->next=p->next

C:

答D:案：A

15、【單選題】待排序記錄的數(shù)量很大時，排序方法效果較好的是

堆排序和快速排序

堆排序和直接插入排序

A:

直接插入排序和直接選擇排序

B:

直接選擇排序和快速排序

C:

D:

答案：A

16、【問答題】題圖給出了矩陣A,請將矩陣A表示成三元組表。

答案：((0,1,2),(2,3,5),(2,5,9),((3,1,6),(4,4,4))。

17、【問答題】根據(jù)有向圖的鄰接表回答下列問題：(1)如何判斷圖中有多少條?。?2)

如何判斷圖中是否存在從頂點i到頂點j的?。?3)如何求頂點i的出度？

答案：(1)圖中弧的條數(shù)為鄰接表的表結(jié)點的個數(shù)。(2)要判斷圖中是否存在從i到j(luò)的

弧,只要看第i個表頭結(jié)點的鏈表中是否存在adjvex為j的表結(jié)點。(3)頂點i的出度

即為:第i個表頭結(jié)點的鏈表中表結(jié)點的個數(shù)。

18、【問答題】設(shè)某通信系統(tǒng)中一個待傳輸?shù)奈谋居?個不同字符，它們的出現(xiàn)頻率分別是

0.5,0.8,1.4,2.2,2.3,2.8,試設(shè)計哈夫曼編碼。

答案：(1)出現(xiàn)頻率為0.5的字符編碼為1000。(2)出現(xiàn)頻率為0.8的字符編碼為

1001。(3)出現(xiàn)頻率為1.4的字符編碼為101。(4)出現(xiàn)頻率為2.2的字符編碼為00。

(5)出現(xiàn)頻率為2.3的字符編碼為01。(6)出現(xiàn)頻率為2.8的字符編碼為11。

19、【問答題】如題圖所示長度為13的散列表，其散列函數(shù)為H(key)=keymod13,在表

中已填入鍵值分別為16,30,54的元素。(1)現(xiàn)要插入鍵值為29的元素，應(yīng)用二次探測

法，計算填入散列表中單元的序號。（要求給出求解過程)(2)二次探測法有什么缺點？

答案：(1)H(29)=29mod13=3,地址3已有鍵值為16的元素,產(chǎn)生沖突。當發(fā)生沖突時，應(yīng)

用二次探測法,得到下一個地址d=(3+12)mod13=4仍沖突,則再求下一個地址d=(3-

??

12)mod13=2仍沖突,直到散列地址為d=(3+22)mod13=7時其位置上沒有元素,則元素填入

散列表中序號為7的位置。(2)不易探測到整個散列表的所有空間。

?

20、【問答題】給定表(19,14,22,01,66,21,83,27,56,13,10)，試按元素在表中的次序?qū)⑺?/p>

們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。

答案：

21、【問答題】寫出計算方陣A[n][n]與B[n][n]的乘積C[n][n]的算法。

答案：

22、【問答題】

答案：

23、【填空題】表示數(shù)據(jù)元素之間的關(guān)聯(lián)方式主要有順序存儲方式和（）存儲方式。

答案：鏈式

24、【填空題】在單鏈表中，如果讓最后一個結(jié)點的指針域指向第一個結(jié)點可以構(gòu)成（）鏈

表。

答案：循環(huán)

25、【填空題】棧的插入運算稱為（）。

答案：進棧

26、【填空題】隊列的鏈接實現(xiàn)實際上是使用一個帶有（）的單鏈表來表示隊列。

答案：頭結(jié)點

27、【填空題】以（）為界的上（下）半部分是一個固定的值c或零，這樣的矩陣叫做下

（上）三角矩陣。

答案：主對角線

28、【填空題】循環(huán)隊列結(jié)構(gòu)類型中含有三個域：data、front和rear,循環(huán)隊列SQ為空的

條件是（）。

答案：SQ.rear==SQ.front

29、【填空題】對于任何完全二叉樹來說，可以采用以（）作為數(shù)組的下標的方法將結(jié)點存

入一維數(shù)組中。

答案：編號

30、【填空題】如果一棵二叉樹中度數(shù)為0的結(jié)點有6個，那么度數(shù)為2的結(jié)點有（）個。

答案：5

31、【填空題】如果G是一個有向圖，則把以頂點v為終點的弧的數(shù)目稱為v的（）。

答案：入度

32、【填空題】一個圖