GESP C++ 五 级 2025年6月真题（180 分钟，总分 100 分）

判断题（共 10 题，每题 2 分，共 20 分）

1. 下面C++代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，a大于b还是小于b都适用。

int gcd(int a, int b)
{
    while (b)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

{{ select(1) }}

• 正确
• 错误

2. 假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的lcm()函数能求相应两数的最小公倍数。

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

{{ select(2) }}

• 正确
• 错误

3. 下面的C++代码用于输出每个数对应的质因数列表，输出形如：{5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]}。

int main()
{
    int n, m;
    cin >> n >> m;
    if (n > m)
        swap(n, m);
    map<int, vector<int>> prime_factor;
    for (int i = n; i <= m; ++i)
    {
        int j = 2, k = i;
        while (k != 1)
        {
            if (k % j == 0)
            {
                prime_factor[i] = prime_factor[i] + j;
                k /= j;
            }
            else
            {
                ++j;
            }
        }
    }
    for (auto &p : prime_factor)
    {
        cout << p.first << ": ";
        for (int v : p.second)
            cout << v << " ";
        cout << endl;
    }
    return 0;
}

{{ select(3) }}

• 正确
• 错误

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

{{ select(4) }}

• 正确
• 错误

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

{{ select(5) }}

• 正确
• 错误

6. 查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为g的单词，他首先翻到字典约一半的页数，发现该页的首字母是m，由于字母表中g位于m之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为g的页码。这种查字典的一系列操作可看作二分查找。

{{ select(6) }}

• 正确
• 错误

7. 求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。

{{ select(7) }}

• 正确
• 错误

8. 分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。

{{ select(8) }}

• 正确
• 错误

9. 函数puzzle定义如下，则调用puzzle(7)程序会无限递归。

int puzzle(int n)
{
    if (n == 1)
        return 1;
    if (n % 2 == 0)
        return puzzle(n / 2);
    return puzzle(3 * n + 1);
}

{{ select(9) }}

• 正确
• 错误

10. 如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为O(n)。

vector<int> linearSieve(int n)
{
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
    {
        if (is_prime[i])
        {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
        {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0)
            {
                break;
            }
        }
    }
    return primes;
}

{{ select(10) }}

• 正确
• 错误