数据结构作业：第10章排序答案.docx

第9章排序
一、填空题(每空1分，共24分)1.

1.
大多数排序算法都有两个基本的操作：比较
和 移动

2.
在对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序时，当把第7个记录60插
入到有序表时，为寻找插入位置至少需比较次。
3.
在插入和选择排序中，若初始数据基本正序，则选用
4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 无序，则最好选用快速排序°
:若初始记录基本
5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是也当
排序，在最坏的情况下所需要的时间是 。
6. 对于n个记录的集合进行归并排序，所需要的平均时间是_ O(nlg2n)
是()(n)o
O若对其进行快速
,所需要的附加空间
8,设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母序的升序重新排列，则: 冒泡排序一趟扫描的结果是_HCOPAMSRDFXY :
初始步长为4的希尔(shell)排序一趟的结果是PACSOHFXRDMY ；
二路归并排序一趟扫描的结果是HOCYAPMSDRFX； 快速排序_趟扫描的结果是FHCDPAMORSYX : 堆排序初始建堆的结果是ADCRFOMSYPHX。
二、单项选择题(每小题1分，共18分)
)1.排序方法中，从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比 较，将其放入已排序序列的正确位置上的方法，称为
A.希尔排序B.冒泡排序
c.插入排序
D.选择排序
)2.快速排序在下列哪种情况下最易发挥其长处。 被排序的数据中含有多个相同排序码 B. 被排序的数据完全无序D.
A. C.
被排序的数据已基本有序
被排序的数据中的最大值和最小值相差悬殊
3.
A. O(n)
对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是
B. O(n2) C. O(nlog2ii) D. O(n3)
4.若一组记录的排序码为(46,79,56,38,40,84),则利用快速排序的方法，以第一个记录为基 准得到的一次划分结果为
A.38, 40,
C,40, 38,
46,
46,
56, 79, 84
56, 79, 84
B.
D.
40,38, 46, 79, 56, 84
40, 38,46, 84, 56, 79
5.堆是一种.
A.插入
,排序。
B.选择
C.交换
D.归并

(C ) 6.堆的形状是一棵C.完全二叉树
C.完全二叉树

C.完全二叉树
D.平衡二叉树
A.二叉排序树B.满二叉树
(B ) 7.若一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为A .79,46, 56,38, 40, 84B. 84, 79, 56, 38,40,46C. 84, 79, 56,46, 40, 38D. 84, 56, 79, 40,46,38（C ） 8.下述几种排序方法中，要求内存最大的是
D.选择排序
A.插入排序B.快速排序C.归并排序9.对关键字序列（56,23,78,92,88,67,19,34）进行增量为3的一趟希尔排序的结果为（D ）。
A)( 19,23,56,34,78,67,88,92)
B) 23,56,78,66,88,92,19,34)
0(19,23,34,56,67,78,88,92)
0(19,23,34,56,67,78,88,92)

0(19,23,34,56,67,78,88,92)
D) (19,23,67,56,34,78,92,88)

10.排序算法中，不稳定的排序是（

A）直接插入排序B）冒泡排序C）堆排序
D）选择排序