第十章 排序
第十章排序
一、名词解释
1.排序
2.内部排序
3.外部排序
4.堆
5.堆排序
二、填空
1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为
________的。
2.按照排序过程涉及的存储设备的不同，排序可分为________排序和
________排序。
3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：
________、________、________、
________等四类。
4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。
5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。
6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。
void straightsort(list r); {for(i=___________;i<=n;i++)
{r[0]=r[i];j=i-1; while(r[0].key ________;j--;} r[j+1]=_______; } } 7.直接插入排序是稳定的，它的时间 复杂性为________，空间复杂度为 ________。 8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag为特征位，定义为布尔型*/ {for(i=1;i<=________;i++) {_______________; for(j=1;j<=_________;j ++) if(r[j+1].key =r[j];r[j]=r[j+1];r[j+1]=p;} if(flag) return; } } 9.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是 ________。 10.以下对r[h],r[h+1],……r[p]子 序列进行一趟忆速排序。请分析算法，并在________上填充适当的语句。 int quickpass(list r,int h,int p) {i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i {while((r[j].key>=x.key)&&(i if(i {________;i++;/* 将 r[j].kiy while((r[i].key<=x.key)&&(i if(i r[j].kiy } } r[i]=________;return(i);/*一趟快速排序结束，将x移至正确的位置*/ } 11.对快速排序来讲，其最好情况下的时间复杂度是________，其最坏情况下的时间复杂度是________。 12.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。 void select(list r,int n) {for(i=1;i<=________;i++)/*每次循环，选择出一个最小键值*/ {k=i; for(j=i+1;j<=n;j++)if(r[j].key if(______)swap(r[k],r[i]）;/*函数swap(r[k],r[i]）交换r[k]和r[i]的位置*/ } } 13.直接选择排序是不稳定的，其时间复杂性为________。 14.树形选择排序要增加________个 结点以保存前面比较的结果。另外，排序的结果还需要另外开辟 ________. 15.树形选择排序可用一棵树来表示 这一排序过程，树中的n个叶子代表待排序记录的键值，叶子上面一层是________两两比较的结果，依次类推。________表示最后选择出来的最小关键字。在选择次最小键值时，只需将叶结点中最小键值改成________，重新进行比较。依次类推。 16.若树形选择排序的叶子数为n，除第一次需执行________次比较就选择出一个最小的键值外，以后的每次都只经过________次比较就选择出一个最小的键值。所以树形选择排序总的时间开销为________。 17.从一个无序序列建立一个堆的方 法是：首先将要排序的所有键值分放到一棵________的各个结点中，然后 从i=________的结点k i 开始，逐步把 以k n/2,k n/2-1 ,k n/2-2 ,……为根的子树排成 堆，直到以k 1 为根的树排成堆，就完成了建堆的过程。 18.堆排序是不稳定，空间复杂度为________。在最坏情况下，其时间复杂性也为________。 19.以下将a h ,…,a m 和a m+1 ,…,a n 两个有 序序列（它们相应的关键字值满足 K h <=…<=K m ,K m+1 <=…<=K n ）合并成一个 有序序列R h ，…,R n （使其关键字值满 足K h <=…<=K n ）。请分析算法，并在 ________上填充适当的语句。 void merge(list a,list R,int h,int m,int n) {i=h;k=h;j=m+1; while((i<=m)&&(j<=n)) {if(a[i].key<=a[j].key){R[k]=___ _____;________;} else{R[k]=________;________;} k++; } while(i<=________){R[k]=a[i];i++ ;k++;} while(j<=________){R[k]=a[j];j++ ;k++;} } 此算法的执行时间为________. 20．归并排序要求待排序列由若干个___________的子序列组成。 21．二路归并排序的时间复杂度是 ___________。 22．对于n个记录的集合进行归并排序，所需的附加空间消耗是 ___________。 23.设表中元素的初始状态是按键值 递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。 24．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序进行排序，最省时间的是___________算法，最费时间的是___________算法。 三、单项选择 1．以下说法错误的是 （） ①直接插入排序的空间复杂度为 O(1)。 ②快速排序附加存储开销为O(log 2 n)。 ③堆排序的空间复杂度为O(n)。 ④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 2．以下不稳定的排序方法是 （） ①直接插入排序②冒泡排序③直接选择排序④二路归并排序3．以下稳定的排序方法是 （） ①快速排序②冒泡排序 ③直接选择排序④ 堆排序 4．以下时间复杂性不是O(n2)的排序方法是 （） ①直接插入排序②二路归并 排序③冒泡排序④直 接选择排序 5．以下时间复杂性不是O(nlog 2 n)的排序方法是 （） ①堆排序② 直接插入 排序③二路归并排序④快 速排序 6．在文件局部有序或文件长度较小的情况下，最佳的排序方法是 （） ①直接插入排序② 冒泡排序 ③ 直接选择排序④归并排序 7．对于大文件的排序要研究在外设上的排序技术，即 （） ①快速排序法② 内排序法 ③外排序法④ 交叉排序法 8．排序的目的是为了以后对已排序的 数据元数进行（）操作。 ①打印输出②分类 ③ 合并④查找 9．当初始序列已按健值有序时，用直 接插入算法进行排序，需要比较的次 数为（） ①n-1 ②log 2 n ③ 2log 2n ④n2 10.快速排序在最坏的情况下的时间 复杂度是 （） ①O(log 2 n) ②O(nlog 2 n) ③ O(n2) ④O(n3) 11.具有24个记录的序列，采用冒泡 排序至少的比较次数是 （） ①1 ②23 ③ 24 ④ 529 12．用某种排序方法对序列（25，84， 21，47，15，27，68，35，20）进行 排序，记录序列的变化情况如下： 25 84 21 47 15 27 68 35 20 15 20 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采取的排序方法是 （） ①直接选择排序②冒泡排序 ③快速排序④二路归并排 序 13．在排序过程中，健值比较的次数 与初始序列的排列顺序无关的是 （） ①直接插入排序和快速排序 ②直接插入排序和归并排序 ③直接选择排序和归并排序 ④快速排序和归并排序 14．（）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。 ①归并排序② 插入排序 ③快速排序④选择排序 15（）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 ①归并排序②插入排序 ③ 快速排序④选择排序 16．（）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。 ①归并排序②插入排序 ③快速排序④选择排序 17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（）方法能够最快地找出其中最大的正整数。 ①快速排序②插入排序 ③ 选择排序④ 归并排序 18一般情况下，以下四种排序方法中，平均查找长度最小的是 （） ①归并排序②快速排序 ③选择排序④插入排序 19．以下四种排序方法中，要求附加的内存容量最大的是 （） ①插入排序②选择排序 ③快速排序④归并排序20已知一个链表中有3000个结点，每个结点存放一个整数，（）可用于解决这3000个整数的排序问题且不需要对算法作大的变动。 ①直接插入排序法 ②简单选择排序方法 ③快速排序方法 ④堆排序方法 21．若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（）次比较。 ①33 ②45 ③70 ④91 22．在任何情况下，快速排序方法的时间性能总是最优的。这种说法 ①正确②错误 23．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（）方法。 ①归并排序②直接插入排序 ③直接选择排序④快速排序。 四、简答及应用 1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。 2．举例说明本章介绍的各排序方法中那些是不稳定的？ 3．相对于树形选择排序，直接选择排序和堆排序有何优点？ 4．试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。 5．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。 （1）（3，10，12，22，36，18，28，40）； （2）（5，8，11，15，23，20，32，7）。 6．对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。 7．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。 五、算法设计 1．设计一个用链表表示的直接选择排序算法。 2．写出非递归调用的快速排序算法。3．插入排序中找插入位置的操作可以通过二分法查找的方法来实现。 试据此写一个改进后的插入排序 方法。 4．一个线性表中的元素为正整数或负整数。设计一个算法，将正整数 和负整数分开，使线性表前一半为 负整数，后一半为正整数。不要求 对这些元素排序，但要求尽量减少 交换次数。5．已知（k 1 ,k 2 ……，k n ）是堆，试写 一个算法将（k 1 ,k 2 ,……，k n ,k n+1 ） 调整为堆。按此思想写一个从空堆 开始一个一个填入元素的建堆算 法（题示：增加一个k n+1 后应从叶 子向根的方向调整）。 6．设计一个用链表表示的直接插入 排序算法。 第十章参考答案 二、填空 1．稳定、不稳定 2.内部、外部 3．插入排序、交换排序、选择排 序、归并排序 4.键值比较、记录移 动、附加空间 5．直接、折半、表、希尔 6.2、r[j]、r[0] 7.O（n2）、O（1） 8.n-1、flag=1、n-i 9.O(n2) 10.j--、r[i]=r[j]、j++、r[j]=r[i]、 x 11.O(nlog2n)、O(n2) 12.n-1、k=j、k!=I 13.O(n2) 14.n-1、存储区 15.叶子、树根、＋∝ 16.n-1、log 2 n、O(nlog 2 n) 17.完全二叉树、n/2 18.O(1)、O(nlog 2 n) 19.a[ii]、ii++、a[j]、j++、m、 n、O(n-h+1) 20.有序 21．O(log 2n) 22.O(n 2) 23.冒泡排序、快速排序 24.插入排序、快速排序 三、单项选择 1. ③ 2. ③ 3. ② 4. ② 5. ② 6. ② 7. ③ 8. ④ 9. ① 10. ③ 11. ② 12. ③ 13. ③ 14. ④ 15. ④ 16. ③ 17. ③ 18. ② 19. ④ 20. ④ 21. ④ 22. ② 23. ③ 四、简答及应用 1．①直接插入排序 序号 1 2 3 4 5 6 7 8 9 10 11 12 关键字 83 40 63 13 84 35 96 57 39 79 61 15 i = 2 40 83 [63 13 84 35 96 57 39 79 61 15] i = 3 40 63 83 [13 84 35 96 57 39 79 61 15] i = 4 13 40 63 83 [84 35 96 57 39 79 61 15] i = 5 13 40 63 83 84 [35 96 57 39 79 61 15] i = 6 13 35 40 63 83 84 [96 57 39 79 61 15] i = 7 13 35 40 63 83 84 96 [57 39 79 61 15] i = 8 13 35 40 57 63 83 84 96 [39 79 61 15] i = 9 13 35 39 40 57 63 83 84 96 [79 61 15] i = 10 13 35 39 40 57 63 79 83 84 96 [61 15] i = 11 13 35 39 40 57 61 63 79 83 84 96 [15] i = 12 13 15 35 39 40 57 61 63 79 83 84 96 ②直接选择排序 序号 1 2 3 4 5 6 7 8 9 10 11 12 关键字 83 40 63 13 84 35 96 57 39 79 61 15 i = 1 13 [40 63 83 84 35 96 57 39 79 61 15] i = 2 13 15 [63 83 84 35 96 57 39 79 61 40] i = 3 13 15 35 [83 84 63 96 57 39 79 61 40] i = 4 13 15 35 39 [84 63 96 57 83 79 61 40] i = 5 13 15 35 39 40 [63 96 57 83 79 61 84] i = 6 13 15 35 39 40 57 [96 63 83 79 61 84] i = 7 13 15 35 39 40 57 61 [63 83 79 96 84] i = 8 13 15 35 39 40 57 61 63 [83 79 96 84] i = 9 13 15 35 39 40 57 61 63 79 [83 96 84] i = 10 13 15 35 39 40 57 61 63 79 83 [96 84] i = 11 13 15 35 39 40 57 61 63 79 83 84 [96] ③快速排序 关键字83 40 63 13 84 35 96 57 39 79 61 15 第一趟排序后 [15 40 63 13 61 35 79 57 39] 83 [96 84] 第二趟排序后 [13] 15 [63 40 61 35 79 57 39] 83 84 [96] 第三趟排序后 13 15 [39 40 61 35 57] 63 [79] 83 84 96 第四趟排序后 13 15 [35] 39 [61 40 57] 63 79 83 84 96 第五趟排序后 13 15 35 39 [57 40] 61 63 79 83 84 96 第六趟排序后 13 15 35 39 40 [57] 61 63 79 83 84 96 第七趟排序后 13 15 35 39 40 57 61 63 79 83 84 96 ④堆排序 关键字：83 40 63 13 84 35 96 57 39 79 61 15 排序成功的序列：96 84 83 79 63 61 57 40 39 35 15 13 排序过程如图简答题8－ 1.1、8－1.2、8－1.3所示。 ⑤归并排序 关键字83 40 63 13 84 35 96 57 39 79 61 15 第一趟排序后 [40 83] [13 63] [35 84] [57 96] [39 79] [15 61] 第二趟排序后 [13 40 63 83] [35 57 84 96] [15 39 61 79] 第三趟排序后 [13 35 40 57 63 83 84 96] [15 39 61 79] 第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96 2．稳定排序有直接插入、冒泡排序、归并排序。 不稳定排序有快速排序、直接选择排序、堆排序。举例如下： ①快速排序 初始状态40 65 38 49 97 65 13 60 排序后13 38 40 49 60 65 65 97 （65表示记录初始位置在65记录位置之后） ②堆排序 初始状态65 38 75 97 80 13 27 65 排序后13 27 38 65 65 75 80 97 ③直接排序 初始状态40 65 38 49 97 65 13 60 排序后13 38 40 49 60 65 65 97 3．直接选择相对于树形选择排序的优点：算法易懂，容易实现，基本上不需要附加空间。而树形排序需要附加n – 1附加空间。 直接选择排序相对于树形选择排序的缺点：直接选择排序每一趟都不保留比较结果比较次数较多，而树形排序则能利用大部分上一次的比较结果，因此时间性能比直接选择排序优越。 堆排序相对于树形排序的优点：堆排序除建第一个堆费时外，其余元素进行堆比较次数小于等于h（h 表示n元素构成的完全二叉树的深度），而树形排序每次比较都是h次。因此，堆排序时间复杂度小于树形排序。堆排序基本也不需要附加空间。 4．直接插入排序、直接选择排序、快速排序、堆排序和归并排序时空性如表： 从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下，时 间性能不如堆排序和归并排序。 而后两者相比的结果是，当n 较大时，归并排序所需时间优于堆排序，但它所需辅助空间最多。 注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于n 较大的情况，有适用于n 较小的情况，还有的与关键字的分布和初始位置有关……因此，在实际使用时，需要根据不同情况适当选用排序方法，甚至可将多种方法结合使用。 5．分析：先按序列画出对应的完全二叉树，再看其是否满足堆的定义。按这一思路，画出的完全二叉树见图简答8-5.1. 显然序列⑴是堆，而序列⑵不是堆，值为 7的元素应该上调，调整过程见图简答题8-5.2. 6.第一趟： [46, 58, 15, 45, 90, 18, 10, 62] [46, 58, 15, 45, 90, 18, 10, 62] . 一次交换之后 二次交换之后 三次交换之后 [10, 18, 15, 45, 90, 46, 58, 62] [10, 18, 15, 45, 90, 46, 58, 62] 四次交换之后 [10, 18, 15, 以上“－” 第一趟： [10 18 15 45] 46 [90 58 62] 第二趟： 10 [18 15 45] 46 [62 58] 90 第三趟： 10 [15] 18 45] 46 [58] 62 90 结果： 10 15 18 45 46 58 62 90 7． ⑴插入排序的每趟的结果 初始值健值序列[12] 5 9 20 6 31 24 i=2 [5 12] 9 20 6 31 24 i=3 [5 9 12] 20 6 31 24 i=4 [5 9 12 20] 6 31 24 i=5 [5 6 9 12 20] 31 24 i=6 [5 6 9 12 20 31] 24 i=7 [5 6 9 12 20 24 31] ⑵冒泡排序的每趟的结果： 初始键值序列[12 5 9 20 6 31 24] 第一趟之后[5 9 12 6 20 24] 31 第二趟之后[5 9 6 12 20] 24 31 第三趟之后[5 6 9 12] 20 24 31 第四趟之后 5 6 9 12 20 24 31 五、算法设计 1.分析：每趟从单链表头部开 始，顺序查找当前链值最小的结点。 找到后，插入到当前的有序表区的最 后。 Void selesort ( lklist L ) /* 设链表L带头结点 */ { q=L; /* 指向第一数据前趋 */ while ( q-> next !=NULL ) { pl = q -> next ; minp =pl; /* minp指向当前已知的最小数 */ while ( pl -> next != NULL ) { if ( pl -> next -> data < minp -> data ) minp = pl -> next ; /* 找到了更小数 */ pl = pl -> next ; /* 继续往下找 */ } if ( minp != q -> next) /* 将最小数交换到第一 个位置上 */ { r1 = minp -> next ; minp -> next = r1 -> next ; /* 删除最小数 */ r2 = q -> next ; q -> next = r2 -> next ; /* 删除当前表中第一个数 */ r1 -> next = q -> next ; q -> next = r1 ; /* 将最小数插入到第一个位置上 */ r2 -> next = minp -> next ; minp -> next = r2 ; /* 将原第一个数放到最小数原位置上 */ } q = q > next ; /* 选择下一个最小数 */ } } 2.分析：先调用划分函数 quickpass () ,以确定中间元素的位置，然后再借助栈分别对中间元素左、 右两边的区域进行快速排序。 Void qksort ( list A ) /* n 为元素个数 */ { InitStack ( S ) ; /* 设置一个栈保存有关参数和变量 */ j = 1 ; h = n ; /* j , h 分别指向表头和表尾 */ while ( ( j < h ) ‖( !empty ( S ) ) ) { while ( j < h ) { quickpass ( A,j,h,i ) ; /* 划分函数 quickpass () 参照教材 */ push ( S,j,h,i ) ; /* 保存变 量值 */ h = i – 1 ; /* 设置对左边进行划分的参数 */ } if ( !empty ( S ) ) { pop ( S,j,h,i ) ; /* 取出变 量值 */ j = i + 1 ; /* 设置对右边进行划分的参数 */ } } } 3．分析：插入排序的基本思想是：每趟从无序区间中取出一个元素，再 按键值大小插入到前面的有序区间中。对于有序区，当然可以用二分查 找来确定插入位置。 Void straightsort ( list A ) /* n 为元素个数，数组下标从1开始， 到n 结束。 */ { for ( i =2 ; i <= n ; i + + ) { low = 1 ; high = i – 1 ; /* low ,high 分为当前元 素上、下界 */ A[0] . key = A[i] . key ; While ( low <= high ) { mid = ( low + high ) /2 ; switch { case : A[0] . key <= A[mid] . key : high = mid – 1 ; /* 修改上界 */ case : A[0] . key > A[mid] . key : low = mid + 1 ; /* 修改下界 */ } for ( j = i-1 ; j >= mid ; j - -) A [j +1] = A [ j ] ; /* 移动数据 */ A[ mid ] = A[ i ] ; } } } 4．分析：本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上、下界相遇。 Void example ( datatype A [n] ) { i = 1, j = n ; /* i , j 为左右边界 */ while ( i < j ) { while ( ( i < j ) && ( A[ i ] < 0 ) ) i++ ; /* 在左边界找正数 */ while ( (i < j ) && ( A[ j ] > 0 )) j - - ; /* 在右边界找负数 */ if ( i < j) { temp = A[ i ]; A[ i ] = A[ j ]; A[ j ] = A [temp ] ; /*交换两个元素的值 */ i++ ; j - -; } } } 5．分析：此问题分为两个算法，第一个算法 shift 假设 a[ 1] , a[ 2 ],…,a[ k]为堆，增加一个无素 a[ k + 1 ],把数组 a[ 1 ],a[ 2 ], …,a[ k + 1 ]调整 为堆。第二个算法heep 从1开始调用 算法sift 将整个数组调整为堆。 Void sift (datatype A[ n ] , int K) /* n > = k + 1 */ { x = A[ K+1] ; i = K +1 ; while ( ( i/2 > 0 )&&( A[i/2]>x) ) { A[i]= A[i./2]; i = i/2;} /*从下往上插入位置 */ A[i] = x ; } Void heap ( datatype A[ n ] ) ; /* 从1开始调用算法sift ，将整个 数组调整为堆 */ { for ( k = 1 ; k <= n-1; k++ ) sift ( A,k ) ; } 6．分析：本算法采用的存储结构 是带头结点的双循环链表。首先找元 素插入位置，然后把元素从原链表中 删除，插入到相应的位置处。请注意 双链表上插入和删除操作的步骤。 Void sort ( dlklist H ) /* 链表H采用带头结点的双循环链表 */ { pre = H -> next ; while ( p != H ) {p = pre -> next ; /* p是有序表的末尾 */ q = p -> next ; /* 保存下一个插入元素 */ while((pre!=H)&&(p->data ->data))pre=pre–prior; /*从后往 前找插入位置 */ if ( pre ! =p -> prior ) { p-> prior->next = p -> next ; /* 删除p */ p-> next->prior = p -> prior; p->next = pre ->next ; /* 插入到pre 之后 */ pre -> next -> prior = p ; p ->prior= pre ; pre ->next = p ; } p=q; } } 1．下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 3.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。 A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序 5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并 6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆 7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。 A. 3 B. 10 C. 15 D. 25 8. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B ) A. l B. 4 C. 3 D. 2 9. 堆排序是（ E ）类排序 A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序 E．归并排序 F．shell排序 G．堆排序 H．基数排序 10.1C 5 2A 3D 4B 5G 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．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。 第9章排序自测卷姓名班级 一、填空题（每空1分，共24分） 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插 入到有序表时，为寻找插入位置至少需比较6 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本 无序，则最好选用快速排序。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2)。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)，所需要的附加空间 是O(n) 。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是H C Q P A M S R D F X Y； 初始步长为4的希尔（shell）排序一趟的结果是P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X； 堆排序初始建堆的结果是A D C R F Q M S Y P H X。 9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取方法，其次选取快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取堆排序、快速排序和归并排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题（每小题1分，共18分） （ C ）1．将5个不同的数据进行排序，至多需要比较次。 Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25 （C）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序（D）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为 第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937 (2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数） 第十章：内部排序练习题 一、选择题 1、下述几种排序方法中，平均查找长度最小的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 2、设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数为（）。 A、6 B、7 C、8 D、20 3、下列排序算法中不稳定的有（）。 A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序 E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序 4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（），相应的时间复杂度为（），该算法是（）排序方法。 A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定J、不稳定 5、对初始状态为递增的表按递增顺序排序，最省时间的是（）算法，最费时间的算法是（）。 A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 8、下列排序中，排序速度与数据的初始排列状态没有关系的是（）。 A、直接选择排序 B、基数排序 C、堆排序 D、直接插入排序 9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（）。 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序 10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 11、每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序 12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。 A、希尔排序 B、归并排序 C、插入排序 D、选择排序 13、n个记录的直接插入排序所需记录关键码的最大比较次数为（）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1 14、n个记录的直接插入排序所需的记录最小移动次数为（）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n 15、快速排序在（）情况下最不利于发挥其长处，在（）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据完全有序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。 第10章排序 一、填空题 1. 大多数排序算法都有两个基本的操作：和。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7 个记录60插入到有序表时，为寻找插入位置至少需比较次。 3. 在插入和选择排序中，若初始数据基本正序，则应选用排序算法；若初始数据基 本反序，则应选用排序算法。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本 无序，则最好选用。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。若对其进 行快速排序，在最坏的情况下所需要的时间是。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间 是。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排 列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；归并排序一趟扫描的结果是；快速排序一趟扫描的结果是；堆排序初始建堆的结果是。 9. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表进行排序，则最省 时间的是算法，最费时间的是算法。 10、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为。 二、单项选择题 1、下列四个序列中，（）是堆。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（） Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序 3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（） Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序 4．对ｎ个不同的排序码进行冒泡排序，在下列（）情况下比较的次数最多。 第十章排序 一、名词解释 1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序 二、填空 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为 ________的。 2.按照排序过程涉及的存储设备的不同，排序可分为________排序和 ________排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有： ________、________、________、 ________等四类。 4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。 5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i<=n;i++) {r[0]=r[i];j=i-1; while(r[0].key 第十章内部排序 10.23 void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 { k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)//二路插入排序的算法 { int d[MAXSIZE]; //辅助存储 x=L.r.key;d=x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x) //插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else //插入后部 { for(j=first;d[j] 第10章排序（参考答案） 18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。 20. 本题为步长为3的一趟希尔排序。 24.枢轴是73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。 64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。 部分答案解释如下： 5. 错误。例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。 12. 错误。堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。 22. 错误。待排序序列为正序时，简单插入排序比归并排序快。 三、填空题 1. 比较,移动 2.生成有序归并段（顺串）,归并 3.希尔排序、简单选择排序、快速排序、堆排序等 4. 冒泡,快速 5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时） 6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 7. n(n-1)/2 8.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->data 第10章排序 一、选择题 1．某内排序方法的稳定性是指( D )。【南京理工大学 1997 一、10（2分）】 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( D )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（D ）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（ B ）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（ B ）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序 6. 快速排序方法在（ D ）情况下最不利于发挥其长处。【燕山大学 2001 一、3 （2分）】 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序 7. 以下序列不是堆的是( D )。【西安电子科技大学 2001应用一、5 （2分）】 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) 8．下列四个序列中，哪一个是堆（ C ）。【北京工商大学 2001 一、8 （3分）】 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 9．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。【北京航空航天大学 1999 一、8（2分）】 A. 插入 B. 选择 C. 希尔 D. 二路归并 10．比较次数与排序的初始状态无关的排序方法是( D )。【北方交通大学 2000 二、2（2分）】A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序 11．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ B ）。 A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 【青岛大学 2000 三、4 （2分）】12．下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序【合肥工业大学 2001 一、3（2分）】13．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。【南京理工大学 1996 一、4 （2分）】 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 14．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。【燕山大学 2001 一、4（2分）】 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) 15．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。 A．冒泡 B. 希尔 C. 快速 D. 堆【南京理工大学 2001 一、12 （1.5分）】 16. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ C ）算法，最费时间的是（ B ）算 法。 A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序【南开大学 2000 一、5】 17. 就平均性能而言，目前最好的内排序方法是( D )排序法。【西安电子科技大学 1998 一、9 (2分）】 A. 冒泡 B. 希尔插入 C. 交换 D. 快速 18．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。 第10章排序 一、基础知识题 10.1 基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最 佳归并树。 【解答】⑴内排序和外排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 ⑵稳定排序和不稳定排序假设待排序记录中有关键字K i=K j（i≠j），且在排序前的序列中R i领先于R j。经过排序后，R i与R j的相对次序保持不变（即R i仍领先于R j），则称这种排序方法是稳定的，否则称之为不稳定的。 ⑶顺串外部排序通常经过两个独立的阶段完成。第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段。 ⑷败者树败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。 ⑸最佳归并树在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼树构造的k叉树称最佳归并树。这棵树中只有度为0和度为k的结点。若用m表示归并段个数，用n k表示度为k的个数，若 (m-1)%(k-1)=0，则不需增加虚段，否则应附加k-(m-1)%(k-1)-1个虚段（即第一个k路归并使用(m-1)%(k-1)+1个归并段）。 10.2设待排序的关键字序列为(15， 21， 6， 30， 23， 6′， 20， 17)，试 分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。 (1) 直接插入排序(2) 希尔排序(增量为5，2，1) (3) 起泡排序 (4) 快速排序(5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序(8) 二路归并排序 (9) 基数排序 【解答】 (1) 直接插入排序 初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接插入排序：【15，21】 第二趟直接插入排序：【6，15，21】 第三趟直接插入排序：【6，15，21，30】 第四趟直接插入排序：【6，15，21，23，30】 第五趟直接插入排序：【6，6′，15，21，23，30】 第六趟直接插入排序：【6，6′，15，20，21，23，30】 第十章排序 一、单项选择题 1.有一组序列48,36,68,99,75,24,58,52进行快速排序，要求结果按从小到大排序，则进行一次划分之后结果为_____。 A. (24 28 36) 48 (52 68 75 99) B. (28 36 24) 48 (75 99 68 52) C. (36 68 99) 48 (75 24 28 52) D. (28 36 24) 48 (99 75 68 52) 2.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是_____。 A. 希尔排序 B. 二分插入排序 C. 合并排序 D. 冒泡排序 3.排序译意风稳定的和不稳定的之分，下列四个说法中，只有______是正确的。 A. 快速排序是稳定的排序方法 B. 堆排序是不稳定的排序方法 C. 希尔排序是稳定的排序方法 D. 冒泡排序是不稳定的排序方法 4. 下列排序方法中，____方法是不稳定的。 A. 冒泡排序 B. 希尔排序 C. 冒泡排序 D. 直接插入排序 5. 下列排序方法中，在待排序的数据已经有序时，花费时间反而最多的是______。 A.快速排序 B. 希尔排序 C. 冒泡排序 D. 堆排序 6. 快速排序方法在最好情况下的时间复杂度为______。 A. O(n) B. O(n2) C. O(nlog2n) D.(log2n) 7. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。 A. 堆排序 B.冒泡排序 C. 直接选择排序 D.快速排序 8. 依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是____。 A. 快速排序 B.插入排序 C. 冒泡排序 D. 堆排序 9. 在表R中排序前已按键值递增顺序排序，则_____方法的比较次数最少。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 选择排序 10. 已知表A中每个元素距其最终位置不远，采用______方法最节省时间。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接选择排序 11. 在下列排序方法中，字比较的次数与记录的初始排列次序无关的是______。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 12. 快速排序方法在_____情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 13. 一组记录的关键字经一趟二路归并排序后得到含有５个长度为２的有序表：[25,48],[16,35],[79,82], [23,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,48,35,79,82,23,36,40,72 D. 16,25,35,48,79,23,36,40,72,82 14. 一组记录的关键码为(46,74,18,53,14,20,40,38,86,65)，利用堆排序的方法建立的初始堆为____。 A. (14,18,38,46,65,40,20,53,86,74) B. (14,38,18,46,65,20,40,53,86,74) C. (14,18,20,38,40,46,53,65,74,86) 一、填充题 1、按排序操作中所涉及的存储器的不同，可以把排序分成和两大类。 内部排序外部排序 2、主关键字是可以地标识一个数据元素的关键字。 唯一 3、希尔排序是属于插入排序的一种类型，它又被称为排序。 缩小增量 4、次关键字是用以标识数据元素的关键字。 多个 5、按关键字与排序结果的关系，可以把排序方法分成和两类。 稳定排序非稳定排序 6、在直接插入排序、希尔排序、直接选择排序、堆排序、快速排序和基数排序中，需要内存量最大的是。 基数排序 7、在堆排序和快速排序中，如果数据元素的原始序列接近正序或反序，则选用最好，如果数据元素的原始序列无序，则最好选用。 堆排序快速排序 8、对于由n个数据元素构成的序列实施冒泡排序时，最少的比较次数是。冒泡排序的结束条件是。 n-1 刚做完的一趟排序没有交换元素 9、对于由n个数据元素构成的序列实施冒泡排序时，数据元素的最少交换次数是，此情况说明该数据元素序列是。 0 已按排序要求有序的 二、单选题（每题2分，共24分） 1、如果采用直接选择排序法来排序一个长度为5，且已按相反顺序排序的数组，共需的比较次数是。 A、1 B、15 C、8 D、10 D 2、有一组随机数25，84，21，47，15，27，68，35，20，现在采用某种算法对它们进行排序， 具体过程如下： （1）25 84 21 47 15 27 68 35 20 （2）20 15 21 25 47 27 68 35 84 （3）15 20 21 25 35 27 47 68 84 （4）15 20 21 25 27 35 47 68 84 请根据以上情况，判断所用的排序方法是。 A、直接选择排序 B、快速排序 C、冒泡排序 D、Shall 排序 B 3、在所有学过的排序方法中，关键字比较次数与记录的初始排列次序无关的是。 A、冒泡排序 B、直接选择排序 C、直接插入排序 D、Shell排序 B 4、设有1000个无序的数据元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用的排序方法是。 A、冒泡排序 B、基数排序 C、堆排序 D、快速排序 C 5、在待排元素序列基本有序的前提下，下面给出的几种排序方法效率最高的是。 A、直接插入排序 B、直接选择排序 C、归并排序 D、快速排序 A 6、现有一待排序列为49，38，65，97，76，13，27，50，如果以第一个数据元素49为支撑元素，在经过一趟快速排序后的结果序列是。 A、27，38，65，97，76，13，49，50 B、27，38，49，97，76，13，65，50 C、27，38，13，49，76，97，65，50 D、27，38，13，97，76，49，65，50 C 7、在下面给出的几种排序方法中，从未排序之序列中依次取出元素与已经排好的序列（开始为空）中的元素进行比较以确定其在已排序列中的位置的排序方法是。 A、冒泡排序 B、希尔排序 C、快速排序 D、直接插入排序 D 第十章排序 一、选择题 1．某内排序方法的稳定性是指( D )。 A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法D．以上都不对 2．下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 3．稳定的排序方法是（ B ） A．直接插入排序和快速排序B．折半插入排序和起泡排序 ] C．简单选择排序和四路归并排序D．树形选择排序和shell排序 4．下列排序方法中，哪一个是稳定的排序方法（ B） A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序 5．若要求尽可能快地对序列进行稳定的排序，则应选（B）。 A．快速排序 B．归并排序 C．冒泡排序 6．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ CE ）就是不稳定的排序方法。 A．起泡排序B．归并排序C．Shell排序D．直接插入排序E．简单选择排序 7．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 8．下面的排序算法中，不稳定的是（ CDF ） ! A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。9．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序（1）其比较次数与序列初态无关的算法是（CDF ）（2）不稳定的排序算法是（ADF ）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< 第10章排序练习题答案 一、填空题 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插 入到有序表时，为寻找插入位置至少需比较3 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 正序时两种方法移动次数均为0，但比较次数量级不同，插入法：n-1即O(n)，选择法：O(n2) 反序时两种方法比较次数量级相同，均为O(n2)，但移动次数不同，插入法：O(n2)，选择法：3(n-1)即O(n) 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无 序，则最好选用快速排序。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2)。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)，所需要的附加空间 是O(n) 。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是H C Q P A M S R D F X Y； 二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X； 堆排序初始建堆的结果是Y S X R P C M H Q D F A。（大根堆） 9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题 （C）1．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 归并排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序 （D）2．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 冒泡排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序 （B）3．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。 Ａ. 从小到大排列好的Ｂ. 从大到小排列好的Ｃ. 元素无序Ｄ. 元素基本有序 （D）4．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 高中数学第十章-排列组合二项定理 考试内容： 分类计数原理与分步计数原理． 排列．排列数公式． 组合．组合数公式．组合数的两个性质． 二项式定理．二项展开式的性质． 考试要求： （1）掌握分类计数原理与分步计数原理，并能用它们分析和解决一些简单的应用问题． （2）理解排列的意义，掌握排列数计算公式，并能用它解决一些简单的应用问题． （3）理解组合的意义，掌握组合数计算公式和组合数的性质，并能用它们解决一些简单的应用问题． （4）掌握二项式定理和二项展开式的性质，并能用它们计算和证明一些简单的问题． §10. 排列组合二项定理 知识要点 一、两个原理. 1. 乘法原理、加法原理. 2. 可．以有．．重复．．元素．． 的排列. 从m 个不同元素中，每次取出n 个元素，元素可以重复出现，按照一定的顺序排成一排，那么第一、第二……第n 位上选取元素的方法都是m 个，所以从m 个不同元素中，每次取出n 个元素可重复排列数m·m·… m = m n .. 例如：n 件物品放入m 个抽屉中，不限放法，共有多少种不同放法？ （解：n m 种） 二、排列. 1. ⑴对排列定义的理解. 定义：从n 个不同的元素中任取m(m ≤n )个元素，按照一定顺序．．．．．．排成一列，叫做从n 个不同元素中取出m 个元素的一个排列. ⑵相同排列. 如果；两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序也必须完全相同. ⑶排列数. 从n 个不同元素中取出m (m≤n )个元素排成一列，称为从n 个不同元素中取出m 个元素的 一个排列. 从n 个不同元素中取出m 个元素的一个排列数，用符号m n A 表示. ⑷排列数公式： ),,()! (! )1()1(N m n n m m n n m n n n A m ∈≤-= +--= 注意：!)!1(!n n n n -+=? 规定0! = 1 111--++=?+=m n m n m n m m m n m n mA A C A A A 11 --=m n m n nA A 规定10 ==n n n C C 2. 含有可重元素．．．．．． 的排列问题. 对含有相同元素求排列个数的方法是：设重集S 有k 个不同元素a 1，a 2,…...a n 其中限重复数 9.1选择题 1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。 A）插入B）选择C）希尔D）二路归并 【答案】A 2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（） A）快速排序B）直接插入排序C）堆排序D）归并排序 【答案】B 3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下： 25 84 21 47 15 27 68 35 20 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则所采用的排序方法是（） Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序 【答案】Ｄ 4．下面给出的四种排序法中，（）排序是不稳定排序法。 A）插入B）冒泡C）二路归并D）堆 【答案】D 5．快速排序方法在（）情况下最不利于发挥其长处。 Ａ）要排序的数据量太大 Ｂ）要排序的数据中含有多个相同值 Ｃ）要排序的数据已基本有序 Ｄ）要排序的数据个数为奇数 【答案】Ｃ 6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（） Ａ）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．对记录的关键码{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．以下序列不是堆的是（）数据结构第10章 习题答案
第10章排序自测题答案
中南大学数据结构与算法第10章内部排序课后作业答案
第十章：内部排序练习题
第10章 排序 作业
第十章 排序
数据结构严蔚敏版第十章答案
第10章 排序答案
第十章排序答案
第10章 排序
第10章 排序
第十章试题(有答案)
第10章 排序练习题及答案
第10章排序练习题答案
高中数学知识点总结-第十章排列组合和二项式定理
数据结构第10章排序练习及答案