数据结构Ch10习题答案

1、第十章内部排序B) 。、择题1用直接插入排序法对下面四个表进行(由小到大)排序，比较次数最少的是(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

2、 次插 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;i0&Ajx) Aj+1=Aj;j-;Aj+1=x3这一段代码所描述的排序方法称作(A) 。A.插入排序B .冒泡排序 C .选择排序D.快速排序4 .这一段代码所描述的排序方法的平均执行时间为(D)

3、_一一_2A.O(log2n)B. O(n) C . O(nlog2n) D. O(n)5 .假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为( B)。2A. O(log 2n) B . O(n) C . O(nlog 2n) D . O(n )6 .在快速排序过程中，每次被划分的表(或了表)分成左、右两个子表，考虑这两个子表，下列结论一定正确是(B)。A.左、右两个子表都已各自排好序B .左边子表中的元素都不大于右边子表中的元素C.左边子表的长度小于右边子表的长度D .左、右两个子表中元素的平均值相等7 .对n个记录进行堆排序，最坏情况下的执行时间为(

4、C)。_一一_2A. O(log 2n)B. O(n) C , O(nlog2n)D. O(n ) 8、设待排序关键码序列为(25、18、9、33、67、82、53、95、12、70),要按关键码值递增的顺序排序，采取以第个关键码为分界元素的快速排序法，第一趟排序完成后关键码表33被放到了第几个位置(D)。A. 39 .若对一个已经排好了序的序列进行排序，在下列四方法中，哪种方法比较好(C)。A.冒泡排序法B .直接选择排序法 C .直接插入排序法 D .堆排序法10 .快速排序的时间复杂度是(A)A. O(nlog 2n)B . O(n2) C . O(n 3)D . O(log 2n)11

5、 .以下关键字序列用快速排序法进行排序，速度最慢的是(C)A.23, 27, 7,19, 11, 25, 32B. 23, 11,19,32,27, 35, 7C.7, 11, 19,23, 25, 27, 32D. 27, 25,32,19,23, 7, 1112.在所有排序方法中，关键码比较的次数与记录的初始排序次序无关的是(D)。A.希尔排序 B .冒泡排序 C .直接插入排序D .直接选择排序13用冒泡排序算法对下列数据后时，数的顺序是（C） 。12， 37， 42，19，27， 35， 56， 44， 10进行从小到大排序，在将最大的数“沉”到最A 12， 37， 42， 19，C

6、12， 37， 19， 27，27，35，35，42，44， 10， 5644， 10， 5612， 37， 42，10， 12， 19，19，27，35，10，44，5627，35，37，42，44，5614 .快速排序方法在（C）情况下最不利于发挥其长处。A.被排序的数据量太大B.被排序的数据中含有多个相同值C.排序数据已基本有序D.被排序数据的数目为奇数15具有12 个记录的序列，采用冒泡排序最少的比较次数是（C） 。A 1 B 144 C 11 D 66从小到大进行排序，其要进行（ C）次比较。16若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,

7、41,24A 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在任何情况下，快速排序方法的时间性能总是最优

8、的这种说法（B） 。A.正确B ,错误18排序的重要目的是为了以后对已排序的数据元素进行（C） 。A.打印输出 B .分类 C .查找 D .合并19当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（D）A n2B nlog 2nC log 2nD n-120用10 万个无序且互不相等的正整数序列，采用顺序列存储方式组织，希望能最快地找出前10 个最大的正整数，采用（D）方法较好。A.快速排序B . shell排序 C .选择排序 D ,堆排序21下面四种排序方法中，平均查找长度最小的是（C） 。A.插入排序B .选择排序 C .快速排序 D .堆排序22在文件局部有序或文

9、件长度较小的情况下，最佳的排序方法是（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 。那么，所采用的排序方法是（D） 。A.选择排序B .希尔排序C .堆排序 D .快速排序

10、24快速排序在最坏的情况下的时间复杂度是（B） 。A O（nlog 2n） 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.起泡

11、排序B .快速排序 C .堆排序 D .基数排序28 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。A.插入排序B .选择排序 C.快速排序D .堆排序29 . 一组记录的排序码为（46, 79, 56, 38, 40, 84）。则利用堆排序的方法，建立的初始堆为（B）。A. 79, 46, 56,38,40, 84B,84,79, 56, 38, 40, 46C. 84, 79, 56,46,40, 38D,84,56, 79, 40, 46, 3830 . 一组记录的排序码为（46, 79, 56, 38, 40, 84）,则利用快速排序的方法，以第一个记录为基准得到的

12、一次划分 结果为（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,79pivodoc40 70 56 | 3884lowhigh4056 38 79 84low31 .排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，将其放入已排序序列 的正确位置上的方法称为（D）。A.希尔排序 B .起泡排序 C .插入排序D .选择排序D）。32 .排序方法中，从未排序序列中挑选元素，并将其放入已排序序列（初始为空）的一端的方法，称为（A.希尔排序B

13、.起泡排序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）排序（分类）的方法有许多种： 法从未排序序列中依次取出元素,与排序序列中的元素作比较，将其放入已排序列的

14、正确位置上； 法从未排序而I中挑选元素，并将其依次放入已排序序的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。供选择答案A、38,40,46,56,79, 84B、40,38,46,79,56, 84C 40,38,46,56,79, 84D 40,38,46,84,56, 7946, 79, 56, 38, 40, 84）,利用快速排序的方法，以第一个记录为基准得到的一次划分结（2） 一组记录的关键字为（果为C 。卜列排序算法中,A、堆排序? B、?快速排序？插入排序？冒泡排序?C?M法可能会出现下面情况：初始数据有序时，花费时间反而最多。冒泡排序？?？ C

15、、快速排序？?？ 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个元素进

16、行起泡排序时，最少的比较次数是（n-1 ）。5 .在堆排序和快速排序中，若原始记录接近正序或反序，则选用（ 堆排序）。若原始记录无序，则选用（ 快速排序）。6 .在插入排序和选择排序中，若初始数据基本正序，则选用（插入排序），若数据基本反序，则选用（选择排序）。7 .在插入排序、希尔排序、选择排序、冒泡排序、快速排序、堆排序中，排序是不稳定的有（希尔排序、快速排序、堆排序）。8 .已知关键字序列51 , 28, 86, 70, 90, 7, 30,用冒泡排序，前三趟排序的结果依次为（28, 51, 70, 86, 7, 30,90）、（28, 51, 70, 7, 30, 86, 90）、（2

17、8, 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）次。2, 15, 23, 38, 54, 96, 60, 45, 8311 .在利用快速排序方法对一组记录(54, 38, 96, 23, 15, 2,

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

19、4。17 .下列程序是按关键字的值从大到小进行直接选择排序的算法，将算法补充完整。 Select(SqList L) for(i=1; i= ;i+) k=i ；for(j=i+1; j= ;j+) ifj.keyk.key) k=j ; if( k!=i )ki);? ?/*rk 与 ri交换*/ 18 .在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用(n-1)次调整算法。19 .在直接选择排序中，数据对象移动次数的时间复杂度为0( n )。20 .第i (i = 0, 1,，n-2)趟从参加排序白序列中第i个第n-1个元素中挑选出一个最小(大)元素，把它

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