数据结构Ch10习题答案

1、.第十章 内部排序一、择题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

2、，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;i0&Ajx) Aj+1=Aj; j-;Aj+1=x3这一段代码所描述的排序方法称作（A）。 A插入排序 B冒泡排序 C选择排序 D快速排序4这一段代码所描述的排序方法的平均执行时间为（D） AO(log2n) BO(n) C O(nlog2n) DO(n2)5假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B

3、）。 AO(log2n) BO(n) CO(nlog2n) DO(n2)6在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。A左、右两个子表都已各自排好序 B左边子表中的元素都不大于右边子表中的元素C左边子表的长度小于右边子表的长度 D左、右两个子表中元素的平均值相等7对n个记录进行堆排序，最坏情况下的执行时间为（C）。 AO(log2n) BO(n) CO(nlog2n) DO(n2)8、设待排序关键码序列为（25、18、9、33、67、82、53、95、12、70），要按关键码值递增的顺序排序，采取以第一个关键码为分界元素的快速排序法，

4、第一趟排序完成后关键码表33被放到了第几个位置（D）。 A3 B5 C7 D99若对一个已经排好了序的序列进行排序，在下列四方法中，哪种方法比较好（C）。A冒泡排序法 B直接选择排序法 C直接插入排序法 D堆排序法10快速排序的时间复杂度是（A） AO(nlog2n) BO(n2) C O(n3) DO(log2n)11以下关键字序列用快速排序法进行排序，速度最慢的是（C）A23，27，7，19，11，25，32 B23，11，19，32，27，35，7C7，11，19，23，25，27，32 D27，25，32，19，23，7，1112在所有排序方法中，关键码比较的次数与记录的初始排序次序无

5、关的是（D）。A希尔排序 B冒泡排序 C直接插入排序 D直接选择排序13用冒泡排序算法对下列数据12，37，42，19，27，35，56，44，10进行从小到大排序，在将最大的数“沉”到最后时，数的顺序是（C）。 A12，37，42，19，27，35，44，10，56 B12，37，42，19，27，35，10，44，56C12，37，19，27，35，42，44，10，56 D10，12，19，27，35，37，42，44，5614快速排序方法在（C）情况下最不利于发挥其长处。A被排序的数据量太大 B被排序的数据中含有多个相同值C排序数据已基本有序 D被排序数据的数目为奇数15具有12个记录

6、的序列，采用冒泡排序最少的比较次数是（C）。 A1 B144 C11 D6616若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，其要进行（C）次比较。 A33 B45 C70 D9114 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 1

7、8 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） An2 Bnlog2n Clog2n Dn-120用10万个无序且互不相等的正整数序列，采用顺序列存储方式组织，希望能最快地找出前10个最大的正整数，采用（D）方法较好。 A快速排序 Bshell排序 C选择排

8、序 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 21 25 35 27 47 68 84；（4）15 20 21 25 27 35 47 68 84。那么，

9、所采用的排序方法是（D）。 A选择排序 B希尔排序 C堆排序 D快速排序24快速排序在最坏的情况下的时间复杂度是（B）。 AO(nlog2n） BO(n2) CO(n3) D都不对25若待排序列已基本有序，要使它完全有序，从关键码比较次数的移动次数和移动次数考虑，应当使用的排序方法是（B）。A堆排序 B直接插入排序 C直接选择排序 D快速排序26已知一个单链表中有3000个结点，每个结点存放一个整数（A）可用于解决这3000个整数的排序问题且不需要对算法做大的变动。A直接插入排序方法 B简单选择排序方法 C快速排序方法 D堆排序方法27设有1000个无序的元素，希望用最快的速度挑选出其中10个

10、最大的元素，最好的方法是（C）。A起泡排序 B快速排序 C堆排序 D基数排序 28在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。A插入排序 B选择排序 C快速排序 D堆排序29一组记录的排序码为（46，79，56，38，40，84）。则利用堆排序的方法，建立的初始堆为(B)。A79，46，56，38，40，84 B84，79，56，38，40，46 C84，79，56，46，40，38 D84，56，79，40，46，3830一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。A38,40,46,56,

11、79,84 B40,38,46,79,56,84 C40,38,46,56,79,84 D40,38,46,84,56,7931排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法称为（D）。 A希尔排序 B起泡排序 C插入排序 D选择排序 32排序方法中，从未排序序列中挑选元素，并将其放入已排序序列（初始为空）的一端的方法，称为（D）。A希尔排序 B起泡排序 C插入排序 D选择排序33对5个不同的数排序至少需要比较（A）次。 A4 B5 C6 D734一个序列中有若干个元素，若只想得到其中第i个元素之前的部分排序，最好采用（C）

12、排序方法。A快速排序 B堆排序 C插入排序 Dshell排序35对一组记录的关键码46，79，56，38，40，84采用堆，则初始化堆后最后一个元素是（BA）。A84 B46 C56 D3836在供选择的答案中填入正确答案：(1)排序（分类）的方法有许多种： 法从未排序序列中依次取出元素，与排序序列中的元素作比较，将其放入已排序列的正确位置上； 法从未排序序列中挑选元素，并将其依次放入已排序序的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。供选择答案选择排序 快速排序 插入排序 冒泡排序 (2)一组记录的关键字为（46，79，56，38，40，84），利用快速

13、排序的方法，以第一个记录为基准得到的一次划分结果为 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），使用简单选择排序和直接插入排序两种方法进行排序，哪一种方法对两个表排序

14、所花费的时间相同（简单选择排序）。2目前内部排序的时间复杂度T(n)的范围是（O(nLogn)至O(n2)）。3内部排序将待排序的记录放在（计算机随机存储器）中进行排序，按排序过程中工作量来区分，可分为（简单的排序方法）、（先进的排序方法）和（基数排序）三类。4 对n个元素进行起泡排序时，最少的比较次数是（n-1）。5在堆排序和快速排序中，若原始记录接近正序或反序，则选用（堆排序）。若原始记录无序，则选用（快速排序）。6在插入排序和选择排序中，若初始数据基本正序，则选用(插入排序)，若数据基本反序,则选用(选择排序)。7在插入排序、希尔排序、选择排序、冒泡排序、快速排序、堆排序中，排序是不稳定

15、的有（希尔排序、快速排序、堆排序）。8已知关键字序列51，28，86，70，90，7，30，用冒泡排序，前三趟排序的结果依次为（28，51，70，86，7，30，90）、（28，51，70，7，30，86，90）、（28，51，7，30，70，86，90）。9、设有9个元素的关键字序列为26，5，71，1，61，11，59，15，48，按堆排序思想选出当前序列的最大值71和61之后，所余7个元素的关键字构成的堆是（59，48，26，15，5，11，1）。10对一组记录（54，38，96，23，15，2，60，45，83）进行直接插入排序，当把第7个记录60 插入到有序表时，为寻找位置需比较(2

16、)次。2，15，23，38，54，96，60，45，8311在利用快速排序方法对一组记录（54，38，96，23，15，2，60，45，83）进行快速排序进，递归调用而使用的栈所能达到的最大深度为（4）、共需递归调用的次数为（5），其中第二次递归调用是对（15，38，2，23）一组记录进行快速排序。12快速排序在平均情况下的时间复杂度为O( nlog2n )。13快速排序在最坏情况下的空间复杂度为O( n )。14在堆排序中，对n个对象建立初始堆需要调用 n/2 次调整算法。 15每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做 归并 排序。16给定一组数据对象的排序码为 46, 79

17、, 56, 38, 40, 84，对其进行一趟快速排序，结果为 40,38,46,79,56,84。17下列程序是按关键字的值从大到小进行直接选择排序的算法，将算法补充完整。Select(SqList L)for(i=1;i=L.length-1;i+)k=i；for(j=i+1;j=L.length;j+)if(L.rj.keyL.rk.key) k=j;if(k!=i)L.rkL.ri); /*rk与ri交换*/18在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用 (n-1) 次调整算法。 19在直接选择排序中，数据对象移动次数的时间复杂度为O( n )。

18、 20第i (i = 0, 1, , n-2) 趟从参加排序的序列中第i个第n-1个元素中挑选出一个最小（大）元素，把它交换到第i个位置，此种排序方法叫做 简单选择 排序。 21对n个数据对象进行堆排序，总的时间复杂度为O( nlog2n )。 22每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫做 交换 排序。 23给定一组数据对象的排序码为 46, 79, 56, 38, 40, 84 ，则利用堆排序方法建立的初始堆（最大堆）为 84,79,56,38,40,46 。 24在直接选择排序中，排序码比较次数的时间复杂度为O( n2 )。 25第i (i = 1, 2, , n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个第i-1个元素组成的有序表中适当的位置，此种排序方法叫做 直接插入 排序。 26快速排序在平均情况下的空间复杂度为O( log2n )。 27快速排序在最坏情况下的时间复杂度为O( n2 )。 三、判断题1( )在任何情况下，快速排序需要进行的排序码比较的次数都是O(nlog2n)。 2( )若将一批杂乱无章的数据按堆结构组织起来, 则堆