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

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

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

1.設棧S和隊列Q的初始狀態為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，元素退棧后即進人隊列Q，若6個元素的出隊序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少為(　　)

A.2
B.3
C.4
D.6

2.設計一個判別表達式中左右括號是否配對出現的算法，采用的最佳數據結構為(　　)

A.線性表的順序存儲結構
B.隊列
C.線性表的鏈式存儲結構
D.棧

3.下列程序段的時間復雜度為(　　)i=0; s=0;while(s<n){  i++;   s =s+i;}

A.

B.

D.

4.設A是n×n的對稱矩陣，將A的對角線及對角線上方的元素Aij(1≤i，j≤n，i≤j)以列優先順序存放在一維數組元素B[1]至B[n(n+1)/2]中，則元素Aij(i≤j)在B中的位置為(　　)

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

5.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現的是(　　)

A.G中有弧

C.G中沒有弧

6.下列序列中，由第一趟快速排序可得到的序列(排序的關鍵字類型是字符串)是(　　)

A.[da，ax，eb，de，bb] ff [ha，gc]
B.[cd，eb，ax，da] ff [ha，gc，bb]
C.[gc，ax，eb，cd，bb] ff [da，ha]
D.[ax，bb，cd，da] ff [eb，gc，ha]

7.不穩定的排序方法是(　　)

A.直接插入排序
B.冒泡排序
C.堆排序
D.二路歸并排序

8.設散列表表長m=14，散列函數為h(k)=k%11，表中已有4個記錄，如果用二次探測法處理沖突，關鍵字為49的記錄的存儲位置是(　　)

A.3
B.5
C.8
D.9

9.若元素1，2，3依次進棧，則退棧不可能出現的次序是(　　)

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

10.直接插入排序的時間復雜度是(　　)

A.

B.

D.

11.稀疏矩陣是指(　　)

A.元素少的矩陣
B.有少量零元素的矩陣
C.有少量非零元素的矩陣
D.行數、列數很少的矩陣

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

A.2k

B.-1

C.

D.-1

13.由帶權為9，2，5，7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為(　　)

A.23
B.37
C.44
D.46

14.有n個頂點的有向完全圖的弧數為(　　)

A.

15.圖的深度優先搜索類似于二叉樹的(　　)

A.先根遍歷
B.中根遍歷
C.后根遍歷
D.層次遍歷

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

11.下列程序段的時間復雜度為________。for( i=1; i<-n; i++ )      for( j=1; j<=n; j++ )             x++;

12.數據結構中結點按邏輯關系依次排列形成一條“鎖鏈”的結構是________。

13.在表長為n的順序表上做刪除運算，平均要移動的結點個數為________。

14.在帶有頭結點的單循環鏈表head中，指針P所指結點為尾結點的條件是________。

15.隊列又稱為________的線性表。

16.順序棧被定義為結構類型，含有兩個域：data和top，則對棧*sq進行初始化的操作是________。

17.對于任何一棵二叉樹T，如果其終端結點數為‰，度為2的結點數為，則________。

18.一棵具有n個結點的二叉樹，采用二叉鏈表存儲，則二叉鏈表中指向孩子結點的指針有________個。

19.若連通圖G的頂點個數為n，則圖G的生成樹的邊數為________。

110.一個具有n個頂點的無向圖的邊數最多為________。

111.中根遍歷二叉排序樹所得到的結點訪問序列是鍵值的________序列。

112.冒泡排序的平均時間復雜度為________。

113.將序列(60，20，23，68，94，70，73)建成堆，則只需把20與________互相交換。

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

21.如題29圖所示，在棧的輸入端元素的輸入順序為A，B，C，D，進棧過程中可以退棧，寫出在棧的輸出端以A開頭和以B開頭的所有輸出序列。

22.一棵二叉樹如題30圖所示，寫出該二叉樹的先根遍歷序列、中根遍歷序列和后根遍歷序列。

23.將題31圖所示的一棵二叉樹轉換成森林。題31圖

24.對于有向無環圖：(1)敘述求拓撲排序算法的基本步驟;(2)對于題32圖，寫出它的4個不同的拓撲排序序列。

25.判別以下序列是否為堆。如果不是，則把它調整為堆。(1)(100，86，48，73，35，39，42，57，66，21);(2)(12，70，33，65，24，56，48，92，86，33)。

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

31.n個結點的完全二叉樹按結點編號將值順序存放在一維數組元素A[1]至A[n]中，試編寫算法實現將順序存儲結構轉換為二叉鏈表存儲結構，其中根結點由tree指向。

32.試寫出冒泡排序算法。