2. 计算机
  3. 对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用______(62)，使用分治(Divide and Conquer)策略的是______(63)算法。 (62)

对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用______(62)，使用分治(Divide and Conquer)策略的是______(63)算法。 (62)

admin2018-07-23  54
问题 对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用______(62)，使用分治(Divide and Conquer)策略的是______(63)算法。
(62)
选项 A、希尔排序
B、直接插入排序
C、快速排序
D、堆排序
答案D
解析 本题考查常见内部排序算法的思想。
    ①希尔排序的思想是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2＜d1重复上述的分组和排序，直至所取的增量dt=1(dt＜dt-1＜…＜d2＜d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
    ②直接插入排序的思想是：每次从无序表中取出第一个元素，把它插入有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入有序表中；第二趟把第三个数与前两个数从后向前扫描，把第三个数按大小插入有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
    ③快速排序的思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
    ④堆排序的思想是(在此介绍用大顶堆排序的基本思想)：a．先将初始文件R[1．．n]建成一个大顶堆，此堆为初始的无序区；b．再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1．．n-1]和有序区R[n]，且满足R[1．．n-1]．keys≤R[n]．key；c．由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1．．n-1]调整为堆，然后再次将R[1．．n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1．n一2]和有序区R[n-1．．n]，且仍满足关系R[1．．n-2]．keys≤R[n-1．．n]．keys，同样要将R[1．．n-2]调整为堆。以此类推，直到无序区只有一个元素为止。
    ⑤冒泡排序的思想是：在排序过程中总是小数往前放，大数往后放，相当于气泡往上升。
    题目要求得到其中第k个元素之前的部分排序，显然堆排序最合适，因为希尔排序、直接插入排序和快速排序都不能实现部分排序。若要把所有元素排序完成，再从结果集中把需要的数列截取出来，很明显效率远远不及堆排序。
    对于第(63)题，可以从快速排序基本思想得到答案。
转载请注明原文地址:https://www.kaotiyun.com/show/HfRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)