數(shù)據(jù)結(jié)構(gòu)概論期末考核試卷
一、單項(xiàng)選擇題 (每小題2分，共30分)
1.下列編碼中屬前綴碼的是( )
A.{1,01,000,001} B.{1,01,011,010}
C.{0,10,110,11} D.{0,1,00,11}
2. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次進(jìn)棧，一個(gè)元素退棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素的出隊(duì)的序列是b,d,c,f,e,a，則棧S的容量至少應(yīng)當(dāng)是( )
A.6 B.4 C.3 D.2
3.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是( )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)
4.要表示省，市，區(qū)，街道的有關(guān)數(shù)據(jù)及其關(guān)系，選擇( )比較合適。
A.線性結(jié)構(gòu) B.樹(shù)結(jié)構(gòu)
C.圖結(jié)構(gòu) D.集合結(jié)構(gòu)
5.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是( )
A.插入操作更加方便 B.刪除操作更加方便
C.不會(huì)出現(xiàn)下溢的情況 D.不會(huì)出現(xiàn)上溢的情況
6.二叉樹(shù)中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為( )
A.8 B.15
C.16 D.32
7.在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，查找成功時(shí)，它的平均查找長(zhǎng)度為( )
A.ASL=n B.ASL=(n+1)/2
C.ASL= +1 D.ASL≈log2(n+1)-1
8.對(duì)22個(gè)記錄的有序表進(jìn)行折半查找，當(dāng)查找失敗時(shí)，至少需要比較( )次關(guān)鍵字。
A.3 B.4
C.5 D.6
9.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是( )
A. 0 3 2 1 B. 0 1 2 3
C. 0 1 3 2 D.0 3 1 2
（第9題配圖：數(shù)組的下標(biāo)為0,1,2,3）
10.對(duì)于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是( )
A.35和41 B.23和39
C.15和44 D.25和51
11.圖的深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的( )
A.先序遍歷 B.中序遍歷
C.后序遍歷 D.層次遍歷
12.下述幾種排序方法中，穩(wěn)定的排序算法是( )
A.直接插入排序 B.快速排序
C.堆排序 D.希爾排序
13.依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為( )
A.希爾排序 B.冒泡排序
C.插入排序 D.選擇排序
14.二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以 ( )
A.它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ) B.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)
C.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ) D.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用
15.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有( )條邊。
A.14 B.28
C.56 D.112
二、填空題（每小題1分，共15分）
1 當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，算法執(zhí)行時(shí)間T(n)的數(shù)量級(jí)被稱為算法的________。
2 設(shè)數(shù)組a[M](M為最大空間個(gè)數(shù))作為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front為隊(duì)頭指針(指向第一個(gè)存放數(shù)據(jù)的位置)，rear為隊(duì)尾指針(指向最后一個(gè)存放數(shù)據(jù)位置的下一個(gè))，則判定Q隊(duì)列的隊(duì)滿條件是_____________。
3 若已知一棵二叉樹(shù)的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是________。
4假設(shè)S和X分別表示進(jìn)棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為_(kāi)__________。
5 在一棵度為3的樹(shù)中，度為2的結(jié)點(diǎn)個(gè)數(shù)是1，度為0的結(jié)點(diǎn)個(gè)數(shù)是6，則度為3的結(jié)點(diǎn)個(gè)數(shù)是________。
6 在數(shù)據(jù)的存放無(wú)規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是____________。
7 n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為_(kāi)______________；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為_(kāi)_____________ 。
8 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用______________；若初始記錄基本無(wú)序，則最好選用_______________。
9 若要求一個(gè)稠密圖G的最小生成樹(shù)，最好用______________算法來(lái)求解。
10 一棵深度為6的滿二叉樹(shù)有 ________________ 個(gè)分支結(jié)點(diǎn)和____________個(gè)葉子。
11 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是_____________。
12 有向圖G用鄰接矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的____________。
三、解答題(每小題8分，共40分)
1. 用普里姆(prim)算法從右圖中的頂點(diǎn)1開(kāi)始逐步構(gòu)造最小生成樹(shù)，要求畫(huà)出構(gòu)造的每一步。
2. 假設(shè)通信電文使用的字符集為{a,b,c,d,e,f,g}，若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，分別求出這些字符的等長(zhǎng)編碼以及哈夫曼編碼，并比較他們的編碼長(zhǎng)度。
3. 待排序的序列為：25,47,36,21,90,84,62,78,15,32。寫(xiě)出用（小根）堆排序的每一趟的結(jié)果。
4. 已知一棵樹(shù)的前序序列為：abefcgdhijk，后序序列為：efbgcijkhda。畫(huà)出這棵樹(shù)。
5. 已知閉散列表的長(zhǎng)度為10(散列地址空間為0..9)，散列函數(shù)為H(K)=K%8，采用線性重新散列技術(shù)解決沖突，將下列一組數(shù)據(jù){25,17,39,47,83,55,99,34}依次插入到散列表中，請(qǐng)畫(huà)出散列表。
四、算法閱讀、設(shè)計(jì)(共5分)
1 閱讀下列函數(shù)algo,并回答問(wèn)題：(5分)
void algo(Queue *Q)
{
Stack S;
InitStack(&S);
while (!QueueEmpty(Q))
Push(&S, DeQueue(Q));
while (! StackEmpty(&S))
ＥnQueue(Q,Pop(&S));
}
(1)假設(shè)隊(duì)列q中的元素為(2,4,5,7,8),其中“2”為隊(duì)頭元素。寫(xiě)出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊(duì)列q；
(2)簡(jiǎn)述算法algo的功能。
五、程序設(shè)計(jì)題（共10分）
1、已知r[]為一維數(shù)組，其中r[0]到r[n-1]為待排序的n個(gè)元素，排序好的元素仍放在r[0]到r[n-1]中，請(qǐng)寫(xiě)出對(duì)該數(shù)組進(jìn)行非遞歸的直接插入排序算法，取名為insertsort(elemtype r[],int n)。 (10分)
