1、實用標準文案第 10 章 排序一、選擇題1 某內(nèi)排序方法的穩(wěn)定性是指（） 。A.該排序算法不允許有相同的關(guān)鍵字記錄B.該排序算法允許有相同的關(guān)鍵字記錄C.平均時間為0 （n log n ）的排序方法D.以上都不對2 下面給出的四種排序法中（）排序法是不穩(wěn)定性排序法。A. 插入B. 冒泡C. 二路歸并D. 堆積3 下列排序算法中，其中（）是穩(wěn)定的。A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接選擇排序，歸并排序D. 歸并排序，冒泡排序5 下列排序方法中，哪一個是穩(wěn)定的排序方法？（）A.直接選擇排序B.二分法插入排序C.希爾排序D.快速排序6 若要求盡可能快地對序列進行穩(wěn)定的排序，則應(yīng)選

2、（ A 快速排序B 歸并排序C 冒泡排序） 。7 如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（ ）就是不穩(wěn)定的排序方法。A.起泡排序B.歸并排序C. Shell排序 D.直接插入排序E.簡單選擇排序8 若要求排序是穩(wěn)定的，且關(guān)鍵字為實數(shù)，則在下列排序方法中應(yīng)選（）排序為宜。A.直接插入B.直接選擇C.堆 D.快速E.基數(shù)9 .若需在O（nlog 2n）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序精彩文檔方法是（A. 快速排序B. 堆排序C. 歸并排序D. 直接插入排序12 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）排

3、序法。A.插入B. 選擇C. 冒泡D. 快速15 在下列排序算法中,哪一個算法的時間復雜度與初始排序無關(guān)（A直接插入排序B. 氣泡排序C. 快速排序D.直接選擇排序16 比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是）。18 數(shù)據(jù)序列（A.直接插入排序2， 1，后的結(jié)果。A. 快速排序19 對一組數(shù)據(jù)（84 ，1 )84 47 25 15 2147 84則采用的排序是（A. 選擇B 起泡排序C.快速排序D 簡單選擇排序簡單選擇排序23 下列排序算法中24 下列序列中，25 有一組數(shù)據(jù)（A. 選擇A. 68 ， 11 ，C. 93 ， 7318，4， 9， 8，

4、 10， 6，B. 冒泡排序47 ， 25 ， 15 ， 21 ）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為）。20）只能是下列排序算法中的C. 選擇排序）的兩趟排序D.插入排序2)15 47 25 84 21B. 冒泡）排序在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。B. 冒泡）是執(zhí)行第一趟快速排序后所得的序列。6923 ， 93， 7368 ， 11 ， 69 ， 23， 183)15 21 25 84 47( 4) 15 21C. 快速C. 歸并D. 堆25D. 插入B. 68 ， 11 ， 69， 2318， 93，D. 68 ， 11 ， 69， 23， 1893 ，73731

5、5 ， 9 ， 7， 8 ， 20 ， -1 ， 7 ，4）用快速排序的劃分方法進行一趟劃分后數(shù)據(jù)的排序為（）（按遞增序）。A 下面的B， C， D 都不對。B 9， 7， 8， 4， -1 ， 7， 15， 20C 20， 15， 8， 9， 7， -1 ， 4， 7 D. 9， 4， 7， 8， 7， -1 ， 15， 2026 一組記錄的關(guān)鍵碼為（46 ， 79， 56， 38， 40， 84） ，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為（） 。A （38,40,46,56,79,84）B. （40,38,46,79,56,84）C （40,38,46,56,79,8

6、4）D. （40,38,46,84,56,79）31. 就平均性能而言，目前最好的內(nèi)排序方法是（）排序法。A. 冒泡 B. 希爾插入C. 交換 D. 快速37. 在排序算法中，每次從未排序的記錄中挑出最?。ɑ蜃畲螅╆P(guān)鍵碼字的記錄，加入到已排序記錄的末尾，該排序方法是（） 。A. 選擇B. 冒泡C. 插入D. 堆38 用直接插入排序方法對下面四個序列進行排序（由小到大）用直接插入排序方法對下面四個序列進行排序（由小到大）,元素比較次數(shù)最少的是39 直接插入排序在最好情況下的時間復雜度為（40.41.A94,32,40,90,80,46,21,69C21,32,46,40,80,69,90,94B

7、D直接插入排序在最好情況下的時間復雜度為（AO(logn)B O(n)C若用冒泡排序方法對序列10,14,26,29,41,52A. 3B. 10C. 15D. 2532,40,21,46,69,94,90,8090,69,80,46,21,32,94,40O(n*logn)D O(n 2)從大到小排序，需進行）次比較。采用簡單選擇排序，比較次數(shù)與移動次數(shù)分別為（）。A. O ( n ) ,O(logn)B. O(logn),0(n*n)C. 0(n*n),0(n)D. 0(nlogn),0(n)43 對下列關(guān)鍵字序列用快速排序法進行排序時，速度最快的情形是（） 。A21,25,5,17,9,

8、23,30B 25,23,30,17,21,5,9C.21,9,17,30,25,23,5D. 5,9,17,21,23,25,3044 對關(guān)鍵碼序列28 ， 16 ， 32 ， 12 ， 60 ， 2， 5， 72 快速排序，從小到大一次劃分結(jié)果為（）。A. （2,5,12,16）26（60,32,72） B. （5,16,2,12）28（60,32,72）C. （2,16,12,5）28（60,32,72） D. （5,16,2,12）28（32,60,72）48. 快速排序方法在（）情況下最不利于發(fā)揮其長處。A. 要排序的數(shù)據(jù)量太大B. 要排序的數(shù)據(jù)中含有多個相同值C. 要排序的數(shù)據(jù)個數(shù)

9、為奇數(shù)D. 要排序的數(shù)據(jù)已基本有序判斷題：1 當待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜度的主要因素。（）2 內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲。（）3 排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。（）4排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（）6 直接選擇排序算法在最好情況下的時間復雜度為O （ N ） 。（）9 在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。（）24 快速排序總比簡單排序快。（）實用標準文案填空題：1.若不考慮基數(shù)排序，則在排序過程中，主要進行的兩種基本操作是關(guān)鍵字的和記錄的7 .對n個記錄的表 中.n進行

10、簡單選擇排序，所需進行白關(guān)鍵字間的比較次數(shù)為 24.設(shè)有字母序列Q,D,F,X,A,P,N,B,Y,M,C,W,請寫出按2路歸并排序方法對該序列進行一 趟掃描后的結(jié)果應(yīng)用題：8.簡述直接插入排序，簡單選擇排序，2-路歸并排序的基本思想以及在時間復雜度和排序穩(wěn)定性上的差別。第10章排序答案、選擇題1.D2.D3.D5.B6.B7.C,E8.A9.C12.C,15.16.D18.19.ADDA23.24.C25.26.C31.CAD37.38.C39.40.C41.43.44.B48.ABCAD部分答案解釋如下：18.對于后三種排序方法兩趟排序后，序列的首部或尾部的兩個元素應(yīng)是有序的兩個極值,而給

11、定的序列并不滿足。、判斷題1.V2. X3. X4. X6. X9. x24. X三、填空題1.比較，移動7. n(n-1)/224. D,Q,F,X,A,P ,B,N,M,YCW應(yīng)用題：8.直接插入排序的基本思想是基于插入，開始假定第一個記錄有序，然后從第二個記錄開始，依次插入到前面有序的子文件中。即將記錄Ri(2<=i<=n)插入到有序子序列 R1.i-1中，使記錄的有序序列從 R1.i-1變?yōu)镽1.i,最終使整個文件有序。共進行n-1趟插入。最壞時間復雜度是 0(n 2),平均時間復雜度是 0(n2),空間復雜度是 0(1),是穩(wěn)定排序。簡單選擇排序的基本思想是基于選擇，開始有序序列長度為零， 第i(1<=i<n)趟簡單選擇排序是，從無序序列 Ri.n的n-i+1記錄中選出關(guān)鍵字最小的記錄，和第 i個記錄交換， 使有序序列逐步擴大，最后整個文件有序。共進行 n-1趟選擇。最壞時間復雜度是 0(n2), 平均時間復雜度是 0(n2),空間復雜度是0(1),是不穩(wěn)定排序。二路并