GESP-C++五级 题库
下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。
下述C++代码实现了归并排序算法,则横线上应填写( )


i < mid
j < right
i <= mid
j <= right
下面关于归并排序,描述正确的是( )。
考虑以下C++代码实现的归并排序算法:
对长度为 n 的数组 arr ,挑用函数 merge_sort(a, 0, n-1) ,在排序过程中 merge 函数的递归调用次数大约是( )。
merge_sort函数的作用是递归进行分治的过程,每次把序列分成两半,然后分别处理,merge函数的作用是把两个有序序列,通过双指针操作,合并为一个有序序列。merge函数的调用次数,先是两个数的合并,执行次数为n/2,然后是4个数合并,执行次数为n/4……大约为O(n)
设A和B是两个长度为n的有序数组,现将A和B合并成一个有序数组,归并排序算法在最坏情况下至少要做( )次比较。
在最坏情况下,两个数组的元素需要逐个比较,直到其中一个数组的所有元素都放入新数组中。当一个数组的所有元素都被放入新数组后,剩下的数组中的元素不需要再与新数组中的元素比较,因此剩余的比较操作可以省略。因此,总的比较次数是n+(n−1),即2n−1
下面C++代码以递归方式实现合并排序,并假设 merge (int T[], int R[], int s, int m, int t) 函数将有序(同样排序规则)的T[s..m]和T[m+1..t]归并到R[s..t]中。横线处应填上代码是( )。

mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)
mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len)
mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)
mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)
在上题的归并排序算法中, mergeSort(listData, start, middle); 和 mergeSort(listData, middle+ 1, end); 涉及到的算法为( )。
归并排序算法的基本思想是( )。(2023.9C++五级)
将数组分成两个子数组,分别排序后再合并。
随机选择一个元素作为枢轴,将数组划分为两个部分。
从数组的最后一个元素开始,依次与前一个元素比较并交换位置。
比较相邻的两个元素,如果顺序错误就交换位置。
下面的C++代码实现归并排序。代码在执行时,将输出一次 HERE 字符串,因为merge()函数仅被调用一次。( )
归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:
分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。
合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。
总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。
归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。( )
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
归并排序体现了分治算法。
快速排序和归并排序的平均时间复杂度均为 O(nlogn),且都是稳定排序。
快速排序的均摊时间复杂度为O(nlogn),归并排序的时间复杂度是稳定的O(nlogn),所以对于时间复杂度的描述是正确的,但是快速排序不是稳定排序。
归并排序和快速排序都采用递归实现,也都是不稳定排序。( )(2024.6-5)
归并排序是一种稳定的排序算法,快速排序是一种不稳定的排序算法
