第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序 B．直接选择排序 C．堆排序 D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。

A．插入排序 B．冒泡排序 C．选择排序 D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C． O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序 B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度 D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)8、设待排序关键码序列为（25、18、9、33、67、82、53、95、12、70），要按关键码值递增的顺序排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码表33被放到了第几个位置（D）。

A．3 B．5 C．7 D．99．若对一个已经排好了序的序列进行排序，在下列四方法中，哪种方法比较好（C）。

A．冒泡排序法 B．直接选择排序法 C．直接插入排序法 D．堆排序法10．快速排序的时间复杂度是（A）A．O(nlog2n) B．O(n2) C． O(n3) D．O(log2n)11．以下关键字序列用快速排序法进行排序，速度最慢的是（C）A．{23，27，7，19，11，25，32} B．{23，11，19，32，27，35，7}C．{7，11，19，23，25，27，32} D．{27，25，32，19，23，7，11}12．在所有排序方法中，关键码比较的次数与记录的初始排序次序无关的是（D）。

A．希尔排序 B．冒泡排序 C．直接插入排序 D．直接选择排序13．用冒泡排序算法对下列数据12，37，42，19，27，35，56，44，10进行从小到大排序，在将最大的数“沉”到最后时，数的顺序是（C）。

A．12，37，42，19，27，35，44，10，56 B．12，37，42，19，27，35，10，44，56C．12，37，19，27，35，42，44，10，56 D．10，12，19，27，35，37，42，44，5614．快速排序方法在（C）情况下最不利于发挥其长处。

A．被排序的数据量太大 B．被排序的数据中含有多个相同值C．排序数据已基本有序 D．被排序数据的数目为奇数15．具有12个记录的序列，采用冒泡排序最少的比较次数是（C）。

A．1 B．144 C．11 D．6616．若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，其要进行（C）次比较。

A．33 B．45 C．70 D．9114 6 18 8 12 16 27 10 26 47 29 41 24 52 比13次6 14 8 12 16 18 10 26 27 29 41 24 47 比12次6 8 12 14 16 10 18 26 27 29 24 41 比11次6 8 12 14 10 16 18 26 27 24 29 比10次6 8 12 10 14 16 18 26 24 27 比9次6 8 10 12 14 16 18 24 26 比8次6 8 10 12 14 16 18 24 比7次17．在任何情况下，快速排序方法的时间性能总是最优的这种说法（B）。

A．正确 B．错误18．排序的重要目的是为了以后对已排序的数据元素进行（C）。

A．打印输出 B．分类 C．查找 D．合并19．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（D）A．n2 B．nlog2n C．log2n D．n-120．用10万个无序且互不相等的正整数序列，采用顺序列存储方式组织，希望能最快地找出前10个最大的正整数，采用（D）方法较好。

A．快速排序 B．shell排序 C．选择排序 D．堆排序21．下面四种排序方法中，平均查找长度最小的是（C）。

A．插入排序 B．选择排序 C．快速排序 D．堆排序22．在文件局部有序或文件长度较小的情况下，最佳的排序方法是（A）A．直接插入排序 B．冒泡排序 C．简单选择排序 D．都不对23．若用某种排序（分类）方法对线性表（25，48，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 2125 35 27 47 68 84；（4）15 20 21 25 27 35 47 68 84。

那么，所采用的排序方法是（D）。

A．选择排序 B．希尔排序 C．堆排序 D．快速排序24．快速排序在最坏的情况下的时间复杂度是（B）。

A．O(nlog2n） B．O(n2) C．O(n3) D．都不对25．若待排序列已基本有序，要使它完全有序，从关键码比较次数的移动次数和移动次数考虑，应当使用的排序方法是（B）。

A．堆排序 B．直接插入排序 C．直接选择排序 D．快速排序26．已知一个单链表中有3000个结点，每个结点存放一个整数（A）可用于解决这3000个整数的排序问题且不需要对算法做大的变动。

A．直接插入排序方法 B．简单选择排序方法 C．快速排序方法 D．堆排序方法27．设有1000个无序的元素，希望用最快的速度挑选出其中10个最大的元素，最好的方法是（C）。

A．起泡排序 B．快速排序 C．堆排序 D．基数排序28．在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。

A．插入排序 B．选择排序 C．快速排序 D．堆排序29．一组记录的排序码为（46，79，56，38，40，84）。

则利用堆排序的方法，建立的初始堆为(B)。

A．79，46，56，38，40，84 B．84，79，56，38，40，46C．84，79，56，46，40，38 D．84，56，79，40，46，3830．一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。

A．38,40,46,56,79,84 B．40,38,46,79,56,84 C．40,38,46,56,79,84 D．40,38,46,84,56,7931．排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法称为（D）。

A．希尔排序 B．起泡排序 C．插入排序 D．选择排序32．排序方法中，从未排序序列中挑选元素，并将其放入已排序序列（初始为空）的一端的方法，称为（D）。

A．希尔排序 B．起泡排序 C．插入排序 D．选择排序33．对5个不同的数排序至少需要比较（A）次。

A．4 B．5 C．6 D．734．一个序列中有若干个元素，若只想得到其中第i个元素之前的部分排序，最好采用（C）排序方法。

A．快速排序 B．堆排序 C．插入排序 D．shell排序35．对一组记录的关键码{46，79，56，38，40，84}采用堆，则初始化堆后最后一个元素是（BA）。

A．84 B．46 C．56 D．3836．在供选择的答案中填入正确答案：(1)排序（分类）的方法有许多种：③法从未排序序列中依次取出元素，与排序序列中的元素作比较，将其放入已排序列的正确位置上；①法从未排序序列中挑选元素，并将其依次放入已排序序的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。

供选择答案①选择排序②快速排序③插入排序④冒泡排序(2)一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。

A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79(3)下列排序算法中， C 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。

A、堆排序B、冒泡排序C、快速排序D、SHELL 排序二、填空题1．对下列两个表：L1=（55，61，68，70，75，65，78，81，93，98，84），L2=（75，70，65，84，98，78，93，55，61，81，68），使用简单选择排序和直接插入排序两种方法进行排序，哪一种方法对两个表排序所花费的时间相同（简单选择排序）。

2．目前内部排序的时间复杂度T(n)的范围是（O(nLogn)至O(n2)）。

3．内部排序将待排序的记录放在（计算机随机存储器）中进行排序，按排序过程中工作量来区分，可分为（简单的排序方法）、（先进的排序方法）和（基数排序）三类。

4．对n个元素进行起泡排序时，最少的比较次数是（n-1）。

5．在堆排序和快速排序中，若原始记录接近正序或反序，则选用（堆排序）。

若原始记录无序，则选用（快速排序）。

6．在插入排序和选择排序中，若初始数据基本正序，则选用(插入排序)，若数据基本反序,则选用(选择排序)。

7．在插入排序、希尔排序、选择排序、冒泡排序、快速排序、堆排序中，排序是不稳定的有（希尔排序、快速排序、堆排序）。