首页 › 题库 › GESP编程能力等级认证 › 7 分治算法

GESP-C++五级 题库

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

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

A

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

B

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

C

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

D

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

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

通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。

A
对
B
错
答案与解析
正确答案:对
确定数组的第一个、最中间和最后一个元素的值;比较这三个元素的大小;选取其中数值上处于中间位置的元素作为枢轴;将该枢轴用于划分操作,使小于枢轴的元素置于其左,大于枢轴的元素置于其右;完成一次划分后递归处理左右子数组。
题目详情
23 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

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

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

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
26 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

分治算法将原问题可以分解成规模更小的子问题,使得求解问题的难度降低。

但由于分治算法需要将问题进行分解,并且需要将多个子问题的解合并为原问题的解,所以分治算法的效率通常比直接求解原问题的效率低。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
27 判断题 偏易 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)。

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

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

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

分治法的核心是:

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

解决:递归解决子问题。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

题目详情
33 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决,最后合并得到原问题的解。(   )

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

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

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

归并排序的时间复杂度是O(NlogN)。(   )

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

一般说来,冒泡排序算法优于归并排序。(2023.9C++五级)

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