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

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

0214220234

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

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

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

A:

類型

B:

運(yùn)算實(shí)現(xiàn)

C:

答D:案：B

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

malloc(p)

sizeof(p)

A:

free(p)

B:

p=NULL

C:

答D:案：C

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

n/4

n/3

A:

n/2

B:

n

C:

答D:案：C

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

棧

隊(duì)列

A:

鏈表

B:

數(shù)組

C:

答D:案：D

5、【單選題】?？梢詫?shí)現(xiàn)

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

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

A:

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

B:

C:

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

答D:案：B

6、【單選題】順序隊(duì)列結(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)個(gè)結(jié)點(diǎn)的有限集合

A:

任何只含一個(gè)結(jié)點(diǎn)的集合不是一棵樹

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é)點(diǎn)P排在結(jié)點(diǎn)Q之前的條件是：在二叉樹中

P在Q的左邊

P在Q的右邊

A:

P是Q的祖先

B:

P是Q的子孫

C:

D:

答案：A

11、【單選題】無向圖中一個(gè)頂點(diǎn)的度是指圖中

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

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

A:

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

B:

與該頂點(diǎn)相鄰接的頂點(diǎn)數(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)解決沖突的幾種方法，描述正確的是

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

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

A:

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

B:

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

C:

答D:案：D

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

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ù)量很大時(shí)，排序方法效果較好的是

堆排序和快速排序

堆排序和直接插入排序

A:

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

B:

直接選擇排序和快速排序

C:

D:

答案：A

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

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

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

如何判斷圖中是否存在從頂點(diǎn)i到頂點(diǎn)j的弧？(3)如何求頂點(diǎn)i的出度？

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

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

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

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

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

答案：(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)用二次探測

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

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

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

??

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

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

?

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

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

答案：

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

答案：

22、【問答題】

答案：

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

答案：鏈?zhǔn)?/p>

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

表。

答案：循環(huán)

25、【填空題】棧的插入運(yùn)算稱為（）。

答案：進(jìn)棧

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

答案：頭結(jié)點(diǎn)

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

（上）三角矩陣。

答案：主對(duì)角線

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

條件是（）。

答案：SQ.rear==SQ.front

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

入一維數(shù)組中。

答案：編號(hào)

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

答案：5

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

答案：入度

32、【填空題】一個(gè)圖