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

1 .下列排序算法中,其中( D )是稳定的。 A. 堆排序,冒泡排序 B. 快速排序,堆排序 C. 直接选择排序,归并排序 D. 归并排序,冒泡排序 2 .有一组数据( 15,9,7,8, 20, -1,7,4) 用快速排序的划分方法进行一趟划分后数据的排序为(A) (按递增序)。 A .下面的 B,C,D 都不对。 ,7,8,4, -1,7, 15, 20 C. 20, 15,8,9,7, -1,4,7 ,4,7,8,7, -1, 15, 20 3. 下列排序算法中, 在每一趟都能选出一个元素放到其最终位置上, 并且其时间性能受数据初始特性影响的是:( B )。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 4 .如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列,用(D )方法最快。 A .起泡排序 B .快速排列 C. Shell 排序 D .堆排序 E .简单选择排序 5 .从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为(A) 排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并 6. 在排序算法中,每次从未排序的记录中挑出最小(或最大)关键码字的记录,加入到已排序记录的末尾,该排序方法是( A)。 A. 选择 B. 冒泡 C. 插入 7. 若用冒泡排序方法对序列{10,14,26,29,41,52} 从大到小排序, 需进行(C) 次比较。 B. 10 C. 15 D. 25 8. 对序列{15 ,9,7,8, 20, -1,4,} 用希尔排序方法排序, 经一趟后序列变为{15 , -l, 4,8, 20,9, 7} 则该次采用的增量是(B) 9. 堆排序是( E )类排序 A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 10. 排序方法有许多种,(1) 法从未排序的序列中依次取出元素, 与已排序序列( 初始时为空) 中的元素作比较, 将其放入已排序序列的正确位置上;(2) 法从未排序的序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端; 交换排序方法是对序列中的元素进行一系列比较,当被比较的两元素逆序时,进行交换;(3)和(4) 是基于这类方法的两种排序方法,而(4) 是比(3) 效率更高的方法;(5) 法是基于选择排序的一种排序方法, 是完全二叉树结构的一个重要应用。(1) --(5):A .选择排序 B .快速排序 C .插入排序 D .起泡排序 E .归并排序 F. shell 排序 G .堆排序 H .基数排序 5 2A 3D 4B 5G 1 .若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的__ ____ 和记录的_____ 。比较, 移动 2 .分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的是_____ 算法,最费时间的是______ 算法。冒泡, 快速 3. 设用希尔排序对数组{98 , 36, -9,0, 47, 23,1,8, 10, 7} 进行排序, 给出的步长(也称增量序列)依次是 4,2,1 则排序需__________ 趟,写出第一趟结束后,数组中