數(shù)據(jù)結(jié)構(gòu)-綜合題

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

2、(W 4St S4 II觸 2002 .設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head,結(jié)點(diǎn)類型為NODE，每個(gè)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域data和一個(gè)指針域 next,該鏈表有兩個(gè)結(jié)點(diǎn)，p指向第二個(gè)結(jié)點(diǎn)(尾結(jié)點(diǎn))，按以下要求寫岀相應(yīng)語(yǔ)句(不要求完整程序，(1)、(2)、( 3)、( 4)是一個(gè)連續(xù)的過程)。(1) 新開辟一個(gè)結(jié)點(diǎn)，使指針s指向該結(jié)點(diǎn)，結(jié)點(diǎn)的數(shù)據(jù)成員data賦值為12)把該結(jié)點(diǎn)插入鏈表的尾部，釋放指針s的指向(3) 刪除鏈表的第一個(gè)結(jié)點(diǎn)(4) 已知pl指向另一個(gè)新結(jié)點(diǎn)，把它插入到p所指結(jié)點(diǎn)和尾結(jié)點(diǎn)之間1) s= (NODE* ) malloc(sizeof(NODE);s->da

3、ta=1;(2) p_>next=s;s->next= NULL ;free(s)(3) head = head ->next；(4) P1->next= p->next ；p->next=p 1；4. ( 1)設(shè)有序列10, 12, 15, 19, 22, 25, 100, 130, 150, 200畫出 對(duì)上述序列進(jìn)行折半查找的判定樹(以序列中的元素作為樹的結(jié)點(diǎn))(2) 為了成功查找到100需要進(jìn)行多少次元素間的比較？為了查找 9, 經(jīng)過多少次元素間的比較可知道查找失?。縧it3袂5.(1)對(duì)給定數(shù)列7,16,4,8,20,9,6,18,5，依次取數(shù)列中

4、的數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2 )對(duì)一個(gè)給定的查找值，簡(jiǎn)述針對(duì)二叉排序樹進(jìn)行查找的算法步驟， 在上述二叉樹中查找元素20共要進(jìn)行多少次元素的比較？圖5(2)先將給定值與根結(jié)點(diǎn)比較，若相等則查找成功，否則若小于根結(jié)點(diǎn)則在左子樹中繼續(xù)查找，大于根結(jié)點(diǎn)在右子樹中查找，查找20共進(jìn)行3次比較。6. (1)設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二 叉排序樹。(2)說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述 二叉排序給岀中序遍歷的結(jié)果。(1)(2)中序遍歷中序 2, 3, 4, 5, 6, 7, 14, 16, 181. (1)已知某二叉樹的后序遍歷序

5、列是debca,中序遍歷序列是dbeac,試畫出該二叉樹(2)若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒 有相等的)，并恰好使該樹成為一棵二叉排序樹，試給岀a、b、c、d、e的大小關(guān)系(3)給岀該樹的前序遍歷序列1.4. ( 1)給定數(shù)列8, 17, 5, 9, 21, 10,數(shù)構(gòu)造一棵二叉排序樹(2)對(duì)上述二叉樹給岀中序遍歷得到的序列7, 19, 6，依次取序列中的(2) 5, 6, 7, 8, 9, 10,17, 18, 19, 215. ( 1)利用篩選過程把序列 42, 82, 67, 102, 16, 32, 57, 52建成 堆(小根堆)，畫岀相應(yīng)的完全二叉樹(不要求中

6、間過程)(2) d<b<evavc(3) abdec2.( 1)已知某二叉樹的先序遍歷序列是aecdb中序遍歷序列是 eadcb,試畫岀該二叉樹(2)給岀上述二叉樹的后序遍歷序列3)若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別是1, 2, 3, 4, 5,并恰好使該樹成為一棵二叉排序樹，試問a、b c、d、e的值各為多少?(2) edbca(3) e=1,a=2,d=3,c=4,b=5(2) 102, 52, 42, 82, 16, 67, 32, 576. ( 1)以給定權(quán)重值1, 2, 12, 13, 20, 25為葉結(jié)點(diǎn)，建立一棵哈夫 曼樹(2)若哈夫曼樹有n個(gè)非葉子結(jié)點(diǎn)，則樹中共有多少

7、結(jié)點(diǎn)。對(duì)給定 的一組權(quán)重值建立的棵哈夫曼樹是否一定唯一3. ( 1)設(shè)有一個(gè)整數(shù)序列40, 28, 6, 72, 100, 3, 54依次取出序列 中的數(shù)，構(gòu)造一棵二叉排序樹(2)對(duì)上述二叉排序樹，在等概率條件下，求成功查找的平均查找長(zhǎng) 度(2) ASL= ( 1x1+2x2+3x3+4 ) /7=18/7(2) 2n-1 不一定唯(2)寫岀對(duì)上述堆對(duì)應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列1. (1)設(shè)head*!和Pi分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭指針和尾指針，head2和P2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個(gè)以 head*為頭指針的單向循環(huán)

8、鏈表，寫岀其中兩個(gè)關(guān)鍵的賦值語(yǔ)句(不用完整程序，結(jié)點(diǎn)的鏈域?yàn)閚ext)(2)單向鏈表的鏈域?yàn)?next，設(shè)指針p指向單向鏈表中的某個(gè)結(jié)點(diǎn)， 指針s指向一個(gè)要插入鏈表的新結(jié)點(diǎn)，現(xiàn)要把s所指結(jié)點(diǎn)插入 p所指結(jié)點(diǎn)之后，某學(xué)生采用以下語(yǔ)句：p->next=s; s->next=p->next;這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫(1) Pi->next= head2； P2->next= headi ；(2) 不對(duì)，s->next= p->next ； p->next=s ；2 . ( 1) 一組記錄的關(guān)鍵字序列為 45，40, 65

9、, 43，35, 95寫出利用 快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果(要求給岀一趟劃分中每次掃描和交換的結(jié)果)(2)同樣對(duì)序列45，40，65, 43，35, 95利用直接插入排序，寫 岀逐次插入過程(從第一個(gè)元素一直到第六個(gè)元素)。45 40 65 43535 40 65 43 35 9535釗卿3 £ 9?35 40 4>H3j55 235 40 43 45 65 9540 45 65 43 35 9540 43 45 65 35 P:35 40 43 45 65 9:3. (1)畫岀對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹(以序號(hào)1,2, 10表示樹結(jié)點(diǎn))(2)對(duì)上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均 查找長(zhǎng)5. ( 1)利用篩選法，把序列37, 77, 62, 97, 11, 27, 52, 47建成 堆(小根堆)，畫出相應(yīng)的完全二叉樹(2)寫岀對(duì)上述堆所對(duì)應(yīng)的二叉樹進(jìn)行前序遍歷得到的序(2) 11, 37, 47, 97, 77, 27, 62, 52 6. ( 1)設(shè)有一個(gè)整數(shù)序列50, 38, 1