數據結構-綜合題

1、綜合題1.設一組記錄的關鍵字序列為(49,83,59,41,43,47),采用堆排序算法完成以下操作：(要求小根堆，并畫出中間過程)(1)以二叉樹描述6個元素的初始堆(2)以二叉樹描述逐次取走堆頂元素后，經調整得到的5個元素、4個元素的堆。3.設有序表為(13,19,25,36,48,51,63,84,91,116,135,200),元素的下標依次為1,2,，12。(1)說出有哪幾個元素需要經過4次元素間的比較才能成功查到(2)畫出對上述有序表進行折半查找所對應的判定樹(樹結點用下標表不)(3)設查找元素5,需要進行多少次元素間的比較才能確定不能查到19舒t2.設有一個不帶頭結點的單向鏈表，頭

2、指針為head,結點類型為NODE,每個結點包含一個數據域data和一個指針域next:,該鏈表有兩個結點，p指向第二個結點(尾結點)，按以下要求寫出相應語句(不要求完整程序，(1)、(2)、(3)、(4)是一個連續(xù)的過程)。(1)新開辟一個結點，使指針s指向該結點，結點的數據成員data賦值為1(2)把該結點插入鏈表的尾部，釋放指針s的指向(3)刪除鏈表的第一個結點(4)已知pl指向另一個新結點，把它插入到p所指結點和尾結點之間(1) s=(NODE*)malloc(sizeof(NODE);s->data=1;(2) p->next=s;s->next=NULL;free

3、(s)(3) head=head->next；(4) p1->next=p->next；p->next=p1；4. (1)設有序列10,12,15,19,22,25,100,130,150,200畫出對上述序列進行折半查找的判定樹(以序列中的元素作為樹的結點)(2)為了成功查找到100需要進行多少次元素間的比較？為了查找9,經過多少次元素間的比較可知道查找失敗？5. (1)對給定數列7,16,4,8,20,9,6,18,5,依次取數列中的數據，構造一棵二叉排序樹。(2)對一個給定的查找值，簡述針對二叉排序樹進行查找的算法步驟，在上述二叉樹中查找元素20共要進行多少次元素

4、的比較？(2)先將給定值與根結點比較，若相等則查找成功，否則若小于根結點則在左子樹中繼續(xù)查找，大于根結點在右子樹中查找，查找20共進行3次比較。6. (1)設有查找表5,14,2,6,18,7,4,16,3,依次取表中數據，構造一棵二叉排序樹。(2)說明如何由序列的二叉排序樹得到相應序列的排序結果，對上述二叉排序給出中序遍歷的結果。(2)中序遍歷中序2,3,4,5,6,7,14,16,181.(1)已知某二叉樹的后序遍歷序列是debca,中序遍歷序列是dbeac,試畫出該二叉樹(2)若上述二叉樹的各個結點的字符分別代表不同的整數(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹，試給出a、b、

5、c、d、e的大小關系(3)給出該樹的前序遍歷序列(1)4.(1)給定數列8,17,5,9,21,10,數構造一棵二叉排序樹(2)對上述二叉樹給出中序遍歷得到的序列7,19,6,依次取序列中的(2) 5,6,7,8,9,10,17,18,19,215.(1)利用篩選過程把序列42,82,67,102,16,32,57,52建成堆(小根堆)，畫出相應的完全二叉樹(不要求中間過程)(2)寫出對上述堆對應的完全二叉樹進行中序遍歷得到的序列(2) d<b<e<a<c(3) abdec2 .(1)已知某二叉樹的先序遍歷序列是aecdb,中序遍歷序列是eadcb,試畫出該二叉樹(2)

6、給出上述二叉樹的后序遍歷序列(3)若上述二叉樹的各個結點的字符分別是1,2,3,4,5,并恰好使該樹成為一棵二叉排序樹，試問a、氏c、d、e的值各為多少？3 .(1)設有一個整數序列40,28,6,72,100,3,54依次取出序列中的數，構造一棵二叉排序樹(2)對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度(2)ASL=(1x1+2x2+3x3+4)/7=18/7看柏構庫(2)102,52,42,82,16,67,32,576.(1)以給定權重值1,2,12,13,20,25為葉結點，建立一棵哈夫曼樹(2)若哈夫曼樹有n個非葉子結點，則樹中共有多少結點。對給定的一組權重值建立的棵

7、哈夫曼樹是否一定唯一(2)2n-1不一定唯1. (1)設headDP1分別是不帶頭結點的單向鏈表A的頭指針和尾指針,head2和P2分別是不帶頭結點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個以headi為頭指針的單向循環(huán)鏈表，寫出其中兩個關鍵的賦值語句(不用完整程序，結點的鏈域為next)。(2)單向鏈表的鏈域為next,設指針p指向單向鏈表中的某個結點，指針s指向一個要插入鏈表的新結點，現要把s所指結點插入p所指結點之后，某學生采用以下語句：p->next=s;s->next=p->next;這樣做正確嗎？若正確則回答正確，若不正確則說明應如何改寫(

8、1) Pi->next=head2；P2->next=headi；(2) 不對，s->next=p->next；p->next=s；2. (1)一組記錄的關鍵字序列為45,40,65,43,35,95寫出利用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結果(要求給出一趟劃分中每次掃描和交換的結果)(2)同樣對序列45,40,65,43,35,95利用直接插入排序，寫出逐次插入過程(從第一個元素一直到第六個元素)。(1) 45406543535406543359535.同43,953540百圖5595354043456595(2) 404565433?P?4043456535配35404345659:3. (1)畫出對長度為10的有序表進行折半查找的判定樹(以序號1,2,10表示樹結點)(2)對上述序列進行折半查找，求等概率條件下，成功查找的平均查找長5. (1)利用篩選法，把序列37,77,62,97,11,27,52,47建成堆(小根堆)，畫出相應的完全二叉樹(2)寫出對上述堆所對應的二叉樹進行前序遍歷得到的序(2)11,37,47,97,77,27,62,526. (1)設有一個整數序列50,38