搜索
习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n•logn)的算法是（）为O(n•n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是()。A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A.选择B.冒泡C.快速D.插入4．下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆5．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。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)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。A．冒泡B.希尔C.快速D.堆7.就平均性能而言，目前最好的内排序方法是()排序法。A.冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A.归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。A.3B.10C.15D.2510.快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序11．下列四个序列中，哪一个是堆（）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1512.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。二、填空题1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。3．直接插入排序用监视哨的作用是___________________________。4．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。5．下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：#includestdio.htypedefstructnode{chardata;structnode*link;}node;node*select(node*head){node*p,*q,*r,*s;p=(node*)malloc(sizeof(node));p-link=head;head=p;while(p-link!=null){q=p-link;r=p;while((1)____________){if(q-link-datar-link-data)r=q;q=q-link;}if((2)___________){s=r-link;r-link=s-link;s-link=((3)_________);((4)_________);}((5)________);}p=head;head=head-link;free(p);return(head);}6．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…,依次下去，直到待排序列为递增序。（注：--）代表两个变量的数据交换）。voidsort(SqList&r,intn){i=1;while((1)______){min=max=1;for(j=i+1;(2)________;++j){if((3)________)min=j;elseif(r[j].keyr[max].key)max=j;}if((4)_________)r[min]----r[j];if(max!=n-i+1){if((5)_______)r[min]----r[n-i+1];else((6)______);}i++;}}//sort7．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。voidoesort(inta[n]){intflag,i,t;do{flag=0;for(i=1;in;i++,i++)if(a[i]a[i+1]){flag=(1)______;t=a[i+1];a[i+1]=a[i];(2)________;}for(3)________if(a[i]a[i+1]){flag=(4)________;t=a[i+1];a[i+1]=a[i];a[i]=t;}}while(5)_________;}三、应用题1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。2．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80，82，85，98，1003．填空并回答相关问题(1)下面是将任意序列调整为最大堆（MAXHEAP）的算法，请将空白部分填上：将任意序列调整为最大堆通过不断调用adjust函数，即：FOR（i=n/2；i0；i--）adjust（list，i，n）；其中list为待调整序列所在数组（从下标1开始），n为序列元素个数，adjust函数为：voidadjust（intlist[]，introot，intn）/*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/{intchild,rootkey;rootkey=list[root];child=2*root;while(child=n){if((childn)&&(list[child]list[child+1]))(1)_______;if(rootkeylist[child])break;else{List[(2)]=list[child];child*=2;}}list[child/2]=rootkey;}(2)．判断下列序列能否构成最大堆：（12，70，33，65，24，56，48，92，86，33）；若不能按上述算法将其调整为堆，调整后的结果为：（）。四、算法设计题：1．设计一个用链表表示的直接选择排序算法。2．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替进行的冒泡排序算法（即双向冒泡排序法）。3．输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行10个记录）。排序方法采用选择排序。4．已知（k1,k2……，kn）是堆，试写一个算法将（k1,k2,……，kn,kn+1）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个kn+1后应从叶子向根的方向调整）。第九章排序一、单项选择题1．（1）DC（2）ADF（3）B（4）ACFBDE2．D3．A4．C5．C6．C7.D8.A9.C10.D11．C12.C二、填空题1.稳定、不稳定2.内部、外部3．免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。4．n(n-1)/25．题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。(1)q-link!=NULL(2)r!=p(3)p-link(4)p-link=s(5)p=p-link6．.(1)in-i+1(2)j=n-i+1(3)r[j].keyr[min].key(4)min!=i(5)max==i(6)r[max]--r[n-i+1]7．(1)1(2)a[i]=t(3)(i=2;i=n;i+=2)(4)1(5)flag三、应用题1．解答：①直接插入排序序号123456789101112关键字834063138435965739796115i=24083[63138435965739796115]i=3406383[138435965739796115]i=413406383[8435965739796115]i=51340638384[35965739796115]i=6133540638384[965739796115]i=713354063838496[5739796115]i=81335405763838496[39796115]i=9133539405763838496[796115]i=1013353940576379838496[6115]i=111335394057616379838496[15]i=12131535394057616379838496②直接选择排序序号123456789101112关键字834063138435965739796115i=113[4063838435965739796115]i=21315[63838435965739796140]i=3131535[838463965739796140]i=413153539[8463965783796140]i=51315353940[63965783796184]i=6131535394057[966383796184]i=713153539405761[6383799684]i=81315353940576163[83799684]i=9131535394057616379[839684]i=1013153539405761637983[9684]i=111315353940576163798384[96]③快速排序关键字834063138435965739796115第一趟排序后[154063136135795739]83[9684]第二趟排序后[13]15[63406135795739]8384[96]第三趟排序后1315[3940613557]63[79]838496第四趟排序后1315[35]39[614057]6379838496第五趟排序后13153539[5740]616379838496第六趟排序后1315353940[57]616379838496第七趟排序后13153539405761637