例子问题
例子问题1:归并排序
归并排序是如何完成的?
可能的答案:
将列表中的每个元素与所有其他元素进行比较,并将其插入合适的位置。
原始列表被分成两组,然后从那里排序。
如果有偶数个元素,列表被分成两组,排序,然后合并到一起。如果有奇数编号的元素,则列表被分为三组。
原始列表被连续地分解成子列表,直到每个子列表包含一个元素,然后子列表被组合在一起。
原始列表被分成4个子列表,然后组合在一起。
正确答案:
原始列表被连续地分解成子列表,直到每个子列表包含一个元素,然后子列表被组合在一起。
解释:
在归并排序中,一个列表被分解成包含一个元素的子列表。然后将每个元素与另一个元素进行比较并进行排序。然后将每个2元素组与其他2元素组组合,比较每组的第一个值,并决定如何将4个元素组合。较大的四组将与另一组四组进行比较,直到过程结束,列表排序完成。
例子问题2:排序
上图代表的是哪种排序算法?
可能的答案:
插入排序
选择排序
Bubblesort
快速排序
归并排序
正确答案:
归并排序
解释:
归并排序包括将一个未排序的列表分解成子数组;对每个子数组进行排序,并将子数组重新组合为更大的数组。
示例问题3:排序
下面的选项中,对于一个无序列表(列表的大小是奇数且列表的大小是有限的),最有效的排序算法是什么?
可能的答案:
归并排序
插入排序
冒泡排序
选择排序
正确答案:
归并排序
解释:
归并排序是最有效的选择。选择排序和插入排序都使用O(N)2)时间。冒泡排序似乎是一个很好的答案,但它使用的是O(N)2)的时间,可以适应使用O(N)时间,但只有在列表接近排序时,所以这是一场赌博。归并排序总是使用O(NlogN)时间,因此它总是四种选择中最有效的。