2024年1月4日发(作者：)

圣才电子书

十万种考研考证电子书、题库视频学习平台

第11章 外排序

一、选择题

1．下列排序算法中，其中（ ）是稳定的。

A．堆排序，起泡排序

B．快速排序，堆排序

C．直接选择排序，归并排序

D．归并排序，起泡排序

【答案】D

2．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A．快速排序

B．堆排序

C．归并排序

D．直接插入排序

【答案】C

【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell排序。时间复杂度平均为O（nlog2n）的有：归并排序、堆排序、shell排序、快速排序。

3．在下面的排序方法中，辅助空间为O（n）的是（ ）。

1 / 11

圣才电子书

．希尔排序

B．堆排序

C．选择排序

D．归并排序

【答案】D

十万种考研考证电子书、题库视频学习平台

4．下列排序算法中，占用辅助空间最多的是（ ）。

A．归并排序

B．快速排序

C．希尔排序

D．堆排序

【答案】A

【解析】归并排序的辅助空间为O（n），快速排序所占用的辅助空间为O（logn），堆排序所占用的辅助空间为O（1）。

5．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A．N

B．2N-1

C．2N

D．N-1

【答案】A

【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新 2 / 11

圣才电子书

十万种考研考证电子书、题库视频学习平台

的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O（n）。

6．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A．插入

B．选择

C．希尔

D．二路归并

【答案】A

【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的记录存放在数组R[0．．n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0．．i-1]和R[i．．n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录R[i]插入到有序区R[0．．i-1]中适当的位置上。使R[0．．i]变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。

二、判断题

1．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）

【答案】×

【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前， 3 / 11

圣才电子书

十万种考研考证电子书、题库视频学习平台

而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

2．排序算法中的比较次数与初始元素序列的排列无关。（ ）

【答案】×

【解析】这个要看是哪个排序算法，比如快速排序，初始序列为有序的情况比较的次数就相对于无序的多。

3．归并排序辅助存储为O（1）。（ ）

【答案】×

【解析】归并排序的辅助存储是O（n）。

4．快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。（ ）

【答案】×

【解析】快速排序最坏的情况下比较次数是O（n2）。

5．在任何情况下，归并排序都比简单插入排序快。（ ）

【答案】×

【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。

6．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）

【答案】×

4 / 11

圣才电子书

十万种考研考证电子书、题库视频学习平台

【解析】外部排序方法：按可用内存大小，将外存上含n个记录的文件分成若干长度为z的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run)。对这些归并段进行逐趟归并，使归并段(有序的子文件)逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序(产生初始归并段)所需的时间m*tIS+外存信息读写的时间d*tIO+内部归并所需的时间S*utmg。

7．在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n／2。（ ）

【答案】×

【解析】当输入文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段

8．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）

【答案】×

【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。

三、填空题

1．外排序的基本操作过程是______和______。

【答案】生成有序归并段（顺串）；归并

5 / 11

圣才电子书

十万种考研考证电子书、题库视频学习平台

2．关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。

【答案】（Q，A，C，S，Q，D，F，X，R，H，M ,Y）；（F，H，C，D，a，A，M, Q，R，S，Y，X）

【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

3．在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。

【答案】归并；堆

4．按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。

【答案】稳定

四、应用题

1．在各种排序方法中，哪些是稳定的?哪些是不稳定的?并为每一种不稳定的排序方法举出一个不稳定的实例。

6 / 11