數(shù)據(jù)結(jié)構(gòu)概論

1、福建師范大學(xué)試卷紙 第 頁 共 7 頁數(shù)據(jù)結(jié)構(gòu)概論考核題、單項(xiàng)選擇題 ( 每小題 2 分，共 30 分)下列編碼中屬前綴碼的是 ( A )1,01,000,001B.1,01,011,010C.0,10,110,11D.0,1,00,11設(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)是 ( C )A.6 B.4 C.3 D.23. 在具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是( B )A.O(1)C.O(nlogn)B.O(n

2、)D.O(n2)要表示省，市，區(qū)，街道的有關(guān)數(shù)據(jù)及其關(guān)系，選擇 ( B ) 比較合適。 A. 線性結(jié)構(gòu) B. 樹結(jié)構(gòu)C. 圖結(jié)構(gòu) D. 集合結(jié)構(gòu)鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是 ( D )A. 插入操作更加方便B. 刪除操作更加方便C. 不會出現(xiàn)下溢的情況D. 不會出現(xiàn)上溢的情況二叉樹中第 5 層上的結(jié)點(diǎn)個(gè)數(shù)最多為 ( C )A.815D.3216在表長為的鏈表中進(jìn)行線性查找，查找成功時(shí)，它的平均查找長度為A.ASL=nB.ASL=(n+1)/2C.ASL= n +1D.ASL log2(n+1)-1對 22 個(gè)記錄的有序表進(jìn)行折半查找，當(dāng)查找失敗時(shí)，至少需要比較 ( B ) 次關(guān)鍵字。 A

3、.3 B.4C.5 D.6已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0 出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是 ( A )A. 0 3 2 1B. 0 1 2 3C. 0 1 3 2D.0 3 1 2第 9 題配圖：數(shù)組的下標(biāo)為 0,1,2,3 )對于哈希函數(shù) H(key)=key%13, 被稱為同義詞的關(guān)鍵字是 ( D ) TOC o 1-5 h z A.35 和 41B.23和 39C.15 和 44D.25和 51圖的深度優(yōu)先遍歷類似于二叉樹的 ( A )A. 先序遍歷B.中序遍歷C. 后序遍歷D.層次遍歷下述幾種排序方法中，穩(wěn)定的排序算法是( A )A. 直接插入排序 B. 快速排序 C. 堆

4、排序 D. 希爾排序依次取出元素與已排序序列(初始時(shí)為空) 置上的方法，稱為 ( C )A. 希爾排序B.C. 插入排序D.中的元素進(jìn)行比較，將其放入已排序序列的正確位冒泡排序 選擇排序14. 二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以A. 它不能用順序存儲結(jié)構(gòu)存儲C. 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲A )B.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用15. 有 8 個(gè)結(jié)點(diǎn)的無向圖最多有 ( B ) 條邊。A.14C.56B.28D.112、填空題(每小題 1分，共 15 分)當(dāng)問題的規(guī)模 n 趨向無窮大時(shí)，算法執(zhí)行時(shí)間 T(n) 的數(shù)量級被稱為算法的 _ 時(shí)間復(fù)雜度 設(shè)數(shù)組 aM(M

5、 為最大空間個(gè)數(shù) ) 作為循環(huán)隊(duì)列 Q 的存儲空間， front 為隊(duì)頭指針 ( 指向第一個(gè)存放數(shù)據(jù)的位置 ） ，rear 為隊(duì)尾指針 （ 指向最后一個(gè)存放數(shù)據(jù)位置的下一個(gè) ） ，則判定 Q隊(duì)列的隊(duì) TOC o 1-5 h z 滿條件是 front=rear 。若已知一棵二叉樹的前序序列是BEFCGD，H中序序列是 FEBGCH，D則它的后序序列必是 _ FEGHDCB。_4假設(shè) S和 X分別表示進(jìn)棧和出棧操作， 由輸入序列“ABC”得到輸出序列 “BCA”的操作序列為 SSXSXX， 則由“ a*b+c/d ”得到“ ab*cd/+ ”的操作序列為 _ b，c， d ， a_。在一棵度為 3

6、 的樹中，度為 2 的結(jié)點(diǎn)個(gè)數(shù)是 1，度為 0 的結(jié)點(diǎn)個(gè)數(shù)是 6，則度為 3 的結(jié)點(diǎn)個(gè)數(shù)是 2。在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是_ 線性查找 。n 個(gè)頂點(diǎn) e 條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為 1 ；若采用鄰接表存儲時(shí)，該算法的時(shí)間復(fù)雜度為 2 。在堆排序和快速排序中，若初始記錄接近正序或反序，則選用_ 堆排序 ；若初始記錄基本無序，則最好選用 _快速排序 。若要求一個(gè)稠密圖 G 的最小生成樹，最好用 _普里姆 算法來求解。一棵深度為 6 的滿二叉樹有 1 個(gè)分支結(jié)點(diǎn)和 2 個(gè)葉子。在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù) n 無關(guān)的查找方法是 _散

7、列表法 有向圖 G用鄰接矩陣存儲，其第 i 行的所有元素之和等于頂點(diǎn) i 的 出度 。三、解答題 （每小題 8 分，共 40分）1. 用普里姆 （prim） 算法從右圖中的頂點(diǎn) 1 開始逐步構(gòu)造最小生成樹，要求畫出構(gòu)造的每一步26 11 6答：假設(shè) N=（V ,E）是一個(gè)具有 n個(gè)頂點(diǎn)的連通網(wǎng)， T=（U,TE）是所求的最小生成樹，其中 U是 T的頂 點(diǎn)集， TE 是 T 的邊集。（ 1）初始 U=u0（u0 V）,TE= ；（2）在所有 uU, vV-U 的邊中選一條代價(jià)最小的邊 （u0，v0）并入集合 TE，同時(shí)將 v0 并入 U；3）重復(fù)（ 2），直到 U=V 為止。此時(shí)， TE 中必含

8、有 n-1 條邊，則 T= （ V ， TE ）為 N 的最小生成樹。2. 假設(shè)通信電文使用的字符集為 a,b,c,d,e,f,g ，若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15， 20，5 和 9，分別求出這些字符的等長編碼以及哈夫曼編碼，并比較他們的編碼 長度。待排序的序列為： 25,47,36,21,90,84,62,78,15,32 。寫出用(小根)堆排序的每一趟的結(jié)果。 int main(int argc, char *argv) int array10 = 24, 17, 85, 13, 9, 54, 76, 45, 5, 63;int num = sizeof(arr

9、ay)/sizeof(int);for(int i = 0; i num-1; i+) for(int j = 0; j num - 1 - i; j+) if(arrayj arrayj+1) int tmp = arrayj;arrayj = arrayj+1; arrayj+1 = tmp; for(int i = 0; i num; i+) printf(%d, arrayi);if(i = num-1) printf(n);已知一棵樹的前序序列為： abefcgdhijk ，后序序列為： efbgcijkhda 。畫出這棵樹。已知閉散列表的長度為 10( 散列地址空間為 0.9) ，

10、散列函數(shù)為 H(K)=K%8，采用線性重新散列 技術(shù)解決沖突，將下列一組數(shù)據(jù) 25,17,39,47,83,55,99,34 依次插入到散列表中，請畫出散 列表。答：(1) H(25) = 1(2) H(16) = 0H(38) = 6H(47) = 7H(79) = 7 與 (4) 沖突,于是線性重新散列即查找 7后面的空槽 ,此時(shí)8為空,因此將 79放入 8 (第九個(gè)位置)中H(82) = 2H(51) = 3H(39) = 7與( 4)沖突,于是線性重新散列即查找 7 后面的空槽 ,此時(shí) 8 已經(jīng)有元素( 5),9為空, 因此將 39放入 9(第十個(gè)位置)中 , 所以最終閉散列表的存儲情

11、況如下所示： 位置：(0)(1)(2)(3)(4)( 5)(6) (7)(8)(9)值： 16 25 82 51 空 空 38 47 79 39 。四、算法閱讀、設(shè)計(jì) (共 5分)1 閱讀下列函數(shù) algo, 并回答問題： (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ì)頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q) 后的隊(duì)列 q；(2) 簡述算法 algo 的功能。答: