《數據結構概論》期末試卷
姓名： 專業(yè)：
學號： 學習中心：
? 成績：
一、單項選擇題 (請將答案填寫在后面的表格中，每小題2分，共30分)
1.查找n個元素的有序表時，最有效的查找方法是( )
A.順序查找 B.分塊查找
C.折半查找 D.二叉排序樹查找
2.具有12個關鍵字的有序表，查找成功時折半查找的平均查找長度是( )
A.3.1 B.4 C.2.5 D.5
3.在具有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是( )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)
4.對平均性能而言，以下最好的內排序方法是( )。
A.冒泡排序 B.希爾排序
C.交換排序 D.快速排序
5.鏈棧與順序棧相比，比較明顯的優(yōu)點是( )
A.插入操作更加方便 B.刪除操作更加方便
C.不會出現下溢的情況 D.不會出現上溢的情況
6.二叉樹中第5層上的結點個數最多為( )
A.8 B.15
C.16 D.32
7.以下數據結構中，( )是非線性數據結構。
A.樹 B.字符串
C.隊 D.棧
8.一個向量的第一個元素的地址是100，每個元素的長度是2 ，則第五個元素的地址是( )。
A.102 B.110
C.108 D.120
9.已知圖的鄰接表如下所示，根據算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是( )
A. 0 3 2 1 B. 0 1 2 3
C. 0 1 3 2 D.0 3 1 2
（第9題配圖：數組的下標為0,1,2,3）
10.對于哈希函數H(key)=key%13,被稱為同義詞的關鍵字是( )
A.35和41 B.23和39
C.15和44 D.25和51
11.有一個有序表為{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要經過( )次與63比較。
A.12 B.6
C.4 D.5
12.下述幾種排序方法中，穩(wěn)定的排序算法是( )
A.直接插入排序 B.快速排序
C.堆排序 D.希爾排序
13.具有n個頂點的無向圖至少要有( )條邊才能確保是一個連通圖。
A.n(n+1) B.n-1
C.n+1 D.n(n-1)
14.二叉樹是非線性數據結構，所以 ( )
A.它不能用順序存儲結構存儲 B.它不能用鏈式存儲結構存儲
C.順序存儲結構和鏈式存儲結構都能存儲 D.順序存儲結構和鏈式存儲結構都不能使用
15.有8個結點的無向圖最多有( )條邊。
A.14 B.28
C.56 D.112
單項選擇題答題表格（請將答案填寫在下表中）
題號 1 2 3 4 5 6 7 8 9 10
答案
題號 11 12 13 14 15
答案
二、填空題（每小題2分，共30分）
1. 下面程序段的時間復雜度為________。
sum=1; for(i=0;sum<n;i++) sum+=1;
2. 設數組a[M](M為最大空間個數)作為循環(huán)隊列Q的存儲空間，front為隊頭指針(指向第一個存放數據的位置)，rear為隊尾指針(指向最后一個存放數據位置的下一個)，則判定Q隊列的隊滿條件是_____________。
3. 若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是________。
4. 散列法存儲的基本思想是由_______________決定數據的存儲地址。
5. 在一棵度為3的樹中，度為2的結點個數是1，度為0的結點個數是6，則度為3的結點個數是________。
6. 設一棵完全二叉樹有700個結點，則共有____________個葉子結點 。
7. n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復雜度為_______________；若采用鄰接表存儲時，該算法的時間復雜度為______________ 。
8. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用______________；若初始記錄基本無序，則最好選用_______________。
9. 若要求一個稀疏圖G的最小生成樹，最好用_______________ 算法來求解。
10. 一棵深度為6的滿二叉樹有 ________________ 個分支結點和____________個葉子。
11.用5個權值{3, 2, 4, 5, 1}構造的哈夫曼（Huffman）樹的帶權路徑長度是__________。
12. 有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的____________。
三、解答題(每小題9分，共27分)
1. 已知以下的有向圖，用Dijkstra算法求出從頂點1出發(fā)到各頂點的最短路徑（按步給分）。
2.待排序的序列為：25,47,36,21,90,84,62,78,15,32。寫出用（大根）堆排序的每一趟的結果。
3.一棵度為2的有序樹與一棵二叉樹有何區(qū)別？
四、程序設計題（共13分）
1、已知r[]為一維數組，其中r[0]到r[n-1]為待排序的n個元素，排序好的元素仍放在r[0]到r[n-1]中，請寫出對該數組進行非遞歸的直接插入排序算法，取名為insertsort(elemtype r[],int n)。
