数据结构(C语言版)习题及答案第九章

数据结构(C语言版)习题及答案

习 题

一、选择题

1、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始

堆为( B )。

A、79，46，56，38，40，80 B、84，79，56，38，40，46

C、84，79，56，46，40，38 D、84，56，79，40，46，38

2、排序趟数与序列原始状态(原始排列)有关的排序方法是（ ACD ）方法。

A、插入排序 B、选择排序 C、冒泡排序 D、快速排序

3 、下列排序方法中，（ B ）是稳定的排序方法。

A、直接选择排序 B、二分法插入排序 C、希尔排序 D、快速排序

4、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟

排序后的结果。

A、选择排序 B、冒泡排序 C、插入排序 D、堆排序

5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，

9，-1，8，20，7，15），则采用的是（ C ）排序。

A、选择 B、快速 C、希尔 D、冒泡

6 、一组待排序记录的关键字为（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,79)

7、用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是

（ C ）。

A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80

C、21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,40

8、若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行

的关键字比较总次数是（ B ）。

A、10 B、15 C、21 D、34

9、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（ A ）。

A、堆排序<快速排序<归并排序 B、堆排序<归并排序<快速排序

C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序

E、以上答案都不对

10、采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k（ ）。

A、有关 B、无关

9.2 填空题

1、在直接插入排序和直接选择排序中，若初始数据基本有序，则选用（直接插入排序），

若初始数据基本反序，则选用（直接选择排序）。

2、在归并排序中，若待排序记录的个数为20，则共需要进行（5）趟归并，在第三趟

归并中，是把长度为（4）的有序表归并为长度为（8）的有序表。

3、在内排序中，平均比较次数最多的是（快速排序），要求附加的内存空间最大的是（归

并排序），排序时不稳定的有（希尔排序）、（选择排序）、（快速排序）和（堆排序）等几种

方法。

4、对n个元素的序列进行冒泡排序，最少的比较次数是（n-1），此时元素的排列情况

数据结构(C语言版)习题及答案

（从小到大排列），在（从大到小排列）情况下比较次数最多，其比较次数为（n(n-1)/2）。

5、对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把

第7条记录60插入到有序表中时，为寻找插入位置需比较（3）次。

9.3 应用题

1、在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方

法举出一个不稳定的实例。

答：稳定的排序算法有直接插入排序、折半插入排序、冒泡排序、归并排序和基数排序。

不稳定的排序算法有希尔排序、直接选择排序、堆排序、快速排序。

例子：讲课是的例子。

2、设待排序的关键码分别为28，13，72，85，39，41，6，20。按折半插入排序已使

前七个记录有序，中间结果如下： 6 13 28 39 41 72 85 20 试在此基础上，沿用上述表达方式，给出继续采用折半插入第八条记录的比较过程，并回答

以下问题：

(1) 使用折半插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？

(2) 在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？

答：

插入20的过程：

① 39>20：r=m-1=3;i<=r;m=(i+r)/2=4/2=2

② 13<20: i=m+1=3;i>r;查找过程结束，插入位置为i。

最终结果为：6 13 20 28 39 41 72 85

（1）插入排序所要进行的比较次数与待排序的记录的初始状态有关。若初始状态基本有序，

每次查找时都会搜索到有序表的最后一个元素才找到插入位置。若每次插入的元素在有序

表中的插入位置靠中间，则查找次数最少。

（2）在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话是对

的。若初始状态基本有序，则折半插入排序，每次查找时都会搜索到有序表的最后一个元

素才找到插入位置。直接插入排序则每次只比较一次就找到合适位置。

3、已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写

完整下示各步骤结果。

建立初始堆：_97 87 26 61 70 12 3 45

堆排序过程：

（1）87 70 26 61 45 12 3 97;（2） 70 61 26 3 45 12 87 97;

（3）61 45 26 3 12 70 87 97;（4） 45 12 26 3 61 70 87 97;

（5）26 12 3 45 61 70 87 97;（6） 12 3 26 45 61 70 87 97;

（7）3 12 26 45 61 70 87 97;

4、全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分

输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为

什么？

答：因排序的元素个数很大，所以需要采用排序速度较快的排序方法。排序速度比较

快的排序方法有快速排序、堆排序、归并排序和基数排序等。其中快速排序、归并排序和

基数排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连

续位置上的最终元素。但堆排序则每次输出一个堆顶元素（即最大或最小元素），然后对堆

数据结构(C语言版)习题及答案

进行再调整，保证堆顶元素总是剩下元素的最大或最小的，从而可知，若在大量数据的文件中，只选取排序后的前几名，采用堆排序最合适。

5、判断下列序列是否为堆，若不是堆，则把它们调整为堆。

（1）100，85，95，75，80，60，82，40，20，10，65;

（2）100，95，85，82，80，75，65，60，40，20，10;

（3）100，85，40，75，80，60，65，95，82，10，20;

（4）10，20，40，60，65，75，80，82，85，95，100;

答：（1）100，85，95，75，80，60，82，40，20，10，65; 是堆。

（2）100，95，85，82，80，75，65，60，40，20，10; 是堆。

（3）100，85，40，75，80，60，65，95，82，10，20; 不是堆

调整以 …… 此处隐藏：2807字，全部文档内容请下载后查看。喜欢就下载吧 ……