PAGEPAGE2軟件學(xué)院2005級<<數(shù)據(jù)結(jié)構(gòu)>>期終試題2006.12.31姓名學(xué)號123得分1．填充題（36分，每空3分）1)設(shè)有n個(gè)不同關(guān)鍵碼的對象在排序前已按關(guān)鍵碼由小到大排好序，用下列方法對其按關(guān)鍵碼進(jìn)行排序，需要進(jìn)行比較的次數(shù)：直接插入排序:n-1，快速排序n*(n-1)/2。在直接插入排序，折半插入排序，直接選擇排序，.起泡排序，快速排序，歸并排序中關(guān)鍵碼比較的次數(shù)與記錄的初始排序無關(guān)的排序方法有。2）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a6,a7,和a8依次通過棧S，一個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，若8個(gè)元素出隊(duì)列的順序是a3,a6,a8,a7,a5,a4,a2,a1,則棧S的容量至少應(yīng)該是多少（即至少應(yīng)該容納多少個(gè)元素）。3）對有10個(gè)元素的有序表,采用二分查找,需要比較4次方可找到的元素個(gè)數(shù)為____3_____________。4）在有51個(gè)結(jié)點(diǎn)的完全二叉樹中,度為1的結(jié)點(diǎn)個(gè)數(shù)是____26________。5）一個(gè)具有n個(gè)頂點(diǎn)的無向圖至多有_____n(n-1)/2__________條邊。該圖又稱為無向完全連同圖。6)一棵AVL樹T中結(jié)點(diǎn)的關(guān)鍵碼均為正整數(shù)(從1開始取值)，它有下列特點(diǎn)：（1）刪除關(guān)鍵碼為k1的某個(gè)葉結(jié)點(diǎn)，然后再插入關(guān)鍵碼k1，得到的AVL樹與原AVL樹T不同；（2）刪除T中關(guān)鍵碼為k2的非葉結(jié)點(diǎn)，然后再插入關(guān)鍵碼k2，得到的AVL樹與原AVL樹T相同；（3）往T中插入某個(gè)關(guān)鍵碼k3，然后再刪除k3，得到的AVL樹與原AVL樹T不同。畫出具有上述特點(diǎn)且結(jié)點(diǎn)個(gè)數(shù)最少的一棵AVL樹。并指出關(guān)鍵碼k1、k2、k3的值分別是多少？7）設(shè)某一二叉樹的中序遍歷序列為A,B,C,D,E,F,G,后序遍歷序列為B,D,C,A,F,G,E,則該二叉樹的先序遍歷序列為______________。8)判別以下序列是否是堆？如果不是，將它調(diào)整為最大堆。{12,70,33,65,24,56,48,92,86,33}2．解答題（40分，每題10分）1)散列表的地址區(qū)間為0-16,散列函數(shù)為H(K)=K%17,采用線性探查法處理沖突，請將關(guān)鍵碼序列26、25、72、38、8、18、59依次存儲(chǔ)到散列表中。(1)元素59存放在散列表中的地址是多少？(2)搜索元素59需要比較的次數(shù)是多少？答：（1）11（2）42）下面是一棵3階B-樹。試分別畫出依次刪除50、40之后的B-樹。503060802040557095答：3）按Dijkstra方法計(jì)算下列圖中從頂點(diǎn)1到其它頂點(diǎn)的最短路徑。按路徑遞增順序?qū)懗鱿群笥?jì)算出的最短路徑（包括起止點(diǎn)和途徑各點(diǎn)）及該路徑長度。答4)給出一組實(shí)數(shù)w={15,1,4,6,12,25,7}畫出以這一組實(shí)數(shù)為權(quán)的哈夫曼樹。并計(jì)算其帶權(quán)的外路徑長度。答：3算法題(24分,第1題10分，第2題14分)已知first為不帶表頭結(jié)點(diǎn)的單鏈表的表頭指針(如下圖所示)，鏈表中存儲(chǔ)的都是整型數(shù)據(jù)，試寫出求所有結(jié)點(diǎn)的data域平均值的遞歸函數(shù)。datalinkdatalinkfirst…..first…..a1a2a3……annull答：給定一棵二叉搜索樹t,其根指針為root,各結(jié)點(diǎn)結(jié)構(gòu)為leftdataright,left,right分別指向該結(jié)點(diǎn)的左、右子樹，假設(shè)data域?yàn)閕nt型。試用Java