GESP 五级 · GESP 202309 C++ 五级 第 12 题

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

#include <iostream>
using namespace std;

void mergeSort(int * listData, int start, int end);
void merge(int * listData, int start, int middle, int end);

void mergeSort(int * listData, int start, int end) {
    if (start >= end)
        return;
    int middle = (start + end) / 2;
    mergeSort(listData, start, middle);
    mergeSort(listData, middle + 1, end);
    merge(listData, start, middle, end);
}

void merge(int * listData, int start, int middle, int end) {
    int leftSize = middle - start + 1;
    int rightSize = end - middle;

    int * left = new int[leftSize];
    int * right = new int[rightSize];
    for (int i = 0; i < leftSize; i++)
        left[i] = listData[start + i];
    for (int j = 0; j < rightSize; j++)
        right[j] = listData[middle + 1 + j];

    int i = 0, j = 0, k = start;
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            listData[k] = left[i];
            i++;
        } else {
            listData[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < leftSize) {
        listData[k] = left[i];
        i++;
        k++;
    }
    while (j < rightSize) {
        listData[k] = right[j];
        j++;
        k++;
    }
    delete[] left;
    delete[] right;
}

int main() {
    int lstA[] = {1, 3, 2, 7, 11, 5, 3};
    int size = sizeof(lstA) / sizeof(lstA[0]);
    mergeSort(lstA, 0, size - 1); // 对lstA执行归并排序

    for (int i = 0; i < size; i++)
        cout << lstA[i] << " ";
    cout << endl;
    return 0;
}

这题别急着数代码行数，先画个递归树。merge 函数只在非叶子节点被调用，每层把区间一分为二直到长度为1就停了。数清楚每一层有多少个区间在合并，加起来就是答案。

最容易犯的错是把数组长度7当成答案，或者误以为 merge 在叶子节点也会执行。其实只要子区间长度大于1，merge 就会跑一次；一旦 split 到只剩一个元素，merge 就不需要了。还有人会去数 main 里调用的次数，或者把 mergeSort 的递归调用次数算进去，这都是偏题。一定要盯着 merge 函数在递归树里的位置，只数非叶子节点。

【考点定位】本题出自 GESP 五级“数据结构与算法”中的递归模块，核心考查归并排序的递归展开过程，特别是 merge() 函数在递归树中的调用规律。命题人专卡“非叶子节点统计”这一盲区，多数考生只会背时间复杂度 O(nlogn)，却对递归展开过程毫无概念——当题目问“函数被调用次数”时，他们习惯性地用数组长度（7）或二分次数（log₂7≈2）去凑答案，完全忽略了 merge() 只在非叶子节点执行的本质。

【概念拆解】归并排序是典型的分治递归：mergeSort 负责拆（split）和合（merge）。关键点在于，merge() 只在区间长度大于1时才被调用；一旦区间长度为1（即 start == end），直接返回，不再进入 merge()。因此，merge() 的调用次数 = 递归树中所有非叶子节点的个数。

【命题视角】命题人喜欢用具体数据（本题数组长度为7）来制造“陷阱”。7不是2的幂，导致递归树最后一层不是完全满的，这很容易让人在数节点时出错。此外，题目只问 merge() 调用次数，不考 mergeSort 总调用次数，要求学生精准区分“拆分”和“合并”两个动作。

【思考心法】拿到题先想什么？→ 先画出递归树。从根节点 mergeSort(0, 6) 开始，每次把区间一分为二，直到子区间长度为1。然后逐层数非叶子节点：

• 第0层（根）：1个节点 (0,6)，长度7>1，调用merge。
• 第1层：2个节点 (0,3) 和 (4,6)，长度分别为4和3，都>1，各调用merge。
• 第2层：继续拆分，得到3个节点 (0,1)、(2,3)、(4,5)、(6,6)？不对，(6,6)长度为1，是叶子。实际第2层非叶子节点是 (0,1)、(2,3)、(4,5) 共3个，长度分别为2、2、2，都>1，各调用merge。
• 第3层：拆分后得到5个节点 (0,0)、(1,1)、(2,2)、(3,3)、(4,4)、(5,5)？不对，(4,5)拆成(4,4)和(5,5)，(0,1)拆成(0,0)和(1,1)，(2,3)拆成(2,2)和(3,3)。此时所有区间长度都是1，全是叶子，不再调用merge。

所以非叶子节点总数 = 1 + 2 + 3 = 6。

【逐层推演】具体怎么算？

• 根节点 mergeSort(0,6)：length=7，调用merge。
• 左子树 mergeSort(0,3)：length=4，调用merge；再拆成 mergeSort(0,1) 和 mergeSort(2,3)，两者 length=2，各调用merge。
• 右子树 mergeSort(4,6)：length=3，调用merge；再拆成 mergeSort(4,5) 和 mergeSort(6,6)，前者 length=2 调用merge，后者 length=1 不调用。
• 继续向下：mergeSort(0,1) 拆成两个 length=1 的叶子；mergeSort(2,3) 拆成两个 length=1 的叶子；mergeSort(4,5) 拆成两个 length=1 的叶子。

至此，所有 merge() 调用完毕。统计：根1次 + 第1层2次 + 第2层3次 = 6次。

【避坑提醒】 1. 别把 mergeSort 的总调用次数（包括叶子节点）当成答案，那是 1+2+3+5 = 11 次，远超选项。 2. 别用数组长度7当答案，那是混淆了元素个数与合并操作数。 3. 别忽略“长度等于1时不合并”的规则，这是本题最隐蔽的坑。 4. 别把 merge() 和 mergeSort() 混为一谈，题目明确问的是 merge() 被调用次数。

【考频与趋势】从真实数据看，“归并排序”在题库中已考过51题，覆盖6个考试级别（2009-2026），其中GESP五级占比最高，达33题。历年分布呈现明显上升趋势：2009年2题、2010年1题、2019年2题、2022年1题、2023年6题、2024年14题、2025年15题、2026年9题。可以看出，近五年归并排序的考查频次从个位数跃升至十余题，且GESP五级仍是重灾区，说明命题人对递归细节的考察越来越精细。

【预测】基于上述数据与经验，未来GESP五级“数据结构与算法”模块仍会高频出现归并排序相关题目，但形式可能更灵活：不再单纯问“调用次数”，而是结合具体数组内容问“某次merge合并后的结果”或“第k次merge合并的是哪两个子区间”。这类题目需要考生真正理解递归树的层次结构，而不仅仅是背公式。因此，建议学生在复习时务必亲手画出不同长度数组的递归树，强化“非叶子节点=合并次数”这一核心认知。