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

1、綜合題綜合題1設(shè)一組記錄的關(guān)鍵字序列為（設(shè)一組記錄的關(guān)鍵字序列為（4949，8383，5959，4141，4343，4747），采用堆排序算法完成以下操作：（要求，采用堆排序算法完成以下操作：（要求小根堆，并畫出中間過程）小根堆，并畫出中間過程）（1）以二叉樹描述）以二叉樹描述6個(gè)元素的初始堆個(gè)元素的初始堆（2）以二叉樹描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的）以二叉樹描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5個(gè)元素、個(gè)元素、4個(gè)元素的堆個(gè)元素

2、的堆（1）（2）4959834143478347414359494983414347834359494143478349594147595947414983434347415983494741835943494741438349595947414383492212130191502515200100104（1）設(shè)有序列）設(shè)有序列1010，1212，1515，1919，2222，2525，100100，130130，150150，2002

3、00畫出對(duì)上述序列進(jìn)行折半查找的判定樹畫出對(duì)上述序列進(jìn)行折半查找的判定樹（以序列中的元素作為樹的結(jié)點(diǎn)）（以序列中的元素作為樹的結(jié)點(diǎn)）（2）為了成功查找到）為了成功查找到100100需要進(jìn)行多少次元素間的比較？為了查找需要進(jìn)行多少次元素間的比較？為了查找9，經(jīng)過多少次元素間的比較可知道查找，經(jīng)過多少次元素間的比較可知道查找失敗？失敗？（1）（2）4次，次，3次5（1）對(duì)給定數(shù)列）對(duì)給定數(shù)列716482096185716482096185，

4、依次取數(shù)列中的數(shù)據(jù)，構(gòu)造一棵二叉排序樹。，依次取數(shù)列中的數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2(2)對(duì)一個(gè)給定的查找值對(duì)一個(gè)給定的查找值簡(jiǎn)述針對(duì)二叉排序樹進(jìn)行查找的算法步驟，在上述二叉樹中查找元素簡(jiǎn)述針對(duì)二叉排序樹進(jìn)行查找的算法步驟，在上述二叉樹中查找元素2020共要共要進(jìn)行多少次元素的比較進(jìn)行多少次元素的比較（1）（2）先將給定值與根結(jié)點(diǎn)比較，若相等則查找成功，否則若小于根結(jié)點(diǎn)則在左子樹中繼續(xù)查找，大于根結(jié)點(diǎn)在右子樹中查找，查找20共進(jìn)行3次

5、比較。6(1)(1)設(shè)有查找表設(shè)有查找表514261874163514261874163依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果。）說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果。（1）(2)中序遍歷中序2，3，4，5，6，7，14，16，1846895716201824616731