2. 计算机
  3. 对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用( )。

对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用( )。

admin2019-06-12  43
问题 对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用(    )。
选项 A、直接插入排序
B、希尔排序
C、快速排序
D、堆排序
答案D
解析 此题考的是常见的内部排序算法。
    直接插入排序的基本思想：每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。
    希尔排序的基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2    直接选择排序的基本思想：首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依此类推，直到所有记录排完为止。
    堆排序的基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。它通过建立初始堆和不断地重建堆，逐个地将排序关键字按顺序输出，从而达到排序的目的。
    冒泡排序的基本思想：将被排序的记录数组R[1..n]垂直排列，每个记录R看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
    快速排序的基本思想：采用了一种分治的策略，将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
    归并排序的基本思想：将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表所组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并，直到得到长度为n的有序表为止，排序结束。
    基数排序的基本思想：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列。
    了解这些算法思想以后，解题就容易了。现在看题目具体要求，题目中“若只需得到其中第k个元素之前的部分排序”有歧义。例如，现在待排序列：
    15    8    9    2    23    69    5
    现要求得到其中第3个元素之前的部分排序。第一种理解：得到“15  8  9”的排序；第二种理解：得到排序后序列“2  5  8  9  1 5  23  69”的“2  5  8   9”；得到排序后第3个元素之前的部分排序：即“2  5  8”。但综合题意，第一种理解可以排除，要达到第一种效果，只需将待排序列定为“15  8  9”即可。对于后两种理解，都只有堆最合适，因为希尔排序、直接插入排序和快速排序都不能实现部分排序。若要达到题目要求，只能把所有元素排序完成，再从结果集中把需要的数列截取出来，这样效率远远不及堆排序。所以本题答案选D。
转载请注明原文地址:https://kaotiyun.com/show/LECZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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