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

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

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

1.下列描述中正確的是(　　)

A.數據元素是數據的最小單位
B.數據結構是具有結構的數據對象
C.數據結構是指相互之間存在一種或多種特定關系的數據元素的集合
D.算法和程序原則上沒有區別，在討論數據結構時兩者是通用的

2.歸并排序的時間復雜度是(　　)

A.

B.

D.

3.二分查找的時間復雜度是(　　)

A.

B.

D.

4.順序存儲的表中有90000個元素，已按關鍵字值升序排列，假設對每個元素進行查找的概率相同，且每個元素的關鍵字值皆不相同，用順序查找法查找時，需平均比較的次數為(　　)

A.25000
B.30000
C.45000
D.90000

5.散列文件是一種(　　)

A.順序文件
B.索引文件
C.鏈接文件
D.計算尋址文件

6.兩個矩陣A：m×n，B：n×p相乘，其時間復雜度為(　　)

A.O(n)
B.O(mnp)

C.

7.常用于函數調用的數據結構是(　　)

A.棧
B.隊列
C.鏈表
D.數組

8.二維數組A[n][m]以列優先順序存儲，數組A中每個元素占用1個字節，A[1][1]為首元素，其地址為0，則元素A[i][j]的地址為(　　)

A.(i-1)×m+(j-1)
B.(j-1)×n+(i-1)
C.(j-1)×n+i
D.j×n+i

9.圖的廣度優先搜索使用的數據結構是(　　)

A.隊列
B.樹
C.棧
D.集合

10.序列(21，19，37，5，2)經冒泡排序法由小到大排序，在第一次執行交換后所得結果為(　　)

A.(19，21，37，5，2)
B.(21，19，5，37，2)
C.(21，19，37，2，5)
D.(2，21，19，37，5)

11.數據在計算機存儲器內表示時，根據結點的關鍵字直接計算出該結點的存儲地址，這種方法稱為(　　)

A.索引存儲方法
B.順序存儲方法
C.鏈式存儲方法
D.散列存儲方法

12.在單鏈表中，存儲每個結點有兩個域，一個是數據域，另一個是指針域，指針域指向該結點的(　　)

A.直接前趨
B.直接后繼
C.開始結點
D.終端結點

13.在已知頭指針的單鏈表中，要在其尾部插入一新結點，其算法所需的時間復雜度為(　　)

A.O(1)

B.

D.

14.在鏈隊列中執行入隊操作，(　　)

A.需判別隊是否空
B.需判別隊是否滿
C.限制在鏈表頭p進行
D.限制在鏈表尾p進行

15.一整數序列26，59，77，31，51，11，19，42，以二路歸并排序從小到大排序，第一階段的歸并結果為(　　)

A.31，51，11，42，26，77，59，19
B.26，59，31，77，11，51，19，42
C.11，19，26，31，42，59，51，77
D.26，11，19，31，51，59，77，42

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

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

12.數據的存儲結構被分為順序存儲結構、_______、散列存儲結構和索引存儲結構4種。

13.從一個長度為n的順序表中刪除第i個元素(1≤i≤n)時，需向前移動_______個元素。

14.在單鏈表中，插入一個新結點需修改_______個指針。

15.在隊列結構中，允許插入的一端稱為_______。

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

17.向一個棧頂指針為top的鏈棧中插入一個新結點*p時，應執行p->next=top和_______操作。

18.有m個葉結點的哈夫曼樹所具有的結點數為_______。

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

110.在一棵樹中，_______結點沒有前驅結點。

111.一個具有n個頂點的有向完全圖的弧數是_______。

112.n個頂點的無向圖G用鄰接矩陣A[n][n]存儲，其中第i列的所有元素之和等于頂點Vi的_______。

113.選擇排序的平均時間復雜度為_______。

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

21.在棧的輸入端元素的輸入順序為1，2，3，4，5，6，進棧過程中可以退棧，則退棧時能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫出進棧、退棧過程，若不能，簡述理由。(用push(x)表示x進棧，pop(x)表示x退棧)

22.已知一棵二叉樹的中根遍歷序列為CBEDFAGH，后根遍歷序列為CEFDBHGA，畫出該二叉樹。

23.給定表(15，11，8，20，14，13)，試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調整為平衡二叉排序樹。

24.如題32圖所示無向圖，(1)寫出其鄰接矩陣;(2)寫出三種以頂點A為起點的深度優先搜索頂點序列。題32圖

25.用冒泡排序法對數據序列(49，38，65，97，76，134，27，49)進行排序，寫出排序過程。并說明冒泡排序是否為穩定排序。

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

31.編寫計算二叉樹中葉子結點數目的算法。

32.開散列表的類型定義如下：typedef struct tagnode{  keytype key;   struct tagnode*next; }*pointer,node;typedef pointer openhash[n];試寫出開散列表上的查找算法。