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

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

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

1.結點按邏輯關系依次排列形成一條“鎖鏈”的數據結構是(　　)

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

2.下面算法程序段的時間復雜度為(　　)for ( int i=0; i<m; i++)       for ( int j=0; j<n; j++)               a[i][j]=i*j;

A.

B.

3.線性結構是(　　)

A.具有n(n≥0)個表元素的有窮序列
B.具有n(n≥0)個字符的有窮序列
C.具有n(n≥0)個結點的有窮序列
D.具有n(n≥0)個數據項的有窮序列

4.單鏈表中刪除由某個指針變量指向的結點的直接后繼，該算法的時間復雜度是(　　)

A.O(1)

B.

C.O(log₂n)

5.關于串的敘述，正確的是(　　)

A.串是含有一個或多個字符的有窮序列
B.空串是只含有空格字符的串
C.空串是含有零個字符或含有空格字符的串
D.串是含有零個或多個字符的有窮序列

6.棧的輸入序列依次為1，2，3，4，則不可能的出棧序列是(　　)

A.1243
B.1432
C.2134
D.4312

7.隊列是(　　)

A.先進先出的線性表
B.先進后出的線性表
C.后進先出的線性表
D.隨意進出的線性表

8.10階上三角矩陣壓縮存儲時需存儲的元素個數為(　　)

A.11
B.56
C.100
D.101

9.深度為k(k≥1)的二叉樹，結點數最多有(　　)

A.2k 個
B.(2^k -1)個
C.2^k-1個
D.(2^k+1)個

10.具有12個結點的二叉樹的二叉鏈表存儲結構中，空鏈域NULL的個數為(　　)

A.11
B.13
C.23
D.25

11.具有n個頂點的無向圖的邊數最多為(　　)

A.n+1
B.n(n+1)
C.n(n-1)/2
D.2n(n+1)

12.三個頂點v1，v2，v3的圖的鄰接矩陣為，該圖中頂點v3的入度為(　　)

A.0
B.1
C.2
D.3

13.順序存儲的表格中有60000個元素，已按關鍵字值升序排列，假定對每個元素進行查找的概率是相同的，且每個元素的關鍵字值不相同。用順序查找法查找時，平均比較次數約為(　　)

A.20000
B.30000
C.40000
D.60000

14.外存儲器的主要特點是(　　)

A.容量小和存取速度低
B.容量大和存取速度低
C.容量大和存取速度高
D.容量小和存取速度高

15.在待排數據基本有序的前提下，效率最高的排序算法是(　　)

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

二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。

11.數據的不可分割的最小標識單位是________，它通常不具有完整確定的實際意義，或不被當作一個整體對待。

12.運算分為加工型運算和引用型運算，讀取操作是________運算。

13.帶有頭結點的單向循環鏈表L(L為頭指針)中，指針p所指結點為尾結點的條件是 ________。

14.在雙鏈表中，前趨指針和后繼指針分別為prior和next。若使指針p往后移動兩個結點，則需執行語句________。

15.元素s₁，s₂，s₃，s₄，s₅，s₆依次進入順序棧S，如果6個元素的退棧順序為s₂，s₃，s₄，s₆，s₅，s₁，則順序棧的容量至少為________。

16. 稀疏矩陣一般采用的壓縮存儲方法是________。

17. 在一棵樹中，________結點沒有雙親。

18.一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、自左至右給所有結點編號。設根結點編號為1，若編號為i的結點有父結點，那么其父結點的編號為________。

19.二叉樹的二叉鏈表存儲結構中判斷指針p所指結點為葉子結點的條件是________。

110.邊稀疏的無向圖采用________存儲較省空間。

111.除第一個頂點和最后一個頂點相同外，其余頂點不重復的回路，稱為________。

112.二分查找算法的時間復雜度是________。

113.要將序列{51，18，23，68，94，70，73}建成堆，則只需把18與________相互交換。

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

21.將題29圖所示的一棵二叉樹轉換成對應的森林。題29圖

22.給定權值{3，9，13，5，7｝，構造相應的哈夫曼(Huffman)樹，并計算其帶權路徑長度。

23.寫出題31圖的鄰接矩陣和每個頂點的入度與出度。題31圖

24.二叉排序樹的各結點的值依次為20~28，請在題32圖中標出各結點的值。                              題32圖

25.用冒泡排序法對數據序列(55，38，65，97，76，138，27，49)進行排序，寫出排序過程中的各趟結果。

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

31.設線性表A =(a1，a2，…，am)，B=(b1，b2，…，bn)，試寫一個按下列規則合并A，B為線性表C的算法，使得        C=(a1，b1，…，am，bm，bm+1，…，bn) 當m≤n時;或者 C=(a1，b1，…，an，bn，an+1，…，am) 當m>n時。線性表A，B和C均以帶頭結點的單鏈表作為存儲結構，且C表利用A表和B表中的結點空間構成。(注意：單鏈表的長度值m和n均未顯式存儲。)

32.二叉樹的二叉鏈表類型定義如下：typedef struct btnode {        datatype data;        struct btnode *lchild, *rchild;} bitreptr;寫出后根遍歷根指針為t的二叉樹的遞歸算法( void postorder( bitreptr *t ))。