中國海洋大學007數(shù)據(jù)結(jié)構(gòu)第1學期A卷+答案

中國海洋大學命題專用紙（首頁）2006學年第1學期試題名稱：數(shù)據(jù)結(jié)構(gòu)（A卷）專業(yè)整：學號姓名授課教師分數(shù)一、簡答下列術(shù)語：（10分）1、算法的時間復(fù)雜度2、棧與隊列的異同3、完全二叉樹、二叉排序樹二、填空（10分）1、在雙向循環(huán)鏈表L中，刪除指針P所指結(jié)點的語句序列是,,free（p）。2、將下三角矩陣A[1..8,1..8]的下三角部分逐行地存儲到起始地址為1000的內(nèi)存單元中.已知每個元素占4個單元，則A（6,4）的地址為。3、高度為5的三階B—樹至少有個結(jié)點。4、分別采用堆排序、快速排序、1認排序和歸并排序算法對初始狀態(tài)已為遞增序列的數(shù)據(jù)表進行遞增排序，最省時間的是算法。三、（8分）已知一棵二叉機勺中序序列是dcbgeahfijk,后序序列是dcegbfhkjia,請構(gòu)造出該二叉樹。四、（10分）假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別是0.07,0.08,0.13,0.22,0.18,0.23,0.04,0.05。請設(shè)計它們相應(yīng)的哈夫曼編碼。使用0?7的二進制表示形式是另一種編碼方案，請比較兩種方案的優(yōu)缺點。五、（10分）設(shè)散列表地址空間為0..6,散列函數(shù)為H（x）=imod7,其中i為鍵值x中第一個字母在字母表中的序號，若鍵值的輸入序列為Jen,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec,用鏈地址法處理沖突，1）構(gòu)造散列表；2）求出在等概率情況下，查找成功時的平均查找長度。六、（15分）（1）對下列數(shù)據(jù)表，寫出采用希爾排序算法排序的每一趟的結(jié)果。（100,12,20,31,1,5,44,66,61,200,30,80,150,4,8）（2）對下列數(shù)據(jù)表，寫出采用快速排序算法排序的第一趟的結(jié)果。（70,12,20,150,44,66,61,200,30,80,28）授課教師張海燕命題教師或命題負責人簽字院系負責人簽字年月日中國海洋大學命題專用紙（附頁）2006學年第1學期試題名稱：數(shù)據(jù)結(jié)構(gòu)（A）共2頁第2頁七、（6分）畫出對應(yīng)于遞增有序表A[1..21]進行二分查找的判定樹。八、（15分）對如下的網(wǎng)，1）寫出其鄰接矩陣。2）求其最小生成樹。（寫出各步狀態(tài)）九、（8分）試編寫一算法，實現(xiàn)無頭結(jié)點的單鏈表的就地逆置，即利用原表的存儲空間將線，性表（a1,a2,…，an-1,a“逆置為（an,an-1,,…，a2,a。。十、（8分）設(shè)計算法以判斷二叉樹T是否為二叉排孑樹（設(shè)T中任意兩個結(jié)點F^值均不相等）。（設(shè)二叉樹以二叉鏈表來存儲，結(jié)點結(jié)構(gòu)為：LchilddataRchild—）答:由二叉樹的中序序列dcbgeahfijk,后序序列dcegbfhkjia,構(gòu)造的二叉樹如下:四、答:分）a:0110b:0111答:由二叉樹的中序序列dcbgeahfijk,后序序列dcegbfhkjia,構(gòu)造的二叉樹如下:四、答:分）a:0110b:0111帶權(quán)路徑長度(2)(1分)0.04:000,0.13:100,帶權(quán)路徑長度0.08:0110.23:1112006學年第一學期數(shù)據(jù)結(jié)構(gòu)（A）卷試題答案一、簡答題（共10分，每個術(shù)語2分）算法的時間復(fù)雜度：一個算法執(zhí)行所需的平均時間長度，其描述了算法效率的高低。棧與隊列的異同：棧是先進后出，只能在棧頂插入元素或刪除元素；隊列是先進先出，在隊頭刪除元素，隊尾插入元素。完全二叉樹：若一棵二叉樹從上到下，從左到右依次編號與滿二叉樹對應(yīng)編號完全相同。則稱此二叉樹為完全二叉樹。二叉排序樹：或者是一棵空樹，或者具有這樣性質(zhì)的樹：（1）左子樹結(jié)點的值均小于根結(jié)點的值，（2）右子樹結(jié)點的值均大于根結(jié)點的值，（3）左、右子樹分別是二叉排序樹。二、填空題（共10分，每個填空2分）p—prior—.next=p—.next,p—.next—.prior=p—.prior107215.插入排序（8分，依照所構(gòu)造的二叉樹正確的比例給分）（10分）（9分，所構(gòu)造的哈夫曼樹為假設(shè)8個字母分別為a,b,c,d,e,f,g,h.出現(xiàn)概率為已知0.07,0.08,0.13,0.22,0.18,0.23,0.04,0.05。對左子樹路徑賦為0,右子樹賦為1,則a,b,c,d,e,f,g,h,i的哈夫曼編碼為：c:110d:10e:010f:00g:1110h:1111WPL=￡w叫=0.07*4+0.08*4+0.13*3+022*2+0.18*3+0.23*2+0.04*4+0.05*4=2.790~7二進制表示如下：0.05:001,0.07:010,0.18:101,0.22:110,WPL=工w叫=(0.04+0.05+0.07+0.08+0.13+0.18+0.22+0.22)*3=3>2.79

比較可知：哈夫曼編碼為不等長碼，信源壓縮度高。比例給比較可知：哈夫曼編碼為不等長碼，信源壓縮度高。比例給用鏈地址法處理沖突，構(gòu)造散列表如下:六、（15分）（1）（7分，依照正確的比例給分）初始關(guān)鍵字：10012假設(shè)各趟希爾排序的間隔分別為第一趟排序結(jié)果:

第二趟排序結(jié)果:

第三趟排序結(jié)果:81220304158121458127,3,1。154666120031801504420302030（2）（8分，依照正確的比例給分）選取70為樞軸初始關(guān)鍵字:701220150?4第一次交換后:28第二次交換后:28第三次交換后:28第四次交換后:28第一趟排序結(jié)果:31314461150448020066446166801001501001002006661200308028122015044666120030801212122020204466612003080150t.ti30446661200304466618015020080150281220304466617020080150七、（6分，依照判定樹的正確比例給分）答：二分查找的判定樹如下：(77^/J_J1DCZ)O()GDCD1C42)(7^)003ct)<CD(八：（15分）■0347-11130/3"（1）（7分）鄰接矩陣為：心02511|73201卜85101(Vb)2(Vc)3(Vd)4(Ve)UV_UVexadjVa3Va4Va7[Va][Vb,Vc,Vd,Ve]Vexadj0Va4Vb3[Va,Vb][Vc,Vd,Ve]Vexadj0Vd20Vd1[Va,Vb,Vd][Vc,Ve]Vexadj0Vd200[Va,Vb,Vd,Ve][Vc]

Vexadj0000[Va,Vb,Vd,Ve,Vc]（2）（8分）（2）（8分）最小生成樹為:九：（8分，依照解題思路的正確程度給分函數(shù)編寫如下：單鏈表如下圖：A1*A2*A3An-1aAnA1*A2*A3An-1aAnStatusReverse(Linklist*L){inti=1;P=L;for(;i<L.length;i+=3){m=p-next;n=mfnext;mfnext=p;nfnext=m;p=n;L-next=Null;十、(8分，依照解題思路的正確程度給分)判斷二叉樹是否為二叉排序樹的程序如下：intPaixu(Bi