发布时间 : 星期六 文章绗崄绔?鎺掑簭 - 鐧惧害鏂囧簱更新完毕开始阅读
第10章 排序 一、选择题
1．某内排序方法的稳定性是指( D )。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 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个元素后即呈有序，k< （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） 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.插入 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，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 26．一组记录的关键码为（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,69 B． 32,40,21,46,69,94,90,80 C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40 39．直接插入排序在最好情况下的时间复杂度为（ B ） 2 A． O(logn) B． O(n) C．O(n*logn) D． O(n) 40.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ C ）次比较。 A. 3 B. 10 C. 15 D. 25 41.采用简单选择排序，比较次数与移动次数分别为( 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. l B. 4 C. 3 D. 2 43．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（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 )的性能差。 23 A．O(NlogN) B．O(N) C．O(N) D．堆排序E．冒泡排序F．选择排序 48.快速排序方法在（ D ）情况下最不利于发挥其长处。 A.要排序的数据量太大 B.要排序的数据中含有多个相同值 C.要排序的数据个数为奇数 D.要排序的数据已基本有序 49．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ D ）位置上。 A．?n/2? B．?n/2? -1 C．1 D．?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,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 52.堆排序是（ E）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（G） A.插入 B.交换 C.归并 D.基数 E.选择 2 F. O（n）和O（1） G. O（nlog2n）和O（1） 2 H. O（nlog2n）和O（n） I. O（n）和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，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．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法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；A法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；D和B是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；G法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序 E．归并排序 F．shell排序 G．堆排序 H．基数排序 60．设要将序列（q,h,c,y,p,a,m,s,r,d,f,x） 中的关键码按字母升序重新排序， （1）（ B）是初始步长为4的shell排序一趟扫描的结果； （2）（ C）是对排序初始建堆的结果； （3）（ A）是以第一个元素为分界元素的快速一趟扫描的结果。 从下面供选择的答案中选出正确答案填入括号内。 A. f ,h ,c ,d ,p ,a ,m ,q ,r ,s ,y ,x B. p ,a ,c ,s ,q ,d ,f ,x ,r ,h ,m ,y C. a ,d ,c ,r ,f ,q ,m ,s ,y ,p ,h ,x D. h ,c ,q ,p ,a ,m ,s ,r ,d ,f ,x ,y E. h ,q ,c ,y ,a ,p ,m ,s ,d ,r ,f ,x 61．对由n个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别是:二路归并排序为( B ),直接插入排序为(D ),快速排序为( B ),其中,归并排序和快速排序所需要的辅助存储分别是( C)和( F)。 22 1-5:A. O(1) B. O（nlog2n） C. O（n） D. O（n） E. O（n(log2n)） F. O（log2n） 62．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是( A ) A．N B．2N-1 C．2N D．N-1 63.基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（ A ）。 A. O(nlogn) B. O(logn) C. O(n) D. O(n*n) 64．已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ B ）。 A. O(nlog2n) B. O(nlog2k) C. O(klog2n) D. O(klog2k) 65．采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k（ A） A． 有关 B． 无关 66．采用败者树进行K路平衡归并时，总的（包括访外）归并效率与K（ A ）。 A．有关 B．无关 二、判断题： 1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ T ） 2．内排序要求数据一定要以顺序方式存储。（ F ） 3．排序算法中的比较次数与初始元素序列的排列无关。（F） 4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ F ） 5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（F ） 6．直接选择排序算法在最好情况下的时间复杂度为O（N）。（ F） 7．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（F） 8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（ F ） 9．在待排数据基本有序的情况下，快速排序效果最好。（ F ） 10．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（ F ） 11．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ F ） 12．堆肯定是一棵平衡二叉树。（ F ） 13．堆是满二叉树。（ F ） 14．（101，88，46，70，34，39，45，58，66，10）是堆。（ T） 15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ T ） 16．堆排序是稳定的排序方法。（ F ） 17．归并排序辅助存储为O（1）。（ F ） 18．在分配排序时，最高位优先分配法比最低位优先分配法简单。（ F） 19． 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快 n 速排序算法的最坏时间复杂性是O(nlog2),所以快速排序比冒泡排序算法效率更高。（ F ） 20．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n） ，而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。（ F ） 21．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（ F ） 22．在任何情况下，归并排序都比简单插入排序快。（ F ） 23．归并排序在任何情况下都比所有简单排序速度快。（ F ） 24．快速排序总比简单排序快。（ F ） 25.中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（ T ） 26．外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( F ) 27．在外部排序时，利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录。( T ) 28．为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。( F ) 29．排序速度，进行外排序时，必须选用最快的内排序算法。( F ) 30．在完成外排序过程中，每个记录的I/O次数必定相等。( F) 31．影响外排序的时间因素主要是内存与外设交换信息的总次数。(T ) 三、填空题 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较__和记录的_移动_。 2.外排序的基本操作过程是_生成有序归并段_和__归并__。