數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2018年4月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2018年4月真題及答案解析（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

一、單項(xiàng)選擇題(本大題共 15 小題，每小題 2 分，共 30 分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請將其選出并將“答題紙冶的相應(yīng)代碼涂黑。 錯(cuò)涂、多涂或未涂均無分。

1.數(shù)據(jù)的邏輯結(jié)構(gòu)分為四種，其中結(jié)構(gòu)最復(fù)雜的是(　　)

A.集合
B.線性結(jié)構(gòu)
C.樹形結(jié)構(gòu)
D.圖結(jié)構(gòu)

2.下面程序是矩陣轉(zhuǎn)置算法 MM 的實(shí)現(xiàn)過程，其時(shí)間復(fù)雜度為(　　)const int n = 3;void MM(int A[n][n]){   int i, j, temp;    for(i = 0; i <n; i++)      for(j = 0; j <i; j++)      {   temp =A[i][j];          A[i][j] =A[j][i];          A[j][i] = temp;      }}

A.O(1)
B.O(log₂n)
C.O(n²)
D.O(2ⁿ)

3.設(shè)順序表的表長為 n，則刪除一個(gè)元素在最壞情況下元素移動次數(shù)為(　　)

A.n-2
B.n-1
C.n
D.n+1

4.帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表 L 為空的條件是(　　)

A.L->next = = L->prior
B.L->prior = =NULL
C.(L->next = = L)&&(L->prior = = L)
D.(L->next = = L)&&(L->prior =NULL)

5.執(zhí)行進(jìn)棧操作，在元素 x 進(jìn)棧前需要進(jìn)行的操作是(　　)

A.判斷棧是否滿，若棧未滿，top 值加 1
B.判斷棧是否空，若棧未空，top 值加 1
C.判斷棧是否滿，若棧未滿，top 值減 1
D.判斷棧是否空，若棧未空，top 值減 1

6.關(guān)于隊(duì)列，下列敘述正確的是(　　)

A.隊(duì)列的元素個(gè)數(shù)可以無窮大
B.隊(duì)列中元素的類型可以不同
C.隊(duì)列是一個(gè)非線性的序列
D.隊(duì)列的特點(diǎn)是先進(jìn)先出

7.設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組 Q[30]中，隊(duì)列非空時(shí)，front 指示隊(duì)列首結(jié)點(diǎn)的前一個(gè)位置，rear 指示隊(duì)列尾結(jié)點(diǎn)。 如果隊(duì)列中元素的個(gè)數(shù)為 10，front 的值為 25，則 rear 應(yīng)指向的元素是(　　)

A.Q[4]
B.Q[5]
C.Q[14]
D.Q[15]

8.二叉樹第 i(i≥1)層上的結(jié)點(diǎn)數(shù)最多為(　　)

A.2i-1
B.i-1
C.2*i
D.2*(i-1)

9.關(guān)于二叉鏈表，下列敘述正確的是(　　)

A.二叉鏈表是二叉樹唯一的鏈?zhǔn)酱鎯Y(jié)構(gòu)
B.對二叉鏈表的訪問可以從任意結(jié)點(diǎn)開始
C.每個(gè)二叉鏈表不需要有一個(gè)指向根節(jié)點(diǎn)的指針
D.二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)包含一個(gè)數(shù)據(jù)域和兩個(gè)指針域

10.假設(shè)初始森林中共有 n 棵二叉樹，每棵樹中都僅有一個(gè)孤立的結(jié)點(diǎn)。將該森林構(gòu)造成哈夫曼樹，則最終求得的哈夫曼樹的結(jié)點(diǎn)數(shù)為(　　)

A.n-1
B.n
C.2n-1
D.2n

11.無向圖中的極大連通子圖是(　　)

A.連通分量
B.生成樹
C.強(qiáng)連通分量
D.強(qiáng)連通圖

12.在用鄰接表表示圖時(shí)，對圖進(jìn)行深度優(yōu)先搜索遍歷的算法的時(shí)間復(fù)雜度為(　　)

A.O(n)
B.O(n+e)
C.O(n²)
D.O(n³)

13.靜態(tài)查找表與動態(tài)查找表二者的根本差別在于(　　)

A.它們的邏輯結(jié)構(gòu)不同
B.施加在其上的操作不同
C.所包含的數(shù)據(jù)元素類型不同
D.存儲實(shí)現(xiàn)不同

14.在散列函數(shù) H( k )= k MOD m 中，一般來講，m 應(yīng)取(　　)

A.奇數(shù)
B.偶數(shù)
C.素?cái)?shù)
D.充分大的數(shù)

15.在下述四種排序算法中，所需輔助存儲量最多的是(　　)

A.堆排序
B.快速排序
C.直接選擇排序
D.歸并排序

二、填空題(本大題共 13 小題，每空 2 分，共 26 分)

11.線性表中如果結(jié)點(diǎn)數(shù)不為零，則除起始結(jié)點(diǎn)沒有直接前驅(qū)外，其他每個(gè)結(jié)點(diǎn)有且僅有_________個(gè)直接前驅(qū)。

12.單鏈表各個(gè)結(jié)點(diǎn)在內(nèi)存中的存儲位置并_________連續(xù)。

13.棧初始化運(yùn)算的目的是_________。

14.假設(shè)以 E 和 O 分別表示進(jìn)棧和出棧操作，則對輸入序列 a，b，c，d，e 進(jìn)行一系列操作EEOEEOEOOO之后，得到的輸出序列為_________。

15.二叉樹的任一結(jié)點(diǎn)都有兩棵子樹，并且這兩棵子樹之間有_________關(guān)系。

16.一棵樹中所有結(jié)點(diǎn)_________的最大值稱為該樹的高度。

17.高度為 h(h≥2)的完全二叉樹至少有_________個(gè)葉子結(jié)點(diǎn)。

18.圖的廣度優(yōu)先搜索遍歷類似于樹的按_________遍歷的過程。

19.稀疏矩陣可以采用_________法進(jìn)行壓縮存儲。

110.完成拓?fù)渑判虻那疤釛l件是 AOV 網(wǎng)中不允許出現(xiàn)_________。

111.數(shù)據(jù)元素的鍵值和_________之間建立的對應(yīng)關(guān)系稱為散列函數(shù)。

112.靜態(tài)查找表是以具有相同特性的數(shù)據(jù)元素集合為邏輯結(jié)構(gòu)，但不包括插入和_________運(yùn)算。

113.設(shè)表中元素的初始狀態(tài)是按鍵值遞增有序的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其按遞增順序進(jìn)行排序，_________排序方法最

三、應(yīng)用題(本大題共 5 小題，每小題 6 分，共 30 分)

21.將題 29 圖所示的二叉樹轉(zhuǎn)換為對應(yīng)的樹或森林。

22.假設(shè)某個(gè)電文由 5 個(gè)字母 a，b，c，d，e 組成，每個(gè)字母在電文中出現(xiàn)的次數(shù)為 7，9，5，6，12，試為這 5 個(gè)字母設(shè)計(jì)哈夫曼樹并寫出對應(yīng)的哈夫曼編碼。 (構(gòu)建新二叉樹時(shí)，要求新二叉樹的左子樹根的權(quán)值小于等于右子樹根的權(quán)值。)

23.題31圖所示為一有向圖，試給出該圖的鄰接表表示及對該圖進(jìn)行拓?fù)渑判虻母鞣N可能的拓?fù)湫蛄小?img style="width: 288px; height: 198px;" src="https://status.shangxueba.com/exam/2019-03-21/922029067186783.png" width="478" height="289"/>

24.設(shè)散列表長度為 11，散列函數(shù) H(key) = key mod 11(mod 為求余運(yùn)算)，給定的鍵值序列為:(3，12，13，27，34，22，38，25)。 試畫出采用線性探測法解決沖突時(shí)所構(gòu)造的散列表，并求出在等概率的情況下查找成功時(shí)的平均查找長度。

25.設(shè)有鍵值序列如題 33 表所示，現(xiàn)采用快速排序算法以位于最左位置的鍵值為基準(zhǔn)對它進(jìn)行排序。 請給出 57，72，88 這三個(gè)元素在第一趟快速排序后的位置。題33表

四、算法設(shè)計(jì)題(本大題共 2 小題，每小題 7 分，共 14 分)

31.假設(shè)單鏈表的類型定義如下:typedef struct node{   DataType data;    struct node *next;}Node, *LinkList;設(shè)計(jì)算法 InitiateLinkList()實(shí)現(xiàn)單鏈表的初始化。

32.已知靜態(tài)查找表順序存儲結(jié)構(gòu)的類型定義如下:const int Maxsize = 20;typedef struct{    KeyType key;   //關(guān)鍵字    …                    //其他域}TableElem;typedef struct{   TableElem elem[Maxsize+1];    int n;}SqTable;設(shè)計(jì)實(shí)現(xiàn)有序表二分查找算法 SearchBin(SqTable T, KeyType key)(假定有序表是按鍵值 從小到大有序)。