GESP 五级 · GESP 202506 C++ 五级 第 19 题

下面的 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);
}

模拟程序执行过程，逐行跟踪变量变化，特别关注循环边界和递归终止条件。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】递归 | 归并排序 | 递归调用栈

1. 考纲定位 本题考查 GESP 五级"算法基础"中递归调用的执行流程。命题人专门选这个题，就是要卡住考生对"递归函数内部语句执行时机"的认知——很多人以为只有顶层会执行，完全忽略了递归返回后的流程。

2. 解题思维 trace 一遍你就懂了：mergeSort 每次被调用时，只要 left<right，就会先递归左右两半，然后打印 HERE，最后 merge。也就是说，每一次合并操作都会触发一次打印。递归树有多少个合并节点，就打印多少次。对于长度为 n 的数组，递归树有 n-1 个合并节点，因此打印次数是 n-1。题目说"仅调用一次、打印一次"，只有当 n=2 时才成立，显然不是任意输入都满足。

3. 陷阱拆解 选项 A 的错误在于"只看了代码结构没看执行流程"。mergeSort 函数体里有 print 语句，它不是只在顶层执行，而是每次调用且满足条件都会执行。命题人利用的正是"递归返回后继续执行函数体剩余代码"这一细节——很多考生把递归想成"只递归不干活"，完全忽略了返回后的 merge 与打印。

4. 反命题思维 如果题目改成"对于长度为 2 的数组，输出一次 HERE"，答案就是 A；如果改成"输出次数等于数组长度减一"，答案也是 A。所以刷到这类题先问：是问特定规模还是任意规模？规模不同，答案截然不同。