数据结构习题参考答案

1、读书破万卷下笔如有神数据结构第九章习题参考答案、判断题（在正确说法的题后括号中打，错误说法的题后括号中打“X”）1、快速排序是一种稳定的排序方法。（X ）2、 在任何情况下，归并排序都比简单插入排序快。（X ）3、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间, 这是影响时间复杂度的主要因素。（V ）4、内排序要求数据一定要以顺序方式存储。（X ）5、 直接选择排序算法在最好情况下的时间复杂度为O （n）。（ X ）6快速排序总比简单排序快。（X ）二、单项选择题1 在已知待排序文件已 基本有序的前提下，效率最高的排序方法是（D.归并排序A .直接插入排序B .直接选择排序

2、C.快速排序2 下列排序方法中，哪一个是 稳定的排序方法？ （ B ）A .直接选择排序B.折半插入排序C.希尔排序D 快速排序3、比较次数与排序的初始状态无关 的排序方法是（B ）。C.快速排序A .直接插入排序B .起泡排序（时间复杂度 0（ n2）单选择排序 4、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21（2） 15 47 25 84 21（3） 15 21 25 84 47（4） 15 21 25 47 84则采用的排序是 （A ）。A.选择B.冒泡C.快速D.插入5、快速排序方法在（D ）情况下最不利于发挥

3、其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序6、用某种排序方法对线性表 结束时的结果为：25，84， 21， 47,15，27，68，35，20进行排序，各趟排序20，21,15,25,84,27,68,35,47（25）15,20,21,25,47,27,68,35,84（左20右47）15,20,21,25,35,27,47,68,84（左35右68）15,20,21,25,27,35,47,68,84；则采用的排序方法为（A .直接插入排序B.希尔排序C.快速排序（选基准）（基准）C ）。D.选择排序三、填空题1、排序

4、算法的时间复杂度可用算法执行中的_关键字比较_次数及_记录移动_次数来衡量。2、 直接插入排序用监视哨的作用是免去查找过程中每一步都要检测整个表是 否查找完毕，提高了查找效率。3、设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4, 2, 1则排序需 3 趟，写出第一趟结 束后，数组中数据的排列次序10,7,-9,0,47,23,1,8,98,36 。4、 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则 最省时间的是冒泡排序算法，最费时间的是 _快速排序算法。四、综合题1、课本P440 9.1题【解答】内部排序指

5、待排序记录全部存放在计算机内存中进行的排序过程；外部排序指待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需不断在内、外存之间进行移动的排序过程。稳定的排序方法有：直接插入排序、折半插入排序、起泡排序、锦标赛排序、归并排序等； 不稳定的排序方法有：希尔排序、直接选择排序、快速排序、堆排序等。2、课本P440 9.2 题【解答】（1）直接插入排序：2 12 16 30 28 10 16* 20 6 182 12 16 30 28 10 16* 20 6 182 12 16 30 28 10 16* 20 6 182 12 16 28 30 10 16* 20 6 182 10 1

6、2 16 28 30 16* 20 6 182 10 12 16 16* 28 30 20 6 182 10 12 16 16* 20 28 30 6 182 6 10 12 16 16* 20 28 30 182 6 10 12 16 16* 18 20 28 30（6）直接选择排序2 12 16 30 28 10 16* 20 6 18 （ 2-）2 6 16 30 28 10 16* 20 12 18（ 6-）2 6 10 30 28 16 16* 20 12 18（ 10-）2 6 10 12 28 16 16* 20 30 18（ 12）2 6 10 12 16 28 16* 20

7、30 18（ 16）2 6 10 12 16 16* 28 20 30 18 .2 6 10 12 16 16* 18 20 30 28 2 6 10 12 16 16* 18 20 30 28 2 6 10 12 16 16* 18 20 28 30 （2）希尔排序（增量为 5，2，1）102 16 6 18 12 16* 20 30 2810 2 16 6 16* 12 18 20 30 282 6 10 12 16 16* 18 20 28 30(3 )起泡排序2 12 6 16 30 28 10 16* 20 182 6 12 10 16 30 28 16* 18 202 6 10 1

8、2 16 16* 30 28 18 202 6 10 12 16 16* 18 30 28 202 6 10 12 16 16* 18 20 30 282 6 10 12 16 16* 18 20 28 30?(4 )快速排序12 2 16 30 28 10 16* 20 6 186 2 10 12 28 16 16* 20 30 182 6 10 12 18 16 16* 20 28 302 6 10 12 16* 16 18 20 28 30其他略3、课本P440 9.4 题【解答】正序则直接插入排序最好；逆序则直接选择排序最好。4、课本P440 9.5 题【解答】如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中,关键码可能向与最终它应移向的位置相反的方向移动。、(n - i) = 1 n(n -1) y25、课本P441 9.8