《數(shù)據(jù)結(jié)構(gòu)》習題匯編09-第九章-排序-試題

1、數(shù)據(jù)結(jié)構(gòu)課程（本科）第九章試題一、單項選擇題1. 若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排列，則采用（ ）方法比較次數(shù)最少。A.直接插入排序B.快速排序C.歸并排序D.直接選擇排序2. 如果只想得到 1024 個元素組成的序列中的前 5 個最小元素，那么用（ ）方法最快。A.起泡排序B.快速排序C.直接選擇排序D.堆排序3. 對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是（ ） 。A. 直接選擇排序B.直接插入排序C. 快速排序D.起泡排序4. 對 5 個不同的數(shù)據(jù)元素進行直接插入排序，最多需要進

2、行（ ）次比較？A. 8B. 10C. 15D. 255. 如果輸入序列是已經(jīng)排好順序的，則下列算法中（）算法最快結(jié)束？A. 起泡排序B.直接插入排序C. 直接選擇排序D.快速排序6. 如果輸入序列是已經(jīng)排好順序的，則下列算法中（）算法最慢結(jié)束？A.起泡排序B.直接插入排序C.直接選擇排序D.快速排序7. 下列排序算法中（ ）算法是不穩(wěn)定的。A.起泡排序B.直接插入排序C.基數(shù)排序D.快速排序8. 假設某文件經(jīng)過內(nèi)部排序得到 100 個初始歸并段， 那么如果要求利用多路平衡歸并在3 趟內(nèi)完成排序，則應取的歸并路數(shù)至少是（ ）。A. 3B. 4C. 5D. 69. 采用任何基于排序碼比較的算法，

3、對5 個互異的整數(shù)進行排序，至少需要（ ）次比較。A. 5B. 6C. 7D. 810. 下列算法中（ ）算法不具有這樣的特性：對某些輸入序列，可能不需要移動數(shù)據(jù)對象即可完成排序。A. 起泡排序B. 希爾排序C. 快速排序D. 直接選擇排序11.使用遞歸的歸并排序算法時，為了保證排序過程的時間復雜度不超過A. 每次序列的劃分應該在線性時間內(nèi)完成B. 每次歸并的兩個子序列長度接近C. 每次歸并在線性時間內(nèi)完成D. 以上全是O(nlog 2n) ，必須做到()。12.在基于 排序碼 比較的排序算法中， (A. 起泡排序C. 歸并排序)算法的最壞情況下的時間復雜度不B.D.高于 O(nlog2n)。

4、希爾排序快速排序13. 在下列排序算法中， ( )算法使用的附加空間與輸入序列的長度及初始排列無關。A. 錦標賽排序B. 快速排序C. 基數(shù)排序D. 歸并排序14. 一個對象序列的排序碼為 46, 79, 56, 38, 40, 84 ，采用快速排序(以位于最左位置的對象為基準而) 得到的第一次劃分結(jié)果為：A. 38, 46, 79, 56, 40, 84 B. 38, 79, 56, 46, 40, 84 C. 40, 38, 46, 79, 56, 84 D. 38, 46, 56, 79, 40, 84 15. 如果將所有中國人按照生日 (不考慮年份， 只考慮月、 日) 來排序， 那么使

5、用下列排序算法中 ()算法最快。A. 歸并排序C. 快速排序B. 希爾排序D.基數(shù)排序參考答案：1. A2. D3. C4. B5. A6. D7. D8. C9. C10. C11. D12. C13. C14. C15. D二、填空題1. 第i(i = 1,2,，n1)趟從參加排序的序列中取出第i個元素，把它插入到由第0個第i-1個元素組成的有序表中適當?shù)奈恢?，此種排序方法叫做排序。2. 第i (i = 0, 1,-2) 趟從參加排序的序列中第i個第n-1個元素中挑選出一個最小(大)元素，把它交換到第i 個位置，此種排序方法叫做 排序。3. 每次直接或通過基準元素間接比較兩個元素，若出現(xiàn)逆

6、序排列，就交換它們的位置，這種排序方法叫做排序。4. 每次使兩個相鄰的有序表合并成一個有序表，這種排序方法叫做 排序。5. 在直接選擇排序中，排序碼比較次數(shù)的時間復雜度為 O() 。6. 在直接選擇排序中，數(shù)據(jù)對象移動次數(shù)的時間復雜度為 O() 。7. 在堆排序中，對n 個對象建立初始堆需要調(diào)用 次調(diào)整算法。8. 在堆排序中， 如果 n 個對象的初始堆已經(jīng)建好， 那么到排序結(jié)束， 還需要從堆頂結(jié)點出發(fā)調(diào)用 次調(diào)整算法。9. 在堆排序中，對任一個分支結(jié)點進行調(diào)整運算的時間復雜度為 O() 。10. 對 n 個數(shù)據(jù)對象進行堆排序，總的時間復雜度為 O() 。11. 給定一組數(shù)據(jù)對象的排序碼為 46

7、, 79, 56, 38, 40, 84 ，則利用堆排序方法建立的初始堆 (最大堆) 為16. 給定一組數(shù)據(jù)對象的排序碼為 46, 79, 56, 38, 40, 84 ，對其進行一趟快速排序，結(jié)果為 17. 在 n 個數(shù)據(jù)對象的二路歸并排序中，每趟歸并的時間復雜度為O() 。18. 在 n 個數(shù)據(jù)對象的二路歸并排序中，整個歸并的時間復雜度為O() 。參考答案： 1 . 插入 2. 直接選擇3. 交換4. 兩路歸并5. n 26. n7. n/28. n-19. log 2 n10. nlog2n11.84,79, 56, 38, 40, 4612.nlog 2n13. n 214.log2n

8、15.n16. 4038 46 79 56 8417.n18.nlog 2n三、判斷題1. 直接選擇排序是一種穩(wěn)定的排序方法。2. 若將一批雜亂無章的數(shù)據(jù)按堆結(jié)構(gòu)組織起來, 則堆中各數(shù)據(jù)是否必然按自小到大的順序排列起來。3. 當輸入序列已經(jīng)有序時，起泡排序需要的排序碼比較次數(shù)比快速排序要少。4. 在任何情況下，快速排序需要進行的排序碼比較的次數(shù)都是O(nlog2n)。5. 在 2048 個互不相同的排序碼中選擇最小的 5 個排序碼，用堆排序比用錦標賽排序更快。log2m 。6. 若用 m 個初始歸并段參加k 路平衡歸并排序，則歸并趟數(shù)應為7. 堆排序是一種穩(wěn)定的排序算法。8. 對于某些輸入序列

9、，起泡排序算法可以通過線性次數(shù)的排序碼比較且無需移動數(shù)據(jù)對象就可以完成排序。9. 如果輸入序列已經(jīng)排好序，則快速排序算法無需移動任何數(shù)據(jù)對象就可以完成排序。10. 希爾排序的最后一趟就是起泡排序。11. 任何基于排序碼比較的算法，對n 個數(shù)據(jù)對象進行排序時，最壞情況下的 時間 復雜度不會低于O(nlog 2n) 。12. 不存在這樣一個基于排序碼比較的算法：它只通過不超過9 次排序碼的比較，就可以對任何 6 個排序碼互異的數(shù)據(jù)對象實現(xiàn)排序。參考答案： 1. 否 2. 否3. 是 4. 否5. 否6. 否 7. 否8. 是9. 否10. 是11. 是 12. 是四、運算題1. 判斷以下序列是否是

10、最小堆？如果不是, 將它調(diào)整為最小堆。(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 。2. 在不要求完全排序時，堆排序是一種高效的算法。這種算法的過程是：( Heapification )把待排序序列看作一棵完全二叉樹，通過反復篩選將其調(diào)整為堆；( Re-heapification )依次取出堆頂，然后將剩余的記錄重新調(diào)整為堆?，F(xiàn)考慮序列 A = 23， 41， 7， 5， 56 ：(1) 給出對應于序列 A 的最小堆 HA (以線性數(shù)組表示)；(2) 給出第一次取出

11、堆頂后，重新調(diào)整HA 后的結(jié)果(以線性數(shù)組表示)；(3) 給出第二次取出堆頂后，重新調(diào)整HA 后的結(jié)果(以線性數(shù)組表示)。3. 希爾排序、直接選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法, 試舉例說明。4. 給出 12 個初始歸并段，其長度分別為 19, 22, 17, 16, 11, 10, 12, 32, 26, 20, 28, 07?，F(xiàn)要做4 路外歸并排序，試畫出表示歸并過程的最佳歸并樹，并計算該歸并樹的帶權(quán)路徑長度WPL 。5. 設輸入文件包含以下數(shù)據(jù)對象的排序碼： 14, 22, 7, 16, 11, 10, 12, 90, 26, 30, 28, 110 。 現(xiàn)采用置換選擇方法生成

12、初始歸并段，并假設內(nèi)存工作區(qū)可同時容納 5 個數(shù)據(jù)對象，請畫出 生成初始歸并段 的過程。6. 在利用置換選擇方法生成初始歸并段時，可另開辟一個與工作區(qū)容量相同的輔助存儲區(qū)(稱為儲備庫)。當輸入對象排序碼小于剛輸出的門檻LastKey 對象的排序碼時，不將它存入工作區(qū)，而暫存于儲備庫中，接著輸入下一對象的排序碼，依次類推，直到儲備庫滿時不再進行輸入，而只是從工作區(qū) 中選擇對象輸出直至工作區(qū)空為止，由此得到一個初始歸并段。然后再將儲備庫中的對象傳送至工作 區(qū)，重新開始置換一選擇。若設輸入文件包含對象的排序碼為19, 22, 17, 16, 11, 10, 12, 32, 26, 20, 28, 0

13、7 。采用上述方法生成初始歸并段，并設工作區(qū)可容納5個對象，請畫出生成初始歸并段的過程。7.假設文件有4500個記錄，在磁盤上每個頁塊可放75個記錄。計算機中用于排序的內(nèi)存區(qū)可容納450個記錄。試問：(1)可建立多少個初始歸并段？每個初始歸并段有多少記錄？存放于多少個頁塊中？(2)應采用幾路歸并？請寫出歸并過程及每趟需要讀寫磁盤的頁塊數(shù)。8.如果某個文件經(jīng)內(nèi)排序得到80個初始歸并段，試問(1)若使用多路歸并執(zhí)行 3趟完成排序，那么應取的歸并路數(shù)至少應為多少？(2)如果操作系統(tǒng)要求一個程序同時可用的輸入/輸出文件的總數(shù)不超過15個，則按多路歸并至少需要幾趟可以完成排序？如果限定這個趟數(shù)，可取的最

14、低路數(shù)是多少？參考答案：1. (1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 為最大堆。調(diào)整為最小堆后為 21,35, 39, 57, 86, 48, 42, 73, 66, 100 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 不是最小堆。調(diào)整為最小堆后為 12, 24, 33, 65, 33, 56, 48, 92, 86, 70 2. (1)建堆結(jié)果Ha =5 23 7 41 56(2)第一次取出堆頂，并重新調(diào)整后Ha =723 56 41(3)第二次取出堆頂，并重新調(diào)整后Ha = 23 41 563.(1)

15、希爾排序 512 275* 061275061275*275*512275061 275 512 21(2)直接選擇排序 275275*512061 i = 1 061275*512275 i = 2 061275*512275 i = 3 061275*275512 (3)快速排序 512275275* 275*275512 (4)堆排序 275275*061170 已經(jīng)是最大堆，交換 275與170 170275*061275對前3個調(diào)整 275*170061275 前3個最大堆,交換 275*與061 061170275*275 對前2個調(diào)整 170061275*275 前2個最大堆，交

16、換 170與061 061170275*275 設初始歸并段個數(shù) n = 12,外歸并路數(shù)k = 4,計算(n-1) % (k-1) = 11 % 3 =2 w 0,必須補 k-2-1 = 1個長度為0的空歸并段，才能構(gòu)造k路歸并樹。此時，歸并樹的內(nèi)結(jié)點應有(n-1+1)/(k-1) = 12/3 = 4 個。4.回區(qū)回回區(qū)回叵回回回回回畫WPL = (3+6+8)*3+(9+18+20+30+44+60+62)*2+(68+85)*1 = 51+ 486+153 = 6905.生成初始歸并段的過程輸入文件InFile內(nèi)存工作區(qū)輸出文件OutFile動作19, 22, 17, 16, 11,

17、10,12, 32, 26, 20, 28, 07輸入5個排序碼10, 12, 32, 26, 20, 28,0719, 22, 17, 16, 1匚選擇11,輸出11, 門檻11,置換1012, 32, 26, 20, 28, 0719, 22, 17, 167)011選擇16,輸出16, 門檻16,置換1232, 26, 20, 28, 0719, 22,伺|12, 1011, 16選擇17,輸出17, 門檻17,置換3226, 20, 28, 07回 22, 32, 12, 1011, 16, 17選擇19,輸出19, 門檻19,置換2620, 28, 0726, 227 32, 12,

18、 1011, 16, 17, 19選擇22,輸出22, 門檻22,置換2028, 07園 20, 32, 12, 1011, 16, 17, 19, 22選擇26,輸出26, 門檻26,置換2807困 20, 32, 12, 1011, 16, 17, 19, 22, 26選擇28,輸出28, 門檻28,置換0707, 20, 322112, 1011, 16, 17, 19, 22, 26, 28選擇32,輸出32, 門檻32,無輸入07, 20, 12, 1011, 16, 17, 19, 22, 26, 28,32無大于門檻的對象， 輸出段結(jié)束符8歷20, 12, 1011, 16, 1

19、7, 19, 22, 26, 28,32, 8選擇07,輸出07, 門檻07,無輸入,20,12,回07選擇10,輸出10, 門檻10,無輸入一,20,一,回一07, 10選擇12,輸出12, 門檻12,無輸入一,20一,一,一07, 10, 12選擇20,輸出20, 門檻20,無輸入, , , ,07, 10, 12, 20無大于門檻的對象， 輸出段結(jié)束符807, 10, 12, 20,8結(jié)束6. 生成初始歸并段的過程輸入文件InFile內(nèi)存工作區(qū)儲備庫輸出文件OutFile動作19, 22, 17, 16, 11,10,12, 32, 26, 20,28, 07輸入5個排序碼10, 12,

20、 32, 26, 20, 28, 0719, 22, 17,16, 11|11選擇11,輸出11, 門檻11,暫存1012, 32, 26, 20, 28, 0719, 22, 17,16 1011選擇16,輸出16, 門檻16,暫存1232, 26, 20, 28, 0719, 22,回 ,10, 1211, 16選擇17,輸出17, 門檻17,置換3226, 20, 28, 07匹22, 32, ,10, 1211, 16, 17選擇19,輸出19, 門檻19,置換2620, 28, 0726, 22, 32, ,10, 1211, 16, 17, 19選擇22,輸出22, 門檻22,暫存

21、2028, 07國,32,10, 12, 2011, 16, 17, 19, 22選擇26,輸出26, 門檻26,置換2807國,32,10, 12, 2011, 16, 17, 19, 22,26選擇28,輸出28, 門檻28,暫存07一,一,321 ,10, 12, 20,0711, 16, 17, 19, 22,26, 28選擇32,輸出32, 門檻32,無輸入,10, 12, 20,0711, 16, 17, 19, 22,26, 28, 32無大于門檻的對象， 輸出段結(jié)束符8將暫存區(qū)內(nèi)容傳送到內(nèi) 存工作區(qū)10, 12, 20, |。7,-11, 16, 17, 19, 22,26,

22、28, 32, 8選擇07,輸出07, 門檻07,無輸入園 12, 20, ,07選擇10,輸出10, 門檻10,無輸入,回 20,07, 10選擇12,輸出12, 門檻12,無輸入一,一,20 ,07, 10, 12選擇20,輸出20, 門檻20,無輸入,07, 10, 12, 20無大于門檻的對象， 輸出段結(jié)束符807, 10, 12, 20,8結(jié)束45007. (1)文件有4500個記錄，計算機中用于排序的內(nèi)存區(qū)可容納450個記錄，可建立的初始歸并段有/ 450 = 10個。每個初始歸并段中有 450個記錄，存于450/ 75 = 6個頁塊中。(2)內(nèi)存區(qū)可容納6個頁塊，可建立6個緩沖區(qū)

23、，其中5個緩沖區(qū)用于輸入，1個緩沖區(qū)用于輸出，因 此，可采用5路歸并。歸并過程如下：450450450450450450450450450450則以皿岫皿皿皿皿皿皿共做了 2趟歸并，每趟需要讀 60個磁盤頁塊，寫出 60個磁盤頁塊。8. (1)設歸并路數(shù)為k,初始歸并段個數(shù) m = 80,根據(jù)歸并趟數(shù)計算公式S = logkm = logk80 = 3得:k3>80o由此解得k>5,即應取的歸并路數(shù)至少為5。(2)設多路歸并的歸并路數(shù)為 k,需要k個輸入緩沖區(qū)和1個輸出緩沖區(qū)。1個緩沖區(qū)對應1個文件, 有k +1 = 15 ,因此k = 14 ,可做14路歸并。由S = logkm

24、 = 10g1480 = 2。即至少需2趟歸并可完成 排序。若限定這個趟數(shù)，由 S = 1ogk80 = 2,有80<k2,可取的最低路數(shù)為 9。即要在2趟內(nèi)完成排序，進 行9路排序即可。五、算法分析題1. 給出下面main ()函數(shù)的執(zhí)行結(jié)果：/ Sorry, no comments available:/ Try to read & understand following lines by yourself/#include <stdio.h>void Exchange ( int s , int i, int j ) int temp = si; si = s

25、j ; sj = temp ;int Partition ( int seq , int low, int high ) int pivotpos = low ;int pivot = seqlow;for ( int i = low+1 ; i <= high ; i+ )if ( seqi < pivot ) pivotpos+ ;if ( pivotpos != i ) Exchange ( seq, pivotpos, i);Exchange ( seq, low, pivotpos );for ( i = 0 ; i < low ; i+ ) printf ( &q

26、uot;t");for ( i = low ; i < pivotpos ; i+ ) printf ( "t%d" , seqi);printf ( "t%d" , seqpivotpos);for ( i = pivotpos+1 ; i <= high ; i+ ) printf ( "t%d" , seqi); printf ( "n");return pivotpos; void main ( ) int testSeq12 = 57, 37, 17, 42, 61,27, 84,

27、06, 19, 59, 93, 23 ;Partition (testSeq, 0, 11);Partition (testSeq, 0, 6);Partition (testSeq, 8, 11); 2. 本題給出一個施加于鏈表的選擇排序的算法。算法中用到一個臨時的表頭結(jié)點head,作為結(jié)果鏈表的表頭結(jié)點，每次從first鏈上摘下值最大的結(jié)點current鏈入head之后。算法結(jié)束前，將 head刪除。template <class T>void LinkList<T> 二 ListSelectSort ( ) LinkNode<T> * head = n

28、ew ListNode<T> , * current, * pre, * p, * q ;int i = 0; while ( ) p = current = first ; q = NULL ; while ( p != NULL ) if ( p-> data > (2) ) pre = q; current = p ; q = p; p = p-> link; if (current = first ) (3);else pre-> link = current -> link;if ( !i ) last = current ;i+;curre

29、nt-> link = head-> link; ;first = head -> link ; delete head;(1)請將缺失的語句部分補上；(2)設待排序的對象個數(shù)n = 7,當排序前各對象排序碼的初始鏈接順序為40, 20, 60, 30, 70, 50, 80 ,試根據(jù)上述算法，畫出每一趟排序時各結(jié)點指針的變化。3. 下面給出一個排序算法，它屬于數(shù)據(jù)表類的成員函數(shù)，其中 currentSize 是數(shù)據(jù)表實例的當前長度， Vector 是存放數(shù)據(jù)表元素的一維數(shù)組。template <class T>void dataList<T> : u

30、nknown ( ) T temp; int i, j, n = currentSize ;for ( i = 1 ; i < n ; i+ )if ( Vectori .key < Vectori - 1.key ) temp = Vectori ; Vectori = Vectori - 1;for ( j = i - 2; j >= 0 ; j- )if ( temp.key < Vectorj.key ) Vectorj+1 = V ectorj ;else break;Vectorj+1 = temp ;(1) 該算法執(zhí)行什么功能？(2) 針對有 n 個數(shù)據(jù)對

31、象的待排序的數(shù)據(jù)表，算法的排序碼比較次數(shù)和對象移動次數(shù)最好是多少？最壞是多少？4. 下面給出一個排序算法，它屬于數(shù)據(jù)表類的成員函數(shù)，其中 currentSize 是數(shù)據(jù)表實例的當前長度， Vector 是存放數(shù)據(jù)表元素的一維數(shù)組。template <class T>void dataList<T> : unknown ( ) T temp; int i , j , d, n = currentSize ;for ( d = n/2 ; d >= 1 ; d /= 2 )/按不同增量劃分子序列for ( i = d ; i < n ; i+ ) /對子序列執(zhí)行

32、直接插入排序temp = Vectori;for ( j = i - d; j >= 0 ; j - = d )if ( temp.key < Vectorj.key ) Vectorj+d = Vectorj ;else break;Vectorj+d = temp ;(1) 該算法執(zhí)行什么功能？(2) 針對一組輸入實例 35, 67, 18, 29, 53, 44, 09, 21 ，畫出每一趟排序過程。5. 下面給出一個排序算法，它屬于數(shù)據(jù)表類的成員函數(shù)，其中 currentSize 是數(shù)據(jù)表實例的當前長度， Vector 是存放數(shù)據(jù)表元素的一維數(shù)組。template <

33、class T>void dataList<T> : unknown ( int left , int right ) /對當前排序區(qū)間 left, right 進行排序int i = left, j = right +1 ;T pivot = Vectorleft ;/把基準元素的值暫存于 temp 中do do i+ ; while ( Vectori.key < pivot.key ) ;do j - ; while ( Vectorj.key > pivot.key ) ;if ( i < j ) /交換 Vectori 和 Vectorj 的值T

34、temp = Vectori ; Vectori = Vectorj ; Vectorj = temp ; while ( i < j ) ;Vectorleft = Vectorj ; Vectorj = pivot ;if ( left < j - 1 ) unknown ( left , j- 1 );/遞歸處理左區(qū)間if ( j+1 < right ) unknown ( j+1, right ) ;/遞歸處理右區(qū)間(1) 該算法的功能是什么？(2) 以下面給出的待排序的數(shù)據(jù)序列為例，畫出每次遞歸執(zhí)行時的結(jié)果序列。 45 48 18 36 72 30 53 15 29

35、 6. 下面給出一個排序算法，它屬于數(shù)據(jù)表類的成員函數(shù)，其中 currentSize 是數(shù)據(jù)表實例的當前長度， Vector 是存放數(shù)據(jù)表元素的一維數(shù)組。template <class T>void dataList<Type> : unknown ( ) int low = 0, high = CurrentSize -1, i, j ; int exchange;while ( low < high ) /當比較范圍多于一個對象時排序j = low ;/記憶元素交換位置for ( i = low ; i < high ; i+ )if ( Vectori

36、.key > Vectori+1.key ) T temp = Vectori;Vectori = Vectori+1;Vectori+1 = temp;j = i ;/記憶右邊最后發(fā)生交換的位置jhigh = j ;/比較范圍上界縮小到j(0) 該算法的功能是什么？(1) 給出待排序數(shù)據(jù)序列為 10, 20, 30, 40, 50, 60 和 60, 50,40, 30, 20, 10，畫出每次執(zhí)行時的結(jié)果 序列。7.下面的程序是一個的兩路歸并算法merge,只需要一個附加存儲。設算法中參加歸并的兩個歸并段是Aleft Amid 和 Amid Aright ，歸并后結(jié)果歸并段放在原地。

37、template <class T>void dataList<T > : merge ( int left, int mid, int right ) int i, j; T temp;for ( i = left; i <= mid ; i+ ) if (Ai > Amid+1 ) temp = Amid;for ( j = mid -1; j >= i ; j- ) Aj+1 = Aj;Ai = Amid+1;for ( j = mid+2 ; j <= right ; j+ )if (temp > Aj ) Aj -1 = Aj;e

38、lse break;Aj -1 = temp ;若A = 12, 28, 35, 42, 67, 9, 31,70 , left = 0 , mid = 4 , right = 7。寫出每次執(zhí)行算法最外層循環(huán)后數(shù)組 的變化，并給出每次執(zhí)行算法最外層循環(huán)時的數(shù)據(jù)記錄移動次數(shù)。參考答案：1 .輸出結(jié)果:233717422761957845993611917623273742615984932 .鏈接表上的直接選擇排序方法(1)缺失語句 first != NULL current-> datafirst = first -> linkhead-> link = current(2)

39、變化過程first40206030705080pre cureentfirst402060307050head80pre cureentfirst4020603050head7080first40203050pre cureenthead607080pre cureentfirst402030head50607080first2030pre cureenthead4050607080pre cureentfirst20head304050607080first20304050607080firstpre cureenthead203040506070803 .算法功能及執(zhí)行效率(1)該算法的功

40、能是直接插入排序。(2)在最好情況下，即所有待排序數(shù)據(jù)對象已經(jīng)有序排序時，排序碼比較次數(shù)為n-1,數(shù)據(jù)移動次數(shù)為0。在最壞情況下，即所有待排序數(shù)據(jù)對象全部逆序排序，排序碼比較次數(shù)和數(shù)據(jù)移動次數(shù)分別為n 1n 1排序碼比較次數(shù)i 口口，數(shù)據(jù)移動次數(shù)i 2 n 4 n 1i i2i i24 .算法功能及執(zhí)行實例的結(jié)果(0)該算法的功能是希爾排序。(2)輸入實例為35, 67, 18, 29, 53, 44, 09, 21 時，每一趟排序過程如下：初始排列3567182953440921i = 135440921536718294i = 209211829354453672i = 309182129

41、3544536715 .算法功能及執(zhí)行實例的結(jié)果(1)該算法的功能是遞歸的快速排序。(2)輸入實例為 45 48 18 36 72 30 53 15 29 時，遞歸執(zhí)行的結(jié)果如下:初始排列454818367230531529 i = 12915183630 45537248 i = 21815 293630 45537248 i = 31518293630 45537248 i = 4151829303645537248 i = 51518293036454853726 .算法功能及執(zhí)行實例的結(jié)果(1)該算法的功能是起泡排序。(2)給出待排序數(shù)據(jù)序列為10, 20, 30, 40, 50, 6

42、0時的執(zhí)行結(jié)果初始排列102030405060lowhighi = 1n0500對于給定待排序數(shù)據(jù)序列60, 50,40, 30, 20, 10時每次執(zhí)行時的結(jié)果初始排列605040302010lowhighn05i = 1504030201060nn04i = 2403020105060nn03i = 3302010405060儲n02i = 4201030405060nn01i = 510203040506000j數(shù)組A每次執(zhí)行最外層循環(huán)后數(shù)組的變化如下:leftmidmid+1rightA01234 temp567i=01J28 .35_42 r 6乙.093170 Ai > Am

43、id+1記錄移動8次i=10912354267316770 Ai <Amid+128記錄移動0次i=209123542316770 Ai <Amid+128記錄移動0次i=30912 2835 - 42_.316770 Ai > Amid+1記錄移動4次i=40912 28313542426770 Ai <Amid+1記錄移動0次六、算法設計題1. 有一種簡單的排序算法，叫做計數(shù)排序( count Sorting ) 。這種排序算法對一個待排序的表(用數(shù)組表示)進行排序，并將排序結(jié)果存放到另一個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同。計數(shù)排序算法針對表中

44、的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小。假設針對某一個記錄，統(tǒng)計出的計數(shù)值為 c ，那么，這個記錄在新的有序表中的合適的存放位置即為 c。(1) 給出適用于計數(shù)排序的數(shù)據(jù)表定義；(2) 使用 C+ 語言編寫實現(xiàn)計數(shù)排序的算法；2. 試設計一個算法, 使得在 O(n) 的時間內(nèi)重排待排序表(用數(shù)組表示)中的數(shù)據(jù)對象, 將所有取負值的排序碼排在所有取正值(非負值)的排序碼之前。 (在寫算法之前首先用 C+ 類定義數(shù)據(jù)表的結(jié)構(gòu))參考答案：1. 計數(shù)排序(1) 數(shù)據(jù)表定義const int DefaultSize = 100 ;template <clas

45、s T> class datalist;template <class T> class Element private:T Key ;Field otherdata;Public:T getKey() return key; void setKey ( const T x ) key = x; template <class T> class datalist public:datalist ( int MaxSz = DefaultSize ) : MaxSize (MaxSz) , CurrentSize(0) Vector = new Element<T> Ma