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

习题九习题九排序排序 一、单项选择题一、单项选择题 1．下列内部排序算法中 A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序，klinkhead; headp; whilep-linknull {qp-link; rp; while 1____________ { if q-link-datalink-data rq; qq-link; } if 2___________ {sr-link; r-links-link; s-link 3_________; 4_________;} 5________ ; } phead; headhead-link; freep; returnhead; } 6．下面的排序算法的思想是 第一趟比较将最小的元素放在r[1]中，最大的元素放在 r[n] 中，第二趟比较将次小的放在 r[2]中，将次大的放在 r[n-1]中，,依次下去，直到待排 序列为递增序。 （注）代表两个变量的数据交换） 。 void sortSqList while1______ { minmax1; for ji1;2________ ;j {if3________ minj; else ifr[j].keyr[max].key maxj; } if4_________ r[min] r[j]; ifmaxn-i1{if 5_______ r[min] r[n-i1]; else 6______; } i; } }D 8. A 9. C 10. D 11．C 12. C 二、填空题 1.稳定、不稳定 2.内部、外部 3．免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 4．nn-1/2 5．题中为操作方便，先增加头结点（最后删除） ，p 指向无序区的前一记录，r 指向最小值 结点的前驱，一趟排序结束，无序区第一个记录与r 所指结点的后继交换指针。 1q-linkNULL 2rp 3p-link 4p-links 5pp-link 6．.1in-i12jn-i13r[j].keyr[min].key4mini5maxi 6r[max]r[n-i1] 7．11 2a[i]t 3i2;in;i2 41 5flag