数据结构第七章排序习题.doc

07排序【单选题】1. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。A、直接插入B、简单选择C、希尔D、二路归并2. 直接插入排序在最好情况下的时间复杂度为（B）。A、O(logn)B、O(n)C、O(n*logn)D、O(n2)3. 设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（B）。A、79,46,56,38,40,80B、84,79,56,38,40,46C、84,79,56,46,40,38D、84,56,79,40,46,384. 设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,56,79,84D、40,38,46,84,56,795. 将两个各有n个元素的有序表归并成一个有序表，最少进行（A）次比较。A、nB、2n-1C、2nD、n-16. 下列排序方法中，排序趟数与待排序列的初始状态有关的是（C）。A、直接插入B、简单选择C、起泡D、堆7. 下列排序方法中，不稳定的是（D）。A、直接插入B、起泡C、二路归并D、堆8. 若要在O(nlog2n)的时间复杂度上完成排序，且要求排序是稳定的，则可选择下列排序方法中的（C）。A、快速B、堆C、二路归并D、直接插入9. 设有1000个无序的数据元素，希望用最快的速度挑选出关键字最大的前10个元素，最好选用（C）排序法。A、起泡B、快速C、堆D、基数10. 若待排元素已按关键字值基本有序，则下列排序方法中效率最高的是（A）。A、直接插入B、简单选择C、快速D、二路归并11. 数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（C）的两趟排序后的结果。A、选择排序B、冒泡排序C、插入排序D、堆排序12. （A）占用的额外空间的空间复杂性为(1)。A、堆排序算法B、归并排序算法C、快速排序算法D、以上答案都不对13. 对一组数据（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）。A、选择B、冒泡C、快速D、插入14. 一个排序算法的时间复杂度与（B）有关。A、排序算法的稳定性B、所需比较关键字的次数C、所采用的存储结构D、所需辅助存储空间的大小15. 适合并行处理的排序算法是（B）。A、选择排序B、快速排序C、希尔排序D、基数排序16. 下列排序算法中，（A）算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。A、快速排序B、堆排序C、希尔排序D、起泡排序17. 有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是（A）。A、希尔排序B、堆排序C、起泡排序D、快速排序18. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A）。A、直接插入排序B、起泡排序C、简单选择排序D、快速排序19. 下列排序算法中，（D）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A、堆排序B、冒泡排序C、快速排序D、插入排序20. 下列排序算法中，占用辅助空间最多的是（A）。A、归并排序B、快速排序C、希尔排序D、堆排序21. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。A、插入B、选择C、希尔D、二路归并22. 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（C）。A、94,32,40,90,80,46,21,69B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,4023. 对序列15，9，7，8，20，-1，4用希尔排序方法排序，经一趟后序列变为15，-l，4，8，20，9，7则该次采用的增量是（B）。A、lB、4C、3D、224. 在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D）位置上。A、n/2B、n/2 -1C、1D、n/2 +225. 对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（A）。A、每次分区后，先处理较短的部分B、每次分区后，先处理较长的部分C、与算法每次分区后的处理顺序无关D、以上三者都不对26. 从堆中删除一个元素的时间复杂度为（B）。A、O(1)B、O(log2n)C、O(n)D、O(nlog2n)【计算题】1. 设有关键字序列（503，087，512，061，908，170，897，275，653，426），试用下列各内部排序方法对其进行排序，要求写出每趟排序结束时关键字序列的状态。(1)直接插入法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：087，503，512，061，908，170，897，275，653，426第二趟：087，503，512，061，908，170，897，275，653，426第三趟：061，087，503，512，908，170，897，275，653，426第四趟：061，087，503，512，908，170，897，275，653，426第五趟：061，087，170，503，512，908，897，275，653，426第六趟：061，087，170，503，512，897，908，275，653，426第七趟：061，087，170，275，503，512，897，908，653，426(2)希尔排序法，增量序列为（5，3，1）；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：170，087，275，061，426，503，897，512，653，908第二趟：061，087，275，170，426，503，897，512，653，908第三趟：061，087，170，275，426，503，512，653，897，908(3)快速排序法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：426，087，275，061，170，503，897，908，653，512第二趟：170，087，275，061，426，503，512，653，897，908第三趟：061，087，170，275，426，503，512，653，897，908第四趟：061，087，170，275，426，503，512，653，897，908(4)堆排序法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：908，653，897，503，426，170，512，275，061，087第二趟：897，653，512，503，426，170，087，275，061，908第三趟：653，503，512，275，426，170，087，061，897，908第四趟：512，503，170，275，426，061，087，653，897，908第五趟：503，426，170，275，087，061，512，653，897，908第六趟：426，275，170，061，087，503，512，653，897，908第七趟：275，087，170，061，426，503，512，653，897，908第八趟：170，087，061，275，426，503，512，653，897，908第九趟：087，061，170，275，426，503，512，653，897，908第十趟：061，087，170，275，426，503，512，653，897，908(5)二路归并排序法；解：初始：503，087，512，061，908，170，897，275，653，426第一趟：087，503，061，512，170，908，275，897，426，653第二趟：061，087，503，512，170，275，897，908，426，653第三趟：061，087，170，275，503，512，897，908，426，653第四趟：061，087，170，275，426，503，512，653，897，908【算法题】下列算法题中可能用到的类如下：public class SortTable private int st ; public SortTable(int length) int i; st=new intlength; for(i=0;isti+1，则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。解：public void oesort( ) boolean change=true; int temp; while (change) change=false; for(i=0;ist.length;i+=2) if (sti+1sti) change=true; temp=sti+1; sti+1=sti; sti=temp; /if /for for(i=1;ist.length;i+=2) if (sti+1sti) change=true; temp=sti+1; sti+1=sti; sti=temp; /if /for /while/oesort(2)设待排数据元素的值互不相同，对它们按计数排序法进行排序，方法为：另设数组count，对每个元素sti，统计关键字值比它小的元素个数存于counti，再依counti值的大小对st中元素进行重排。解：public void countSort( )/计数排序算法 int c =new int st.length; for(i=0;ist.length;i+) ci=0; for(i=0;ist.length-1;i+) for(j=i+1;jst.length;j+) /对每一对元素 if(aiaj) cj+; else ci+; for(i=0;in;i+)/依次求出关键字最小,第二小,.,最大的记录 min=0; for(j=0;jn;j+) if(cj