15()方法是从未排序序列中挑选元素,并将其依次放入已排序序列的一端。 ①归并排序 ②插入排序 ③快速排序 ④选择排序 16.()方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位 置上 ①归并排序 ②插入排序 ③快速排序 ④选择排序 17.将上万个一组无序并且互不相等的正整数序列,存放于顺序存储结构中,采用() 方法能够最快地找出其中最大的正整数 ①快速排序 ②插入排序 ③选择排序 ④归并排序 18一般情况下,以下四种排序方法中,平均查找长度最小的是 ①归并排序 ②快速排序 ③选择排序 ④插入排序 19.以下四种排序方法中,要求附加的内存容量最大的是 插入排序 ②选择排序 ③快速排序 ④归并排序 20已知一个链表中有3000个结点,每个结点存放一个整数,( 可用于解决这3000个 整数的排序问题且不需要对算法作大的变动。 ①直接插入排序法 ②简单选择排序方法 ③快速排序方法 ④堆排序方法 21.若用冒泡排序法对序列(18,14,6,27,8,12,16,52,10,26,47,29,41,24) 从小到大进行排序,共要进行()次比较。 ②45 370 ④91 2.在任何情况下,快速排序方法的时间性能总是最优的。这种说法 ①正确 ②错误 23.对一个由n个整数组成的序列,借助排序过程找出其中的最大值,希望比较次数和移动 次数最少,应选用()方法 ①归并排序 ②直接插入排序 ③直接选择排序 ④快速排序 四、简答及应用 1.对于给定的一组键值:83,40,63,13,84,35,96,57,39,79,61,15,分别画出应 用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟 的结果 2.举例说明本章介绍的各排序方法中那些是不稳定的? 3.相对于树形选择排序,直接选择排序和堆排序有何优点? 4.试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。 5.判断下列两序列是否为堆?如不是,按照建堆的思想把它调整为堆,并用图表示建堆的过 (1)(3,10,12,22,36,18,28,40); (2)(5,8,11,15,23,20,32,7)。 6.对于下列一组关键字46,58,15,45,90,18,10,62,试写出快速排序每一趟的排序结 果,并标出每一趟中各元素的移动方向。 7.已知数据序列为(12,5,9,20,6,31,24),对该数据序列进行排序,试写出插入排序 和冒泡排序每趟的结果 五、算法设计 1.设计一个用链表表示的直接选择排序算法。 2.写出非递归调用的快速排序算法。 3.插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的15（ ）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 ①归并排序 ②插入排序 ③ 快速排序 ④选择排序 16．（ ）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位 置上。 ①归并排序 ②插入排序 ③快速排序 ④选择排序 17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（ ） 方法能够最快地找出其中最大的正整数。 ①快速排序 ②插入排序 ③ 选择排序 ④ 归并排序 18 一般情况下，以下四种排序方法中，平均查找长度最小的是 （ ） ①归并排序 ②快速排序 ③选择排序 ④插入排序 19．以下四种排序方法中，要求附加的内存容量最大的是 （ ） ①插入排序 ②选择排序 ③快速排序 ④归并排序 20 已知一个链表中有 3000 个结点，每个结点存放一个整数，（ ）可用于解决这 3000 个 整数的排序问题且不需要对算法作大的变动。 ①直接插入排序法 ②简单选择排序方法 ③快速排序方法 ④堆排序方法 21．若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24） 从小到大进行排序，共要进行（ ）次比较。 ①33 ②45 ③70 ④91 22．在任何情况下，快速排序方法的时间性能总是最优的。这种说法 ①正确 ②错误 23．对一个由 n 个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动 次数最少，应选用（ ）方法。 ①归并排序 ②直接插入排序 ③直接选择排序 ④快速排序。 四、简答及应用 1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应 用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟 的结果。 2．举例说明本章介绍的各排序方法中那些是不稳定的？ 3．相对于树形选择排序，直接选择排序和堆排序有何优点？ 4．试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。 5．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过 程。 （1）（3，10，12，22，36，18，28，40）； （2）（5，8，11，15，23，20，32，7）。 6．对于下列一组关键字 46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结 果，并标出每一趟中各元素的移动方向。 7．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序 和冒泡排序每趟的结果。 五、算法设计 1． 设计一个用链表表示的直接选择排序算法。 2． 写出非递归调用的快速排序算法。 3． 插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的