數據結構導論試題
課程代碼：02142
壹、單項選擇題(本大題***15小題，每小題2分，***30分)
在每小題列出的四個備選項中只有壹個是符合題目要求的，請將其代碼填寫在題後的括號內。錯選、多選或未選均無分。
1．下列描述中正確的是( )
A.數據元素是數據的最小單位
B.數據結構是具有結構的數據對象
C.數據結構是指相互之間存在壹種或多種特定關系的數據元素的集合
D.算法和程序原則上沒有區別，在討論數據結構時兩者是通用的
2．歸並排序的時間復雜度是( )
A．O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
3．二分查找的時間復雜度是( )
A．O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
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.O(n2)
D.O（mp）
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.O（log2n）
C.O（n）
D.O（n2）
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分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16．下列程序段的時間復雜度為_______。
i=0；s=0；
while（s<n）
{i++；
s=s+i；
}
17．數據的存儲結構被分為順序存儲結構、_______、散列存儲結構和索引存儲結構4種。
18．從壹個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動_______個元素。
19．在單鏈表中，插入壹個新結點需修改_______個指針。
20．在隊列結構中，允許插入的壹端稱為_______。
21．稀疏矩陣采用的壓縮存儲方法是_______。
22．向壹個棧頂指針為top的鏈棧中插入壹個新結點*p時，應執行p->next=top和_______操作。
23．有m個葉結點的哈夫曼樹所具有的結點數為_______。
24．在壹棵具有n個結點的完全二叉樹中，從樹根起，自上而下、自左至右地給所有結點編號。設根結點編號為1。若編號為i的結點有右孩子，那麽其右孩子的編號為_______。
25．在壹棵樹中，_______結點沒有前驅結點。
26．壹個具有n個頂點的有向完全圖的弧數是_______。
27．n個頂點的無向圖G用鄰接矩陣A［n］［n］存儲，其中第i列的所有元素之和等於頂點Vi的_______。
28．選擇排序的平均時間復雜度為_______。
三、應用題(本大題***5小題，每小題6分，***30分)
29．在棧的輸入端元素的輸入順序為1，2，3，4，5，6，進棧過程中可以退棧，則退棧時能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫出進棧、退棧過程，若不能，簡述理由。（用push（x）表示x進棧，pop(x)表示x退棧）
30．已知壹棵二叉樹的中根遍歷序列為CBEDFAGH，後根遍歷序列為CEFDBHGA，畫出該二叉樹。
31．給定表（15，11，8，20，14，13），試按元素在表中的順序將它們依次插入壹棵初始時為空的二叉排序樹，畫出插入完成後的二叉排序樹，並判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調整為平衡二叉排序樹。
32．如題32圖所示無向圖，（1）寫出其鄰接矩陣；（2）寫出三種以頂點A為起點的深度優
先搜索頂點序列。
題32圖
33．用冒泡排序法對數據序列（49，38，65，97，76，134，27，49）進行排序，寫出排序過程。並說明冒泡排序是否為穩定排序。
四、算法設計題(本大題***2小題，每小題7分，***14分)
34.編寫計算二叉樹中葉子結點數目的算法。
35.開散列表的類型定義如下：
typedef struct tagnode
{keytype key;
struct tagnode*next;
}*pointer,node;
typedef pointer openhash［n］;
試寫出開散列表上的查找算法。