CCF GESP C++ 五级 (2026 年 09 月)

一、单选题（每题 2 分，共 30 分）

1. ⼩杨⽤单链表保存任务序列，并同时维护头指针 head 和尾指针 tail 。在链表⾮空且已知 tail 的情况 下，在表尾插⼊新结点的时间复杂度是（ ）。

struct Node {
    int value;
    Node *next;
};
Node *head;
Node *tail;

{{ select(1) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n \log n)$

2. 在不带哨兵结点的双向链表中，结点 p 既不是头结点也不是尾结点。删除 p 的正确代码是（ ） A. B. C. D.

struct Node {
    int value;
    Node *prev;
    Node *next;
};

A.

p->prev = p->next;
p->next = p->prev;
delete p;

B.

p->prev->next = p;
p->next->prev = p;
delete p;

C.

p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

D.

p->next = p->prev;
p->prev->next = nullptr;
delete p;

{{ select(2) }}

• A
• B
• C
• D

3. 下⾯函数使⽤快慢指针查找单链表的中间结点。横线处应填写（ ） 5

struct Node {
    int value;
    Node *next;
};
Node *middle(Node *head) {
    Node *slow = head;
    Node *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        ______________________
    }
    return slow;
}

{{ select(3) }}

• fast = fast->next;
• fast = fast->next->next;
• fast = slow->next;
• fast = head->next;

4. 函数 gcd(int a, int b) 定义如下，则 gcd(105, 45) 的结果是（ ）

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

{{ select(4) }}

• 3
• 5
• 15
• 45

5. 下⾯函数⽤于判断正整数 n 是否为质数。横线处的最佳写法是（ ）

bool isPrime(int n) {
    if (n < 2)
        return false;
    for (int i = 2; __________________; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

{{ select(5) }}

• i < n
• i <= n / 2
• i * i < n
• (long long) i * i <= n

6. 下⾯代码实现线性筛法。为了保证每个合数只被其最⼩质因⼦筛去⼀次，横线处应填写（ ） 4

vector<int> linearSieve(int n) {
    vector<bool> composite(n + 1, false);
    vector<int> primes;
    
    for (int i = 2; i <= n; i++) {
        if (!composite[i])
            primes.push_back(i);
        for (int p : primes) {
            if ((long long)i * p > n)
                break;
            composite[i * p] = true;
            if (__________________)
                break;
        }
    }
    return primes;
}

{{ select(6) }}

• p % i == 0
• i % p == 0
• i == p
• i * p == n

7. 根据唯⼀分解定理，整数 的正确质因数分解是（ ） A. B. C. D.

{{ select(7) }}

• $2^2 \times 3^3 \times 7$
• $2^3 \times 3^2 \times 7$
• $2^2 \times 3^2 \times 21$
• $2 \times 3^3 \times 14$

8. 函数 f(int n) 定义如下，则 f(4) 的结果是（ ）

int f(int n) {
    if (n == 1)
        return 1;
    return n + f(n - 1);
}

{{ select(8) }}

• 4
• 7
• 9
• 10

9. 在升序数组中查找第⼀个严格⼤于 x 的元素位置，下⾯代码中的横线应填写（ ）

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

{{ select(9) }}

• a[mid] < x
• a[mid] >= x
• a[mid] <= x
• a[mid] > x

10. ⼩杨需要把若⼲箱货物按原顺序分配到 days 天中，每天运输连续的若⼲箱，求能够完成任务的最⼩载重 量。函数 check(cap) 判断载重量为 cap 时能否在规定天数内运完。横线处应填写（ ）。 3

long long l = maxWeight;
long long r = totalWeight;

while (l < r) {
    long long mid = l + (r - l) / 2;
    if (check(mid)) {
        ____________________
    } else {
        ____________________
    }
}
cout << l;

{{ select(10) }}

• l = mid + 1; 和 r = mid;
• r = mid; 和 l = mid + 1;
• r = mid - 1; 和 l = mid;
• l = mid; 和 r = mid - 1;

11. 下⾯是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写 （ ）。

while (i <= mid && j <= right) {
    if (__________________) {
        temp.push_back(a[i++]);
    } else {
        temp.push_back(a[j++]);
    }
}

{{ select(11) }}

• a[i] < a[j]
• a[i] > a[j]
• a[i] >= a[j]
• a[i] <= a[j]

12. 下⾯快速排序的划分函数以 a[right] 为枢轴，并把不⼤于枢轴的元素移动到左侧。横线处应填写 （ ）。

int partition(int a[], int left, int right) {
    int pivot = a[right];
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
        if (__________________) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[right]);
    return i + 1;
}

{{ select(12) }}

• a[j] <= pivot
• a[j] > pivot
• a[i] <= pivot
• a[right] < a[j]

13. ⼩杨要在⼀个教室安排尽可能多场活动，每场活动具有开始时间 start 和结束时间 end 。采⽤贪⼼算法 时，正确的选择策略是（ ）。

struct Activity {
    int start;
    int end;
};

{{ select(13) }}

• 每次选择开始时间最早的活动
• 每次选择持续时间最短的活动
• 每次选择参与⼈数最少的活动
• 按结束时间从早到晚排序，依次选择与已选活动不冲突的活动

14. 下⾯函数使⽤迭代⽅法求最⼤连续⼦段和。对于数组 {-2, 3, -1, 5, -6, 2} ，函数返回值是 （ ）。

int maxSubArray(const vector<int> &a) {
    int best = a[0];
    int current = a[0];
    for (int i = 1; i < (int)a.size(); i++) {
        current = max(a[i], current + a[i]);
        best = max(best, current);
    }
    return best;
}

{{ select(14) }}

• 5
• 6
• 7
• 8

15. 数组 a 和 b 按低位在前的顺序保存两个⾮负⼤整数。下⾯代码实现⾼精度加法，横线处应填写 （ ）。 5

vector<int> add(const vector<int> &a, const vector<int> &b) {
    vector<int> c;
    int carry = 0;
    int n = max(a.size(), b.size());
    
    for (int i = 0; i < n; i++) {
        int sum = carry;
        if (i < a.size())
            sum += a[i];
        if (i < b.size())
            sum += b[i];
        c.push_back(sum % 10);
        ____________________
    }
    if (carry)
        c.push_back(carry);
    return c;
}

{{ select(15) }}

• carry = sum % 10;
• carry = sum;
• carry = sum / 10;
• carry = c[i] / 10;

二、判断题（每题 2 分，共 20 分）

1. 下⾯代码在已知结点 p 的情况下，能够以 的时间在单链表的 p 结点之后插⼊新结点 s

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

{{ select(16) }}

• 对
• 错

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

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

{{ select(17) }}

• 对
• 错

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(18) }}

• 对
• 错

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(19) }}

• 对
• 错

5. 下⾯程序的时间复杂度为

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

{{ select(20) }}

• 对
• 错

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(21) }}

• 对
• 错

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

{{ select(22) }}

• 对
• 错

8. 归并排序的递推式为 ，对应的时间复杂度为

{{ select(23) }}

• 对
• 错

9. 下⾯的贪⼼代码⼀定能对任意硬币⾯值集合 coins 求出 money 所需的最少硬币数

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

{{ select(24) }}

• 对
• 错

10. 假设两个⾮负⾼精度整数分别存储在数组 a 和 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(25) }}

• 对
• 错