文本内容:
习题
91.下列算法中,某一趟排序结束后未必能选出一个记录放在其最终位置上的是A.堆排序B.冒泡排序C.直接插入排序D.快速排序
2.假如只想得到1000个记录中关键字最小的前4个记录排序的序列,用方法最好A.冒泡排序B.快速排序C.堆排序D.选择排序
3.是不稳定的排序方法A.冒泡排序B.归并排序C.插入排序D.选择排序
4.已知数据表A中每个元素距其排序的最终位置不远,则采用排序算法最省时间A.堆排序B.插入排序C.直接选择排序D.快速排序
5.对初始状态为递增序列的表按递增顺序排序,最省时间的是算法,最费时间的是算法A.堆排序B.快速排序C.插入排序D.归并排序A.冒泡排序B.希尔插入C.交换排序D.快速排序
6.就平均性能而言,目前最好的内部排序方法是
7.在含有n个关键字的最小堆堆顶元素最小中,关键字最大的记录有可能存储在位置上A.Ln/2j B.Ln/2j-1C.1D.[_n/2」+
28.以下序列不是堆的是oA.100,85,98,77,80,60,82,40,20,10,66B.100,98,85,82,80,77,66,60,40,20,10C.10,20,40,60,66,77,80,82,85,98,100D.100,85,40,77,80,60,66,98,82,10,
209.对下列关键字序列用快速排序算法排序,哪一种情况排序的速度最快?哪一种情况排序的速度最慢?为什么?A.19,23,3,15,7,21,28B.23,21,28,15,19,3,7C.3,7,15,19,21,23,
2810.简述直接插入排序、直接选择排序、二路归并排序的基本思想及在时间复杂度和排序稳定性上的差别H.在堆排序、快速排序和归并排序中1若只从存储空间考虑,则应首先选取哪种排序方法,其次选取哪种排序方法,最后选取哪种排序方法?2若只从排序结果的稳定性考虑,则应选取哪种排序方法?3若只从平均情况下排序最快考虑,则应选取哪种排序方法?4若只从最坏情况下排序最快并且要节省内存考虑,则应选取哪种排序方法?
12.设有5个互不相同的元素a、b、c、d、e,能否通过7次比较就将其排好序?如果能,请列出其比较过程;如果不能,则说明原因
13.已知待排序的序列为{703,127,63,58,907,273,846,325,685,412,试完成下列各题1根据以上序列建立一个堆画出建立初始堆的过程,希望先输出最小值2输出最小值后,如何得到次小值画出堆调整的过程
14.已知记录的关键字序列{385,123,62,38,29,5,856,23,35,68,试按链式基数排序法排序,画出一趟分配和收集的过程
15.有一个整数数组a[O..n.l]中存有互不相同的取值在1〜n之间的n个整数请设计一个算法在0n时间内将数组a中的元素递增排序存放在另一个同样大小的数组b中
16.对于给定的含有n个互不相同的元素的无序数组利用快速排序的方法,求得a中的第k iWkWn小的元素,并分析所设计的算法的最好及平均时间复杂度
17.荷兰国旗难题“是计算机科学中的一个程序难题,它是由Edsger Dijkstra提出的,荷兰国旗是由红、白、蓝三色组成的,需要将红、白、蓝三种颜色按照顺序排序现在用0,1,2分别代表红白蓝三种颜色,例如{0,1,2,0,2,1}排序后应为{0,0,1,h2,2}o请设计程序,在On时间内将其排序。