排序及其问题详解

1、实用标准文案精彩文档第 10 章排序一、选择题1.某内排序方法的稳定性是指 ()。A .该排序算法不允许有相同的关键字记录B .该排序算法允许有相同的关键字记录D .以上都不对C.平均时间为0 ( n log n )的排序方法2下面给出的四种排序法中 ()排序法是不稳定性排序法。A. 插入B. 冒泡C. 二路归并D. 堆积3下列排序算法中，其中()是稳定的。A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序5下列排序方法中，哪一个是稳定的排序方法？(A .直接选择排序B 二分法插入排序C .希尔排序D 快速排序6若要求尽可能快地对序列进行稳定的排序

2、，则应选(A .快速排序B.归并排序C.冒泡排序)。7如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。 ( )就是不稳定的排序方法。A .起泡排序B.归并排序CShell 排序D 直接插入排序E.简单选择排序)排序为宜。8.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选(A .直接插入B .直接选择C .堆 D .快速E.基数 9 .若需在O(nlog 2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序12 .排序趟数与序列的原始状态有关的排序

3、方法是 （）排序法。A .插入B. 选择C. 冒泡D. 快速15.在下列排序算法中 ,哪一个算法的时间复杂度与初始排序无关（）。16.18.A. 直接插入排序 B. 气泡排序C. 快速排序D.直接选择排序比较次数与排序的初始状态无关的排序方法是 （A 直接插入排序B .起泡排序数据序列（ 2， 1，后的结果。A. 快速排序19 .对一组数据（ 84 ，1 ) 84 47 25 15 2147 84则采用的排序是 （A. 选择23 .下列排序算法中A. 选择24 .下列序列中，A. 68 ，11，18，C. 93 ，7325 .有一组数据（）。C .快速排序D.4，9，8， 10 ， 6 ， 2

4、0 ）只能是下列排序算法中的 （B. 冒泡排序C. 选择排序D.简单选择排序）的两趟排序插入排序47 ，25 ，15 ，21 ）排序，数据的排列次序在排序的过程中的变化为2) 15 47 25 84 21）。B. 冒泡3) 15 21 25 84 47(4) 15 21 25C. 快速D. 插入）排序在一趟结束后不一定能选出一个元素放在其最终位置上。B. 冒泡C. 归并D. 堆）是执行第一趟快速排序后所得的序列。6923 ，93 ，7368 ，11，69 ，23，1815，9，7，8，20，-1，7，4）B. 68 ，11，69，2318，93，73D. 68 ，11，69，23，1893 ，

5、73用快速排序的划分方法进行一趟划分后数据的排序为 （）（按递增序） 。A 下面的 B， C，D 都不对。B9，7，8，4，-1 ，7，15，20C20，15，8，9，7，-1 ，4，7D. 9，4，7，8，7，-1 ，15，2026 一组记录的关键码为（ 46 ，79，56， 38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A (38,40,46,56,79,84)B. (40,38,46,79,56,84)C(40,38,46,56,79,84)D. (40,38,46,84,56,79)31. 就平均性能而言，目前最好的内排序方法是 （）排序法。A.

6、 冒泡 B. 希尔插入 C. 交换 D. 快速37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（）。A. 选择B. 冒泡C. 插入D. 堆38用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是）。A 94,32,40,90,80,46,21,69B32,40,21,46,69,94,90,803940.41.C 21,32,46,40,80,69,90,94D90,69,80,46,21,32,94,40直接插入排序在最好情况下的时间复杂度为（A O(logn)B O(n)C若用冒泡排序方法对序列 10,1

7、4,26,29,41,52A. 3B. 10C. 15O(n*logn)DO(n 2)从大到小排序，需进行D. 25采用简单选择排序，比较次数与移动次数分别为 （）。）次比较。A. O (n) ,O(logn)B. O(logn),0(n*n)C. 0(n*n),0(n)D. 0(nlogn),0(n)）。43 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（A 21,25,5,17,9,23,30B25,23,30,17,21,5,9C 21,9,17,30,25,23,5D. 5,9,17,21,23,25,3044 对关键码序列 28，16 ，32，12，60，2，5，72 快

8、速排序，从小到大一次划分结果为）。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. 快速排序方法在（）情况下最不利于发挥其长处。A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序判断题：1 .当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（2.内排序要求数据一定要以顺序方式存储。3.排序算法中的比较次数与初始元素

9、序列的排列无关。4.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（6.直接选择排序算法在最好情况下的时间复杂度为O（ N ）。（ ）9.在待排数据基本有序的情况下，快速排序效果最好。24 .快速排序总比简单排序快。（填空题:和记1.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的录的O 7 .对n个记录的表r1.n进行简单选择排序，所需进行的关键字间的比较次数为24 .设有字母序列Q,D,F,X,A,P,N,B,Y,M,C,W，请写出按2路归并排序方法对该序列进行一趟扫描后的结果应用题:8 .简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间

10、复杂度和排序稳定性上的差别。第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.对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值,而给定的序列并不满足。二、判断题1. V2. X3. X4. X6. X9. X24. X三、填空题1.比较，移动7. n(n-1)/224. D,Q,F,X,A,P ,B,N,M,Y,C,W应用题:8.直接插入排序的基本思想是基于插入，开始假定

11、第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从 R1.i-1变为R1.i，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是 0(n 2)，平均时间复杂度是0(n 2)，空间复杂度是 0(1)，是稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1=in)趟简单选择排序是，从无序序列Ri.n的n-i+1记录中选出关键字最小的记录，和第i个记录交换,使有序序列逐步扩大，最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是0(1)，是不稳定排序。二