《排序及其问题详解》由会员分享，可在线阅读，更多相关《排序及其问题详解（7页珍藏版）》请在金锄头文库上搜索。
1、第 10章 排序一、选择题1某内排序方法的稳定性是指（ ）。A该排序算法不允许有相同的关键字记录B该排序算法允许有相同的关键字记录C 平均时间为0（n log n）的排序方法D 以上都不对2下面给出的四种排序法中（）排序法是不稳定性排序法。A. 插入B. 冒泡C. 二路归并D. 堆积3下列排序算法中，其中（）是稳定的。A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序 D. 归并排序，冒泡排序5 下歹蛀非序方法中，哪一个是稳定的排序方法？（）A直接选择排序B二分法插入排序C希尔排序D快速排序6 若要求尽可能快地对序列进行稳定的排序，则应选（A 快速排序B 归并排序C 冒
2、泡排序）。7如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒， 则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。A 起泡排序B 归并排序 C Shell排序D.直接插入排序E.简单选择排序8若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。A直接插入B直接选择C堆D快速E基数9 若需在O（nlog）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序12排序趟数与序列的原始状态有关的排序方法是（ ）排序法。A插入B. 选择C. 冒泡D. 快速15在下列排序算法中
3、,哪一个算法的时间复杂度与初始排序无关（）。A 直接插入排序 B. 气泡排序 C. 快速排序 D.直接选择排序16比较次数与排序的初始状态无关的排序方法是（）。A直接插入排序B起泡排序C快速排序D简单选择排序18数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的（）的两趟排序后的结果。A. 快速排序B. 冒泡排序C. 选择排序D. 插入排序19对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为1） 84 47 25 15 212） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 2547 84则采用的排
4、序是 （）。A. 选择B. 冒泡C. 快速D. 插入23下列排序算法中（）排序在一趟结束后不一定能选出一个元素放在其最终位置上。A. 选择B. 冒泡C. 归并D. 堆24下列序列中，（）是执行第一趟快速排序后所得的序列。A. 68，11，18，6923，93，73B. 68，11，69，2318，93，73C. 93，7368，11，69，23，18D. 68，11，69，23，1893，73用快速排序的划分方法进行一趟划分后25有一组数据（15，9，7，8，20，-1，7，4）数据的排序为 ( )(按递增序)。A 下面的 B,C,D 都不对。B.9,7,8,4,-1,7,15,20C20，1
5、5，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. 冒泡 B. 希尔插入 C. 交换 D. 快速37. 在排序算法中，每次从未排序的记录中挑出最小(或最大)关键码字的记录，加入到已 排序记录的末尾，该排序方法
6、是( )。A. 选择B. 冒泡C. 插入D. 堆38. 用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是 ( )。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,4039. 直接插入排序在最好情况下的时间复杂度为()A. O(logn) B. O(n)C. O(n*logn) D. O(n2)40. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行( )次比较。A. 3 B. 10 C.
7、 15D. 2541. 采用简单选择排序，比较次数与移动次数分别为( )。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,30 B25,23,30,17,21,5,9C . 21,9,17,30,25,23,5 D. 5,9,17,21,23,25,3044对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为 ( )。A. (2,5,12,16)26(60,32,72) B.
8、(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. 排序算法中的比较次数与初始元素序列的排列无关。()4. 排序的稳定性是指排序算法中的比较次数保持不变
9、，且算法能够终止。()6直接选择排序算法在最好情况下的时间复杂度为O(N)()9.在待排数据基本有序的情况下，快速排序效果最好。( )24.快速排序总比简单排序快。( )填空题：1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的和记录的。7对n个记录的表r1.n进行简单选择排序，所需进行的关键字间的比较次数为。24 设有字母序列Q,D,F,XAPN,B,Y,M,C,W请写出按2路归并排序方法对该序列进行一趟扫描后的结果。应用题：8简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序 稳定性上的差别。第10章 排序 答案一、选择题1.D2.D3.D5.
10、B6.B7.C,E8.A9.C12.C,15.16.D18.19.A23.24.C25.26.C31.37.38.C39.40.C41.43.44.B48.部分答案解释如下：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. 直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开 始，衣次插入到前面有序的子文件中。即将记录Ri(2 = i = n)插入
11、到有序子序列R1.i-1 中，吏记录的有序序列从R1.i-1变为R1.i，最终使整个文件有序。共进行n-1趟插入。 最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1 = in)趟简单选 择排序是，从无序序列Ri.n的n-i+1记录中选出关键字最小的记录，和第i个记录交换， 使有序序列逐步扩大，最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0(n 2)， 平均时间复杂度是0(n2)，空间复杂度是O(1)，是不稳定排序。二路并归排序的基本思想是基于归并，开始将具有n个待排序记录的序列看成是n个 长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两 两归并，得到n/4个长度为4的有序序列。如此重复，经过log2n趟归并，最终得到一 个长度为n的有序序列。最坏时间复杂度和平均时间复杂度都是0(nlog2n)，空间复杂度是 O(n)，是稳定排序。
