1、單元測驗10一.判斷題(下列各題，正確的請在前面的括號內打，；錯誤的打X )(義)(1)如果某種排序算法不穩定，則該排序方法就沒有實用價值。(，)(2)希爾排序是不穩定的排序。(義)(3)冒泡排序是不穩定的排序。(，)(4)對n個記錄的進行快速排序，所需要的平均時間是O(nlog 2n)。(義)(5)堆排序所需的時間與待排序的記錄個數無關。(，)(6)當待排序的元素個數很多時，為了交換元素的位置要占用較多的時間，這是影響時間復 雜度的主要因素。(義)(7)快速排序在 任何情況 下都比其它排序方法速度快。(，)(8)對快速排序來說，初始序列為正序或反序都是最壞情況。(，)(9)采用歸并排序可以實

2、現外排序。(，)(10)采用希爾方法排序時，若關鍵字的排列雜亂無序，則效率最高。二.填空題(1)大多數排序算法都有兩個基本的操作:比較 和移動。(2) 評價排序算法優劣的主要標準是時間復雜度和算法所需的附加空間。(3) 根據被處理的數據在計算機中使用不同的存儲設備，排序可分為：內排序 和外排序。(4) 外排序是指在排序過程中，數據的主要部分存放在計算機的外存 中。(5) 對n個關鍵字進行冒泡排序，其可能的最小比較次數為：n-1 次。(6) 在最壞情況下，在第i趟直接插入排序中，要進行 上次關鍵字的比較。(7) 對n個關鍵字進行冒泡排序，時間復雜度為O(n 2)(8) 快速排序在最壞情況下的時間

3、復雜度是O(n 2)。O(log2n)O(n) 。不變的排序方法,稱為穩插入排序 較好。(9) 對于n個記錄的集合進行歸并排序，所需要的平均時間為：(10) 對于n個記錄的集合進行歸并排序，所需要的附加空間是(11) 若原始數據接近無序，則選用快速排序最好。(12) 在排序前，關鍵字值相等的不同記錄，排序后相對位置保持 定排序方法。(13)在插入排序和選擇排序中，若初始數據基本正序，則選用(14)當增量為1時，該趟希爾排序與直接插入排序基本一致。(15)第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是冒泡排序。(16)依次將每個記錄插入到一個有序的子文件中的排序方法稱為直接插入排序。(

4、17)在插入排序、選擇排序和歸并排序中，排序是不穩定的為：選擇排序。(18)在對一組記錄(54, 38, 96, 23, 15, 72, 60, 45, 83)進行直接插入排序時，當把第 7個記錄60插入到有序表時，為尋找插入位置需比較工次。(19)兩個序列分別為:L1=25 , 57, 48, 37, 92, 86, 12, 33L2=25 , 37, 33, 12, 48, 57, 86, 92。用冒泡排序法對L1和L2進行排序，交換次數較少的是序列：L2 。(20)對一組記錄(54, 35, 96, 21, 12, 72, 60, 44, 80)進行直接選擇排序時，第四次選擇和 交換后，

5、未排序記錄是54 , 72, 60, 96, 80 。三.選擇題(1)排序是根據(A )的大小重新安排各元素的順序。A .關鍵字 B .數組 C .元素件 D .結點(2)評價排序算法好壞的標準主要是( D )。A.執行時間B.輔助空間C.算法本身的復雜度D.執行時間和所需的輔助空間(3)直接插入排序的方法是( B )的排序方法。A .不穩定 B .穩定 C .外部 D .選擇(4)直接插入排序的方法要求被排序的數據( B )存儲。A .必須鏈表B .必須順序C.順序或鏈表D .可以任意(5)排序方法中，從無序序列中選擇關鍵字最小的記錄，將其與無序區(初始為空)的第一個記錄交換的排序方法，稱為

6、 (D )。A .希爾排序 B.歸并排序C.插入排序D.選擇排序(6)每次把待排序方的區間劃分為左、右兩個區間，其中左區間中元素的值不大于基準元素的值，右區間中元素的值不小于基準元素的值，此種排序方法叫做( C )。A.冒泡排序B .堆排序 C.快速排序D.歸并排序(7)快速排序在(C )情況下最易發揮其長處。A.待排序的數據中含有多個相同的關鍵字B.待排序的數據已基本有序C.待排序的數據完全無序D .待排序的數據中最大值與最小值相差懸殊(8)下述幾種排序方法中，要求內存量最大的是：( D )。A .插入排序B .選擇排序C.快速排序D.歸并排序(9)直接插入排序的方法是從第( B )個元素開

7、始，插入到前邊適當位置的排序方法。A . 1B. 2 C. 3 D. n(10)堆的形狀是一棵(C )。A.二叉排序樹B .滿二叉樹C .完全二叉樹D .平衡二叉樹(11)內排序是指在排序的整個過程中，全部數據都在計算機的( A )中完成的排序。A .內存 B .外存 C .內存和外存D .寄存器(12)快速排序的方法是( A )的排序方法。A .不穩定 B .穩定 C .外部 D .選擇(13)下列排序方法中，關鍵字比較次數與記錄的初始排列次序無關的是(A )。A.選擇排序B.希爾排序C.插入排序D.冒泡排序(14)下述幾種排序方法中，平均時間復雜度最小的是( A )。B ）。A.希爾排序B

8、.插入排序C.冒泡排序D.選擇排序(15)對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是A. O(n).。(").O(nlog 2n).。.)(16)冒泡排序的方法對n個數據進行排序，第一趟排序共需要比較(C )次。(17)對n個不同的排序碼進行冒泡(遞增)排序，在下列(A.從小到大排列好的 B.從大到小排列好的 C.元素無序)情況比較的次數最多。D .元素基本有序(18)用直接插入排序法對下面的四個序列進行由小到大的排序,元素比較次數最少的是(B )。A , 94, 32, 40, 90, 80, 46, 21, 69 B.21, 3246, 40, 80, 69,

9、90, 94C . 32, 40, 21, 46, 69, 94, 90, 80 D(19) 一組記錄的排序碼為(25, 48, 16, 35, 79按歸并排序的方法對該序列進行一趟歸并后的結果為：.90, 6980, 46, 21, 32, 94, 4082, 23, 40),其中含有4個長度為2的有序表,A , 16 25 35 48 23 40 79 82 36 72.16 25 35 48 79 82 23 36 40 72C . 16 25 48 35 79 82 23 36 40 72.16 25 35 48 79 23 36 40 72 82(20) 一個數據序列的關鍵字為：基準

10、得到第一次劃分的結果為：(467956,38,40,84),采用快速排序，并以第一個數為A. ( 38, 40, 46567984)(403846, 79,56, 84).( 40, 38, 46567984)(403846, 79,56, 84)四.1 .解：排序過程分析已知數據序列101088,第一趟結束時結果: 第二趟結束時結果: 第三趟結束時結果: 第四趟結束時結果: 第五趟結束時結果:18 8 8 8 7 7181510101071815, 7161518151010151815152 .已知數據序列18, 17,60,4016,寫出采用直接插入算法排序時,每一趟排序的結果。1616

11、16序的結果。解：181760 40181616180732,73, 65,寫出采用直接插入算法排序時，每一趟排07 32 73 65第一趟結束時結果 第二趟結束時結果 第三趟結束時結果 第四趟結束時結果 第五趟結束時結果 第六趟結束時結果 第七趟結束時結果3 .已知數據序列1717170707070718 60 40 0718181717171760 40 07401818181817 , 18, 60,60 07403232326032327373656532327373656540 607340 60 73656540 60 65 7340, 7, 32, 73, 65, 85請寫出采用

12、冒泡排序法對該序列作升序排序時每一趟的結果。解：17 18 60 40 7 32 73 65 85第一趟排序結果：17 18 40 7 32 60 65 73 85第二趟排序結果：17 18 7 32 40 60 65 73第三趟排序結果：17 71832406065口第四趟排序結果：7 1718324060第五趟排序結果：7 17183240J第五趟排序過程中已無記錄交換，排序結束。4 . 已知數據序列80, 18, 9, 90, 27, 75, 42, 69, 34 請寫出采用冒泡排序法對該序列作升序排序時每一趟的結果。解：80 18 09 90 27 75 42 69 34第一趟排序結果

13、：1809802775426934 90|第二趟排序結果：0918277542693480第三趟排序結果：09 18 27 42 69 34 75 匚第四趟排序結果：091827423469第五趟排序結果：0918273440|第六趟排序結果：09 18 27 34第六趟排序過程中已無記錄交換，排序結束。5 .已知數據序列10,18,4, 3, 6,12,9,15,8,寫出希爾排序每一趟（設 d=4、2、1）排序的結果。解：10 18 4 3 6 12 9 15 8d=46 12 4 3 8 18 9 15 10d=24 3 6 12 8 15 9 18 10d=13 4 6 8 9 10 1

14、2 15 186 .已知數據序列12, 02, 16, 30, 28, 10, 17, 20, 06, 18,寫出希爾排序每一趟排序的結果。（設 d=5、2、1）解： 12 02 16 30 28 10 17 20 06 18d=510021606181217203028I|I|J|Id=2 Illi12021606171218203028I I I I I I I I I Id=102 06 10 12 16 17 18 20 28 307 .已知數據序列10, 18, 4, 3, 6, 12, 9, 15,寫出二路歸并排序的每一趟排序結果。10 18 4 3 6 12 9 15I I I

15、I I I|10 18 3 4 6 12 9 15第一趟排序結果3 4 10 18 61215第二趟排序結果3 4 6 9 10121518第三趟排序結果8.解:已知數據序列53364836, 60, 718, 41,寫出采用簡單選擇排序的每一趟排序結果。53 36 48 36 60 7 18 41(7)(7(7(7(7(7(7(736 4818)184836369.解10.解:7五.181818181836)36363636364836)36363636已知數據序列10 1 low7 1low101515第一趟排序結果:1,已知數據序列106060605353531836366041)535

16、341414115,48)4848485353)414141416060604818,15 high53 60 )7, 15,試畫出采用快速排序法，第一趟排序的結果。交換¥ 10 15 *1 jhigh>T IIt交換7 1 10 18 15 15 high J .low1, 1518, 7, 15,試寫出采用快速排序法，第一趟排序的結果。1 10 18 15 15二分插入排序程序填空void BInsSort()/按遞增序對R1R n 進行二分插入排序 int i, j, low, high, m;for ( i=2; i<=n ; i+) R0=Ri;/設定R0為監視

17、哨low=1;high=while (low<=high)m=(low+high)/2 ;if ( R0<Rm)high=m-1 ;elselow=m+1; for (j=i-1;j>=high+1;j-)元素后移插入Rl+1= R j /Rhigh=R0;/ 六.算法題1 .以單鏈表為存儲結構，寫一個直接選擇排序算法。 解： void selectsort(pointer h) pointer p,q,r,s,t;t=NULL; while(h) p=h; q=NULL;s=h; r=NULL; while (p) if (p->key<s->key) s

18、=p； p=q； if (s=h)h=h->link; else h=s;s->link=t; t=s; h=t; 2 .以單鏈表作為存儲結構實現直接插入排序算法。 解： void InsertList(List head) Lnode *p, * pprev , q,*qprev, *current; if (!head)return;pprev=head;p=head->next;查找插入位置最大，無須插入while (p) q=head; qprev=NULL; while (q->key < p->key) / qprev=q; q=q->ne

19、xt; if (q= =p)/ p插在表頭插在中間某個位置上初、終下標自右向左找非負 數/ 自左向右找負 數pprev=p; p=p->next; else current=p; p=p->next;pprev->next=p;current->next=q;if (q=head)/head=current;else/qprev->next=current;3設計一個算法，使得在盡可能少的時間內重排數組，將所有取負值的關鍵字放在所有取非負值的 關鍵字之前。解： void part (int a ) i=1;j=n;/while (i<j) while (i&

20、lt;j && aj>=0)/j-;while (i<j && ai<0) i+;if (i<j) t=ai;ai=aj;aj=t;i+;j-; 4設已排序的文件用單鏈表表示，再插入一個新記錄，仍然按關鍵字從小到大的次序排序，試寫出該算法。void insert(lklist head;datatype x)s=new ( node );s->key=x;s->next= NULL;if (head= =NULL)head=s;else p=head;q= NULL;while ( p! =NULL) && (

21、s->key > p->key ) q=p; p=p->next; if (q= =NULL) s->next=head; head=s; else if (p=NULL)q->next=s;else s->next=q->next; q->next=s; 排序過程分析1 .果。解:已知數據序列50,60,40, 20,80, 15, 10, 45,試畫出采用快速排序法，第一趟排序的結2.45 , 10, 40已知數據序列20,1550 80，6082,40,66, 13,84, 36, 96, 57, 39, 80, 61, 14,寫出二

22、路歸并排序的每一趟排序結果。解：82 40 66 13 84 36 96 57 39 80 61 14結果。解：40 63 11 843593 58 394.解:(11)(11(11(11(11(11(11(11(1163 40 8415)15151515151515359315583940 8435)3535358439)3939353535393939已知數據序列18 ,18 17 6035404040)4040404017,9393939358)5858585893393984848458585860,63)636340,40 07 32 738484)15636363636393938

23、4 93)07, 32, 73, 65,寫出采用冒泡排序法每一趟排序的結果。654082 1366 3684 5796 3980 1461A趟排序結果1340 6682 36578496 1439 6180第二趟排序結果1336 4057 66828496 1439 6180第三趟排序結果1314 3639 40576166 8082 8496第四趟排序結果3.已知數據序列40,63,11, 84，35,93, 58,39, 15,寫出采用簡單選擇排序的每一趟排序第一趟結束時結果：17 18 40 07 32 60 65 73 匚第二趟結束時結果：17 18 07 32 40 60 65第三趟

24、結束時結果：1707183240601第四趟結束時結果：0717183240 U第五趟結束時結果：07171832已無交換，結束。5 .已知數據序列10 , 18, 14, 13, 16, 12, 11, 9, 15, 08,寫出希爾排序每一趟排序的結果（設 d=5、 2、 1）。解： 10 18 14 13 16 12 11 09 15 08d=510 11 09 13 08 12 18 14 15 16d=208 110912101315141816口 IIII I IIId=108 09 10 11 12 13 14 15 16 186 .已知數據序列39, 28, 55, 80, 75

25、, 06, 17, 45,寫出采用直接插入算法排序時，每一趟排 序的結果。解： 39第一趟結束時結果: 第二趟結束時結果: 第三趟結束時結果: 第四趟結束時結果: 第五趟結束時結果: 第六趟結束時結果: 第七趟結束時結果:2855 80 75 06 17 4528 39 55 80 75 0628 39 55 80 75 0617 4517 4528 39 55 80 07 32 73 6507 2839558032736507 2832395580736507 2832395573806507 28323955657380程序填空1 .設表的長度為L,試填空完成直接插入排序程序。void i

26、nsertsort(int R)/按遞增序對R1R n 進行直接插入排序 int i,j;for ( i=2; i<=L ; i+ ) R0=Ri;/設定R0為監視哨j=i-1while (R0<_Rj)Rj+1=Rjj-;Rj+1=R0/插入第i個記錄2.直接選擇排序void selectsort ( )/ int i, j, k ；for (i=1;i<= n ;i+) k=i ；for (j=i+1 J<=n;j+)/if (Rj<Rk)k=j；if (! k=j ) R0=R i ；/Ri = Rk； Rk=R0；按遞增序對R1 Rn進行直接選擇排序選擇選擇關鍵字最小的記錄交換關鍵字3.二分插入排序void BInsSort( )/ int i, j, low, high, m;for ( i=2; i<= n ; i+) R0=Ri；/low=1;high= n ;while (low