第十章-排序

第10章排序一、选择题1．某内排序方法的稳定性是指(D)。A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对2．下面给出的四种排序法中(D)排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆积3．下列排序算法中，其中（D）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序4．稳定的排序方法是（B）A．直接插入排序和快速排序B．折半插入排序和起泡排序C．简单选择排序和四路归并排序D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（B）A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（B）。A．快速排序B．归并排序C．冒泡排序7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（CE）就是不稳定的排序方法。A．起泡排序B．归并排序C．Shell排序D．直接插入排序E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（A）排序为宜。A．直接插入B．直接选择C．堆D．快速E．基数9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C）。A.快速排序B.堆排序C.归并排序D.直接插入排序10．下面的排序算法中，不稳定的是（C,D,F）A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。11．下列内部排序算法中：A．快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（D,C）（2）不稳定的排序算法是（A,D,F）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（B）（4）排序的平均时间复杂度为O(n•logn)的算法是（(A,C,F)）为O(n•n)的算法是（(B,D,E)）12．排序趟数与序列的原始状态有关的排序方法是(CD)排序法。A．插入B.选择C.冒泡D.快速13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。(A)A．选择排序法B.插入排序法C.快速排序法D.堆积排序法14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是(BD)。A．直接插入B.二分法插入C.快速排序D.归并排序15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D）。A．直接插入排序B.气泡排序C.快速排序D.直接选择排序16．比较次数与排序的初始状态无关的排序方法是(D)。A．直接插入排序B．起泡排序C．快速排序D．简单选择排序17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(C)的两趟排序后的结果。A．选择排序B.冒泡排序C.插入排序D.堆排序18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(A)的两趟排序后的结果。A.快速排序B.冒泡排序C.选择排序D.插入排序19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是(A)。A.选择B.冒泡C.快速D.插入20．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（C）排序。A.选择B.快速C.希尔D.冒泡21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（C）排序。A．选择B.堆C.直接插入D.冒泡22．下列排序算法中(B)不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序23．下列排序算法中(C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆24．下列序列中，（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]25．有一组数据（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，2026．一组记录的关键码为（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)27.在下面的排序方法中，辅助空间为O（n）的是(D)。A．希尔排序B.堆排序C.选择排序D.归并排序28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是(C)排序。A．冒泡B.希尔C.快速D.堆29.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（B）。A.直接插入排序B.快速排序C.直接选择排序D.堆排序30.对初始状态为递增序列的表按递增顺序排序，最省时间的是（C）算法，最费时间的是（B）算法。A.堆排序B.快速排序C.插入排序D.归并排序31.就平均性能而言，目前最好的内排序方法是(D)排序法。A.冒泡B.希尔插入C.交换D.快速32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（D）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序33．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A）A．直接插入排序B．冒泡排序C．简单选择排序4．下列排序算法中，（D）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序35.下列排序算法中，占用辅助空间最多的是：(A)A.归并排序B.快速排序C.希尔排序D.堆排序36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为(A)排序法。A.插入B.选择C.希尔D.二路归并37.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（A）。A.选择B.冒泡C.插入D.堆38．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（C）。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．直接插入排序在最好情况下的时间复杂度为（B）A．O(logn)B．O(n)C．O(n*logn)D．O(n2)40.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（C）次比较。A.3B.10C.15D.2541.采用简单选择排序，比较次数与移动次数分别为(C)。A.O（n）,O(logn)B.O(logn),0(n*n)C.0(n*n),0(n)D.0(nlogn),0(n)42.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是(B)A.lB.4C.3D.243．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（A）。A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}C．{21,9,17,30,25,23,5}Ｄ．{5,9,17,21,23,25,30}44．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（B）。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)45．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（A）A．每次分区后，先处理较短的部分B．每次分区后，先处理较长的部分C．与算法每次分区后的处理顺序无关D．以上三者都不对46．当n个整型数据是有序时，对这n个数据用快速排序算法排序，则时间复杂度是(6)，当用递归算法求n!时，算法的时间复杂度是(7)，则：(6)-(7)=（C）A.O(n)B.O(nlogn)C.O(n*n)D.O(logn)47．快速排序在最坏情况下的时间复杂度是(B),比(D)的性能差。A．O(NlogN)B．O(N2)C．O(N3)D．堆排序E．冒泡排序F．选择排序48.快速排序方法在（D）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序49．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D）位置上。A．n/2B．n/2-1C．1D．n/2+2【中科院计算所2000一、4（2分）】50.以下序列不是堆的是(D)。A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)51．下列四个序列中，哪一个是堆（C）。【北京工商大学2001一、8（3分）】A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1552.堆排序是（E）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（G）A.插入B.交换C.归并D.基数E.选择F.O（n2）和O（1）G.O（nlog2n）和O（1）H.O（nlog2n）和O（n）I.O（n2）和O（n）53．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（B）。A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)54．对n个记录的文件进行堆排序，最坏情况下的执行时间是多少？（C）A．O（log2n）B．O（n）C．O（nlog2n）D．O（n*n）55.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（C）A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。56.归并排序中，归并的趟数是(B)。A．O（n）B．O(logn)C．O(nlogn)D．O(n*n)57．在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫(B)A．插入排序B．枚举排序C．选择排序D．交换排序58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（A）A．堆排序〈快速排序〈归并排序B．堆排序〈归并排序〈快速排序C．堆排序〉归并排序〉快速排序D．堆排序快速排序归并排序E．以上答案都不对59．排序方法有许多种，C法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，