第十章排序 名词解释 1.排序 2.内部排序3.外部排序 4.堆 5.堆排序 、填空 1.若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保 持不变,则称这种排序方法是的,否则称为 的 2.按照排序过程涉及的存储设备的不同,排序可分为 排序和 排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类,主要有: 等四类。 4在排序算法中,分析算法的时间复杂性时,通常以 和 为标准操作。评价 排序的另一个主要标准是执行算法所需要的 5.常用的插入排序方法有 插入排序、 插入排序 插入排序和 插入排序。 6.以下为直接插入排序的算法。请分析算法,并在 上填充适当的语句 void straightsort(list r) ifor (i= i=x key)&&(i<j)) /*自尾端进行比较* ;i++;/*将r[j.kiy<x.key的记示移至i所指位置* while((r[i]. key<=x key)&&(i<j)) /*自首行端进行比较*/ if(i<j)[ j-;}/*将r[j].kiy<x.key的记示移至j所指位置*/
第十章 排序 一、名词解释 1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序 二、填空 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保 持不变，则称这种排序方法是________的，否则称为________的。 2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、 ________、________等四类。 4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价 排序的另一个主要标准是执行算法所需要的________。 5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和 ________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i=x.key)&&(i<j))________;/*自尾端进行比较*/ if(i<j) {________;i++;/* 将 r[j].kiy<x.key 的记示移至 i 所指位置*/ while((r[i].key<=x.key)&&(i<j))________;/*自首行端进行比较*/ if(i<j){________;j--;}/* 将 r[j].kiy<x.key 的记示移至 j 所指位置*/ }
r[i]= return(i);/*一趟快速排序结束,将x移至正确的位置* 1.对快速排序来讲,其最好情况下的时间复杂度是 其最坏情况下的时间复杂度是 12.以下是直接选择排序的算法。请分析算法,并在横线上填充适当的语句 void select(list r, int n Ifor (i=l:i<= i+)/*每次循环,选择出一个最小键值* for(j=i+1: j<=n; j++)if(r[j]. key<r[k]. key) )swap(r[k],r[i]);/函数swap(r[k],r[i])交换r[k]和r[i]的位置* 13.直接选择排序是不稳定的,其时间复杂性为 14.树形选择排序要增加 个结点以保存前面比较的结果。另外,排序的结果还需要另 外开辟 15.树形选择排序可用一棵树来表示这一排序过程,树中的n个叶子代表待排序记录的键值 叶子上面一层是 两两比较的结果,依次类推。 表示最后选择出来的最小关 键字。在选择次最小键值时,只需将叶结点中最小键值改成 重新进行比较。依次 类推。 16.若树形选择排序的叶子数为n,除第一次需执行 次比较就选择出一个最小的键值 外,以后的每次都只经过 次比较就选择出一个最小的键值。所以树形选择排序总的 时间开销为 17.从一个无序序列建立一个堆的方法是:首先将要排序的所有键值分放到一棵的各 个结点中,然后从i 的结点k开始,逐步把以k/2,k21,kw2,…为根的子树排成 堆,直到以k为根的树排成堆,就完成了建堆的过程 18.堆排序是不稳定,空间复杂度为 。在最坏情况下,其时间复杂性也为 19.以下将a,…,a和an,…,an两个有序序列(它们相应的关键字值满足K<=…<=K,K< <=K)合并成一个有序序列R,…,R(使其关键字值满足K<=…<=K)。请分析算法,并在 上填充适当的语句。 void merge(list a, list R, int h, int m, int n) li=h: k=h: j=m+1 while((i<=m)&&(j<=n)) Hif(ali]. key<=aLj] key)IRIk] else iRak] k++ while(i< ){R[k]=a[i];i++;k++;} while(j<= R[k]=a[j;j+;k++;} 此算法的执行时间为 20.归并排序要求待排序列由若干个 的子序列组成。 21.二路归并排序的时间复杂度是 22.对于n个记录的集合进行归并排序,所需的附加空间消耗是
} 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<r[k].key)________; if(______)swap(r[k],r[i]）;/*函数 swap(r[k],r[i]）交换 r[k]和 r[i]的位置*/ } } 13.直接选择排序是不稳定的，其时间复杂性为________。 14.树形选择排序要增加________个结点以保存前面比较的结果。另外，排序的结果还需要另 外开辟________. 15.树形选择排序可用一棵树来表示这一排序过程，树中的 n 个叶子代表待排序记录的键值， 叶子上面一层是________两两比较的结果，依次类推。________表示最后选择出来的最小关 键字。在选择次最小键值时，只需将叶结点中最小键值改成________，重新进行比较。依次 类推。 16.若树形选择排序的叶子数为 n，除第一次需执行________次比较就选择出一个最小的键值 外，以后的每次都只经过________次比较就选择出一个最小的键值。所以树形选择排序总的 时间开销为________。 17.从一个无序序列建立一个堆的方法是：首先将要排序的所有键值分放到一棵________的各 个结点中，然后从 i=________的结点 ki 开始，逐步把以 kn/2,kn/2-1,kn/2-2,……为根的子树排成 堆，直到以 k1 为根的树排成堆，就完成了建堆的过程。 18.堆排序是不稳定，空间复杂度为________。在最坏情况下，其时间复杂性也为________。 19.以下将 ah,…,am和 am+1,…,an 两个有序序列（它们相应的关键字值满足 Kh<=…<=Km,Km+1<=… <=Kn）合并成一个有序序列 Rh，…,Rn（使其关键字值满足 Kh<=…<=Kn）。请分析算法，并在 ________上填充适当的语句。 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.设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、冒泡排序和归并排序 方法对其仍按递增顺序进行排序,则 最省时间, 最费时间 4.分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递 增顺序进行排序,最省时间的是 算法,最费时间的是 算法 单项选择 1.以下说法错误的是 ①直接插入排序的空间复杂度为0(1) ②快速排序附加存储开销为0(log2n) ③堆排序的空间复杂度为0(n)。 ④二路归并排序的空间复杂度为0(n),需要附加两倍的存储开销。 以下不稳定的排序方法是 ①直接插入排序 ②冒泡排序 ③直接选择排序④二路归并排序 3.以下稳定的排序方法是 ①快速排序 ②冒泡排序 ③直接选择排序④堆排序 4.以下时间复杂性不是0(mn2)的排序方法是 ①直接插入排序 ②二路归并排序③冒泡排序 ④直接选择排序 5.以下时间复杂性不是0nlog2n)的排序方法是 ①堆排序 ②直接插入排序③二路归并排序④快速排序 6.在文件局部有序或文件长度较小的情况下,最佳的排序方法是 ①直接插入排序②冒泡排序 ③直接选择排序④归并排序 7.对于大文件的排序要研究在外设上的排序技术,即 ①快速排序法 ②内排序法 ③外排序法④交叉排序法 8.排序的目的是为了以后对已排序的数据元数进行 )操作 ①打印输出 ②分类 ③合并 ④查找 9.当初始序列己按健值有序时,用直接插入算法进行排序,需要比较的次数为() ②l0g2n ③2logn ④n 10.快速排序在最坏的情况下的时间复杂度是 ①0(logn) ②0(nlog2n) ③0(n2) ④0(n) 1.具有24个记录的序列,采用冒泡排序至少的比较次数是 12.用某种排序方法对序列(25,84,21,47,15,27,68,35,20)进行排序,记录序列 的变化情况如下 25842147152768 555 212547276 21253527476884 021252735476884 则采取的排序方法是 直接选择排序 ②冒泡排序 ③快速排序 ④二路归并排序 3.在排序过程中,健值比较的次数与初始序列的排列顺序无关的是 ①直接插入排序和快速排序 ②直接插入排序和归并排序 ③直接选择排序和归并排序 ④快速排序和归并排序 14.()方法是从未排序序列中依次取出元素与已排序序列中的元素作比较,将其放入已 排序序列的正确位置上。 ①归并排序 ②插入排序 ③快速排序 ④选择排序
23.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序 方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。 24．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递 增顺序进行排序，最省时间的是___________算法，最费时间的是___________算法。 三、单项选择 1． 以下说法错误的是 （ ） ①直接插入排序的空间复杂度为 O(1)。 ②快速排序附加存储开销为 O(log2n)。 ③堆排序的空间复杂度为 O(n)。 ④二路归并排序的空间复杂度为 O(n),需要附加两倍的存储开销。 2． 以下不稳定的排序方法是 （ ） ①直接插入排序 ②冒泡排序 ③直接选择排序 ④二路归并排序 3． 以下稳定的排序方法是 （ ） ①快速排序 ②冒泡排序 ③直接选择排序 ④ 堆排序 4． 以下时间复杂性不是 O(n2 )的排序方法是 （ ） ①直接插入排序 ②二路归并排序 ③冒泡排序 ④直接选择排序 5． 以下时间复杂性不是 O(nlog2n)的排序方法是 （ ） ①堆排序 ② 直接插入排序 ③二路归并排序 ④快速排序 6． 在文件局部有序或文件长度较小的情况下，最佳的排序方法是 （ ） ①直接插入排序 ② 冒泡排序 ③ 直接选择排序 ④归并排序 7． 对于大文件的排序要研究在外设上的排序技术，即 （ ） ①快速排序法 ② 内排序法 ③外排序法 ④ 交叉排序法 8．排序的目的是为了以后对已排序的数据元数进行（ ）操作。 ①打印输出 ②分类 ③ 合并 ④查找 9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ） ①n-1 ②log2n ③ 2log2n ④n 2 10.快速排序在最坏的情况下的时间复杂度是 （ ） ①O(log2n) ②O(nlog2n) ③ 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) 从小到大进行排序,共要进行()次比较。 ②45 370 ④91 2.在任何情况下,快速排序方法的时间性能总是最优的。这种说法 ①正确 ②错误 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.插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的
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,k2……,kn)是堆,试写一个算法将(k,k2,…,kn,kn)调整为堆。按此思想 写一个从空堆开始一个一个填入元素的建堆算法(题示:增加一个km后应从叶子向根的 方向调整) 6.设计一个用链表表示的直接插入排序算法
插入排序方法。 4． 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性 表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。 5． 已知（k1,k2……，kn）是堆，试写一个算法将（k1,k2,……，kn,kn+1）调整为堆。按此思想 写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个 k n+1 后应从叶子向根的 方向调整）。 6． 设计一个用链表表示的直接插入排序算法