第十章排序

第十章排序一、名词解释1.排序2.内部排序3.外部排序4.堆5.堆排序二、填空1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。voidstraightsort(listr);{for(i=___________;i=n;i++){r[0]=r[i];j=i-1;while(r[0].keyr[j].key){r[j+1]=________;j--;}r[j+1]=_______;}}7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。voidbulbblesort(intn,listr)/*flag为特征位，定义为布尔型*/{for(i=1;i=________;i++){_______________;for(j=1;j=_________;j++)if(r[j+1].keyr[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;}if(flag)return;}}9.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。10.以下对r[h],r[h+1],……r[p]子序列进行一趟忆速排序。请分析算法，并在________上填充适当的语句。intquickpass(listr,inth,intp){i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/while(ij){while((r[j].key=x.key)&&(ij))________;/*自尾端进行比较*/if(ij){________;i++;/*将r[j].kiyx.key的记示移至i所指位置*/while((r[i].key=x.key)&&(ij))________;/*自首行端进行比较*/if(ij){________;j--;}/*将r[j].kiyx.key的记示移至j所指位置*/}}r[i]=________;return(i);/*一趟快速排序结束，将x移至正确的位置*/}11.对快速排序来讲，其最好情况下的时间复杂度是________，其最坏情况下的时间复杂度是________。12.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。voidselect(listr,intn){for(i=1;i=________;i++)/*每次循环，选择出一个最小键值*/{k=i;for(j=i+1;j=n;j++)if(r[j].keyr[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）。请分析算法，并在________上填充适当的语句。voidmerge(lista,listR,inth,intm,intn){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(log2n)。③堆排序的空间复杂度为O(n)。④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。2．以下不稳定的排序方法是（）①直接插入排序②冒泡排序③直接选择排序④二路归并排序3．以下稳定的排序方法是（）①快速排序②冒泡排序③直接选择排序④堆排序4．以下时间复杂性不是O(n2)的排序方法是（）①直接插入排序②二路归并排序③冒泡排序④直接选择排序5．以下时间复杂性不是O(nlog2n)的排序方法是（）①堆排序②直接插入排序③二路归并排序④快速排序6．在文件局部有序或文件长度较小的情况下，最佳的排序方法是（）①直接插入排序②冒泡排序③直接选择排序④归并排序7．对于大文件的排序要研究在外设上的排序技术，即（）①快速排序法②内排序法③外排序法④交叉排序法8．排序的目的是为了以后对已排序的数据元数进行（）操作。①打印输出②分类③合并④查找9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（）①n-1②log2n③2log2n④n210.快速排序在最坏的情况下的时间复杂度是（）①O(log2n)②O(nlog2n)③O(n2)④O(n3)11.具有24个记录的序列，采用冒泡排序至少的比较次数是（）①1②23③24④52912．用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：258421471527683520152021254727683584152021253527476884152021252735476884则采取的排序方法是（）①直接选择排序②冒泡排序③快速排序④二路归并排序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④9122．在任何情况下，快速排序方法的时间性能总是最优的。这种说法①正确②错误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．已知（k1,k2……，kn）是堆，试写一个算法将（k1,k2,……，kn,kn+1）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个kn+1后应从叶子向根的方向调整）。6．设计一个用链表表示的直接插入排序算法。第十章参考答案二、填空1．稳定、不稳定2.内部、外部3．插入排序、交换排序、选择排序、归并排序4.键值比较、记录移动、附加空间5．直接、折半、表、希尔6.2、r[j]、r[0]7.O（n2）、O（1）8.n-1、flag=1、n-i9.O