内容发布更新时间 : 2024/5/18 20:20:20星期一 下面是文章的全部内容请认真阅读。

读书破万卷 下笔如有神

《数据结构》第九章习题参考答案

一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）

1、快速排序是一种稳定的排序方法。（ × ） 2、在任何情况下，归并排序都比简单插入排序快。（ × ）

3、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ √ ） 4、内排序要求数据一定要以顺序方式存储。（ × ） 5、直接选择排序算法在最好情况下的时间复杂度为O（n）。( × ) 6、快速排序总比简单排序快。( × ) 二、单项选择题

1．在已知待排序文件已基本有序的前提下，效率最高的排序方法是（ A ）。

A．直接插入排序 B．直接选择排序 C．快速排序 D．归并排序

2．下列排序方法中，哪一个是稳定的排序方法？（ B ）

A．直接选择排序 B．折半插入排序 C．希尔排序 D．快速排序

3、比较次数与排序的初始状态无关的排序方法是( B )。 A．直接插入排序 B．起泡排序 （时间复杂度O（n2）） C．快速排序 D．简单选择排序

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 ）情况下最不利于发挥其长处。

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 ；则采用的排序方法为（ C ）。

A．直接插入排序 B．希尔排序 C．快速排序（选基准） D．选择排序

三、填空题 1、排序算法的时间复杂度可用算法执行中的__关键字比较_次数及__记录移动__次数来衡量。

读书破万卷 下笔如有神

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题

【解答】

内部排序指待排序记录全部存放在计算机内存中进行的排序过程； 外部排序指待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需不断在内、外存之间进行移动的排序过程。

稳定的排序方法有：直接插入排序、折半插入排序、起泡排序、锦标赛排序、归并排序等； 不稳定的排序方法有：希尔排序、直接选择排序、快速排序、堆排序等。

2、课本P440 9.2题

【解答】（1）直接插入排序：2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30 16* 20 6 18 2 10 12 16 16* 28 30 20 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 20 28 30 18 2 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 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）

10 2 16 6 18 12 16* 20 30 28

10 2 16 6 16* 12 18 20 30 28 2 6 10 12 16 16* 18 20 28 30

读书破万卷 下笔如有神

（3）起泡排序

2 12 6 16 30 28 10 16* 20 18 2 6 12 10 16 30 28 16* 18 20 2 6 10 12 16 16* 30 28 18 20 2 6 10 12 16 16* 18 30 28 20 2 6 10 12 16 16* 18 20 30 28 2 6 10 12 16 16* 18 20 28 30

？（4）快速排序

12 2 16 30 28 10 16* 20 6 18 6 2 10 12 28 16 16* 20 30 18 2 6 10 12 18 16 16* 20 28 30 2 6 10 12 16* 16 18 20 28 30

其他略……

3、课本P440 9.4题

【解答】正序则直接插入排序最好；逆序则直接选择排序最好。

4、课本P440 9.5题

【解答】如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关键码可能向与最终它应移向的位置相反的方向移动。

5、课本P441 9.8题

1n2已经有序的情况下快速排序的排序码比较次数将为：?(n?i)?n(n?1)?，所以记

22i?1n?1为O（n2）。

6、课本P441 9.12题 【解答】略

7、课本P441 9.14题

排序码是非负整数，快速排序最快；要求辅助空间为O（1），则选用堆排序；若要求稳定且排序码为浮点数时，则选择基数排序。