上传第10章排序习题

9.1 选择题

1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。 A）插入 B）选择 C）希尔 D）二路归并 【答案】A

2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（ ） A）快速排序 B）直接插入排序 C）堆排序 D）归并排序 【答案】B

4．下面给出的四种排序法中，（ ）排序是不稳定排序法。 A）插入 B）冒泡 C）二路归并 D）堆 【答案】D

5．快速排序方法在（ ）情况下最不利于发挥其长处。 Ａ）要排序的数据量太大

Ｂ）要排序的数据中含有多个相同值 Ｃ）要排序的数据已基本有序 Ｄ）要排序的数据个数为奇数 【答案】Ｃ

7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为： 50,26,38,80,70,90 ,8,30,40,20 50,8,30,40,20,90,26,38,80,70 26,8,30,40,20,80,50,38,90,70

8,20,26,30,38,40,50,70,80,90 其使用的排序方法是（ ）

A）快速排序 B）基数排序 C）希尔排序 D）归并排序 【答案】C

8．在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是（ ） A）直接插入排序 B）冒泡排序 C）简单选择排序 D）归并排序 【答案】A

【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n-1趟排序，也即时间复杂度仍为O(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(n log2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n)降至O(n)。

9．在下列算法中，（ ）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A）堆排序 B）冒泡排序 C）插入排序 D）快速排序 【答案】C

【解析】在插入排序中，如果待排序列中的最后一个元素其关键字值为最小，则在最后一趟开始之前，前n-1个排好序的元素都不在其最终位置上，与排好序后的位置相差一个位置。因此，选C。

10．设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用（ ）方法最好 A）快速排序 B）堆排序 C）基数排序 【答案】B

2

【解析】用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素。

11．对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是（ ） A）简单选择排序 B）快速排序 C）希尔排序 D）二路归并排序 【答案】C

12．以下序列不是堆的是（ ） A）100,85,98,77,80,60,82,40,20,10,66 B）100,98,85,82,80,77,66,60,40,20,10 C）10,20,40,60,66,77,80,82,85,98,100 D）100,85,40,77,80,60,66,98,82,10,20 【答案】D

【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

13．下面排序方法中，关键字比较次数与记录的初始排列无关的是（ ） A）希尔排序 B）冒泡排序 C）直接插入排序 D）直接选择排序 【答案】D

【解析】如果初始排列基本有序，则对希尔排序来说，前几趟的插入工作大为减少。冒泡排序和直接插入排序都与初始排序序列有关，只有直接选择排序与初始序列无关．故选D。

14．一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（ ）

A）80,45,50,40,42,85 B）85,80,55,40,42, 45 C）85,80,55,45,42,40 D）85,55,80,42,45,40 【答案】B

16．n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ ） A）O(1) B）O(log2n) C）O(n2) D）O(n) 【答案】D

【解析】最好情况下至少需要一趟排序，即比较n-1次，故选D。

17．n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素(包括开始将基准元素移到临时变量的那一次)。 A）n／2 B）n-1 C）n D）n+l 【答案】D

【解析】移动次数最多的情况是对n-1个元素比较时都需移动，加上开始将基准元素移到临时变量以及由临时变量移至正确位置的二次，即共需n+1次，故选D。 18．下述几种排序方法中，要求内存量最大的是（ ） A）插入排序 B）选择排序 C）快速排序 D）归并排序 【答案】D

【解析】插入排序和选择排序需要的辅助空间为O(1)，快速排序需要的辅助空间为O(log2n )，归并排序需要的辅助空间为O(n)，因此选D。 19．下面排序方法中，时间复杂度不是O(n2)的是（ ）

A）直接插入排序 B）二路归并排序 C）冒泡排序 D）直接选择排序 【答案】B

【解析】直接插入排序、冒泡排序和直接选择排序的时间复杂度为O(n2)，而二路归并排序的时间复杂度为O(n log2n)，故选B。

20．对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（ ） A）70,75,82,90, 23,16,10,68 B）70,75,68,23,10,16,90,82 C）82,75,70,16,10,90,68,23 D）23,10,16,70,82,75,68,90 【答案】A

【解析】快速排序第一趟划分的方法是：将第1个元素放入最终排好序序列中的正确位置上，则在这个位置右边小于该元素值的元素都将移到其左边，在这个位置左边大于该元素值的元素都将其移到其右边。由此得到A需移动的元素最多，故选A。 9.2 填空题

2．在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取_____________方法，其次选取_____________方法；若只从排序结果的稳定性考虑，则应先择_____________方法；若只从平均情况下排序的速度来考虑，则选择_____________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_____________方法。

【答案】（1）堆排序 （2）快速排序 （3）归并排序 （4）快速 （5）堆

3．对n个元素的序列进行冒泡排序，最少的比较次数是_____________，此时元素的排列情况为_____________，在_____________情况下比较次数最多，其比较次数为_____（4）_ ____。 【答案】

（1）n-1 （2）从小到大排序 （3）元素从大到小排列 （4）n(n-1)/2 【解析】初始元素正序时，第一趟比较n-1次，并无数据交换，则不再比较，故只比较n-1次。若反序，则比较(n-1)+(n-2)+(n-3)+…..+2+1共n(n-1)/2次。 4．希尔排序是把记录按下标的一定增量分组，对每组记录进行直接插入排序，随着增量_____________，所分成的组包含的记录越来越多，当增量的值为_____________时，整个数组合为一组。 【答案】（1）减少 （2）1

5．直接插入排序需借助的存储单元个数（空间复杂度）为_____________，最好情况下直接插入排序的算法时间复杂度为_____________，最坏情况下该算法的时间复杂度为_____________。 【答案】（1）1 （2）O(n) （3）O(n2)

6．对n个数据进行简单选择排序，所需进行的关键字间的比较次数为_____________，时间复杂度为_____________。 【答案】（1）n(n-1)/2 （2）O(n2)

7．对于关键字序列(12，13，11，18，60，15，7，20，25，100)，用筛选法建堆，必须从键值为_____________的关键字开始。 【答案】60

【解析】建堆必须从n／2结点开始，而10／2=5位置的结点值为60，故填60。 8．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较_____________次。 【答案】3

【解析】当把第7个记录60插入到有序表时，则前6个记录已经有序，此时记录60由后向前与有序表中的元素进行比较，直到遇到值小于60的记录为止，也即在有序表(15，23，38，54，72，96)中共需比较3次，因此填3。

9．若对顺序存储在A[l]～A[9]的记录(76，38，62，53，80，74，83，65，85)进行堆排序，已知除第一个元素76外，以其余元素为根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到A数组下标为_____________的位置上。 【答案】8

【解析】从树结构关键字值看，除根外是小根堆。对第一元素进行筛运算时，得到的数据序列为：38,53,62,65,80,74,83,76,85。

11．在时间复杂度为O(log2n)的排序方法中，_____________排序方法是稳定的；在时间复杂度为O(n)的排序方法中，_____________排序方法是不稳定的。 【答案】（1）归并 （2）直接选择

12．设表中元素的初态是按键值递增的，若分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则_____________最省时间，_____________最费时间。

【答案】（1）冒泡排序 （2）快速排序

【解析】若初始序列已经有序，则冒泡排序仅需一趟(比较n-1次)；而快速排序则需n-1趟，其时间复杂度升至O(n2)。因此填：冒泡排序，快速排序。 13．从一个无序序列建立一个堆的方法是：首先将要排序的n个键值分放到一棵______________的各个结点中，然后从i=_____________的结点Ki开始，逐步把以Ki-1、Ki-2、…、K1为根的子树排成堆，直到以Kl为根的树排成堆，就完成了建堆的过程。

【答案】（1）完全二叉树 （2）n／2下取整。 9.4 应用题

2．冒泡排序算法是否稳定？为什么？

【答案】冒泡排序算法是稳定的。因为依据该排序算法的基本思想，排序过程只比较相邻两个记录的关键字，若交换记录也只在相邻二个记录之间进行，从而可知在交换过程中不会出现跨越多个记录的情形。即使是相邻两个记录关键字相同

时，经过比较也不会产生相邻记录的交换。所以冒泡排序法不会改变相同关键字记录的相对次序，故是稳定的。

3．在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？

【答案】如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如： 初始关键字：59 45 10 90 第一趟排序：45 10 59 90 第二趟排序：10 45 59 90

其中45在第一趟排序中移向了与最终位置相反的方向。但在快速排序中不会出现这种情况，因为在每趟排序中，比基准元素大的都交换到右边，而比基准元素小的都交换到左边。

4．设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。

（1） 直接插入排序 （3） 起泡排序 （5） 基数排序

（2） 希尔排序（增量为5,2,1） （4） 快速排序 （6） 堆排序

【答案】

（1） 直接插入排序

（2） 希尔排序(增量为5,2,1)

（3）起泡排序

（4） 快速排序

（5）基数排序

按最低位分配

收集

按最高位分配

收集

【算法源代码】

void dbSort(int r[ ],int n) {int i=1,j,t,b=1; while(b) }

4．写出快速排序的非递归算法。

【算法分析】设对记录空间R[1..n]进行快速排序，要求用非递归算法，可以利用一个栈s来进行，其类型类型为SqStack，每个栈元素含两个域：一个是top域，即栈顶指针；另一个为data域，用于存放元素，其中data数组元素含两个域，一个为low，一个为high，分别指示某个子文件的首、尾记录的首、尾地址，设栈空间最大容量为MAXSIZE，而且假定在整个排序过程中不会发生溢出。

{b=0;

for(j=n-i;j>=i;j--) /*找最小元素*/ if (r[j]

{b=1; t=r[j];r[j]=r[j-1];r[j-1]=t; for(j=i;jr[j+1])

{b=1; t=r[j];r[j]=r[j+1]; i++; }

r[j+1]=t;}

}

【算法源代码】 QuikSort(int R[ ],int n) {int i,j,lw,hg,temp; SqStack *s; s->top=1;

s->data[s->top].low=1;s->data[s->top].high=n;

while(s->top!=0) /*栈非空，则取出一个子文件进行划分*/

{

lw=s->data[s->top].low; hg= s->data[s->top].high; s->top--;

i=lw; j=hg; temp=R[i]; do

{while(itemp)j--; if(i

if (i+1

}

{s->top++;

s->data[s->top].low=i+1; }

s->data[s->top].high=hg;

if (lw

{ s->top++;

s->data[s->top].low=lw; }

s->data[s->top].high=i-1;

5．对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。

【算法分析】利用快速排序方法排序时，若low小于high，此时应找出基准位置，若基准位置恰是要找的第j个位置，则直接返回该位置的数，若刚才的基准位置大于要找位置，则查找区域的上限改为刚才划分的基准位置-1，否则查找区域的下限改为刚才划分的基准位置+1。 【算法源代码】

int QuickSort(SqList R,int j,int low,int high) { int pivotpos; if(low

{ pivotpos=Partition(R,low,high) /*对R[low..high]做划分*/

if (pivotpos==j) return R[j]; else if (pivotpos>j)

return quicksort(R,j,low,pivotpos-1); else

return quicksort(R,j,pivotpos+1,high); } }

6．将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重新编写直接插入排序算法。 【算法分析】

用R[n]作哨兵，则在插入数据时则是由后向前递推，即来一个待插入的数，把该数插入到其后的序列是有序的数据序列中，此时把待插入的数放到R[n]中，然后找到插入其后序列的合适位置，此时需要把后续数据中的部分逐个前移，空出适当位置后，把R[n]中保存的插入值直接放到空位置中去。 【算法源代码】

void InsertSort(SqList R) { int i,j;

for(i=n-2;i>=0;i--) if(R[i].key>R[i+1].key) { R[n]=R[i];j=i+1;/*R[n]是哨兵*/ do{

R[j-1]=R[j];/*将关键字小于R[i].key的记录向右移*/ j++;

}while(R[j].key

R[j-1]=R[n]; /*将R[i]插入到正确位置上*/ } }

本文来源：https://www.bwwdw.com/article/3mea.html