数据结构课后习题第十章

1.在下列排序算法中，稳定的事（ ），平均速度最快的是（ ），所需辅助存储空间最多的是（ ）。

A.希尔排序 B.快速排序 C.堆排序 D.归并排序 2.若要在O(

n)数量级的时间内完成对数组的排序，且要求排序

是稳定的，则可选择的排序方式应该是（ ）。

A.快速排序 B.堆排序 C.归并排序 D.希尔排序

3.在下列排序算法中，（ ）算法的时间复杂度与初始排序无关。 A.直接插入排序 B.起泡排序 C.快速排序 D.直接选择排序

4.一组记录关键字序列是（46,79,56,38,40,84），则用堆排序方法建立的初始大根堆是（）。

A.79,46,56,38,40,84 B.84,79,56,38,40,46

C.84,79,56,46,40,38 D.94,56,79,40,46,38

5.一组记录的关键字序列是（46,79,56,38,40,84），则用快速排序方法，以第一个关键字为支点，得到的第一次划分结果是（ ）。 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

6.一组记录的关键字序列是（25,48,16,35,79,82,26,40,36,72），用二路归并排序方法进行排序，则第二趟归并的结果是（ ）。 A.16,25,35,48,23,40,79,82,36,72 B.16,25,35,48,79,82,23,36,40,72

C.16,25,35,46,23,36,40,79,82,72 D.16,25,35,48,79,23,36,40,72,82

7.在以下排序方法中，关键字比较的次数与记录的初始排列次序有关的是（）

A.归并排序 B.堆排序 C.插入排序 D.选择排序

8.下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

A. 堆排序B.冒泡排序 C.希尔排序 D.快速排序

9.数据序列（8,9,10,4,5,6,20,1,2）只能是下列排序算法中的（）的两趟排序后的结果。

A.选择排序 B.冒泡排序 C.插入排序 D.堆排序 10.直接插入排序在最好的情况下，其时间复杂度为（） A.O(logn) B.O(n) C.O(

) D.O(nlogn)

11.对一组数据（84,47,25,15,21）排序，数据的排列次序在排序的过程中的变化如下。

初始状态： 84 47 25 15 21 第一趟： 15 47 25 84 21 第二趟： 15 21 25 84 47

第三趟： 15 21 25 47 84 则采用的是（）排序方法

A.选择 B.冒泡 C.快速 D.插入

12.下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。

A. 快速排序B.Shell排序 C.堆排序 D.冒泡排序

13．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。

A.直接插入排序 B.冒泡排序 C.简单选择排序 D.快速排序 14.如果只想得到1000个元素组成的序列中第5个最小元素之间的部分排列序列，用（ ）方法最快。

A.起泡排序 B.快速排序 C.Shell排序 D.堆排序 E. 简单选择排序

15.对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的是（ ）算法。

A.堆排序 B.快速排序 C.插入排序 D.归并排序 16.起泡排序在最好情况下的时间杂度为（ ）。 A.O（logn） B.O(n) C.O(nlogn) D.O(n2)

17.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序方法与初态无关，则可选择的排序方法是（ ）。

A．快速排序 B.堆排序 C.归并排序 D.直接插入排序 19.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述

中，正确的是（）。

A．递归次序与初始数据的排列次序无关

B．每次划分后先处理较长的分区可以减少递归次数 C．每次划分后先处理较短的分区可以减少递归次数 D．递归次数与每次划分后得到的分区处理次序无关

20.对一组数据(2,12,16,85,5,10)进行排序，若前三趟排序结果如下。

第一趟：2,12,16,5,10,88 第二趟：2,12,5,10,16,88 第三趟：2,5,10,12,16,88 则采用的排序方法可能是（）。

A.冒泡排序法 B.希尔排序法 C.归并排序法 D.基数排序法 二、填空题

1.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的（ ）和记录的（ ）。 2.不受待排序初始序列的影响，时间复杂度为（ ）。

3.分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，最省时间的是（ ）算法，最费时间的是（ ）算法。 4.设有字符序列（Q,H,C,Y,P,A,M,S,E,D,F,X），则用初始步长为4的希尔排序方法将其按字符升序排序，第一趟扫描的结果是（ ）。 5.快速排序的最大递归深度是（ ），最小递归深度是（ ）。

（）的排序算法是

6.对n个元素的序列利用起泡法排序时，最好情况时的最少比较次数是（ ）。

7.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是（ ），需要辅助内存空间最大的是（ ）。

8.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序算法不稳定的有（ ）。

9.在插入排序和选择排序两种算法中，若待排序的序列已基本正序，则选用（ ）较好，若待排序的序列已基本反序，则选用（ ）较好。

10.在堆排序和快速排序两种算法中，若待排序的序列已基本有序，则选用（ ）较好，若待排序的序列完全无序，则选用（ ）较好。

三、计算与算法设计题

1、已知序列（10,18,4,3,6,12,1,9,18,8），请用希尔排序（增量=3， =1）写出每一趟排序的结果。

2、已知序列（10,18,4,3,6,12,1,9,18,8），请用快速排序写出每一趟排序的结果。（每次取第一个元素为支点）

3、已知序列（10,18,4,3,12,9,18,8），请用堆排序写出每一趟（建好初始堆，L.r[1]与L.r[n]互换后为第一趟）排序的结果。 4、已知关键字序列（K1,K2,K3,

）是大根堆

（1）试写出一算法将（K1,K2,K3,，）调整为大根堆。

（2）利用（1）的算法写一个建大根堆的算法。

本文来源：https://www.bwwdw.com/article/8ujr.html