數(shù)據(jù)結(jié)構(gòu)課堂習(xí)題4

1、第10章 內(nèi)部排序第9章 排序選擇題1下列排序方法中，哪一種是穩(wěn)定的排序方法：(B)A）選擇排序 B ）歸并排序 C）快速排序 D）希爾排序2快速排序每次劃分的效果好壞和以下何種因素有直接關(guān)系：(C )A）關(guān)鍵字的排列情況 B）數(shù)據(jù)元素的個(gè)數(shù) C ）軸的相對(duì)大小 D）關(guān)鍵字值的最大值3對(duì)以下幾個(gè)關(guān)鍵字序列進(jìn)行快速排序，以第一個(gè)元素為軸，一次劃分效果最好的是：( c)A）1，2，3，4，5 B）2，1，3，4，5 C ）3，1，2，4，5 D）5，3，1，2，44對(duì)以下幾個(gè)關(guān)鍵字序列進(jìn)行快速排序，以第一個(gè)元素為軸，一次劃分效果不好的是：(D)A）4，1，2，3，6，5，7 B）4，3，1，7，6

2、，5，2C）4，2，1，3，6，7，5 D ）1，2，3，4，5，6，75設(shè)待排序數(shù)據(jù)元素序列為4，1，2，3 ，應(yīng)用一種排序方法進(jìn)行遞增序排序，已知一趟后的結(jié)果為1，2，3，4 ，則所選用的排序方法為：( C )A）直接插入 B）直接選擇 C ）冒泡（從前向后） D）C 冒泡（從后向前）6排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無關(guān)的是：(C )A）希爾排序 B）歸并排序(有關(guān)) C ）直接選擇排序 D）直接插入排序7下列字符序列中，不符合堆定義的為：(C)A）ACDGHMPQRXB）ACMDHPXGQR C）ADPRCQXMHGD）ADCMPGHXRQ三、填空題 1 排序是指將無序的數(shù)

3、據(jù)元素序列轉(zhuǎn)變成一個(gè)有序序列，把序列中的記錄，通過某些方法整理成按 關(guān)鍵字 遞增或遞減次序排列的處理過程。2 排序算法分成 內(nèi)部排序算法 和 外部排序算法 。3 排序算法的穩(wěn)定性是指 關(guān)鍵字值 相同的記錄經(jīng)過排序后的 相對(duì)位置 是否發(fā)生變化，永不發(fā)生變化的排序算法，就是 穩(wěn)定的 ；否則就是 不穩(wěn)定的 。4 排序算法的基本操作是 關(guān)鍵字的比較 和 關(guān)鍵字的移動(dòng) 。5 排序算法的 時(shí)間效率 取決于關(guān)鍵字的比較和記錄的移動(dòng)等基本操作的次數(shù)。1對(duì)插入、選擇、快速、和歸并四種排序算法，回答下列問題。）（1）在待排序的元素序列基本有序時(shí)，效率最高的排序方法是那一種？答：插入排序（2）排序要求內(nèi)存量最大的排

4、序方法是那一種？答：歸并排序（3）關(guān)鍵字比較次數(shù)與元素的初始排列次序無關(guān)的排序方法是那一種？答：選擇排序（4）寫出其中排序不穩(wěn)定的方法。答：選擇排序、快速排序2 設(shè)有6 0 0 0個(gè)無序的元素，若希望最快的選出前l(fā) 0個(gè)最大的元素，問在快速排序、堆排序、歸并排序、希爾排序中，采用那種算法最好?為什么?解答：雖然這些都是高速排序，但快速排序、歸并排序、希爾排序和基數(shù)排序都是排序結(jié)束后才能最后決定數(shù)據(jù)元素的個(gè)數(shù)的次序。而堆排序則是每次就取出一個(gè)最大的元素，只要10次就能取出10個(gè)最大的元素。因此堆排序最好。5、以關(guān)鍵字序列(265，301，751，129，937，863，742，694，076，4

5、38)為例，分別寫出執(zhí)行以下排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。(1) 直接插入排序 (2)希爾排序 (3)冒泡排序 (4)快速排序(5) 直接選擇排序 (6) 堆排序 (7) 歸并排序 上述方法中，哪些是穩(wěn)定的排序?哪些是非穩(wěn)定的排序?對(duì)不穩(wěn)定的排序試舉出一個(gè)不穩(wěn)定的實(shí)例。 n 答：(1)直接插入排序:(方括號(hào)表示無序區(qū))n 初始態(tài): 265 301 751 129 937 863 742 694 076 438n 第一趟：265 301 751 129 937 863 742 694 076 438n 第二趟：265 301 751 129 937 863 742 694 076

6、438n 第三趟：129 265 301 751 937 863 742 694 076 438n 第四趟：129 265 301 751 937 863 742 694 076 438n 第五趟：129 265 301 751 863 937 742 694 076 438n 第六趟：129 265 301 742 751 863 937 694 076 438n 第七趟：129 265 301 694 742 751 863 937 076 438n 第八趟：076 129 265 301 694 742 751 863 937 438n 第九趟：076 129 265 301 438 6

7、94 742 751 863 937 n -(2)希爾排序(增量為5，3，1)初始態(tài): 265 301 751 129 937 863 742 694 076 438第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 -3)冒泡排序(方括號(hào)為無序區(qū))初始態(tài) 265 301 751 129 937 863 742 694 076 438第一趟： 076 265 301 751 129 9

8、37 863 742 694 438第二趟： 076 129 265 301 751 438 937 863 742 694第三趟： 076 129 265 301 438 694 751 937 863 742第四趟： 076 129 265 301 438 694 742 751 937 863第五趟： 076 129 265 301 438 694 742 751 863 937第六趟： 076 129 265 301 438 694 742 751 863 937快速排序：（方括號(hào)表示無序區(qū)，層表示對(duì)應(yīng)的遞歸樹的層數(shù)）初始態(tài)： 265 301 751 129 937 863 742 6

9、94 076 438第二層： 076 129 265 751 937 863 742 694 301 438第三層： 076 129 265 438 301 694 742 751 863 937第四層： 076 129 265 301 438 694 742 751 863 937第五層： 076 129 265 301 438 694 742 751 863 937第六層： 076 129 265 301 438 694 742 751 863 937-5）直接選擇排序：(方括號(hào)為無序區(qū))初始態(tài) 265 301 751 129 937 863 742 694 076 438第一趟： 076

10、 301 751 129 937 863 742 694 265 438第二趟： 076 129 751 301 937 863 742 694 265 438第三趟： 076 129 265 301 937 863 742 694 751 438第四趟： 076 129 265 301 937 863 742 694 751 438第五趟： 076 129 265 301 438 863 742 694 751 937第六趟： 076 129 265 301 438 694 742 751 863 937第七趟： 076 129 265 301 438 694 742 751 863 937

11、第八趟： 076 129 265 301 438 694 742 751 937 863第九趟： 076 129 265 301 438 694 742 751 863 937（6)堆排序：（通過畫二叉樹可以一步步得出排序結(jié)果）初始態(tài) 265 301 751 129 937 863 742 694 076 438建立初始堆：937 694 863 265 438 751 742 129 075 301第一次排序重建堆：863 694 751 765 438 301 742 129 075 937第二次排序重建堆：751 694 742 265 438 301 075 129 863 937第三

12、次排序重建堆：742 694 301 265 438 129 075 751 863 937第四次排序重建堆：694 438 301 265 075 129 742 751 863 937第五次排序重建堆：438 265 301 129 075 694 742 751 863 937第六次排序重建堆：301 265 075 129 438 694 742 751 863 937第七次排序重建堆：265 129 075 301 438 694 742 751 863 937第八次排序重建堆：129 075265 301 438 694 742 751 863 937第九次排序重建堆：075 12

13、9 265 301 438 694 742 751 863 937（7）歸并排序（為了表示方便，采用自底向上的歸并，方括號(hào)為有序區(qū)）初始態(tài)：265 301 751 129 937 863 742 694 076 438第一趟：265 301 129 751 863 937 694 742 076 438第二趟：129 265 301 751 694 742 863 937 076 438第三趟：129 265 301 694 742 751 863 937 076 438第四趟：076 129 265 301 438 694 742 751 863 937（8）基數(shù)排序（方括號(hào)內(nèi)表示一個(gè)箱子共

14、有10個(gè)箱子，箱號(hào)從0到9）初始態(tài) ：265 301 751 129 937 863 742 694 076 438第一趟： 301 751 742 863 694 265 076 937 438 129第二趟：301 129 937 438 742 751 863 265 076 694第三趟：075 129 265 301 438 694 742 751 863 937 在上面的排序方法中，直接插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定的，其他排序算法均是不穩(wěn)定的，現(xiàn)舉實(shí)例如下：以帶*號(hào)的表示區(qū)別。希爾排序：8,1,10,5,6,*8快速排序：2,*2,1直接選擇排序：2,*2,1堆排序

15、：2,*2,16 判別下列序列是否為堆(小根堆或大根堆)，若不是，則將其調(diào)整為堆：(1) (100,86,48,73,35,39,42,57,66,21);(2) (12,70,33,65,24,56,48,92,86,33);(3) (103,97,56,38,66,23,42,12,30,52,06,20);(4) (05,56,20,23,40,38,29,61,35,76,28,100).堆的性質(zhì)是：任一非葉結(jié)點(diǎn)上的關(guān)鍵字均不大于(或不小于)其孩子結(jié)點(diǎn)上的關(guān)鍵字。據(jù)此我們可以通過畫二叉樹來進(jìn)行判斷和調(diào)整：(1) 此序列是大根堆。(2) 此序列不是堆，經(jīng)調(diào)整后成為小根堆：(12，24，3

16、3，65，33，56，48，92，86，70)(3) 此序列是一大根堆。(4) 此序列不是堆，經(jīng)調(diào)整后成為小根堆：（05，23，20，35，28，38，29，61，56，76，40，100）8、設(shè)計(jì)一算法，使得在盡可能少的時(shí)間內(nèi)重排數(shù)組，將所有取負(fù)值的關(guān)鍵字放在所有取非負(fù)值的關(guān)鍵字之前。請(qǐng)分析算法的時(shí)間復(fù)雜度。 因?yàn)橹恍鑼⒇?fù)數(shù)關(guān)鍵字排在前面而無需進(jìn)行精確排列順序，因此本算法采用兩端掃描的方法，就象快速排序采用的方法一樣，左邊掃描到正數(shù)時(shí)停止，開始掃描右邊，遇到負(fù)數(shù)時(shí)與左邊的當(dāng)前記錄交換，如此交替進(jìn)行，一趟下來就可以完成排序。void ReSort(SeqList R)/重排數(shù)組，使負(fù)值關(guān)鍵字在前int i=1,j=n;/數(shù)