第六章_排序练习

第10章排序一、选择题1．某内排序方法的稳定性是指()。A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对2．下面给出的四种排序法中()排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆积3．下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序B．归并排序C．冒泡排序）。8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。A．直接插入B．直接选择C．堆D．快速E．基数9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序11．下列内部排序算法中：A．快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（B）（4）排序的平均时间复杂度为O(n•logn)的算法是（）为O(n•n)的算法是（）12．排序趟数与序列的原始状态有关的排序方法是()排序法。A．插入B.选择C.冒泡D.快速13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。()A．选择排序法B.插入排序法C.快速排序法D.堆积排序法14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是()。A．直接插入B.二分法插入C.快速排序D.归并排序15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A．直接插入排序B.气泡排序C.快速排序D.直接选择排序16．比较次数与排序的初始状态无关的排序方法是()。A．直接插入排序B．起泡排序C．快速排序D．简单选择排序17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。A．选择排序B.冒泡排序C.插入排序D.堆排序18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的()的两趟排序后的结果。A.快速排序B.冒泡排序C.选择排序D.插入排序19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A.选择B.冒泡C.快速D.插入23．下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆24．下列序列中，（）是执行第一趟快速排序后所得的序列。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．下面的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，2037.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（）。A.选择B.冒泡C.插入D.堆38．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。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．直接插入排序在最好情况下的时间复杂度为（）A．O(logn)B．O(n)C．O(n*logn)D．O(n2)40.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。A.3B.10C.15D.2552.堆排序是（）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（）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）58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A．堆排序〈快速排序〈归并排序B．堆排序〈归并排序〈快速排序C．堆排序〉归并排序〉快速排序D．堆排序快速排序归并排序E．以上答案都不对59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。（1）--（5）:A．选择排序B．快速排序C．插入排序D．起泡排序E．归并排序F．shell排序G．堆排序H．基数排序三、填空题1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的___。4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。5.不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。22．堆是一种有用的数据结构.堆排序是一种_(1)_排序，堆实质上是一棵_(2)_结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_，所需的附加存储结点是_(4)_。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_(5)_。四、应用题2.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。第10章排序（参考答案）一、选择题1.D2.D3.D4.B5.B6.B7.C,E8.A9.C10.C,D,F11.1D,C11.2A,D,F11.3B11.4(A,C,F)(B,D,E)12.C,D13.A14.B,D15.D16.D17.C18.A19.A20.C21.C22.B23.C24.C25.A26.C27.D28.C29.B30.C,B31.D32.D33.A34.D35.A36.A37.A38.C39.B40.C41.C42.B43.A44.B45.A46.C47.B,D48.D49.D50.D51.C52.E,G53.B54.C55.C56.B57.B58.A59.1C59.2A59.3D59.4B59.5G60.1B60.2C60.3A61.1B61.2D61.3B61.4C61.5F62.A63.A64.B65.A66.A部分答案解释如下：18.对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。20.本题为步长为3的一趟希尔排序。24.枢轴是73。49.小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。64.因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。二、填空题1.比较,移动2.生成有序归并段（顺串）,归并3.希尔排序、简单选择排序、快速排序、堆排序等4.冒泡,快速5.(1)简单选择排序(2)直接插入排序（最小的元素在最后时）22.(1)选择(2)完全二叉树(3)O(Nlog2N)(4)O(1)(5)满足堆的性质三、应用题2.排序方平均时间最坏情况辅助空间稳定不稳定排序举例法性直接插入排序O（n2）O（n2）O（1）稳定折半插入排序O（n2）O（n2）O（1）稳定二路插入排序O（n2）O（n2）O（n）稳定表插入排序O（n2）O（n2）O（1）稳定起泡排序O（n2）O（n2）O（1）稳定直接选择排序O（n2）O（n2）O（1）不稳定2,2’,1希尔排序O（n1.3）O（n1.3）O（1）不稳定3,2,2’,1(d=2,d=1)快速排序O（nlog2n）O（n2）O（log2n）不稳定2,2’,1堆排序O（nlog2n）O（nlog2n）O（1）不稳定2,1,1’(极大堆)2-路归并排序O（nlog2n）O（nlog2n）O（n）稳定基数排序O(d*(rd+n))O(d*(rd+n))O(rd)稳定