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

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

1. 下面代码在已知结点 p 的情况下，能够以 $O(1)$ 的时间在单链表的 p 结点之后插入新结点 s 。

s->next = p->next;
p->next = s;

{{ select(1) }}

• 正确
• 错误

2. 下面代码可以安全地删除单链表的头结点，并使 head 指向删除后的新头结点。

Node *p = head;
delete p;
head = p->next;

{{ select(2) }}

• 正确
• 错误

3. 下面欧几里得算法既适用于 a > b ，也适用于 a < b ，只要 a 、b 是正整数。

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

{{ select(3) }}

• 正确
• 错误

4. 下面埃氏筛从 i * i 开始标记，是因为 i * i 之前的 i 的合数倍数已经被更小的质因子标记过。

for (int i = 2; (long long)i * i <= n; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}

{{ select(4) }}

• 正确
• 错误

5. 下面程序的时间复杂度为 $O(n)$。

for (int i = 1; i <= n; i *= 2) {
    cout << i << endl;
}

{{ select(5) }}

• 正确
• 错误

6. 若数组 a 已按升序排列，下面函数能够返回最后一个小于等于 x 的元素下标；如果不存在，则返回 -1 。

int findLastLE(const vector<int> &a, int x) {
    int l = 0, r = (int)a.size() - 1;
    int ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

{{ select(6) }}

• 正确
• 错误

7. 快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为 $O(n \log n)$。

{{ select(7) }}

• 正确
• 错误

8. 归并排序的递推式为 $T(n) = 2T(n/2) + O(n)$，对应的时间复杂度为 $O(n \log n)$。

{{ select(8) }}

• 正确
• 错误

9. 下面的贪心代码一定能对任意硬币面值集合 coins 求出 money 所需的最少硬币数。

int count = 0;
for (int coin : coins) { // coins 按面值从大到小排列
    count += money / coin;
    money %= coin;
}

{{ select(9) }}

• 正确
• 错误

10. 假设两个非负高精度整数分别存储在数组 a 和 b 中，且 $a \ge b$。数组采用低位在前的方式存储，即 a[0] 表示个位。下面代码中的 c 可以正确保存 a - b 的各位数字。

int borrow = 0;
for (int i = 0; i < len; ++i) {
    int t = a[i] - b[i] + borrow;
    if (t < 0) {
        t += 10;
        borrow = 1;
    } else {
        borrow = 0;
    }
    c[i] = t;
}

{{ select(10) }}

• 正确
• 错误