?數(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)論2018年4月真題及答案解析（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考歷年真題試卷，包含答案及詳細解析。

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

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 的實現(xiàn)過程，其時間復(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，則刪除一個元素在最壞情況下元素移動次數(shù)為(　　)

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

4.帶頭結(jié)點的雙向循環(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í)行進棧操作，在元素 x 進棧前需要進行的操作是(　　)

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

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

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

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

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

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

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

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

A.二叉鏈表是二叉樹唯一的鏈式存儲結(jié)構(gòu)
B.對二叉鏈表的訪問可以從任意結(jié)點開始
C.每個二叉鏈表不需要有一個指向根節(jié)點的指針
D.二叉鏈表的結(jié)點結(jié)構(gòu)包含一個數(shù)據(jù)域和兩個指針域

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

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

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

A.連通分量
B.生成樹
C.強連通分量
D.強連通圖

12.在用鄰接表表示圖時，對圖進行深度優(yōu)先搜索遍歷的算法的時間復(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.存儲實現(xiàn)不同

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

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

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

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

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

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

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

13.棧初始化運算的目的是_________。

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

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

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

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

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

19.稀疏矩陣可以采用_________法進行壓縮存儲。

110.完成拓撲排序的前提條件是 AOV 網(wǎng)中不允許出現(xiàn)_________。

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

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

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

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

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

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

23.題31圖所示為一有向圖，試給出該圖的鄰接表表示及對該圖進行拓撲排序的各種可能的拓撲序列。

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

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

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

31.假設(shè)單鏈表的類型定義如下:typedef struct node{   DataType data;    struct node *next;}Node, *LinkList;設(shè)計算法 InitiateLinkList()實現(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è)計實現(xiàn)有序表二分查找算法 SearchBin(SqTable T, KeyType key)(假定有序表是按鍵值 從小到大有序)。