内部排序练习课件.ppt

内部排序练习;一、选择题; 2.设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数是 （　　　）。 A．6　　　　　　　 B．7　　　　　　　 C．8 D．20 ; 3.将5个不同的数据进行排序，至少需要比较 （ ）次，至多需要比较（　　　）次。 A．4 B．5 C．6 D．7 E．8 F．9 G．10 H．11 ;4.下列排序算法中不稳定的有（　　 　）。 A．直接选择排序 　　　　　　 B．直接插入排序 C．冒泡排序　　　　　　　　　D．二叉排序 E．Shell排序　　　　　　　　　F．快速排序 G．归并排序　　　　　　　　　H．堆排序 I．基数排序 ;5.内部排序多个关键字的文件，最坏情况下最块的排序方法是（　　　），相应的时间复杂度为（　　　），该算法是 （　　　）排序方法。 A．快速排序　　　　B．插入排序　　C．归并排序　　　　 D．简单选择排序 E．O(nlog2 n)　　　　F．O(n2)　　　　G．O(n2log2 n) H．O(n) I．稳定　　　　　　 J．不稳定 ; 6.在文件“局部有序”（待排序元素序列基本有序）的情况下，最佳内部排序算法是（　　　）。 A．直接插入排序　　　　　　　　　B．冒泡排序 C．直接选择排序　　　　　　　　　D．基数排序 ; 7.对初始状态为递增的表按递增顺序排序，最省时间的是（　　　）算法，最费时间的是（　　　）算法。 A．堆排序　　　　B．快速排序　　C．插入排序　　　D．归并排序 ;8.下述几种排序方法中，要求内存量最大的是（　　　）。 A．插入排序　　　B．选择排序　　　　C．快速排序　　　D．归并排序 ; 9.在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （　　　）。 A．希尔排序 B．冒泡排序 C．插入排序 D．选择排序 ; 10.下列排序中，排序速度与数据的初始排列状态没有关系的有（　　　）。 A．直接选择排序　B．基数排序　　　　C．堆排序　　　　D．直接插入排序 ; 11.排序趟数与数据的原始状态无关的排序方法是（　　　）排序法。 A．希尔　　　　　B．选择　　　　　　C．冒泡　　　　　D．快速 ; 12.若需在O(nlog2 n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（　　　）。 A．快速排序　　B．堆排序　　C．归并排序　　D．直接插入排序 ;13.排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（　　　）。 A．希尔排序　　　B．冒泡排序　　　　C．插入排序　　　D．选择排序 ;14.每次把待排序的元素划分为左、右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间元素的关键字均大于基准元素的关键字，则此排序方法叫做（　　　）。 A．堆排序　　　　B．快速排序　　　　C．冒泡排序　　　D．Shell排序 ;15.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（　　　）。 A．希尔排序　　　B．归并排序　　　　C．插入排序　　　D．选择排序 ;16.用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下： （1）（25，84，21，47，15，27，68，35，20） （2）（20，15，21，25，47，27，68，35，84） （3）（15，20，21，25，35，27，47，68，84） （4）（15，20，21，25，27，35，47，68，84） 则所采用的排序方法是（　　　）。 A．选择排序　　　 B．希尔排序　　　　C．归并排序　　　　 D．快速排序 ;17.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（　　）；从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（　　　）；依次将每两个相邻的有序表合并成一个有序表的排序方法叫做（　　　）；当两个元素比较出现反序时（即逆序）就相互交换位置的排序方法叫做（　　　）。 A．归并排序　　　 B．选择排序　　　C．交换排序　　 D．插入排序 ;18.一组记录的关键字为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为