1、07排序【單選題】1.從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列 的合適位置，該排序方法稱為( A)排序法。A、直接插入 B、簡(jiǎn)單選擇 C、希爾 D、二路歸并2.直接插入排序在最好情況下的時(shí)間復(fù)雜度為(B)。A、O(logn) B、O(n) C、O(n*logn)D、O(n2)3.設(shè)有一組關(guān)鍵字值(46,79,56,38,40,84)，則用堆排序的方法建立的初始堆為( B)。A、79,46,56,38,40,80C、84,79,56,46,40,38B、84,79,56,38,40,46D、84,56,79,40,46,384.設(shè)有一組關(guān)鍵字值 (4

2、6,79,56,38,40,84),則用快速排序的方法,結(jié)果為(C)。A、38,40,46,56,79,84 B、40,38,46,79,56,84C、40,38,46,56,79,84 D、40,38,46,84,56,795.將兩個(gè)各有 n 個(gè)元素的有序表歸并成一個(gè)有序表，最少進(jìn)行( A)次比較。A、n B、2n-1 C、2n D、n-16.下列排序方法中，排序趟數(shù)與待排序列的初始狀態(tài)有關(guān)的是( C)。A、直接插入B、簡(jiǎn)單選擇 C、起泡D、堆7.下列排序方法中，不穩(wěn)定的是( D)。A、直接插入B、起泡 C、二路歸并D、堆8.若要在 O(nlog2n)的時(shí)間復(fù)雜度上完成排序，且要求排序是穩(wěn)定

3、的，則可選擇下列排序方法中的(C)。A、快速B、堆C、二路歸并D、直接插入9.設(shè)有 1000 個(gè)無(wú)序的數(shù)據(jù)元素，希望用最快的速度挑選出關(guān)鍵字最大的前10 個(gè)元素，最好選用(C)排序法。A、起泡 B、快速 C、堆 D、基數(shù)10. 若待排兀素已按關(guān)鍵字值基本有序，則下列排序方法中效率最局的是( A)。A、直接插入 B、簡(jiǎn)單選擇 C、快速 D、二路歸并11. 數(shù)據(jù)序列(8, 9, 10, 4, 5, 6, 20, 1 , 2)只能是下列排序算法中的(C)的兩趟排序后的結(jié)果。A、選擇排序B、冒泡排序 C、插入排序 D、堆排序以第一個(gè)記錄為基準(zhǔn)得到的一次劃分12. (A)占用的額外空間的空間復(fù)雜性為 O

4、(1)。A、堆排序算法B、歸并排序算法C、快速排序算法D、以上答案都不對(duì)13. 對(duì)一組數(shù)據(jù)（84, 47, 25, 15, 21）排序，數(shù)據(jù)的排列次序在排序的過(guò)程中的變化為（1） 84 47 25 15 21（2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84則采用的排序是（A ）。A、選擇 B、冒泡 C、快速 D、插入14. 一個(gè)排序算法的時(shí)間復(fù)雜度與（ B）有關(guān)。A、排序算法的穩(wěn)定性B、所需比較關(guān)鍵字的次數(shù)C、所采用的存儲(chǔ)結(jié)構(gòu)D、所需輔助存儲(chǔ)空間的大小15. 適合并行處理的排序算法是（B）。A、選擇排序 B、快速排序C、希爾排序D

5、、基數(shù)排序16. 下列排序算法中，（A）算法可能會(huì)出現(xiàn)下面的情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。A、快速排序 B、堆排序 C、希爾排序D、起泡排序17. 有些排序算法在每趟排序過(guò)程中，都會(huì)有一個(gè)元素被放置在其最終的位置上，下列算法不會(huì)出現(xiàn)此 情況的是（A ）。A、希爾排序 B、堆排序 C、起泡排序D、快速排序18. 在文件“局部有序”或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法是（ A ）。A、直接插入排序B、起泡排序C、簡(jiǎn)單選擇排序D、快速排序19. 下列排序算法中，（D）算法可能會(huì)出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的 位置上。A、堆排序 B、冒泡排序 C、快速排序D

6、、插入排序20. 下列排序算法中，占用輔助空間最多的是（ A ）。A、歸并排序 B、快速排序C、希爾排序D、堆排序21. 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（ A）排序法。A、插入B、選擇 C、希爾 D、二路歸并22. 用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（C）。A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,4023. 對(duì)序列1

7、5 , 9, 7, 8, 20, -1, 4用希爾排序方法排序，經(jīng)一趟后序列變?yōu)?5 , -1, 4, 8, 20, 9,7則該次采用的增量是（B ）。A、1 B、4 C、3 D、224. 在含有 n 個(gè)關(guān)鍵字的小根堆（堆頂元素最小）中，關(guān)鍵字最大的記錄有可能存儲(chǔ)在（D）位置上。A、W2B、W2-1 C、1 D、TI/2 -+225. 對(duì) n 個(gè)記錄的線性表進(jìn)行快速排序?yàn)闇p少算法的遞歸深度，以下敘述正確的是( A)。A、每次分區(qū)后，先處理較短的部分B、每次分區(qū)后，先處理較長(zhǎng)的部分C、與算法每次分區(qū)后的處理順序無(wú)關(guān)D、以上三者都不對(duì)26. 從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為( B)。A、O(1)

8、B、O(log2n) C、O(n) D、O(nlog2n)【計(jì)算題】1.設(shè)有關(guān)鍵字序列(503, 087, 512, 061 , 908, 170, 897, 275, 653, 426),試用下列各內(nèi)部排序方法對(duì)其進(jìn)行排序，要求寫出每趟排序結(jié)束時(shí)關(guān)鍵字序列的狀態(tài)。(1)直接插入法；解：初始:503, 087,512061 908170 897 275 653 426第趟087, 503,512061 908170 897 275 653 426第二趟087, 503,512,061 908170 897 275 653 426第三趟061, 087,503512, 908,170 897 2

9、75 653 426第四趟061, 087,503512, 908:,170 897 275 653 426第五趟061, 087,170503 512908, 897, 275, 653, 426第八趟061, 087,170503 512897, 908, 275, 653, 426第七趟061, 087,170275 503512, 897, 908, 653, 426(2)希爾排序法，增量序列為(5, 3,1);解：初 始：503, 087, 512, 061, 908, 170, 897, 275, 653, 426第一趟：170, 087, 275, 061, 426, 503,

10、897, 512, 653, 908第二趟：061, 087, 275, 170, 426, 503, 897, 512, 653, 908第三趟：061, 087, 170, 275, 426, 503, 512, 653, 897, 908(3)快速排序法;解:(4)堆排序法;解：初始503087 512 061 908 170 897 275 653426第趟908653 897 503 426 170 512 275 061087第二趟897653 512 503 426 170 087 275 061908第三趟653503 512 275 426 170 087 061 89790

11、8第四趟512503 170 275 426 061 087 653 897908第五趟503426 170 275 087 061 512 653 897908第八趟426275 170 061 087 503 512 653 897908第七趟275087 170 061 426 503 512 653 897908第八趟170087 061 275 426 503 512 653 897908第九趟087061 170 275 426 503 512 653 897908第十趟061087 170 275 426 503 512 653 897908初始:第趟:第二趟:第三趟：503，4

12、26，170，061087，087，087，512,275,275,061, 908, 170, 897, 275, 653, 426061, 170, 503, 897, 908, 653, 512061, 426 口，503, 512, 653, 897, 908087, 170, 275, 426, 503, 512, 653, 897, 908第四趟061, 087, 170, 275, 426, 503, 512, 653, 897,908(5)二路歸并排序法；解：初 始：503, 087, 512, 061, 908, 170, 897, 275, 653, 426第一趟第二趟第三

13、趟第四趟087061503, 061, 512, 170, 908, 275, 897, 426, 653 087,503,512, 170, 275, 897, 908, :426, 653061,061,087,087，170170275, 503, 512, 897, 908, 426, 653275, 426, 503, 512, 653, 897, 908【算法題】下列算法題中可能用到的類如下：public class SortTable (private int st;public SortTable(int length)(int i;st=new intlength;for(i

14、=0;isti+1,則將二者交換，以后重復(fù)上述二趟過(guò)程交換進(jìn)行，直至整個(gè)數(shù)組有序。解：public void oesort( )(boolean change=true;int temp;while (change)(change=false;for(i=0;ist.length;i+=2)if (sti+1sti)(change=true;temp=sti+1; sti+1=sti; sti=temp;/if/forfor(i=1;ist.length;i+=2)if (sti+1sti)change=true;temp=sti+1; sti+1=sti; sti=temp;/if/for/

15、while/oesort(2) 設(shè)待排數(shù)據(jù)元素的值互不相同，對(duì)它們按計(jì)數(shù)排序法進(jìn)行排序，方法為：另設(shè)數(shù)組count,對(duì)每個(gè)元素 sti,統(tǒng)計(jì)關(guān)鍵字值比它小的元素個(gè)數(shù)存于counti,再依 counti值的大小對(duì) st 中元素進(jìn)行重排。解：public void countSort( )/ 計(jì)數(shù)排序算法int c =new int st.length;for(i=0;ist.length;i+) ci=0;for(i=0;ist.length-1;i+)for(j=i+1;jst.length;j+) / 對(duì)每一對(duì)元素if(aiaj) cj+;else ci+;for(i=0;in;i+)/依次求出關(guān)鍵字最小，第二小，最大的記錄min=0;for(j=0;jn;j+)if(cjcmin) m