GESP 五级 · 2026 真题

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

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

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

01struct Node{
02    int val;
03    Node* next;
04    Node(int v):val(v),next(nullptr){}
05};
06Node* eraseAll(Node* head, int x){
07    Node dummy(0);
08    dummy.next = head;
09    Node* cur = &dummy;
10    while(cur->next){
11        if(cur->next->val == x){
12            Node* del = cur->next;
13            ____________
14            delete del;
15        }else cur = cur->next;
16    }
17    return dummy.next;
18}

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

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

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

01vector<int> euler_sieve(int n) {
02    vector<bool> is_composite(n + 1, false);
03    vector<int>  primes;
04    for (int i = 2; i <= n; i++) {
05        if (!is_composite[i])
06            primes.push_back(i);
07        for (int j = 0; ____________ && (long long)i * primes[j] <= n; j++) {
08            is_composite[i * primes[j]] = true;
09            if (i % primes[j] == 0)
10                break;
11        }
12    }
13    return primes;
14}

埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（ ）。

01vector<int> eratosthenes_sieve(int n) {
02    vector<bool> is_composite(n + 1, false);
03    vector<int>  primes;
04    for (int i = 2; i <= n; i++) {
05        if (is_composite[i]) continue;
06        primes.push_back(i);
07        for (long long j = (long long)i * i; j <= n; j += i)
08            is_composite[j] = true;
09    }
10    return primes;
11}

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

01bool check(int n, int a[], int k, int dist) {
02    int cnt = 1;
03    int last = a[0];
04    for (int i = 1; i < n; i++) {
05        if (a[i] - last >= dist) {
06            cnt++;
07            last = a[i];
08        }
09    }
10    return cnt >= k;
11}
12
13int solve(int n, int a[], int k) {
14    std::sort(a, a + n);
15    int l = 0;
16    int r = a[n - 1] - a[0];
17    while (l < r) {
18        int mid = (l + r + 1) / 2;
19        if (check(n, a, k, mid))
20            l = mid;
21        else
22            r = mid - 1;
23    }
24    return l;
25}
26
27int main() {
28    int a[] = {1, 2, 8, 4, 9};
29    int n = 5;
30    int k = 3;
31    std::cout << solve(n, a, k) << std::endl;
32    return 0;
33}

在升序数组中查找第一个大于等于 x 的位置，下面循环中横线应填（ ）。

01int lowerBound(const vector<int>& a, int x){
02    int l=0, r=a.size();
03    while(l<r){
04        int mid = l + (r - l)/2;
05        if(a[mid] >= x)  ____________;
06        else l = mid + 1;
07    }
08    return l;
09}

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

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

01const int MAXN = 100005;
02long long a[MAXN];
03int n, m;
04bool check(long long x){
05    long long cnt = 0;
06    for(int i = 1; i <= n; i++){
07        if(x == 0) return true;
08        cnt += a[i] / x;
09        if(cnt >= m) return true;
10    }
11    return false;
12}
13int main(){
14    cin >> n >> m;
15    long long mx = 0;
16    for(int i = 1; i <= n; i++){
17        cin >> a[i];
18        mx = max(mx, a[i]);
19    }
20    long long l = 1, r = mx;
21    long long ans = 0;
22    while(l <= r){
23        long long mid = l + (r - l) / 2;
24        if(check(mid)){
25            ans = mid;
26            ____________
27        }else{
28            ____________
29        }
30    }
31    cout << ans << endl;
32    return 0;
33}

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

01int solve(vector<int>& a, int l, int r){
02    if(l == r) return a[l];
03    int mid = l + (r - l) / 2;
04    int left = solve(a, l, mid);
05    int right = solve(a, mid + 1, r);
06    int sum = 0, lmax = INT_MIN;
07    for(int i = mid; i >= l; i--){
08        sum += a[i];
09        lmax = max(lmax, sum);
10    }
11    sum = 0;
12    int rmax = INT_MIN;
13    for(int i = mid + 1; i <= r; i++){
14        sum += a[i];
15        rmax = max(rmax, sum);
16    }
17    return max({left, right, lmax + rmax});
18}

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。

A 组：A = {12, 35, 67, 89}，B 组：B = {20, 45, 55, 78}，下面是归并合并函数的核心循环，横线处应填入（ ）。

01int i = 0, j = 0;
02vector<int> result;
03while (i < A.size() && j < B.size()) {
04    if (____________) {
05        result.push_back(A[i++]);
06    } else {
07        result.push_back(B[j++]);
08    }
09}
10while (i < A.size()) {
11    result.push_back(A[i++]);
12}
13while (j < B.size()) {
14    result.push_back(B[j++]);
15}

有 $n$ 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（ ）。

01void quicksort(vector<int>& a, int l, int r) {
02    if (l >= r) return;
03    int pivot = a[l];
04    int i = l, j = r;
05    while (i < j) {
06        while (i < j && a[j] >= pivot) j--;
07        while (i < j && a[i] <= pivot) i++;
08        if (i < j) swap(a[i], a[j]);
09    }
10    swap(a[l], a[i]);
11    quicksort(a, l, i - 1);
12    quicksort(a, i + 1, r);
13}

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

下面代码实现两个整数除法，其中被除数为一个"大整数"，用字符串表示，除数是一个小整数，用 int 表示，则横线处应该填写（ ）。

01int main(){
02    string s;
03    int b;
04    cin >> s >> b;
05    vector<int> a;
06    for(char c : s){
07        a.push_back(c - '0');
08    }
09    vector<int> c;
10    long long rem = 0;
11    for(int i = 0; i < a.size(); i++){
12        rem = rem * 10 + a[i];
13        int q = rem / b;
14        c.push_back(q);
15        ____________
16    }
17    int pos = 0;
18    while(pos < c.size() - 1 && c[pos] == 0) pos++;
19    for(int i = pos; i < c.size(); i++){
20        cout << c[i];
21    }
22    cout << endl;
23    cout << rem << endl;
24    return 0;
25}

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

若数组 a 已按升序排列，则下面代码可以正确实现"在 a 中查找第一个大于等于 x 的元素的位置"。

01int lowerBound(vector<int>& a, int x){
02    int l=0, r=a.size();
03    while(l < r) {
04        int mid = (l + r) / 2;
05        if( a[mid] >= x) r = mid;
06        else l = mid + 1;
07    }
08    return l;
09}

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

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

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

01long long cnt=0;
02void merge_count(vector<int>& a, int l, int m, int r){
03    int i = l, j = m + 1;
04    while(i <= m && j <= r) {
05        if(a[i] <= a[j]) i++;
06        else {
07            cnt += (m - i + 1);
08            j++;
09        }
10    }
11}

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

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

01bool check(int n, int a[], int k, int dist) {
02    int cnt = 1;
03    int last = a[0];
04
05    for (int i = 1; i < n; i++) {
06        if (a[i] - last >= dist) {
07            cnt++;
08            last = a[i];
09        }
10    }
11
12    return cnt >= k;
13}
14
15int solve(int n, int a[], int k) {
16    std::sort(a, a + n);
17
18    int l = 0;
19    int r = a[n - 1] - a[0];
20
21    while (l < r) {
22        int mid = (l + r + 1) / 2;
23
24        if (check(n, a, k, mid))
25            l = mid;
26        else
27            r = mid - 1;
28    }
29
30    return l;
31}
32
33int main() {
34    int a[] = {1, 2, 8, 4, 9};
35    int n = 5;
36    int k = 3;
37
38    std::cout << solve(n, a, k) << std::endl;
39
40    return 0;
41}

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

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

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