数据结构之内排序

第十章 排序

一、选择题

1．下列内部排序算法中：

A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 冒泡排序 F. 堆排序

（1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ） （3）排序的平均时间复杂度为O(n?logn)的算法是（ ）为O(n?n)的算法是（ ） 2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序 3．对一组数据（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. 选择 B. 冒泡 C. 快速 D. 插入

4．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。

A. 选择 B. 快速 C. 希尔 D. 冒泡

5．对序列{15，9，7，8，20，-1，4}进行排序，经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（ ）排序。

A．选择 B. 堆 C. 直接插入 D. 冒泡

6．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序

7．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择 B. 冒泡 C. 归并 D. 堆

8．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。

A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 4，9，7，8，7，-1，15，20 9．一组记录的关键码为（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) 10. 在下面的排序方法中，辅助空间为O（n）的是( ) 。

A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序

二、填空题

1、在内排序的过程中,通常需要对待排序的关键码进行扫描,采用不同重新排序方法,会产生不同的排序中间结果。设要将序列中的关键码按字母序的升序排列，则( 1 )是冒泡排序一趟扫描的结果,( 2 )是初始步长为4的希尔(SHELL)排序一趟扫描的结果,( 3 ) 是归并排序一趟扫描的结果,( 4 )是以第一个元素为分界元素的快速排序一趟扫描的结果,( 5 )是堆排序初始建堆的结果。

1-5: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

2．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。

3. 外排序的基本操作过程是_______和_______。 4. 属于不稳定排序的有__________。

4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。 三、应用题

1已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。

(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 (2) 输出最小值后，如何得到次小值。（并画出相应结果图）

2. 给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？

第十章 内排序 答案

一、选择题

1、1.CD 2.ADF 3.(ADF) (BCE) 2-5 DACC 6-10 BCDCD 二、填空题 1．（1）h,c,q,p,a,m,s,r,d,f,x,y （2）p,a,c,s,q,d,f,x,r,h,m,y （3）h,q,c,y,a,p,m,s,d,r,f,x （4）f,h,c,d,p,a,m,q,r,s,y,x （5）a,d,c,r,f,q,m,s,y,p,h,x 2. 比较,移动

3. 生成有序归并段（顺串）,归并

4. 希尔排序、简单选择排序、快速排序、堆排序 5．冒泡、快速 三、应用题 1、(1)建小堆

61 503

87 170 87 512 275 462 512 897 61 908 170 897

503 653 908 275 653 462

(2) 求次小值 87 908

275 170 87 170

275 503 653 462 61 512897 503 908 653 61 462 512 897 2、一趟快速排序：22,19,13,6,24,38,43,32 初始大堆：43,38,32,22,24,6,13,19

二路并归：第一趟：19,24,32,43,6,38,13,22 第二趟：19,24,32,43,6,13,22,38 第三趟：6,13,19,22,24,32,38,43

堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差。