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

1、 福建師范大學(xué)試卷紙 第 1 頁(yè) 共 7 頁(yè)《數(shù)據(jù)結(jié)構(gòu)概論》期末考核試題 《數(shù)據(jù)結(jié)構(gòu)概論》期末考核試題一、單項(xiàng)選擇題 (每小題 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 和隊(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)并使鏈表仍

3、然有序的時(shí)間復(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.樹(shù)結(jié)構(gòu)C.圖結(jié)構(gòu) D.集合結(jié)構(gòu)5

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

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

6、 D.69.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn) 0 出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是( A )福建師范大學(xué)試卷紙 第 3 頁(yè) 共 7 頁(yè)___。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ì)滿條件是____ (rear –

7、 front)%m= =1________ ________。3 若已知一棵二叉樹(shù)的前序序列是 BEFCGDH，中序序列是 FEBGCHD，則它的后序序列必是____ FEGHDCB____。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ù)

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

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