2006年數據結構期末試卷

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