1、汕頭職業(yè)技術(shù)學(xué)院2007-2009學(xué)年第二學(xué)期期末試卷（B）課程名稱數(shù)據(jù)結(jié)構(gòu)學(xué)分_擬題人何漢陽審題人_系(校區(qū))計(jì)算機(jī)系班級_學(xué)號_姓名_題號一二三四五六七八總分評卷人得分一、判斷題（每題1分，共15分）1、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)質(zhì)儲藏形式。（）2、分配給單鏈表的內(nèi)存地址必定是連續(xù)的。（）3、在有n個元素的序次表中，刪除任意一個元素所需搬動結(jié)點(diǎn)的平局次數(shù)為n-1。（）4、對于單循環(huán)鏈表，從表中任一結(jié)點(diǎn)都能掃描表中的全部結(jié)點(diǎn)。（）5、棧是一種對進(jìn)棧、出棧操作總次數(shù)做了限制的線性表。（）6、無論是序次隊(duì)列還是鏈接隊(duì)列，插入和刪除元素運(yùn)算的時間復(fù)雜度都是O(1）。（）7、表示稀罕矩陣的

2、三元組序次中，各元素的排列序次與矩陣元素值的大小有關(guān)。（）8、完好二叉樹中只有度為0和度為2的結(jié)點(diǎn)。（）9、已知二叉樹的先序序列和后序序列，其實(shí)不能夠唯一確定這棵二叉樹。（）10、哈夫曼樹中，權(quán)值較大的葉結(jié)點(diǎn)一般都離根結(jié)點(diǎn)較遠(yuǎn)。（）11、若是表示有向圖的毗鄰矩陣是對稱矩陣，則該有向圖必然是完好有向圖。（）12、有向圖的遍歷不能采用廣度優(yōu)先找尋方法。（）13、序次表和單鏈表表示的有序表均可使用二分查找法來提高查找速度。（）14、只有在記錄的要點(diǎn)字的初始狀態(tài)為逆序排列的情況下，直接選擇排序過程中元素的搬動次數(shù)才會達(dá)到最大值。（）15、內(nèi)排序中的快速排序方法，在任何情況下均可獲取最快的排序收效。（）

3、二、選擇題（每題2分，共40分）1_中任何兩個結(jié)點(diǎn)之間都沒有邏輯關(guān)系。會集B)圖狀結(jié)構(gòu)C)樹型結(jié)構(gòu)D)線性結(jié)構(gòu)2計(jì)算機(jī)算法指的是_。A)計(jì)算方法B)調(diào)換方法C)排序方法D)解決某一問題的有限運(yùn)算序列3下面_的時間復(fù)雜性最好，即執(zhí)行時間最短。A)O(n)B)O(nlogn)C)O(log3n)D)O(n)224在一個長度為n的序次表中，向第i個元素(1in+1)地址插入一個新元素時，需要從后向前依次后移_個元素。A)n-iB)iC)n-i-1D)n-i+l5對序次儲藏的線性表，設(shè)其長度為n，在任何地址上插入或刪除操作都是等概率的，插入一個元素時-1-/4平均搬動表中的_個元素。A)n/2B)(n

4、-1)2C)(n+1)2D)n6單鏈表要求內(nèi)存中可用儲藏單元的地址。A)必定是連續(xù)的B)必然是不連續(xù)的C)部分地址必定是連續(xù)的D)能夠是連續(xù)的，也能夠是不連續(xù)的7在一個單鏈表中，若要刪除p指針?biāo)赶蚪Y(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行_。A)p-next=pB)p=p-next-nextC)p-next=p-next-nextD)p=p-next；p-next=p-next-next8若某鏈表最常用的操作是在最后一個結(jié)點(diǎn)此后插入一個結(jié)點(diǎn)和刪除最后一個結(jié)點(diǎn)，則采用_存儲方式最節(jié)約時間。單鏈表B)雙鏈表C)單循環(huán)鏈表D)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表9采用鏈接方式儲藏線性表的優(yōu)點(diǎn)是_。便于隨機(jī)存取B)開銷的儲藏空間較序次

5、儲藏少便于插入和刪除操作D)數(shù)據(jù)元素的物理序次和邏輯序次相同10在下面棧的基本運(yùn)算中，不是加工型運(yùn)算的是_。初始化B)進(jìn)棧C)退棧D)判棧空11在序次棧中進(jìn)行退棧操作時，_。A)誰先誰后都能夠B)先搬動棧頂指針，后取出元素C)不分先后，同時進(jìn)行D)先取出元素，后搬動棧頂指針12假設(shè)一個棧的輸入序列為A，B，C，D，E，則以下序列中不能能是棧的輸出序列的是_。A)B，C，D，A，EB)E，D，A，C，BC)B，C，A，D，ED)A，E，D，C，B13在由n個單元組成的序次儲藏的循環(huán)隊(duì)列sq中，假設(shè)f和r分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件是_。A)f=(r十1)nB)(r-1)n=fC)f

6、=rD)(f+1)n=r14樹最適合于表示_。A)有序數(shù)據(jù)元素B)無序數(shù)據(jù)元素C)元素之間無聯(lián)系的數(shù)據(jù)D)元素之間擁有分支層次關(guān)系的數(shù)據(jù)15在一棵深度為k的完好二叉樹中，所含結(jié)點(diǎn)個數(shù)不小于_。A)2kB)2k+1C)2k-1D)2k-116在以下儲藏形式中，_不是樹的儲藏形式。A)雙親表示法B)序次儲藏表示C)孩子兄弟表示法D)孩子鏈表表示法17對于長度為8的序次儲藏結(jié)構(gòu)的有序表，若采用二分查找法查找，在等概率的情況下的平均查找長度為_的值除以8。A)17B)19C)21D)2018若對n個元素進(jìn)行直接插入排序，則進(jìn)行第i趟排序過程前，有序表中的元素個數(shù)為_。A)1B)i-1C)iD)i+l1

7、9在對n個元素進(jìn)行冒泡排序的過程中，第一趟排序至多需要進(jìn)行_。對相鄰元素之間的交換。A)n2B)n-1C)nD)n+l20以下四種排序方法中，需要附加的內(nèi)存空間最大的是_。A)插入排序B)選擇排序C)快度排序D)歸并排序三、列表說明用Prim算法求解以下列圖最小生成樹的生成過程。（15分）-2-/4四、試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除（一個）最小值結(jié)點(diǎn)的“高效”算法。（10分）五、要點(diǎn)碼序列為47,7,29,11,16,92,22,8,3,50,37,89,21，哈希函數(shù)為H(k)=k%11，畫出其開散列表辦理矛盾表示圖，并計(jì)算查找成功的平均查找長度。（10分）。六、寫出序次表大將監(jiān)察哨設(shè)在高端

8、的序次查找算方法程序，并要寫出在main()主函數(shù)中調(diào)用的過程語句。查找表的結(jié)構(gòu)定義同課本一致，查找表的元素值和長度經(jīng)過鍵盤輸入。（10分）。2007-2009學(xué)年第二學(xué)期期末試卷（B）答案課程名稱數(shù)據(jù)結(jié)構(gòu)擬題人何漢陽一、判斷題（每題1分，共15分）15、610、1115、二、選擇題（每題2分，共40分）15、ADCDA610、DCDCD1115、DBADD1620、DBCBD三、解：（15分）設(shè)從極點(diǎn)0出發(fā)U=0,V-U=1,2,3,4,5,6Adjvex/000000k=5Lowcost02810(0,5)U=0,5,V-U=1,2,3,4,6Adjvex/000500k=4Lowcost

9、028250(5,4)U=0,5,4,V-U=1,2,3,6Adjvex/004504k=3Lowcost028220024(4,3)U=0,5,4,3,V-U=1,2,6Adjvex/034503k=2Lowcost0281200018(3,2)U=0,5,4,3,2,V-U=1,6Adjvex/234503k=1Lowcost016000018(2,1)U=0,5,4,3,2,1,V-U=6Adjvex/234501k=6Lowcost00000014(1,6)U=0,5,4,3,2,1,6,V-U=四、解：（10分）002810128016142160123120221842202524

10、51025061418240voidDelMinNode(LINKLIST*head)LINKLIST*p,*q,*r;/r為指向最小值結(jié)點(diǎn)的前一個結(jié)點(diǎn)-3-/4p=head-next;q=head;r=q;/假設(shè)第一個值結(jié)點(diǎn)最小while(pNULL)q=p;p=p-next;if(p-datanext-data)r=q;if(r-next-next=NULL)/若最小值是尾結(jié)點(diǎn)p=r-next;r-next=NULL;free(p);elsep=r-next;r-next=p-next;free(p);五、解：（10分）0112217/13查找成功的平均查找長度ASL（1+1+2+1+1+

11、1+2+1+2+1+2+1+1）/13六、解：（10分）891#include2#defineMAXSIZE1004733typedefstructintkey;49237516SSELEMENT;typedefstruct650SSELEMENTrMAXSIZE;29intlen;778SSTABLE;89intseq_search(intk,SSTABLEst)intj=0;1021st.rst.len.key=k;while(st.rj.key!=k)j+;if(jst.len)returnj+1;elsereturn0;voidmain()intk,i;SSTABLEst;printf(InputLen:);scanf(%d,&st.len);for(i=0;ist.len;i+)scanf(%d,&st.ri.key);printf(nsearchthenumber:);scanf(%d,&k);i=