排序习题数据结构.doc

习题九 排序一、单项选择题1下列内部排序算法中： A快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序（1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（ ）（4）排序的平均时间复杂度为O(nlogn)的算法是（ ）为O(nn)的算法是（ ）2比较次数与排序的初始状态无关的排序方法是( )。A直接插入排序 B起泡排序 C快速排序 D简单选择排序3对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 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. 3 B. 10 C. 15 D. 25 10. 快速排序方法在（ ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序11下列四个序列中，哪一个是堆（ ）。A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,1512. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）A-1，4，8，9，20，7，15，7 B-1，7，15，7，4，8，20，9C-1，4，7，8，20，15，7，9 DA，B，C均不对。二、填空题1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是_的，否则称为_的。2.按照排序过程涉及的存储设备的不同，排序可分为_排序和_排序。3直接插入排序用监视哨的作用是_。4对n个记录的表r1.n进行简单选择排序，所需进行的关键字间的比较次数为_。5下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：#include typedef struct node char data; struct node *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-datalink-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下面的排序算法的思想是：第一趟比较将最小的元素放在r1中，最大的元素放在rn中，第二趟比较将次小的放在r2中，将次大的放在rn-1中，,依次下去，直到待排序列为递增序。（注：）代表两个变量的数据交换）。void sort(SqList &r,int n) i=1;while(1)_) min=max=1;for (j=i+1;(2)_ ;+j) if(3)_) min=j; else if(rj.keyrmax.key) max=j; if(4)_) rmin rj;if(max!=n-i+1)if (5)_) rmin rn-i+1; else (6)_); i+;/sort 7下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将ai和ai+1进行比较,第二趟对所有偶数的i,将ai和ai+1进行比较,每次比较时若aiai+1,将二者交换;以后重复上述二趟过程,直至整个数组有序。void oesort (int an)int flag,i,t; do flag=0;for(i=1;iai+1) flag=(1)_; t=ai+1; ai+1=ai; (2)_;for (3)_ if (aiai+1) flag=(4)_;t=ai+1; ai+1=ai; ai=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)下面是将任意序列调整为最大堆（MAX HEAP）的算法，请将空白部分填上：将任意序列调整为最大堆通过不断调用adjust函数，即：FOR（i=n/2；i 0；i- -）adjust（list，i，n）；其中list为待调整序列所在数组（从下标1开始），n为序列元素个数，adjust函数为：void adjust（int list，int root，int n）/*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/int child,rootkey;rootkey=listroot;child=2*root;while(child=n)if(childn)&(listchildlistchild) break; elseList(2) =listchild; child*=2; listchild/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）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个k n+1后应从叶子向根的方向调整）。第九章 排序一、单项选择题1（1） DC （2）ADF （3）B （4）ACF BDE 2D3A4C5C6C7. D8. A9. C10. D11C12. C二、填空题1.稳定、不稳定2.内部、外部3免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。4n(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)rj.keyrmin.key (4)min!=i (5)max=i (6)rmaxrn-i+17(1)1 (2)ai=t (3)(i=2;i next !=NULL ) pl = q - next ; minp =pl; /* minp指向当前已知的最小数 */ while ( pl - next != NULL ) if ( pl - next - data 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 ; /* 选择下一个最小数 */ 2void BubbleSort2(int a,int n) /相邻两趟向相反方向起泡的冒泡排序算法 change=1;low=0;high=n-1; /冒泡的上下界 while(lowhigh & change) change=0; /设不发生交换 for(i=low;iai+1)aiai+1;change=1; /有交换，修改标志change high-; /修改上界 for(i=high;ilow;i-) /从下向上起泡 if(aiai-1)aiai-1;change=1; low+; /修改下界 /while/BubbleSort2 算法讨论题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。3typedef struct int num; float score; RecType;void SelectSort(RecType R51，int n) for(i=1; in; i+) /选择第i大的记录，并交换到位k=i; /假定第i个元素的关键字最大 for(j=i+1;jRk.score) k=j;if(i!=k) Ri Rk; /与第i个记录交换/for for(i=1; i = k + 1 */ x = A K+1 ; i = K +1 ;while ( ( i/2 0 )&( Ai/2x) ) Ai= Ai./2; i = i/2; /*从下往上插入位置 */Ai = x ; Void heap ( datatype A n ) ; /* 从1开始调用算法sift ，将整个数组调整为堆 */ for ( k = 1 ; k = n-1; k+ ) sift ( A,k ) ;