数据结构排序习题

1、07排序【单选题】1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列 的合适位置，该排序方法称为( A)排序法。A、直接插入 B、简单选择 C、希尔 D、二路归并2.直接插入排序在最好情况下的时间复杂度为(B)。A、O(logn) B、O(n) C、O(n*logn)D、O(n2)3.设有一组关键字值(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.设有一组关键字值 (4

2、6,79,56,38,40,84),则用快速排序的方法,结果为(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.将两个各有 n 个元素的有序表归并成一个有序表，最少进行( A)次比较。A、n B、2n-1 C、2n D、n-16.下列排序方法中，排序趟数与待排序列的初始状态有关的是( C)。A、直接插入B、简单选择 C、起泡D、堆7.下列排序方法中，不稳定的是( D)。A、直接插入B、起泡 C、二路归并D、堆8.若要在 O(nlog2n)的时间复杂度上完成排序，且要求排序是稳定

3、的，则可选择下列排序方法中的(C)。A、快速B、堆C、二路归并D、直接插入9.设有 1000 个无序的数据元素，希望用最快的速度挑选出关键字最大的前10 个元素，最好选用(C)排序法。A、起泡 B、快速 C、堆 D、基数10. 若待排兀素已按关键字值基本有序，则下列排序方法中效率最局的是( A)。A、直接插入 B、简单选择 C、快速 D、二路归并11. 数据序列(8, 9, 10, 4, 5, 6, 20, 1 , 2)只能是下列排序算法中的(C)的两趟排序后的结果。A、选择排序B、冒泡排序 C、插入排序 D、堆排序以第一个记录为基准得到的一次划分12. (A)占用的额外空间的空间复杂性为 O

4、(1)。A、堆排序算法B、归并排序算法C、快速排序算法D、以上答案都不对13. 对一组数据（84, 47, 25, 15, 21）排序，数据的排列次序在排序的过程中的变化为（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. 一个排序算法的时间复杂度与（ B）有关。A、排序算法的稳定性B、所需比较关键字的次数C、所采用的存储结构D、所需辅助存储空间的大小15. 适合并行处理的排序算法是（B）。A、选择排序 B、快速排序C、希尔排序D

5、、基数排序16. 下列排序算法中，（A）算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。A、快速排序 B、堆排序 C、希尔排序D、起泡排序17. 有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此 情况的是（A ）。A、希尔排序 B、堆排序 C、起泡排序D、快速排序18. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ A ）。A、直接插入排序B、起泡排序C、简单选择排序D、快速排序19. 下列排序算法中，（D）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的 位置上。A、堆排序 B、冒泡排序 C、快速排序D

6、、插入排序20. 下列排序算法中，占用辅助空间最多的是（ A ）。A、归并排序 B、快速排序C、希尔排序D、堆排序21. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ A）排序法。A、插入B、选择 C、希尔 D、二路归并22. 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（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. 对序列1

7、5 , 9, 7, 8, 20, -1, 4用希尔排序方法排序，经一趟后序列变为15 , -1, 4, 8, 20, 9,7则该次采用的增量是（B ）。A、1 B、4 C、3 D、224. 在含有 n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D）位置上。A、W2B、W2-1 C、1 D、TI/2 -+225. 对 n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是( A)。A、每次分区后，先处理较短的部分B、每次分区后，先处理较长的部分C、与算法每次分区后的处理顺序无关D、以上三者都不对26. 从堆中删除一个元素的时间复杂度为( B)。A、O(1)

8、B、O(log2n) C、O(n) D、O(nlog2n)【计算题】1.设有关键字序列(503, 087, 512, 061 , 908, 170, 897, 275, 653, 426),试用下列各内部排序方法对其进行排序，要求写出每趟排序结束时关键字序列的状态。(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,则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。解：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) 设待排数据元素的值互不相同，对它们按计数排序法进行排序，方法为：另设数组count,对每个元素 sti,统计关键字值比它小的元素个数存于counti,再依 counti值的大小对 st 中元素进行重排。解：public void countSort( )/ 计数排序算法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+) / 对每一对元素if(aiaj) cj+;else ci+;for(i=0;in;i+)/依次求出关键字最小，第二小，最大的记录min=0;for(j=0;jn;j+)if(cjcmin) m