数据结构第10章 习题答案.doc

A. 堆排序,冒泡排序 B. 快速排序,堆排序
C. 直接选择排序,归并排序 D. 归并排序,冒泡排序
(15,9,7,8,20,-1,7,4) 用快速排序的划分方法进行一趟划分后数据的排序为( A )(按递增序)。
,C,D都不对。 ,7,8,4,-1,7,15,20
,15,8,9,7,-1,4,7 D. 9,4,7,8,7,-1,15,20
,在每一趟都能选出一个元素放到其最终位置上,并且其时间性能受数据初始特性影响的是:( B )。
A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序
,用( D )方法最快。

,然后将其放在已排序序列的合适位置,该排序方法称为( A )排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并
6. 在排序算法中,每次从未排序的记录中挑出最小(或最大)关键码字的记录,加入到已排序记录的末尾,该排序方法是( A )。
A. 选择 B. 冒泡 C. 插入 D. 堆
7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进行( C )次比较。
A. 3 B. 10 C. 15 D. 25
8. 对序列{15,9,7,8,20,-1,4,} 用希尔排序方法排序,经一趟后序列变为{15,-l,4,8,20,9,7}则该次采用的增量是( B )
A. l B. 4 C. 3 D. 2
9. 堆排序是( E )类排序
A. 插入 B. 交换 C. 归并 D. 基数 E. 选择
,(1)法从未排序的序列中依次取出元素,与已排序序列(初始时为空)中的元素作比较,将其放入已排序序列的正确位置上;(2)法从未排序的序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端; 交换排序方法是对序列中的元素进行一系列比较,当被比较的两元素逆序时,进行交换;(3)和(4)是基于这类方法的两种排序方法, 而(4)是比(3)效率更高的方法;(5)法是基于选择排序的一种排序方法,是完全二叉树结构的一个重要应用。
(1)--(5):

5 2A 3D 4B 5G
,则在排序过程中,主要进行的两种基本操作是关键字的__
____和记录的_____。比较,移动
,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的是_____算法,最费时间的是______算法。冒泡,快速
3. 设用希尔排序对数组{98,36,-9,0,47,23,1,8,10,7}进行排序,给出的步长(也称增量序列)依次是4,2,1则排序需__________趟,写出第一趟结束后,数组中数据的排列次序__________。3,(10,7,-9,0,47,23,1,8,98,36)
(28,07