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

數(shù)據(jù)結(jié)構概論考核題一、單項選擇題（每小題2分，共30分）TOC\o"1-5"\h\z下列編碼中屬前綴碼的是（A ）{1,01,000,001} B.{1,01,011,010}C.{0,10,110,11} D.{0,1,00,11}設棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次進棧，一個元素退棧后即進入隊列Q，若6個元素的出隊的序列是b,d,c,f,e,a，則棧S的容量至少應當是（C ）A.6 B.4 C.3 D.2在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復雜度是（B）A.O（1） B.O（n）C.O（nlogn） D.O（n2）要表示省，市，區(qū)，街道的有關數(shù)據(jù)及其關系，選擇（B ）比較合適。A.線性結(jié)構 B.樹結(jié)構C.圖結(jié)構 D.集合結(jié)構）B.刪除操作更加方便D.不會出現(xiàn)上溢的情況）B.刪除操作更加方便D.不會出現(xiàn)上溢的情況A.插入操作更加方便C.不會出現(xiàn)下溢的情況二叉樹中第5層上的結(jié)點個數(shù)最多為（C）A.8 B.15C.16 D.32在表長為n的鏈表中進行線性查找，查找成功時，它的平均查找長度為（B）A.ASL=n B.ASL=（n+1）/2C.ASL='n+1 D.ASL^log2（n+1）-1對22個記錄的有序表進行折半查找，當查找失敗時，至少需要比較（B ）次關鍵字。A.3 B.4C.5 D.6已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是（A）A.0321 B.0123

C.0132（第9題配圖：數(shù)組的下標為0,1,2,3）C.0132（第9題配圖：數(shù)組的下標為0,1,2,3）對于哈希函數(shù)H（key）=key%13，被稱為同義詞的關鍵字是（D）A.35和41 B.23和39C.15和44 D.25和51圖的深度優(yōu)先遍歷類似于二叉樹的（A）A.先序遍歷 B.中序遍歷C.后序遍歷 D.層次遍歷下述幾種排序方法中，穩(wěn)定的排序算法是（A）A.直接插入排序 B.快速排序C.堆排序 D.希爾排序依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（C）A.希爾排序 B.冒泡排序C.插入排序 D.選擇排序二叉樹是非線性數(shù)據(jù)結(jié)構，所以（A二叉樹是非線性數(shù)據(jù)結(jié)構，所以（AA.它不能用順序存儲結(jié)構存儲C.順序存儲結(jié)構和鏈式存儲結(jié)構都能存儲）它不能用鏈式存儲結(jié)構存儲D.順序存儲結(jié)構和鏈式存儲結(jié)構都不能使用有8個結(jié)點的無向圖最多有（B）條邊。A.14 B.2856 D.112二、填空題（每小題1分，共15分）1當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T（n）的數(shù)量級被稱為算法的時間復雜度一—。2設數(shù)組a[M]（M為最大空間個數(shù)）作為循環(huán)隊列Q的存儲空間，front為隊頭指針（指向第一個存放數(shù)據(jù)的位置)，rear為隊尾指針(指向最后一個存放數(shù)據(jù)位置的下一個)，則判定Q隊列的隊滿條件是__front==rear 。3若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是_FEGHDCB。4假設S和X分別表示進棧和出棧操作，由輸入序列“ABC"得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為―b，c，d，a_。5在一棵度為3的樹中，度為2的結(jié)點個數(shù)是1，度為0的結(jié)點個數(shù)是6,則度為3的結(jié)點個數(shù)是2 。6在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是__。7n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復雜度為―1；若采用鄰接表存儲時，該算法的時間復雜度為—2。8在堆排序和快速排序中，若初始記錄接近正序或反序，則選用—;若初始記錄基本無序，則最好選用。9若要求一個稠密圖G的最小生成樹，最好用_普里姆 算法來求解。10一棵深度為6的滿二叉樹有1個分支結(jié)點和2個葉子。11在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關的查找方法是—。12有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的出度 。三、解答題(每小題8分，共40分)用普里姆(prim)算法從右圖中的頂點1開始逐步構造最小生成樹，要求畫出構造的每一步。答：假設N=(V,E)是一個具有n個頂點的連通網(wǎng)，T=(U,TE)是所求的最小生成樹，其中U是T的頂點集，TE是T的邊集。初始U={u0}(u0EV),TE5；在所有uEU,vEV-U的邊中選一條代價最小的邊(u0，v0)并入集合TE，同時將v0并入U；

(3)重復(2),直到U=V為止。此時，TE中必含有n-1條邊，則T=(V,{TE})為N的最小生成樹。假設通信電文使用的字符集為{a,b,c,d,e,f,g}，若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，分別求出這些字符的等長編碼以及哈夫曼編碼，并比較他們的編碼長度。11.如八八/\0.11?,17八八0.0!> 聞.〔〕了JO.1D/\JW口當恕嚶晤夫妾溫碼房從項結(jié)點開始.找IF子結(jié)點.也就呈祖關亭捋.款認注左為".拄右為L所以土’為希蒞是mi,3舟1r：：u/e：ii]h^：idio4f：iouin[motionIL

待排序的序列為：25,47,36,21,90,84,62,78,15,32。寫出用(小根)堆排序的每一趟的結(jié)果。intmain(intargc,char*argv[]){intarray[10]={24,17,85,13,9,54,76,45,5,63};intnum=sizeof(array)/sizeof(int);for(inti=0;i<num-1;i++){for(intj=0;j<num-1-i;j++){if(array[j]<array[j+1]){inttmp=array[j];array[j]=array[j+1];array[j+1]=tmp;}}}for(inti=0;i<num;i++){printf(〃％d〃，array[i]);if(i==num-1){printf(〃\n〃)；}已知一棵樹的前序序列為：abefcgdhijk，后序序列為：efbgcijkhda。畫出這棵樹。答：前序序列為：abefcgdhijk，后序序列為：efbgcijkhda已知閉散列表的長度為10(散列地址空間為0..9)，散列函數(shù)為H(K)=K%8，采用線性重新散列技術解決沖突，將下列一組數(shù)據(jù)｛25,17,39,47,83,55,99,34｝依次插入到散列表中，請畫出散列表。答：(1)H(25)=1H(16)=0H(38)=6H(47)=7⑸H(79)=7與(4)沖突，于是線性重新散列即查找7后面的空槽，此時8為空,因此將79放入8(第九個位置)中H(82)=2H(51)=3⑻H(39)=7與(4)沖突，于是線性重新散列即查找7后面的空槽，此時8已經(jīng)有元素(5),9為空，因此將39放入9(第十個位置)中,所以最終閉散列表的存儲情況如下所示：位置：(0)(1)(2)(3)(4)(5)(6) (7)(8)(9)值：16 25 82 51空空38 47 79 39。四、算法閱讀、設計(共5分)1閱讀下列函數(shù)algo,并回答問題：(5分)voidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))EnQueue(Q,Pop(&S));}⑴假設隊列q中的元素為(2,4,5,7,8),其中“2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&