CCF GESP 2026年3月认证 C++ 5级

一 单选题
共 15 道 每题 2 分 共计 30 分
第 1 题

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

A

在单链表中，若已知任意结点的指针，则可以在 $O(1)$ 时间内删除该结点。
B

循环链表中一定不存在空指针。
C

在循环双链表中，尾结点的 next 指针一定为 nullptr。
D

在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。
第 2 题

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

A 
s->next=p; 
p->prev=s; 
p->next=s; 
s->prev=p;
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;
第 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;
}
A

cur = cur->next;
B

cur->next = del->next;
C

del->next = cur->next;
D

cur->next = nullptr;
第 4 题

对如下代码实现的欧几里得算法（辗转相除法），执行 gcd(48,18) 得到的调用序列为（ ）。

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

gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0)
B

gcd(48,18) → gcd(30,18) → gcd(12,18)
C

gcd(48,18) → gcd(18,30) → gcd(30,6)
D

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;
}
A

j <= n
B

j < sqrt(n)
C

j < primes.size()
D

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;
}
A

因为 2∗i 一定不是合数
B

i∗i 一定是质数
C

小于 i∗i 的 i 的倍数已被更小质因子筛过
D

这样可以把时间复杂度降为 $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;
}
A

2
B

3
C

4
D

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;
}
A

r = mid
B

r = mid - 1
C

l = mid
D

l = mid + 1
第 9 题

关于递归函数调用，下列说法错误的是（ ）。

A

递归调用层次过深时，可能会耗尽栈空间导致栈溢出

B

尾递归函数可以通过编译器优化来避免栈溢出

C

所有递归函数都可以通过循环结构来改写，从而避免栈溢出

D

栈溢出发生时，程序会抛出异常并可以继续执行后续代码

第 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;
}
A 
l = mid + 1;
r = mid - 1;
B 
l = mid - 1;
r = mid + 1;
C 
l = mid + 1;
r = mid;
D 
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});
}
A

$O(n^2)$
B

$O(n\ log\,n)$
C

$O(log\,n)$
D

$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++]); 
}
A

A[i] >= B[j]
B

A[i] <= B[j]
C

i >= j
D

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);
}
A

$O(n)$
B

$O(n\ log\,n)$
C

$O(n^2)$
D

$O(log\,n)$
第 14 题

下面关于排序算法的描述中，不正确的是（ ）。

A

冒泡排序和插入排序都是稳定的排序算法

B

快速排序和归并排序都是不稳定的排序算法

C

冒泡排序和插入排序最好时间复杂度均为 $O(n)$

D

归并排序在最好、最坏和平均三种情况下的时间复杂度均为 $O(n\ log\,n)$

第 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;
}
A

rem /= b;
B

rem %= b;
C

rem = b;
D

rem = q;
单选题部分已到底了。