數(shù)據(jù)結(jié)構(gòu)考試題目

一、填空題（每空1分，共15分）1、實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法有：⑴，⑵。2、若算法中的語(yǔ)句執(zhí)行次數(shù)之和為T（n）=3525n+4nlogn，則算法的時(shí)間復(fù)雜度是⑶。3、假設(shè)以S和X分別表示進(jìn)棧和出棧操作，則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列操作SSXSXSSXXX之后，得到的輸出序列為⑷ 。4、 在串S="structure"中，以t為首字符的子串有⑸個(gè)。5、下三角矩陣A[n][n]按行優(yōu)先存儲(chǔ)在一維數(shù)組B中，實(shí)現(xiàn)隨機(jī)存取下三角中元素A[i][j]的地址公式是⑹。（注意元素下標(biāo)是從0開(kāi)始）6、 廣義表（（a,b）,c,d,（e,（f,g）））的表頭是⑺，表尾是⑻，表的長(zhǎng)度為⑼，表的深度為⑽。7、 包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，深度最大為（11），深度最小為（12）。8、 含有n個(gè)結(jié)點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（13）。9、快速排序在（⑷的初始狀態(tài)下，時(shí)間效率最差，其時(shí)間復(fù)雜度為0（n2）。平均情況下快速排序的時(shí)間復(fù)雜度為（15）。二、 簡(jiǎn)答題（每小題5分，共20分）1、 數(shù)據(jù)結(jié)構(gòu)中研究的經(jīng)典結(jié)構(gòu)有那些？各有什么特點(diǎn)？2、 棧上有那些基本運(yùn)算？請(qǐng)寫出鏈棧的抽象數(shù)據(jù)類型定義。（提示：先定義結(jié)點(diǎn)結(jié)構(gòu)，再定義鏈棧類，在類中只給出函數(shù)聲明，不需要定義函數(shù)）4、 什么叫穩(wěn)定排序？請(qǐng)列舉出三種實(shí)現(xiàn)穩(wěn)定排序的排序算法名稱。5、 散列函數(shù)的設(shè)計(jì)原則是什么？有那些常用的散列函數(shù)設(shè)計(jì)方法？三、 假設(shè)在長(zhǎng)度大于1的循環(huán)鏈表中，即無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，S為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)S的前趨結(jié)點(diǎn)。（8分）四、 已知葉子結(jié)點(diǎn)（a,b,c,d,e,f）及對(duì)應(yīng)的權(quán)值（12,5,3,20,9,10），請(qǐng)畫出哈夫曼樹(shù)并給出各葉子結(jié)點(diǎn)的哈夫曼編碼。（10分）五、已知有如下二叉樹(shù)：（共15分）（1） 畫出該二叉樹(shù)的二叉鏈表存儲(chǔ)示意圖；（4分）（2） 寫出前序遍歷的遞歸算法；（5分）（3） 寫出前序、中序、后序遍歷得到的結(jié)點(diǎn)序列（6分）六、已知有向圖：（共15分）G=（V，E）V={a,b,c,d,e,f,g}E={<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<c,f>,<d,f>,<e,g>,<f,g>}（1） 畫出此有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)圖示；（5分）（2） 寫出一個(gè)拓?fù)湫蛄?；?分）（3） 假設(shè)初始時(shí)各頂點(diǎn)的入度已經(jīng)存放在鄰接表的in域中，請(qǐng)用偽代碼寫出拓?fù)渑判蛩惴?。?分）七、已知散列函數(shù)為：H（k）=kmod7，用拉鏈法處理沖突，請(qǐng)畫出依次插入23,14,9,6,18,30,49,12,34后的散列表，并求出檢索成功的平均檢索長(zhǎng)度。（9分）八、設(shè)有八枚硬幣，分別表示為a，b，c，d，e，f，g，h，其中有且僅有一枚硬幣是偽造的，假幣的重量與真幣的重量不同，可能輕，也可能重?，F(xiàn)要求以天平為工具，用最少的比較次數(shù)挑選出假幣，并同時(shí)確定這枚硬幣的重量比其它真幣是輕還是重。寫出你的判定過(guò)程或畫出判定樹(shù)。（8分）一、填空題（每空1分，共10分）1．順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由存儲(chǔ)位置表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的。非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（）。3．n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有（ ）個(gè)非零元素。（ ）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。由權(quán)值為｛3,8,6,2,5｝的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，其帶權(quán)路徑長(zhǎng)度為（ ）。設(shè)S="I_am_a_teacther，"其長(zhǎng)度為（ ）。稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是（ ）和（）。分塊有序是指將文件劃分為若干塊，（ ）無(wú)序，（）有序。二、 判斷題（你認(rèn)為正確的請(qǐng)打?qū)?，錯(cuò)誤的打錯(cuò)。每題2分，共10分）線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。B—樹(shù)是一種動(dòng)態(tài)索引結(jié)構(gòu)，它既適用于隨機(jī)查找，也適用于順序查找。在線索二叉樹(shù)中，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索。用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。在索引順序表上采用分塊查找，在等概率情況下，其平均查找長(zhǎng)度不僅與子表個(gè)數(shù)有關(guān)，而且與每一個(gè)子表中的對(duì)象個(gè)數(shù)有關(guān)。三、 單選題（請(qǐng)把你認(rèn)為正確的答案填入括號(hào)內(nèi)，每小題1分，共10分）假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（）。A樹(shù)B圖 C線性表 D集合在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。A棧 B隊(duì)列C數(shù)組D線性表若某線性表經(jīng)常的操作是取第i個(gè)元素和找第i個(gè)元素的前趨，則采用（）存儲(chǔ)方法最節(jié)省時(shí)間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表廣義表（a,b,（c,（d）））的表尾是（）。A（d） B（c,（d）） CbD（b,（c,（d）））

5．堆的形狀是一棵（）。A二叉排序樹(shù) B滿二叉樹(shù) C完全二叉樹(shù) D判定樹(shù)設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5、e6依次通過(guò)棧S,—個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1,則棧S的容量至少應(yīng)該是（）。A6 B4 C3 D2G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有（）個(gè)頂點(diǎn)。A6B7C8D9設(shè)有5000個(gè)元素，希望用最快的速度挑選出前10個(gè)最大的，采用（）方法最好。A快速排序 B堆排序C希爾排序 D歸并排序設(shè)有10000個(gè)記錄，通過(guò)分塊劃分為若干子表并建立索引，那么為了提高查找效率，每一個(gè)子表的大小應(yīng)設(shè)計(jì)為（ ）。A100B200 C10D5設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）。A連接B模式匹配C求子串D求串長(zhǎng)四、簡(jiǎn)單應(yīng)用題（47分）1已知一個(gè)非空二叉樹(shù)，中序遍歷序列為CGBAHEDJFI；后序遍歷序列為GBCHEJIFDA,試將這棵二叉樹(shù)構(gòu)造出來(lái)。若已知前序和后序遍歷結(jié)果,能否構(gòu)造出這棵二叉樹(shù),舉例說(shuō)明。（9分）二維數(shù)組M中每個(gè)元素的長(zhǎng)度是3個(gè)字節(jié)，行下標(biāo)從0到7,列下標(biāo)從0到9,從首地址d開(kāi)始存儲(chǔ)。若按行優(yōu)先方式存儲(chǔ)，元素M[7][5]的起始地址為多少，若按列優(yōu)先方式存儲(chǔ)，元素M[7][5]的起始地址為多少。（5分）如右圖所示：（1）從頂點(diǎn)A出發(fā)，畫出深度優(yōu)先生成樹(shù)；（2） 從頂點(diǎn)E出發(fā)，畫出廣度優(yōu)先生成樹(shù)；（3） 根據(jù)Kruskal算法，求出它的最小生成樹(shù)。（12分）第4題圖如右圖是一棵正在進(jìn)行插入運(yùn)算的平衡二叉樹(shù)，關(guān)鍵碼70的插入使它失去了平衡，按照平衡二叉樹(shù)的插入方法，需要對(duì)它的結(jié)構(gòu)進(jìn)行調(diào)整以恢復(fù)平衡。請(qǐng)畫出調(diào)整后的平衡二叉樹(shù)。（5分）第4題圖5．寫出下列程序段的時(shí)間復(fù)雜度。(3分)5．寫出下列程序段的時(shí)間復(fù)雜度。(3分)(1)count=0;x=1;while(x<N){x*=2;count++;}(2)i=1;k=0;n=100;

while(i<N-1)&NBSP;&NBSP;&NBSP;{k=k+10*i;i++;}第5題圖6．設(shè)記錄的關(guān)鍵碼集合為K={15,25,26,4,5,20,3,12,2},(1)設(shè)散列函數(shù)為H(k)=kmod15,散列表表長(zhǎng)為16，采用線性探測(cè)法處理沖突，試構(gòu)造閉散列表；(2)寫出對(duì)K進(jìn)行直接插入排序的每趟排序結(jié)果。(13分)五、 閱讀程序(8分)下面?zhèn)未a是一個(gè)廣度優(yōu)先遍歷算法，請(qǐng)給出該算法在下圖上執(zhí)行BFS(G,v1)的結(jié)果，指出其中的錯(cuò)誤產(chǎn)生原因，如何修改？voidBFS(ALGraph*G,intk){ /*G是圖的鄰接表，k是頂點(diǎn)序號(hào)*/InitQueue(&Q);/*初始化隊(duì)列Q*/EnQueue(&Q,k); /*k入隊(duì)*/while(!QueueEmpty(&Q)){i=DeQueue(&Q);/*隊(duì)頭元素出隊(duì)*/visited[i]=1;/*設(shè)置訪問(wèn)標(biāo)記*/訪問(wèn)頂點(diǎn)vi;for(p=G->adjlist[i].firstedge[i];p;p=p->next)/*遍歷頂點(diǎn)vi的相鄰頂點(diǎn)vj(設(shè)p->adjvex=j)*/if(!visited[p->adjvex])EnQueue(&Q,p->adjvex);/*頂點(diǎn)vj的序號(hào)入隊(duì)*/}}六、 已知非空單鏈表第一個(gè)結(jié)點(diǎn)的指針為head，寫一個(gè)算法，找出鏈表中的數(shù)據(jù)域值最大的那個(gè)結(jié)點(diǎn)，并將其鏈接到鏈表的最前面。8(分)七、 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，求二叉樹(shù)的深度。(7分)一、 填空題（每空1分，共10分）（）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。已知線性表A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用4個(gè)存儲(chǔ)單元，第9個(gè)元素的地址為144，則第一個(gè)元素的地址是（）。數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A[0][0]為第一個(gè)元素，其存儲(chǔ)地址為d，每個(gè)元素占1個(gè)存儲(chǔ)單元，則元素A[8][5]的存儲(chǔ)地址為（）。已知廣義表LS=（a,（b,c，d）,e）,用Head和Tail函數(shù)取出LS中原子b的運(yùn)算是（）。設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，該二叉樹(shù)的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是（），最小值是（）。某二叉樹(shù)的前序遍歷序列是ABCDEFG中序遍歷序列是CBDAFGE則其后序遍歷序列是（）。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（）。9■快速排序在（）情況下最不利于發(fā)揮其長(zhǎng)處。二、 選擇題（每題1分，共10分）算法指的是（）。A對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。B計(jì)算機(jī)程序C解決問(wèn)題的計(jì)算方法D數(shù)據(jù)處理鏈表不具有的特點(diǎn)是（）。A可隨機(jī)訪問(wèn)任一元素B插入、刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性表長(zhǎng)度成正比設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過(guò)棧S,—個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1,則棧S的容量至少應(yīng)該是（ ）。A6 B4 C3 D2設(shè)二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則其深度為（）。An-1BnC丨：J^+1D不能確定一個(gè)高度為h的滿二叉樹(shù)共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（）成立。An=h+mBh+m=2nCm=h-1Dn=2m-1下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是（）。A關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C所有的關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成D某些關(guān)鍵活動(dòng)若提前完成，那么整個(gè)工程將會(huì)提前完成靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（）。A它們的邏輯結(jié)構(gòu)不一樣 B施加在其上的操作不同C所包含的數(shù)據(jù)元素的類型不一樣D存儲(chǔ)實(shí)現(xiàn)不一樣散列技術(shù)中的沖突指的是（）。A兩個(gè)元素具有相同的序號(hào)B兩個(gè)元素的鍵值不同，而其他屬性相同C數(shù)據(jù)元素過(guò)多D不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址當(dāng)待排序序列基本有序或個(gè)數(shù)較小的情況下，最佳的內(nèi)部排序方法是（。A直接插入排序B起泡排序C簡(jiǎn)單選擇排序D快速排序設(shè)要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按升序排列，（）是堆排序初始建堆的結(jié)果。A（F,H,C,D,P,A,M,Q,R,S,Y,X）

TOC\o"1-5"\h\zB（P, A, C,S,Q,D, F, X, R,H, M, Y）C（A, D, C,R,F,Q, M, S, Y,P, H, X）D（H, C, Q,P,A,M, S, R, D,F, X, Y）三、解答下列各題（共55分）舉例說(shuō)明在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用。（8分）在無(wú)回溯的模式匹配KMP算法中，關(guān)鍵是在匹配不成功時(shí)確定模式的滑動(dòng)距離。設(shè)模式T="abaababc",求模式T在每一個(gè)位置j匹配不成功時(shí)的滑動(dòng)距離next[j]°（6分）已知一棵二叉樹(shù)如下圖所示，畫出該二叉樹(shù)的順序存儲(chǔ)、二叉鏈表、三叉鏈表存儲(chǔ)示意圖。（8分）已知上圖所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)說(shuō)明Prim算法的求解思想，并寫出用Prim算法求最小生成樹(shù)的過(guò)程。（10分）已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對(duì)該字符串用[0,1]進(jìn)行前綴編碼，問(wèn)該字符串的編碼至少有多少位。（8分）將數(shù)列（24,15,38,27,121,76,130）的各元素依次插入一棵初始為空的二叉排序樹(shù)中，請(qǐng)畫出最后的結(jié)果，在這棵二叉排序樹(shù)上刪除值為38的結(jié)點(diǎn)，請(qǐng)畫出刪除后的