數據結構導論2018年4月真題及答案解析（02142）

數據結構導論2018年4月真題及答案解析（02142），該試卷為數據結構導論自考歷年真題試卷，包含答案及詳細解析。

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

1.數據的邏輯結構分為四種，其中結構最復雜的是(　　)

A.集合
B.線性結構
C.樹形結構
D.圖結構

2.下面程序是矩陣轉置算法 MM 的實現過程，其時間復雜度為(　　)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.設順序表的表長為 n，則刪除一個元素在最壞情況下元素移動次數為(　　)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

12.在用鄰接表表示圖時，對圖進行深度優先搜索遍歷的算法的時間復雜度為(　　)

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

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

A.它們的邏輯結構不同
B.施加在其上的操作不同
C.所包含的數據元素類型不同
D.存儲實現不同

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

A.奇數
B.偶數
C.素數
D.充分大的數

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

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

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

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

12.單鏈表各個結點在內存中的存儲位置并_________連續。

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

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

15.二叉樹的任一結點都有兩棵子樹，并且這兩棵子樹之間有_________關系。

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

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

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

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

110.完成拓撲排序的前提條件是 AOV 網中不允許出現_________。

111.數據元素的鍵值和_________之間建立的對應關系稱為散列函數。

112.靜態查找表是以具有相同特性的數據元素集合為邏輯結構，但不包括插入和_________運算。

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

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

21.將題 29 圖所示的二叉樹轉換為對應的樹或森林。

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

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

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

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

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

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

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