福建師范大學(xué)19年8月課程考試《數(shù)據(jù)結(jié)構(gòu)概論 》作業(yè)考核試題[離線作業(yè)]

1、 福建師范大學(xué)試卷紙 第 1 頁 共 7 頁《數(shù)據(jù)結(jié)構(gòu)概論》期末考核試題 《數(shù)據(jù)結(jié)構(gòu)概論》期末考核試題一、單項選擇題 (每小題 2 分，共 30 分)1.下列編碼中屬前綴碼的是( A )A.{1,01,000,001} B.{1,01,011,010}C.{0,10,110,11}

2、 D.{0,1,00,11}2. 設(shè)棧 S 和隊列 Q 的初始狀態(tài)為空，元素 a,b,c,d,e,f 依次進(jìn)棧，一個元素退棧后即進(jìn)入隊列Q，若 6 個元素的出隊的序列是 b,d,c,f,e,a，則棧 S 的容量至少應(yīng)當(dāng)是( C )A.6 B.4 C.3 D.23.在具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍

3、然有序的時間復(fù)雜度是( D )A.O(1) B.O(n)C.O(nlogn) D.O(n2)4.要表示省，市，區(qū)，街道的有關(guān)數(shù)據(jù)及其關(guān)系，選擇( B )比較合適。A.線性結(jié)構(gòu) B.樹結(jié)構(gòu)C.圖結(jié)構(gòu) D.集合結(jié)構(gòu)5

4、.鏈棧與順序棧相比，比較明顯的優(yōu)點是( D )A.插入操作更加方便 B.刪除操作更加方便C.不會出現(xiàn)下溢的情況 D.不會出現(xiàn)上溢的情況6.二叉樹中第 5 層上的結(jié)點個數(shù)最多為( C )A.8 B.15C.16 D.327.在表長為ｎ的鏈表中進(jìn)

5、行線性查找，查找成功時，它的平均查找長度為( B )A.ASL=n B.ASL=(n+1)/2C.ASL= +1 D.ASL≈log2(n+1)-1 n8.對 22 個記錄的有序表進(jìn)行折半查找，當(dāng)查找失敗時，至少需要比較( B )次關(guān)鍵字。A.3 B.4C.5

6、 D.69.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點 0 出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是( A )福建師范大學(xué)試卷紙 第 3 頁 共 7 頁___。2 設(shè)數(shù)組 a[M](M 為最大空間個數(shù))作為循環(huán)隊列 Q 的存儲空間，front 為隊頭指針(指向第一個存放數(shù)據(jù)的位置)，rear 為隊尾指針(指向最后一個存放數(shù)據(jù)位置的下一個)，則判定 Q 隊列的隊滿條件是____ (rear –

7、 front)%m= =1________ ________。3 若已知一棵二叉樹的前序序列是 BEFCGDH，中序序列是 FEBGCHD，則它的后序序列必是____ FEGHDCB____。4 假設(shè) S 和 X 分別表示進(jìn)棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為___ ________。5 在一棵度為 3 的樹中，度為 2 的結(jié)點個數(shù)

8、是 1，度為 0 的結(jié)點個數(shù)是 6，則度為 3 的結(jié)點個數(shù)是___2_____。6 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是____順序查找________。7 n 個頂點 e 條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復(fù)雜度為______ O(n2)_________；若采用鄰接表存儲時，該算法的時間復(fù)雜度為______ O(n+e) ________ 。8 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用_

9、___堆排序 ________；若初始記錄基本無序，則最好選用______快速排序_________。9 若要求一個稠密圖 G 的最小生成樹，最好用______普里姆(Prim) ________算法來求解。10 一棵深度為 6 的滿二叉樹有 ________63________ 個分支結(jié)點和________32____個葉子。11 在各種查找方法中，平均查找長度與結(jié)點個數(shù) n 無關(guān)的查找方法是_____順序查找________。12