第十章内排习题.doc

PAGE  PAGE 3 第十章 内部排序 一，选择 1. 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（ ）。 A. O(nlogn) B. O(logn) C. O(n) D. O(n*n) 2．下列排序算法中，其中（ ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 3．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 4．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 5. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。 6． 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( ) A．插入排序 B．枚举排序 C．选择排序 D．交换排序 7．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（ ） A．堆排序〈　快速排序〈归并排序 B．堆排序〈　归并排序〈 快速排序 C．堆排序〉 归并排序 〉快速排序 D．堆排序 快速排序 归并排序 8．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。 A． 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序 9．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是( ) A．N B．2N-1 C．2N D．N-1 10．一组记录的关键码为（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) 11. 在下面的排序方法中，辅助空间为O（n）的是( ) 。 A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 12．下列排序算法中，在待排序数据已有序时，??费时间反而最多的是( )排序。 A． 冒泡 B. 希尔 C. 快速 D. 堆 13.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 14. 以下序列不是堆的是( )。 (100,85,98,77,80,60,82,40,20,10,66) B. (100,98,85,82,80,77,66,60,40,20,10) (10,20,40,60,66,77,80,82,85,98,100) D. (100,85,40,77,80,60,66,98,82,10,20) 15．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。 A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序 1.A2.D3.A4.C5.C6.B7.A8.D9.A10.C11.D12.C13.B14.D15.D 二，判断 1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ ） 2．内排序要求数据一定要以顺序方式存储。 （ ） 3．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ） 4．直接选择排序算法在最好情况下的时间复杂度为O（N）。（ ） 5．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ） 6．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（ ） 7．快速