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

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

1. 关于单链表、双链表和循环链表，下列说法正确的是（ ）

{{ select(1) }}

• 在单链表中，若已知任意结点的指针，则可以在o(1) 时间内删除该结点。
• 循环链表中⼀定不存在空指针。
• 在循环双链表中，尾结点的 next 指针⼀定为 nullptr 。
• 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向⾃⾝。

2. 双向循环链表中要在结点 p 之前插⼊新结点 s （均⾮空），以下指针操作正确的是（ ）

A.

s -> next = p;
p -> prev = s;
q -> next = s;
s -> prev = q;

B.

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

C.

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

D.

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

{{ select(2) }}

• A
• B
• C
• D

3. 下⾯函数⽤“哑结点”统⼀处理删除单向链表中的头结点与中间结点。横线处应填（ ）

struct Node{
    int val;
    Node* next;
    Node(int v):val(v),next(nullptr){}
};
Node* eraseAll(Node* head, int x){
    Node dummy(0);
    dummy.next = head;
    Node* cur = &dummy;
    while(cur->next){
        if(cur->next->val == x){
            Node* del = cur->next;
            ______________________
            delete del;
        }else cur = cur->next;
    }
    return dummy.next;
}

{{ select(3) }}

• cur = cur->next;
• cur->next = del->next;
• del->next = cur->next;
• cur->next = nullptr;

4. 对如下代码实现的欧⼏⾥得算法（辗转相除法），执⾏ gcd(48, 18) 得到的调⽤序列为（ ）

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

{{ select(4) }}

• gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
• gcd(48,18) -> gcd(30,18) -> gcd(12,18)
• gcd(48,18) -> gcd(18,30) -> gcd(30,6)
• gcd(48,18) -> gcd(12,18) -> gcd(6,12)

5. 下⾯代码实现了欧拉（线性）筛，横线处应填写（ ）

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

{{ select(5) }}

• j <= n
• j < sqrt(n)
• j < primes.size()
• j < i

6. 埃⽒筛中将内层循环从 $j = i*i$ 开始⽽不是 $j = 2*i$的主要原因是（ ）。

vector<int> eratosthenes_sieve(int n) {
    vector<bool> is_composite(n + 1, false);
    vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (is_composite[i]) continue;
        primes.push_back(i);
        for (long long j = (long long)i * i; j <= n; j += i)
            is_composite[j] = true;
    }
    return primes;
}
}

{{ select(6) }}

• 因为 2*i ⼀定不是合数
• i*i ⼀定是质数
• ⼩于 i*i 的 i 的倍数已被更⼩质因⼦筛过
• 这样可以把时间复杂度降为$O(n)$

7. 下⾯程序的运⾏结果为（ ）

bool check(int n, int a[], int k, int dist) {
    int cnt = 1;
    int last = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] - last >= dist) {
            cnt++;
            last = a[i];
        }
    }
    return cnt >= k;
}
int solve(int n, int a[], int k) {
    std::sort(a, a + n);
    int l = 0;
    int r = a[n - 1] - a[0];
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (check(n, a, k, mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}
int main() {
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;
    std::cout << solve(n, a, k) << std::endl;
    return 0;
}
}

{{ select(7) }}

• 2
• 3
• 4
• 5

8. 在升序数组中查找第⼀个⼤于等于 x 的位置，下⾯循环中横线应填（ ）

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

{{ select(8) }}

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

9. 关于递归函数调⽤，下列说法错误的是（ ）

{{ select(9) }}

• 递归调⽤层次过深时，可能会耗尽栈空间导致栈溢出
• 尾递归函数可以通过编译器优化来避免栈溢出
• 所有递归函数都可以通过循环结构来改写，从⽽避免栈溢出
• 栈溢出发⽣时，程序会抛出异常并可以继续执⾏后续代码

10. 给定 n 根⽊头，第 i 根长度为 a[i] 。要切成不少于 m 段等长⽊段，求最⼤可能长度，则横线上应填 写（ ）。

const int MAXN = 100005;
long long a[MAXN];
int n, m;
bool check(long long x){
    long long cnt = 0;
    for(int i = 1; i <= n; i++){
    if(x == 0) return true;
    cnt += a[i] / x;
    if(cnt >= m) return true;
    }
    return false;
}
int main(){
cin >> n >> m;
long long mx = 0;
for(int i = 1; i <= n; i++){
    cin >> a[i];
    mx = max(mx, a[i]);
}
long long l = 1, r = mx;
long long ans = 0;
while(l <= r){
    long long mid = l + (r - l) / 2;
    if(check(mid)){
        ans = mid;
        ______________________
    }else{
        ______________________
    }
}
cout << ans << endl;
return 0;
}

{{ select(10) }}

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

11. 下⾯代码⽤分治求“最⼤连续⼦段和”，其时间复杂度为（ ）

int solve(vector<int>& a, int l, int r){
    if(l == r) return a[l];
    int mid = l + (r - l) / 2;
    int left = solve(a, l, mid);
    int right = solve(a, mid + 1, r);
    int sum = 0, lmax = INT_MIN;
    for(int i = mid; i >= l; i--){
        sum += a[i];
        lmax = max(lmax, sum);
    }
    sum = 0;
    int rmax = INT_MIN;
    for(int i = mid + 1; i <= r; i++){
        sum += a[i];
        rmax = max(rmax, sum);
    }
    return max({left, right, lmax + rmax});
}
}

{{ select(11) }}

• $O(n^2)$
• $O(n \log n)$
• $O(\log n)$
• $O(n)$

12. 游戏⼤赛决赛，两组选⼿分别按得分从⼩到⼤排好队，现在要把他们合并成⼀个有序排⾏榜 A组： A = {12, 35, 67, 89} ，B组： B = {20, 45, 55, 78} ，下⾯是归并合并函数的核⼼循环，横线处应填 ⼊（ ）。

int i = 0, j = 0;
vector<int> result;
while (i < A.size() && j < B.size()) {
    if (___________________) {
    result.push_back(A[i++]);
    } else {
    result.push_back(B[j++]);
}
}
while (i < A.size()) {
    result.push_back(A[i++]);
}
while (j < B.size()) {
    result.push_back(B[j++]);
}
}

{{ select(12) }}

• A[i] >= B[j]
• A[i] <= B[j]
• i >= j
• i <= j

13. 有 n 位同学的成绩已经从⼩到⼤排好序，现在对它执⾏下⾯这段以第⼀个元素为 pivot 的快速排序，请 问此次排序的时间复杂度是（ ）。

void quicksort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int pivot = a[l];
    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        while (i < j && a[i] <= pivot) i++;
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[i]);
    quicksort(a, l, i - 1);
    quicksort(a, i + 1, r);
}

{{ select(13) }}

• $O(n^2)$
• $O(n \log n)$
• $O(\log n)$
• $O(n)$

14. 下⾯关于排序算法的描述中，不正确的是( )

{{ select(14) }}

• 冒泡排序和插⼊排序都是稳定的排序算法
• 快速排序和归并排序都是不稳定的排序算法
• 冒泡排序和插⼊排序最好时间复杂度均为$O(n)$
• 归并排序在最好、最坏和平均三种情况的时间复杂度均为$O(nlogn)$

15. 下⾯代码实现两个整数除法，其中被除数为⼀个“⼤整数”，⽤字符串表⽰，除数是⼀个⼩整数，⽤ int 表 ⽰，则横线处应该填写（ ）。

int main(){
    string s;
    int b;
    cin >> s >> b;
    vector<int> a;
    for(char c : s){
        a.push_back(c - '0');
    }
    vector<int> c;
    long long rem = 0;
    for(int i = 0; i < a.size(); i++){
        rem = rem * 10 + a[i];
        int q = rem / b;
        c.push_back(q);
        ______________________
    }
    int pos = 0;
    while(pos < c.size() - 1 && c[pos] == 0) pos++;
    for(int i = pos; i < c.size(); i++){
        cout << c[i];
    }
    cout << endl;
    cout << rem << endl;
    return 0;
}

{{ select(15) }}

• rem /= b;
• rem %= b;
• rem = b;
• rem = q;

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

1. 有⼀个存储了 n 个整数的线性表，分别⽤数组和单链表两种⽅式实现。在已知下标（或结点指针）的前提 下，数组的随机访问是 $O(1)$， ⽽在链表中已知某结点的指针时，在该结点之后插⼊⼀个新结点的操作也是 $O(1)$。

{{ select(16) }}

• 对
• 错

2. 若数组 a 已按升序排列，则下⾯代码可以正确实现 “在 a 中查找第⼀个⼤于等于 x 的元素的位置”

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

{{ select(17) }}

• 对
• 错

3. 快速排序只要每次都选取中间元素作为枢轴，就⼀定是稳定排序

{{ select(18) }}

• 对
• 错

4. 若某算法满足递推式：$T(n) = 2T(n/2) + O(n)$，则其时间复杂度为 $O(n \log n)$。

{{ select(19) }}

• 对
• 错

5. 在⼀个数组中，如果两个元素 a[i] 和 a[j] 满⾜ i < j 且 a[i] > a[j] ，则 a[i] 和 a[j] 是⼀个逆 序对。 下⾯代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。

long long cnt=0;
void merge_count(vector<int>& a, int l, int m, int r){
    int i = l, j = m + 1;
    while(i <= m && j <= r) {
        if(a[i] <= a[j]) i++;
        else {
            cnt += (m - i+ 1);
            j++;
        }
    }
}

{{ select(20) }}

• 对
• 错

6. 唯⼀分解定理保证：若⼀个数未被任何不超过其平⽅根的质数筛去，则它⼀定是质数

{{ select(21) }}

• 对
• 错

7. 假设数组 a 的值域范围是 D ，以下程序的时间复杂度是$O(nlogn+nlogD)$。

bool check(int n, int a[], int k, int dist) {
    int cnt = 1;
    int last = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] - last >= dist) {
        cnt++;
        last = a[i];
    }
    }
    return cnt >= k;
}
int solve(int n, int a[], int k) {
    std::sort(a, a + n);
    int l = 0;
    int r = a[n - 1] - a[0];
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (check(n, a, k, mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}
int main() {
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;
    std::cout << solve(n, a, k) << std::endl;
    return 0;
}

{{ select(22) }}

• 对
• 错

8. 若⼀个问题满⾜最优⼦结构性质，则⼀定可以⽤贪⼼算法得到最优解。

{{ select(23) }}

• 对
• 错

9. 线性筛相⽐埃⽒筛的核⼼改进在于：埃⽒筛中⼀个合数可能被多个质数重复标记，线性筛通过"每个合数只 被其最⼤质因⼦筛去"的策略，保证每个合数恰好被标记⼀次，从⽽实现 $O(n)$的时间复杂度。

{{ select(24) }}

• 对
• 错

10. 任何递归程序都可以改写为等价的⾮递归程序，但改写后的⾮递归程序⼀定需要显式地使⽤栈来模拟递归 调⽤过程。

{{ select(25) }}

• 对
• 错