2022年排序练习题及答案 .pdf
第十章排序一、选择题1某内排序方法的稳定性是指( D )。A该排序算法不允许有相同的关键字记录B该排序算法允许有相同的关键字记录C平均时间为0（n log n ）的排序方法D以上都不对2下列排序算法中，其中（ D ）是稳定的。A. 堆排序，冒泡排序B. 快速排序，堆排序 C. 直接选择排序，归并排序D. 归并排序，冒泡排序3稳定的排序方法是（ B ）A直接插入排序和快速排序B折半插入排序和起泡排序C简单选择排序和四路归并排序D树形选择排序和shell 排序4下列排序方法中，哪一个是稳定的排序方法？（ B）A直接选择排序B二分法插入排序C希尔排序D快速排序5若要求尽可能快地对序列进行稳定的排序，则应选（B）。A快速排序 B归并排序 C冒泡排序6如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ CE ）就是不稳定的排序方法。A起泡排序B归并排序CShell 排序D直接插入排序E简单选择排序7若需在 O(nlog2n) 的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序8下面的排序算法中，不稳定的是（ CDF ）A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。9下列内部排序算法中：A快速排序B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序（1） 其比较次数与序列初态无关的算法是（CDF ）（2）不稳定的排序算法是（ ADF ）（3）在初始序列已基本有序（除去 n 个元素中的某k 个元素后即呈有序，kn ）的情况下，排序效率最高的算法是（ B ）（4） 排序的平均时间复杂度为O(n?logn) 的算法是（ ACF ） 为 O(n?n)的算法是（BDE ） 。10数据序列（ 8，9，10 ，4，5，6，20， 1，2）只能是下列排序算法中的( C )的两趟排序后的结果。A选择排序B.冒泡排序C.插入排序D.堆排序11数据序列（ 2，1，4，9，8，10 ，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。A. 快速排序B. 冒泡排序C. 选择排序D. 插入排序12对一组数据（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. 插入13对序列 15 ，9，7，8，20， -1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15 ；则采用的是（ C ）排序。A. 选择B. 快速C. 希尔D. 冒泡名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 14 若上题的数据经一趟排序后的排列为9，15 ，7，8，20，-1，4，则采用的是（ C ）排序。A选择B. 堆C. 直接插入D. 冒泡15 下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序 B. shell 排序 C. 堆排序D.冒泡排序16下列排序算法中( C ) 排序在一趟结束后不一定能选出一个元素放在其最终位置上。A. 选择B. 冒泡C. 归并D. 堆17下列序列中，（C ）是执行第一趟快速排序后所得的序列。A. 68 ，11 ，18，69 23 ，93，73 B. 68 ，11，69，23 18 ，93，73 C. 93 ，73 68 ，11， 69，23，18 D. 68 ，11，69，23，18 93，73 18有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为( A ) （按递增序）。A下面的 B，C，D 都不对。B9，7，8，4，-1，7，15，20 C20，15，8，9，7， -1，4， 7 D. 9 ，4，7，8，7，-1，15，20 19一组记录的关键码为（46，79，56 ，38，40， 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C ）。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) 20. 在下面的排序方法中，辅助空间为O（n）的是 ( D ) 。A希尔排序B. 堆排序C. 选择排序D. 归并排序21下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。A 冒泡 B. 希尔 C. 快速 D. 堆22. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序23. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（C ）算法，最费时间的是（B ）算法。A. 堆排序B. 快速排序C. 插入排序D. 归并排序31. 就平均性能而言，目前最好的内排序方法是( D ) 排序法。A. 冒泡B. 希尔插入C. 交换 D. 快速24 如果只想得到1000 个元素组成的序列中第5 个最小元素之前的部分排序的序列，用（ D ）方法最快。A起泡排序B快速排列 CShell 排序 D堆排序 E简单选择排序二、判断题：1当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（）2内排序要求数据一定要以顺序方式存储。（ ）3排序算法中的比较次数与初始元素序列的排列无关。（）4排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（）5在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）6直接选择排序算法在最好情况下的时间复杂度为O（N）。（）7两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）8在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n ) 。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 9在待排数据基本有序的情况下，快速排序效果最好。（）10当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（）11快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（）12堆肯定是一棵平衡二叉树。（ ）13堆是满二叉树。（）14（ 101，88，46，70， 34，39，45 ，58，66，10）是堆。（）15在用堆排序算法排序时，如果要进行增序排序，则需要采用“ 大根堆 ” 。（）16堆排序是稳定的排序方法。（ ）17归并排序辅助存储为O（1）。（）18在分配排序时，最高位优先分配法比最低位优先分配法简单。（ ）19 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是 O(n*n), 而快速排序算法的最坏时间复杂性是O(nlog2n), 所以快速排序比冒泡排序算法效率更高。（ ）20交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n ） ，而快速排序算法的最坏时间复杂性是O（nlog2n ）；所以快速排序比冒泡排序效率更高。 ()21快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n) 。（ ）22在任何情况下，归并排序都比简单插入排序快。（ ）23归并排序在任何情况下都比所有简单排序速度快。（ ）24快速排序总比简单排序快。（ ）25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -
