2026年3月 GESP C++ 5级

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

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

下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填（ ）。

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

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

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

下面代码实现了欧拉（线性）筛，横线处应填写（ ）。

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

埃氏筛中将内层循环从 $j=i\times i$ 开始而不是 $j=2\times 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;
}

下面程序的运行结果为（ ）。

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

在升序数组中查找第一个大于等于 $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;
}

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

给定 $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;
}

下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。

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 组：$A=\{12,35,67,89\}$，B 组：$B=\{20,45,55,78\}$，下面是归并合并函数的核心循环，横线处应填入（ ）。

int i = 0, j = 0;
vector<int> result;
while (i <

有 $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);
}

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

下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 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;
}

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

若数组 $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;
}

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

若某算法满足递推式： ，则其时间复杂度为 。

在一个数组中，如果两个元素 $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++;
        }
    }
}

根据唯一分解定理，如果大于 $1$ 的整数 $n$ 不能被任何不超其平方根的质数整除，那么 $n$ 必定是质数。

假设数组的值域范围是 [0,109][0, 10^9][0,109]，以下程序的时间复杂度是 $O(n\log n)$。

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

若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。

线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过“每个合数只被其最大质因子筛去”的策略，保证每个合数恰好被标记一次，从而实现 $O(n)$ 的时间复杂度。

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

试题名称：有限不循环小数

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

若 1a\frac{1}{a}a1​ 可化为一个有限的，不循环的小数，则称 $a$ 为终止数。

请你求出在 $L$ 到 $R$ 中终止数的数量。

输入格式

输入一行，包含两个整数 $L,R$。

输出格式

输出一行，包含一个整数，表示 $L$ 到 $R$ 中终止数的数量。

样例输入 #1

2 11

样例输出 #1

5

说明/提示

样例解释

在 $[2,11]$ 终止数有 $2$、$4$、$5$、$8$、$10$。

数据范围

保证 1≤L≤R≤1061 \le L \le R \le 10^61≤L≤R≤106。

试题名称：找数

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

给定一个包含 $n$ 个互不相同的正整数的数组 $A$ 与一个包含 $m$ 个互不相同的正整数的数组 $B$，请你帮忙计算有多少个数在数组 $A$ 与数组 $B$ 中均出现。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个正整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​ 表示数组 $A$。

第三行包含 $m$ 个正整数 b1,b2,⋯ ,bmb_1,b_2,\cdots,b_mb1​,b2​,⋯,bm​ 表示数组 $B$。

输出格式

输出一个整数，表示在数组 $A$ 与数组 $B$ 中均出现的数的个数。

样例输入 #1

3 5
4 2 3
3 1 5 4 6

样例输出 #1

2

说明/提示

样例解释

样例 1 中，$4$、$3$ 在数组 $A$ 与 $B$ 中均出现。

数据范围

对于 $40\%$ 的数据，保证 $1\le n,m\le 1000$。

对于 $100\%$ 的数据，保证 1≤n,m≤1051 \leq n,m \leq 10^51≤n,m≤105，1≤ai,bi≤1091 \leq a_i,b_i \leq 10^91≤ai​,bi​≤109。