数据结构第九章排序习题及答案

习题九习题九排序排序 一、单项选择题一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序，klink=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．下面的排序算法的思想是： 第一趟比较将最小的元素放在r[1]中，最大的元素放在 r[n] 中，第二趟比较将次小的放在 r[2]中，将次大的放在 r[n-1]中，…,依次下去，直到待排 序列为递增序。 （注：）代表两个变量的数据交换） 。 void sort(SqList while((1)______) { min=max=1; for (j=i+1;(2)________ ;++j) {if((3)________) min=j; else if(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++; } }D 8. A 9. C 10. D 11．C 12. C 二、填空题 1.稳定、不稳定 2.内部、外部 3．免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 4．n(n-1)/2 5．题中为操作方便，先增加头结点（最后删除） ，p 指向无序区的前一记录，r 指向最小值 结点的前驱，一趟排序结束，无序区第一个记录与r 所指结点的后继交换指针。 (1)q-link!=NULL (2)r!=p (3)p-link (4)p-link=s (5)p=p-link 6．.(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