首页 › 题库 › GESP编程能力等级认证 › 7.1 归并排序

GESP-C++五级 题库

共 22 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 7.1 归并排序 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。

void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) { 
    int i = l, j = mid + 1, k = l; 
    while (i <= mid && j <= r) { 
        if (arr[i] <= arr[j]) temp[k++] = arr[i++]; 
        else temp[k++] = arr[j++]; 
    } 
    while (i <= mid) temp[k++] = arr[i++]; 
    while (j <= r) temp[k++] = arr[j++]; 
    for (int p = l; p <= r; p++) arr[p] = temp[p]; 
} 
void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) { 
    if (l >= r) return; 
    int mid = l + (r - l) / 2; 
    mergeSort(arr, temp, l, mid); 
    mergeSort(arr, temp, mid + 1, r); 
    merge(arr, temp, l, mid, r); 
}


A
归并排序的平均复杂度是O(nlogn)。
B
归并排序需要O(n)的额外空间。
C
归并排序在最坏情况的时间复杂度是O(n^2)。
D
归并排序适合大规模数据。
答案与解析
正确答案:C
归并排序通过分治法将数组递归分割至单个元素,再逐层合并有序子序列。每次合并操作比较两个已排序子区间元素,按序放入临时数组,最终复制回原数组。递归深度为logn量级,每层合并总耗时O(n),整体时间复杂度由递归树结构决定。算法执行过程中需辅助数组存储中间结果,空间开销与输入规模成正比。无论数据初始分布如何,拆分与合并过程的行为保持一致,其时间复杂度在最坏、平均和最好情况下均相同。大规模数据处理中,该算法表现出稳定的性能特征。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下述C++代码实现了归并排序算法,则横线上应填写( )

A

i < mid

B

j < right

C

i <= mid

D

j <= right

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面关于归并排序,描述正确的是( )。

A
归并排序是一个不稳定的排序算法。
B
归并排序的时间复杂度在最优、最差和平均情况下都是 (nlogn)。
C
归并排序需要额外的 O(1) 空间。
D
对于输入数组 {12, 11, 13, 5, 6, 7},代码输出结果为:7 6 5 13 12 11。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

考虑以下C++代码实现的归并排序算法:

void merge(int arr[], int left, int mid, int right) {
	int n1 = mid - left + 1;
	int n2 = right - mid;
	
	int L[n1], R[n2];
	
	for (int i = 0; i < n1; i++)
		L[i] = arr[left + i];
	for (int j = 0; j < n2; j++)
		R[j] = arr[mid + 1 + j];
		
	int i = 0, j = 0, k = left;
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

void merge_sort(int arr[], int left, int right) {
	if (left < right) {
		int mid = left + (right - left) / 2;
		
		merge_sort(arr, left, mid);
		merge_sort(arr, mid + 1, right);
		
		merge(arr, left, mid, right);
	}
}

对长度为 n 的数组 arr ,挑用函数 merge_sort(a, 0, n-1) ,在排序过程中 merge 函数的递归调用次数大约是( )。

A
O(1)
B
O(n)
C
O(logn)
D
O(nlogn)
答案与解析
正确答案:B

merge_sort函数的作用是递归进行分治的过程,每次把序列分成两半,然后分别处理,merge函数的作用是把两个有序序列,通过双指针操作,合并为一个有序序列。merge函数的调用次数,先是两个数的合并,执行次数为n/2,然后是4个数合并,执行次数为n/4……大约为O(n)

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

设A和B是两个长度为n的有序数组,现将A和B合并成一个有序数组,归并排序算法在最坏情况下至少要做( )次比较。

A
n2
B
nlogn
C
2n−1
D
n
答案与解析
正确答案:C

在最坏情况下,两个数组的元素需要逐个比较,直到其中一个数组的所有元素都放入新数组中。当一个数组的所有元素都被放入新数组后,剩下的数组中的元素不需要再与新数组中的元素比较,因此剩余的比较操作可以省略。因此,总的比较次数是n+(n−1),即2n−1

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

归并排序的基本思想是(   )。

A
动态规划
B
分治
C
贪心算法
D
回溯算法
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面C++代码以递归方式实现合并排序,并假设 merge (int T[], int R[], int s, int m, int t) 函数将有序(同样排序规则)的T[s..m]和T[m+1..t]归并到R[s..t]中。横线处应填上代码是(   )。

A

mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)

B

mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len)

C

mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)

D

mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面代码用于归并排序,其中 merge() 函数被调用次数为(     )。

A
0
B
1
C
6
D
7
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

在上题的归并排序算法中, mergeSort(listData, start, middle); 和 mergeSort(listData, middle+ 1, end); 涉及到的算法为(     )。

A
搜索算法
B
分治算法
C
贪心算法
D
递推算法
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

归并排序算法的基本思想是(     )。(2023.9C++五级)

A

将数组分成两个子数组,分别排序后再合并。

B

随机选择一个元素作为枢轴,将数组划分为两个部分。

C

从数组的最后一个元素开始,依次与前一个元素比较并交换位置。

D

比较相邻的两个元素,如果顺序错误就交换位置。

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

快速排序和归并排序都是稳定的排序算法。2025.9-5

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

下面的C++代码实现归并排序。代码在执行时,将输出一次 HERE 字符串,因为merge()函数仅被调用一次。( )

void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int p = 0; p < k; ++p) {
        arr[left + p] = temp[p];
    }
}
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    std::cout << "HERE";
    merge(arr, left, mid, right);
}
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

归并排序的最好、最坏和平均时间复杂度均为 O(n log n)。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )

A
对
B
错
答案与解析
正确答案:对

归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:

分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。

合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。

总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。

题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。( )

A
对
B
错
答案与解析
正确答案:对

分治法的核心是:

分解:将问题划分为若干 相互独立且结构相同 的子问题。

解决:递归解决子问题。

合并:将子问题的解合并为原问题的解。

归并排序体现了分治算法。

题目详情
16 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

递归算法必须有一个明确的结束条件,否则会导致无限递归并可能引发栈溢出。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

快速排序和归并排序的平均时间复杂度均为 O(nlogn),且都是稳定排序。(2024.12-5)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

快速排序和归并排序的平均时间复杂度均为 O(nlogn),且都是稳定排序。

A
对
B
错
答案与解析
正确答案:错

快速排序的均摊时间复杂度为O(nlogn),归并排序的时间复杂度是稳定的O(nlogn),所以对于时间复杂度的描述是正确的,但是快速排序不是稳定排序。

题目详情
19 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

归并排序和快速排序都采用递归实现,也都是不稳定排序。( )(2024.6-5)

A
对
B
错
答案与解析
正确答案:错

归并排序是一种稳定的排序算法,快速排序是一种不稳定的排序算法

题目详情
20 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

分治算法的典型应用之一是归并排序,其时间复杂度为O(NlogN)。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情