數(shù)據(jù)結(jié)構(gòu)形考作業(yè)GEGROUPsystemofficero,lm[GIHUA16H-GEIHUAGEIHUA8Q8-題目題目#已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對(duì)該數(shù)列從小到大排序，經(jīng)過(guò)一趟冒泡排序后的序列為（）。選擇一項(xiàng)：16，28，34，54，73，62，60，26，43，9516，28，34，54，62，60，73，26，43，9528，16，34，54，62，73，60，26，43，9528，16，34，54，62，60，73，26，43，95題目20一組記錄的關(guān)鍵字序列為（56，30，89，66，48，50，94，87，100），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）。選擇一項(xiàng)：48，30，50，56，66，89，94，87，10050，30，48，66，56，89，94，87，10030，50，48，56，66，89，94，100，8750，30，48，56，66，89，94，87，100題目題目25如果要求一個(gè)線(xiàn)性表既能較快地查找，又能動(dòng)態(tài)適應(yīng)變化要求，可以采用（）查找方法。選擇一項(xiàng)：折半順序分塊散列二、填空題（每小題1分，共16分）題目22在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是哈希表查找法題目23關(guān)鍵字是記錄某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以識(shí)別、確定一個(gè)記錄。題目24在一個(gè)查找表中，能夠唯一地確定一個(gè)記錄的關(guān)鍵字稱(chēng)為主關(guān)鍵字。平均查找長(zhǎng)度是指為確定記錄在查找表中的位置，需要與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的數(shù)學(xué)期望值。題目26順序查找是一種最簡(jiǎn)單的查找方法。題目27折半查找又稱(chēng)為二分查找。使用該查找算法的前提條件是，查找表中記錄相應(yīng)的關(guān)鍵字值必須按升序或降序排列。題目28折半查找只適用于順序存儲(chǔ)結(jié)構(gòu)的有序表。題目29分塊查找又稱(chēng)為索引順序查找，它是一種介于順序查找和折半查找之間的查找方法。題目30二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的一棵二叉樹(shù)：（1）若左子數(shù)不空，則左子樹(shù)所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。（2）若右子數(shù)不空，則右子樹(shù)所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。（3）左右子樹(shù)又分別是二叉排序樹(shù)。題目題目31哈希表是用來(lái)存放查找表中記錄序列的表，每一個(gè)記錄的存儲(chǔ)位置是以該記錄得到關(guān)鍵字為自變量，由相應(yīng)哈希函數(shù)計(jì)算所得到的函數(shù)值。題目32冒泡排序是一種比較簡(jiǎn)單的交換排序方法。題目33在對(duì)一組記錄（50，40，95，20，15，70，60，45，80）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需要比較3次。題目34在堆排序和快速排序中，若原始記錄接近正序和反序，則選用堆排序，若原始記錄無(wú)序，則最好選用快速排序。題目35n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行n-1趟冒泡，第j趟冒泡要進(jìn)行n-j次元素間的比較。題目36當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整。題目37對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按關(guān)鍵字排序結(jié)果是唯一的。三、綜合題（每小題7分，共42分）題目38已知序列（70，83，100，105，10，32，7，9），請(qǐng)寫(xiě)出對(duì)此序列采用插入排序法進(jìn)行升序排序時(shí)各趟的結(jié)果。原始序列：（70），83，100，65，10，32，7，9第1趟：（70，83），100，65，10，32，7,，9第2趟：（70，83，100），65，10，32，7，9第3趟：（65，70，83，100），10，32，7，9第4趟：（10，65，70，83，100），32，7，9第5趟：（10，32，65，70，83，100），7，9第6趟：（7，10，32，65，70，83，100），9第7趟：（7，9，10，32，65，70，83，100）題目39已知序列（10，18，4，3，6，12，1，9，15，8），請(qǐng)寫(xiě)出對(duì)此序列采用歸并排序法進(jìn)行升序排序時(shí)各趟的結(jié)果。原始序列：10,18,4,3,6,12,1,9,15,8第1趟：[10,18][3,4][6,12][1,9][8,15]第2趟：[3,4,10,18,][1,6,9,12][8,15]第3趟：[3,4,10,18,][1,6,8,9,12,15]第4趟：[1,3,4,6,8,9,10,12,15,18]題目40已知序列（17，18，60，40，7，32，73，65，85）請(qǐng)給出采用冒泡排序法對(duì)該序列作升序排列時(shí)的每一趟結(jié)果。原始序列：256,301,751,129,937,863,742,694,076,438第1趟：256,301,129,751,863,742,694,076,438,937第2趟：256,129,301,751,742,694,076,438,863,937第3趟：129,256,301,742,694,076,438,751,863,937第4趟：129,256,301,694,076,438,742,751,863,937第5趟：129,256,301,076,438,742,694,751,863,937第6趟：129,256,076,301,438,742,694,751,863,937第7趟：129,076,256,301,438,742,694,751,863,937第8趟：129,076,256,301,438,742,694,751,863,937第9趟：129,076,256,301,438,742,694,751,863,937題目41（1）利用篩選過(guò)程把序列｛42，82，67，102，16，32，57，52｝建成堆（小根堆），畫(huà)出相應(yīng)的完全二叉樹(shù)（不要求中間過(guò)程）。（2）寫(xiě)出對(duì)上述堆對(duì)應(yīng)的完全二叉樹(shù)進(jìn)行中序遍歷得到的序列。（1） 堆 初始樹(shù)（2）102,52,42,82,16,67,32,57題目42設(shè)查找表為（20，19，24，57，68，11）（1）用冒泡對(duì)該表進(jìn)行排序，要求寫(xiě)出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡第j趟要進(jìn)行多少次元素間的比較（2）在排序后的有序表的基礎(chǔ)上，畫(huà)出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)。（要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn)）（3）求在等概率條件下，對(duì)上述有序表成功查找的平均查找長(zhǎng)度。（1）原序列1615205364715 16 2053 7 64 n-1 趟15 16 207 53 64 n-j次15 16 7 20 53 6471516205364⑵⑵（3）平均查找長(zhǎng)度=（1*1+2*2+3*3）/6=14/6題目43如下是一棵二叉排序樹(shù)，A1