數(shù)據(jù)結(jié)構(gòu)單元練習(xí)10

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

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

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

4、17)在插入排序、選擇排序和歸并排序中，排序是不穩(wěn)定的為：選擇排序。(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進行排序，交換次數(shù)較少的是序列：L2 。(20)對一組記錄(54, 35, 96, 21, 12, 72, 60, 44, 80)進行直接選擇排序時，第四次選擇和 交換后，

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

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

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

8、.插入排序C.冒泡排序D.選擇排序(15)對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是A. O(n).。(").O(nlog 2n).。.)(16)冒泡排序的方法對n個數(shù)據(jù)進行排序，第一趟排序共需要比較(C )次。(17)對n個不同的排序碼進行冒泡(遞增)排序，在下列(A.從小到大排列好的 B.從大到小排列好的 C.元素?zé)o序)情況比較的次數(shù)最多。D .元素基本有序(18)用直接插入排序法對下面的四個序列進行由小到大的排序,元素比較次數(shù)最少的是(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按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為：.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) 一個數(shù)據(jù)序列的關(guān)鍵字為：基準

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

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

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

13、：1809802775426934 90|第二趟排序結(jié)果：0918277542693480第三趟排序結(jié)果：09 18 27 42 69 34 75 匚第四趟排序結(jié)果：091827423469第五趟排序結(jié)果：0918273440|第六趟排序結(jié)果：09 18 27 34第六趟排序過程中已無記錄交換，排序結(jié)束。5 .已知數(shù)據(jù)序列10,18,4, 3, 6,12,9,15,8,寫出希爾排序每一趟（設(shè) d=4、2、1）排序的結(jié)果。解：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 .已知數(shù)據(jù)序列12, 02, 16, 30, 28, 10, 17, 20, 06, 18,寫出希爾排序每一趟排序的結(jié)果。（設(shè) 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 .已知數(shù)據(jù)序列10, 18, 4, 3, 6, 12, 9, 15,寫出二路歸并排序的每一趟排序結(jié)果。10 18 4 3 6 12 9 15I I I

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

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

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 .以單鏈表為存儲結(jié)構(gòu)，寫一個直接選擇排序算法。 解： 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 .以單鏈表作為存儲結(jié)構(gòu)實現(xiàn)直接插入排序算法。 解： 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插在表頭插在中間某個位置上初、終下標自右向左找非負 數(shù)/ 自左向右找負 數(shù)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設(shè)計一個算法，使得在盡可能少的時間內(nèi)重排數(shù)組，將所有取負值的關(guān)鍵字放在所有取非負值的 關(guān)鍵字之前。解： 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設(shè)已排序的文件用單鏈表表示，再插入一個新記錄，仍然按關(guān)鍵字從小到大的次序排序，試寫出該算法。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 .果。解:已知數(shù)據(jù)序列50,60,40, 20,80, 15, 10, 45,試畫出采用快速排序法，第一趟排序的結(jié)2.45 , 10, 40已知數(shù)據(jù)序列20,1550 80，6082,40,66, 13,84, 36, 96, 57, 39, 80, 61, 14,寫出二

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

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

24、結(jié)束時結(jié)果：1707183240601第四趟結(jié)束時結(jié)果：0717183240 U第五趟結(jié)束時結(jié)果：07171832已無交換，結(jié)束。5 .已知數(shù)據(jù)序列10 , 18, 14, 13, 16, 12, 11, 9, 15, 08,寫出希爾排序每一趟排序的結(jié)果（設(shè) 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 .已知數(shù)據(jù)序列39, 28, 55, 80, 75

25、, 06, 17, 45,寫出采用直接插入算法排序時，每一趟排 序的結(jié)果。解： 39第一趟結(jié)束時結(jié)果: 第二趟結(jié)束時結(jié)果: 第三趟結(jié)束時結(jié)果: 第四趟結(jié)束時結(jié)果: 第五趟結(jié)束時結(jié)果: 第六趟結(jié)束時結(jié)果: 第七趟結(jié)束時結(jié)果: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 .設(shè)表的長度為L,試填空完成直接插入排序程序。void i

26、nsertsort(int R)/按遞增序?qū)1R n 進行直接插入排序 int i,j;for ( i=2; i<=L ; i+ ) R0=Ri;/設(shè)定R0為監(jiān)視哨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；按遞增序?qū)1 Rn進行直接選擇排序選擇選擇關(guān)鍵字最小的記錄交換關(guān)鍵字3.二分插入排序void BInsSort( )/ int i, j, low, high, m;for ( i=2; i<= n ; i+) R0=Ri；/low=1;high= n ;while (low