1、數據結構課程（本科）第九章試題、單項選擇題1. 若待排序對象序列在排序前已按其排序碼遞增順序排列，則采用（）方法比較次數最少。A. 直接插入排序B.快速排序C. 歸并排序D.直接選擇排序2. 如果只想得到1024 個元素組成的序列中的前5 個最小元素，那么用（）方法最快。A. 起泡排序B.快速排序C. 直接選擇排序D.堆排序3. 對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是（） 。A. 直接選擇排序B.直接插入排序C. 快速排序D.起泡排序4. 對 5 個不同的數據元素進行直接插入排序，最多需要進行（

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

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

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

5、并排序C. 快速排序B. 希爾排序D.基數排序參考答案：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個元素組成的有序表中適當的位置，此種排序方法叫做排序。2 .第i （i = 0, 1,-2） 趟從參加排序的序列中第i個第n-1個元素中挑選出一個最小（大）元素，把它交換到第i 個位置，此種排序方法叫做排序。3 . 每次直接或通過基準元素間接比較兩個元素，若出現逆序排列，就交換它們的位置，這種排序方法

6、叫做 排序。4 . 每次使兩個相鄰的有序表合并成一個有序表，這種排序方法叫做排序。5 . 在直接選擇排序中，排序碼比較次數的時間復雜度為O（） 。6 . 在直接選擇排序中，數據對象移動次數的時間復雜度為O（） 。7 .在堆排序中，對n個對象建立初始堆需要調用 次調整算法。8 .在堆排序中，如果n個對象的初始堆已經建好，那么到排序結束，還需要從堆頂結點出發調用 次調整算法。9 .在堆排序中，對任一個分支結點進彳T調整運算的時間復雜度為0()。10 .對n個數據對象進行堆排序，總的時間復雜度為0()。11 .給定一組數據對象的排序碼為46, 79, 56, 38, 40, 84 ,則利用堆排序方法

7、建立的初始堆(最大堆)為12 .快速排序在平均情況下的時間復雜度為0()。13 .快速排序在最壞情況下的時間復雜度為0()。14 .快速排序在平均情況下的空間復雜度為0()。15 .快速排序在最壞情況下的空間復雜度為0()。16 .給定一組數據對象的排序碼為46, 79, 56, 38,40, 84,對其進行一趟快速排序，結果為 17 .在n個數據對象的二路歸并排序中，每趟歸并的時間復雜度為0()。18 .在n個數據對象的二路歸并排序中，整個歸并的時間復雜度為0()。參考答案：1.插入2.直接選擇3.交換4.兩路歸并5.n26.n7.|ln/2 _l8.n-19.log 2n10. nlog

8、2n13. n 216. 40 38 46 79 56 8411.84, 79, 56, 38, 40, 4614. log 2n17. n12. nlog 2n15. n18. nlog 2n三、判斷題1 .直接選擇排序是一種穩定的排序方法。2 .若將一批雜亂無章的數據按堆結構組織起來，則堆中各數據是否必然按自小到大的順序排列起來。3 .當輸入序列已經有序時，起泡排序需要的排序碼比較次數比快速排序要少。4 .在任何情況下，快速排序需要進行的排序碼比較的次數都是0(nlog2n)。5 .在2048個互不相同的排序碼中選擇最小的5個排序碼，用堆排序比用錦標賽排序更快。6 .若用m個初始歸并段參加

9、 k路平衡歸并排序，則歸并趟數應為log2m 7 .堆排序是一種穩定的排序算法。8 .對于某些輸入序列，起泡排序算法可以通過線性次數的排序碼比較且無需移動數據對象就可以完成排 序。9 .如果輸入序列已經排好序，則快速排序算法無需移動任何數據對象就可以完成排序。10 .希爾排序的最后一趟就是起泡排序。11 .任何基于排序碼比較的算法，對 n個數據對象進行排序時，最壞情況下的時間復雜度不會低于O(nlog 2n)o12 .不存在這樣一個基于排序碼比較的算法：它只通過不超過9次排序碼的比較，就可以對任何 6個排序碼互異的數據對象實現排序。參考答案：1.否 2.否 3.是 4.否 5.否6.否7.否

10、8.是 9.否 10.是11.是 12.是四、運算題1 .判斷以下序列是否是最小堆？如果不是，將它調整為最小堆。(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 。2 .在不要求完全排序時，堆排序是一種高效的算法。這種算法的過程是：(Heapification )把待排序序列看作一棵完全二叉樹，通過反復篩選將其調整為堆；(Re-heapification )依次取出堆頂，然后將剩余的記錄重新調整為堆。現考慮序列 A = 23, 41, 7, 5, 56 :(1)給出對應于

11、序列 A的最小堆Ha (以線性數組表示)；(2)給出第一次取出堆頂后，重新調整Ha后的結果(以線性數組表示)；(3)給出第二次取出堆頂后，重新調整Ha后的結果(以線性數組表示)。3 .希爾排序、直接選擇排序、快速排序和堆排序是不穩定的排序方法，試舉例說明。4 .給出12個初始歸并段，其長度分別為19, 22, 17, 16, 11, 10, 12, 32, 26, 20, 28, 07。現要做4路外歸并排序，試畫出表示歸并過程的最佳歸并樹，并計算該歸并樹的帶權路徑長度WPL。5 .設輸入文件包含以下數據對象的排序碼：14, 22, 7, 16, 11, 10, 12, 90, 26, 30,

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

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

14、趟可以完成排序？如果限定這個趟數，可取的最低路數是多少？參考答案：1. (1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 為最大堆。調整為最小堆后為 21,35, 39, 57, 86, 48, 42, 73, 66, 100 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 不是最小堆。調整為最小堆后為 12, 24, 33, 65, 33, 56, 48, 92, 86, 70 2.(1)建堆結果(2)(3)Ha =5 23 7 41 56A次取出堆頂，并重新調整后Ha =7 23 56 41第二次取出堆頂，并重新調

15、整后Ha = 23 41563.(1)希爾排序 512275275*061 2 275*061512275 1 061275*275512 (2)直接選擇排序 275275*512061i =1 061275*512275 i =2 061275*512275 i =3 061275*275512 (3)快速排序 512275275* 275*275512 (4)堆排序 275275*061170 已經是最大堆，交換 275與170 170275*061275刈刖3個調整 275*170061275 前3個最大堆,交換 275*上0 0614. 061170275*275 對前2個調整 170

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

17、 22, 17, 16, 11, 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, 011選擇16,輸出16, 門檻16,置換1232, 26, 20, 28, 0719, 22, 1 團12, 1011, 16選擇17,輸出17, 門檻17,置換3226, 20, 28, 07回 22, 32, 12, 1011, 16, 17選擇19,輸出19, 門檻19,置換2620, 28, 07

18、26,困 32, 12, 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, 32Jl2, 1011, 16, 17, 19, 22, 26, 28選擇32,輸出32, 門檻32,無輸入07, 20, 12, 1011, 16, 17, 19, 22, 26, 28,32無大于門檻的對象， 輸出段結束符8歷20, 12,

19、1011, 16, 17, 19, 22, 26, 28,32, 8選擇07,輸出07, 門檻07,無輸入一, 20, 一, 12, 10|07選擇10,輸出10, 門檻10,無輸入一, 20, 一, 12,| 一07, 10選擇12,輸出12, 門檻12,無輸入一,20,| 一,一,一07, 10, 12選擇20,輸出20, 門檻20,無輸入, , , ,07, 10, 12, 20無大于門檻的對象， 輸出段結束符807, 10, 12, 20,8結束6. 生成初始歸并段的過程輸入文件InFile內存工作區儲備庫輸出文件OutFile動作19, 22, 17, 16, 11,10,12, 3

20、2, 26, 20,28, 07輸入5個排序碼10, 12, 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

21、, 16, 17, 19選擇22,輸出22, 門檻22,暫存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無大于門檻的對象， 輸出段結束符8將暫存區內容傳送到內 存工作區10, 12, 20

22、, |。7,-11, 16, 17, 19, 22,26, 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無大于門檻的對象， 輸出段結束符807, 10, 12, 20,8結束45007. (1)文件有4500個記錄，計算機中用于排序的內存區可容納450個記錄，可建立的初始歸并段有/ 450 = 10個。每個初始歸并段中有 450個記錄，存于450/ 75

23、= 6個頁塊中。(2)內存區可容納6個頁塊，可建立6個緩沖區，其中5個緩沖區用于輸入，1個緩沖區用于輸出，因 此，可采用5路歸并。歸并過程如下：450450450450450450450450450450則則皿則皿皿則皿皿岫'lf !4500IIIIIIIIIIIIIIIIIIIIIIIIIIIIH共做了 2趟歸并，每趟需要讀 60個磁盤頁塊，寫出 60個磁盤頁塊。8. (1)設歸并路數為k,初始歸并段個數 m = 80,根據歸并趟數計算公式S = logkm = logk80l = 3得:k3>80o由此解得k>5,即應取的歸并路數至少為5。(2)設多路歸并的歸并路數為

24、k,需要k個輸入緩沖區和1個輸出緩沖區。1個緩沖區對應1個文件, 有k +1 = 15 ,因此k = 14 ,可做14路歸并。由S = 一logkm = _ 10g1480= 2。即至少需2趟歸并可完成 排序。若限定這個趟數，由 S = logk80l = 2,有80<k2,可取的最低路數為 9。即要在2趟內完成排序，進 行9路排序即可。五、算法分析題1 .給出下面main ()函數的執行結果：/ Sorry, no comments available:/ Try to read & understand following lines by yourself/# includ

25、e <stdio.h>void Exchange ( int s , int i, int j ) int temp = si; si = sj ; 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)

26、;Exchange ( seq, low, pivotpos );for ( i = 0; i < low ; i+ ) printf ( "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")

27、;return pivotpos;void main ( ) int testSeq12 = 57, 37, 17, 42, 61,27, 84, 06, 19, 59, 93, 23 ;Partition (testSeq, 0, 11);Partition (testSeq, 0, 6);Partition (testSeq, 8, 11); 2 .本題給出一個施加于鏈表的選擇排序的算法。算法中用到一個臨時的表頭結點head,作為結果鏈表的表頭結點，每次從first鏈上摘下值最大的結點current鏈入head之后。算法結束前，將 head刪除。template < classT&g

28、t;void LinkList<T> : ListSelectSort ( ) LinkNode<T> * head = new ListNode<T> , * current, * pre, * p, * q ;int i = 0;while ( CD ) 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)

29、;elsepre->link = current ->link ;if ( !i ) last = current ;i+ ；current->link = head -> link; first = head -> link; delete head;(1)請將缺失的語句部分補上；(2)設待排序的對象個數n = 7,當排序前各對象排序碼的初始鏈接順序為40, 20, 60, 30, 70, 50, 80 ,試根據上述算法，畫出每一趟排序時各結點指針的變化。3 . 下面給出一個排序算法，它屬于數據表類的成員函數，其中currentSize 是數據表實例的當前長度，

30、Vector 是存放數據表元素的一維數組。template <class T>void dataList<T> : unknown ( ) 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

31、 = V ectorj ;else break;Vectorj+1 = temp ;(1) 該算法執行什么功能？(2) 針對有 n 個數據對象的待排序的數據表，算法的排序碼比較次數和對象移動次數最好是多少？最壞是多少？4 . 下面給出一個排序算法，它屬于數據表類的成員函數，其中currentSize 是數據表實例的當前長度，Vector 是存放數據表元素的一維數組。template <class T>void dataList<T> : unknown ( ) T temp;int i , j, d, n = currentSize ;for ( d = n/2 ; d

32、 >= 1 ; d /= 2 )/按不同增量劃分子序列for ( i = d ; i < n ; i+ ) /對子序列執行直接插入排序temp = Vectori;for ( j = i - d; j >= 0 ; j - = d )if ( temp.key < Vectorj.key ) Vectorj+d = Vectorj ;else break;Vectorj+d = temp ;(1) 該算法執行什么功能？(2) 針對一組輸入實例35, 67, 18, 29, 53, 44, 09, 21 ，畫出每一趟排序過程。5 . 下面給出一個排序算法，它屬于數據表類的

33、成員函數，其中currentSize 是數據表實例的當前長度，Vector 是存放數據表元素的一維數組。template <class T>void dataList<T> : unknown ( int left, int right ) /對當前排序區間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 &

34、gt; pivot.key ); if ( i < j ) 交換 Vectori和 Vectorj的值T temp = Vectori ; Vectori = Vectorj ; Vectorj = temp ; while ( i < j );Vectorleft = Vectorj ; Vectorj = pivot ;if ( left < j -1 ) unknown ( left , j-1 ); 遞歸處理左區間 if ( j+1 < right ) unknown ( j+1, right ); 遞歸處理右區間 (1)該算法的功能是什么？(2)以下面給出的待

35、排序的數據序列為例，畫出每次遞歸執行時的結果序列。 45 48 18 36 72 30 53 15 29 6 .下面給出一個排序算法，它屬于數據表類的成員函數，其中 currentSize是數據表實例的當前長度， Vector是存放數據表元素的一維數組。template < class T>void dataList<Type> : unknown ( ) int low = 0, high = CurrentSize -1, i, j; int exchange;while ( low < high ) 當比較范圍多于一個對象時排序j = low ;記憶元素交換

36、位置for ( i = low ; i < high ; i+ )if ( Vectori.key > Vectori+1.key ) T temp = Vectori;Vectori = Vectori+1;Vectori+1 = temp;j = i;記憶右邊最后發生交換的位置j high = j;比較范圍上界縮小到j (0)該算法的功能是什么？(1)給出待排序數據序列為10, 20, 30, 40, 50, 60 和60, 50,40, 30, 20,10 ,畫出每次執行時的結果序列。7 .下面的程序是一個的兩路歸并算法merge,只需要一個附加存儲。設算法中參加歸并的兩個歸

37、并段是Aleft 3mid和Amid -Aright,歸并后結果歸并段放在原地。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 <= righ

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

39、t ->link head-> link = current(2)變化過程first40206030705080pre cureentfirst402060307050head80cureentfirst4020603050prehead7080first40203050pre cureenthead607080pre cureentfirst402030head50607080first2030pre cureenthead4050607080pre cureentfirst20head304050607080first20304050607080first3.算法功能及執行效率

40、(1)該算法的功能是直接插入排序。(2)在最好情況下，即所有待排序數據對象已經有序排序時，排序碼比較次數為n-1,數據移動次數為0。在最壞情況下，即所有待排序數據對象全部逆序排序，排序碼比較次數和數據移動次數分別為pre cureenthead20304050607080排序碼比較次數nfinnn二1),數據移動次數 £(i +2)=(n+4g1)ii 224.算法功能及執行實例的結果(0)該算法的功能是希爾排序。(2)輸入實例為 35, 67, 18, 29, 53, 44, 09, 21 時，每一趟排序過程如下:初始排列3567182953440921增量i = 13544092

41、1536718294i = 209211829354453672i = 3091821293544536715.算法功能及執行實例的結果(1)該算法的功能是遞歸的快速排序。(2)輸入實例為 45 48 18 36 72 30 53 15 29 時，遞歸執行的結果如下:初始排列454818367230531529 i = 12915183630 45537248 i = 21815 293630 45537248 i = 31518293630 45537248 i = 4151829303645537248 i = 51518293036454853726.算法功能及執行實例的結果(1)該算法

42、的功能是起泡排序。(2)給出待排序數據序列為10, 20, 30, 40, 50, 60時的執行結果初始排列102030405060lowhighi = 1n0500對于給定待排序數據序列60, 50,40, 30, 20, 10時每次執行時的結果初始排列605040302010lowhighn05i = 1504030201060nn04i = 2403020105060nn03i = 3302010405060nn02i = 4201030405060nn01i = 510203040506000j數組A每次執行最外層循環后數組的變化如下:leftmidmid+1rightA01234te

43、mp567i=012 , 28 十35_42 十 67_093170Ai > Amid+1i=10912354267316770記錄移動8次Ai <Amid+128記錄移動0次i=209123542316770Ai <Amid+128記錄移動0次i=30912 2835 _ 42a * 316770Ai > Amid+11記錄移動4次i=40912 28313542426770Ai <Amid+1記錄移動0次六、算法設計題1. 有一種簡單的排序算法，叫做計數排序(count Sorting ) 。這種排序算法對一個待排序的表(用數組表示)進行排序，并將排序結果存放

44、到另一個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同。計數排序算法針對表中的每個記錄，掃描待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小。假設針對某一個記錄，統計出的計數值為c,那么，這個記錄在新的有序表中的合適的存放位置即為c。(1) 給出適用于計數排序的數據表定義；(2) 使用 C+ 語言編寫實現計數排序的算法；2.試設計一個算法，使得在O(n)的時間內重排待排序表(用數組表示)中的數據對象，將所有取負值的排序碼排在所有取正值(非負值)的排序碼之前。(在寫算法之前首先用C+ 類定義數據表的結構)。參考答案：1. 計數排序(1) 數據表定義const int Def

45、aultSize = 100 ;template <class 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<