數(shù)據(jù)結(jié)構(gòu)排序習(xí)題

1、07排序【單選題】1. 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（A）排序法。A、直接插入B、簡單選擇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,80B、84,79,56,38,40,46C、84,79,56,46,40,38D、84,56,79,40,46,384. 設(shè)有一組關(guān)鍵字值（46,79,

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

3、穩(wěn)定的，則可選擇下列排序方法中的（C）。A、快速B、堆C、二路歸并D、直接插入9. 設(shè)有1000個(gè)無序的數(shù)據(jù)元素，希望用最快的速度挑選出關(guān)鍵字最大的前10個(gè)元素，最好選用（C）排序法。A、起泡B、快速C、堆D、基數(shù)10. 若待排元素已按關(guān)鍵字值基本有序，則下列排序方法中效率最高的是（A）。A、直接插入B、簡單選擇C、快速D、二路歸并11. 數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（C）的兩趟排序后的結(jié)果。A、選擇排序B、冒泡排序C、插入排序D、堆排序12. （A）占用的額外空間的空間復(fù)雜性為(1)。A、堆排序算法B、歸并排序算法C、快速排序算法D、以上答案都不對

4、13. 對一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（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、所采用的存儲結(jié)構(gòu)D、所需輔助存儲空間的大小15. 適合并行處理的排序算法是（B）。A、選擇排序B、快速排序C、希爾排序D、基數(shù)排序16. 下列排序算法中，（A）算法可能會出現(xiàn)下面的情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。

5、A、快速排序B、堆排序C、希爾排序D、起泡排序17. 有些排序算法在每趟排序過程中，都會有一個(gè)元素被放置在其最終的位置上，下列算法不會出現(xiàn)此情況的是（A）。A、希爾排序B、堆排序C、起泡排序D、快速排序18. 在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序的方法是（A）。A、直接插入排序B、起泡排序C、簡單選擇排序D、快速排序19. 下列排序算法中，（D）算法可能會出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。A、堆排序B、冒泡排序C、快速排序D、插入排序20. 下列排序算法中，占用輔助空間最多的是（A）。A、歸并排序B、快速排序C、希爾排序D、堆排序21. 從未排序

6、序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（A）排序法。A、插入B、選擇C、希爾D、二路歸并22. 用直接插入排序方法對下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（C）。A、94,32,40,90,80,46,21,69B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,4023. 對序列15，9，7，8，20，-1，4用希爾排序方法排序，經(jīng)一趟后序列變?yōu)?5，-l，4，8，20，9，7則該次采用的增量是（B）。A、lB、4C、

7、3D、224. 在含有n個(gè)關(guān)鍵字的小根堆（堆頂元素最?。┲校P(guān)鍵字最大的記錄有可能存儲在（D）位置上。A、ën/2ûB、ën/2û -1C、1D、ën/2û +225. 對n個(gè)記錄的線性表進(jìn)行快速排序?yàn)闇p少算法的遞歸深度，以下敘述正確的是（A）。A、每次分區(qū)后，先處理較短的部分B、每次分區(qū)后，先處理較長的部分C、與算法每次分區(qū)后的處理順序無關(guān)D、以上三者都不對26. 從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為（B）。A、O(1)B、O(log2n)C、O(n)D、O(nlog2n)【計(jì)算題】1. 設(shè)有關(guān)鍵字序列（503，087，512，061，

8、908，170，897，275，653，426），試用下列各內(nèi)部排序方法對其進(jìn)行排序，要求寫出每趟排序結(jié)束時(shí)關(guān)鍵字序列的狀態(tài)。(1)直接插入法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：087，503，512，061，908，170，897，275，653，426第二趟：087，503，512，061，908，170，897，275，653，426第三趟：061，087，503，512，908，170，897，275，653，426第四趟：061，087，503，512，908，170，897，275，653，426第五趟：061，087，

9、170，503，512，908，897，275，653，426第六趟：061，087，170，503，512，897，908，275，653，426第七趟：061，087，170，275，503，512，897，908，653，426(2)希爾排序法，增量序列為（5，3，1）；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：170，087，275，061，426，503，897，512，653，908第二趟：061，087，275，170，426，503，897，512，653，908第三趟：061，087，170，275，426，503，512

10、，653，897，908(3)快速排序法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：426，087，275，061，170，503，897，908，653，512第二趟：170，087，275，061，426，503，512，653，897，908第三趟：061，087，170，275，426，503，512，653，897，908第四趟：061，087，170，275，426，503，512，653，897，908(4)堆排序法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：908，653

11、，897，503，426，170，512，275，061，087第二趟：897，653，512，503，426，170，087，275，061，908第三趟：653，503，512，275，426，170，087，061，897，908第四趟：512，503，170，275，426，061，087，653，897，908第五趟：503，426，170，275，087，061，512，653，897，908第六趟：426，275，170，061，087，503，512，653，897，908第七趟：275，087，170，061，426，503，512，653，897，908第八趟：170，08

12、7，061，275，426，503，512，653，897，908第九趟：087，061，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第一趟：087，503，061，512，170，908，275，897，426，653第二趟：061，087，503，512，170，275，897，908，426，653第三趟：061，087，170，275，503，512，897，908，426，

13、653第四趟：061，087，170，275，426，503，512，653，897，908【算法題】下列算法題中可能用到的類如下：public class SortTable private int st ; public SortTable(int length) int i; st=new intlength; for(i=0;i<length;i+) sti=(int)(Math.random()*10000); /構(gòu)造函數(shù)/SortTable1. 在SortTable類中添加實(shí)現(xiàn)如下功能的方法：(1)對數(shù)據(jù)元素按奇偶轉(zhuǎn)換排序法進(jìn)行排序。方法為：第一趟對所有奇數(shù)的i，將sti和s

14、ti+1進(jìn)行比較，第二趟對所有偶數(shù)的i，將sti和sti+1進(jìn)行比較，每次比較時(shí)若sti>sti+1，則將二者交換，以后重復(fù)上述二趟過程交換進(jìn)行，直至整個(gè)數(shù)組有序。解：public void oesort( ) boolean change=true; int temp; while (change) change=false; for(i=0;i<st.length;i+=2) if (sti+1<sti) change=true; temp=sti+1; sti+1=sti; sti=temp; /if /for for(i=1;i<st.length;i+=2)

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