搜索
第十章排序一、选择题1．某内排序方法的稳定性是指(D)。A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法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．归并排序C．Shell排序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）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是(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.冒泡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都不对。B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，2019．一组记录的关键码为（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．快速排列C．Shell排序D．堆排序E．简单选择排序二、判断题：1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（√）2．内排序要求数据一定要以顺序方式存储。（╳）3．排序算法中的比较次数与初始元素序列的排列无关。（╳）4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（╳）5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（╳）6．直接选择排序算法在最好情况下的时间复杂度为O（N）。（╳）7．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（╳）8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。（╳）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.中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（√）