GESP 五级 · 2026 真题

假设 head != nullptr，下面是实现单向循环链表在头节点后插入新节点的代码，横线处应填入（ ）。

01struct Node {
02    int val;
03    Node* next;
04};
05
06void insertAfterHead(Node* head, int x) {
07    Node* newNode = new Node;
08    newNode->val = x;
09    ______________________ // 在此处填入代码
10}

下面代码遍历并输出一个循环单链表，其中 head 指向链表的第一个节点，横线处应填入的是（ ）。

01struct Node {
02    int val;
03    Node* next;
04};
05
06void printList(Node* head) {
07    if (head == nullptr) return;
08    Node* p = head;
09    _______________________ // 在此处填入代码
10    cout << endl;
11}

双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点）p，下面写法正确的是（ ）。

01struct Node {
02    int val;
03    Node* prev;
04    Node* next;
05};

使用如下欧几里得算法求 gcd(105, 45) 时，函数 gcd(a, b) 的递归调用序列正确的是（ ）。

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

下面代码实现线性筛（欧拉筛），以筛选出 $n$ 以内的所有素数。横线处的代码应为（ ）。

01vector<int> sieve(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04    if (n >= 0) is_prime[0] = false;
05    if (n >= 1) is_prime[1] = false;
06    for (int i = 2; i <= n; ++i) {
07        if (is_prime[i]) {
08            primes.push_back(i);
09        }
10        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
11            is_prime[i * primes[j]] = false;
12            if (________________) break; // 在此处填入代码
13        }
14    }
15    return primes;
16}

下面关于埃氏筛法的说法正确的是（ ）。

下面代码实现了计算 $x^n$ 的快速幂算法，该算法体现的编程思想是（ ）。

01long long power(long long x, int n) {
02    if (n == 0) return 1;
03    long long res = power(x, n / 2);
04    if (n % 2 == 0) return res * res;
05    else return res * res * x;
06}

下面代码用于统计 n 中因子 2 出现了多少次。若 n = 40，输出是（ ）。

01int n = 40;
02int cnt = 0;
03while (n % 2 == 0) {
04    cnt++;
05    n /= 2;
06}
07cout << cnt;

在一个有序数组中查找第一个大于或等于 x 的元素位置，横线处应填写（ ）。

01int lowerBound(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}

有若干根木头，长度存于 wood。每切一刀可以把一段木头分成两段。函数 check(wood, K, x) 返回：用不超过 K 刀，能否使所有木段长度都不超过 x。下面代码使用二分答案查找最小可行的 x，横线处应填（ ）。

01int binary_cut(vector<int>& wood, int K) {
02    int l = 1;
03    int r = 0;
04    for (int len : wood) r = max(r, len);
05    while (l < r) {
06        int mid = l + (r - l) / 2;
07        if (check(wood, K, mid))
08            ________________; // 在此处填入代码
09        else l = mid + 1;
10    }
11    return l;
12}

下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（ ）。

01int partition(vector<int>& arr, int low, int high) {
02    int pivot = arr[low];
03    int i = low, j = high;
04    while (i < j) {
05        while (i < j && arr[j] >= pivot) j--;
06        while (i < j && arr[i] <= pivot) i++;
07        if (i < j) swap(arr[i], arr[j]);
08    }
09    ________________; // 在此处填入代码
10    return i;
11}

下面哪句话最符合归并排序的思想？（ ）

在对长度为 $n$（$n\ge1$）的数组进行归并排序的过程中，mergeArray 函数（合并两个有序子数组的操作）被调用的次数是（ ）。

01const int MAXN = 100005;
02int a[MAXN];
03int tempArr[MAXN];
04
05void mergeArray(int left, int mid, int right) {
06    int i = left;      // 左半部分起点
07    int j = mid + 1;   // 右半部分起点
08    int k = left;      // 临时数组下标
09
10    while (i <= mid && j <= right) {
11        if (a[i] <= a[j]) {
12            tempArr[k++] = a[i++];
13        } else {
14            tempArr[k++] = a[j++];
15        }
16    }
17
18    while (i <= mid) {
19        tempArr[k++] = a[i++];
20    }
21
22    while (j <= right) {
23        tempArr[k++] = a[j++];
24    }
25
26    for (int p = left; p <= right; p++) {
27        a[p] = tempArr[p];
28    }
29}
30
31void mergeSort(int left, int right) {
32    if (left >= right) {
33        return;
34    }
35
36    int mid = left + (right - left) / 2;
37    mergeSort(left, mid);
38    mergeSort(mid + 1, right);
39    mergeArray(left, mid, right);
40}

小杨在学校义卖会上负责打包“零食盲盒”。每个盲盒重量不同，快递盒最多承重 limit 克，每个快递盒最多装两个盲盒。为了尽量少用快递盒，他采用如下策略：

（$1$）每次把最轻的盲盒和最重的盲盒尝试放在一起；

（$2$）如果两者重量之和不超过 limit，就一起装；

（$3$）否则，只能让最重的盲盒单独装一盒。

下面代码用于计算最少需要多少个快递盒，则横线处应填入的是（ ）。

01int minBoxes(vector<int>& w, int limit) {
02    sort(w.begin(), w.end());
03    int l = 0, r = w.size() - 1;
04    int boxes = 0;
05    while (l <= r) {
06        if (w[l] + w[r] <= limit) {
07            __________; // 在此处填入代码
08        } else {
09            r--;
10        }
11        boxes++;
12    }
13    return boxes;
14}

高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（ ）。

01if (a[i] < b[i]) {
02    a[i + 1]--;
03    ________________;
04}
05t = a[i] - b[i];

数组的存储空间在物理上通常是连续的，而链表的结点可以存储在不连续的内存空间中。

带哨兵头尾节点的双向循环链表，在表头插入节点 p，以下四步操作无论什么顺序执行结果都正确。

① p->next = head->next;
② p->prev = head;
③ head->next->prev = p;
④ head->next = p;

对任意正整数 a、b，以下两种写法的 gcd 函数返回值完全相同。

01int gcd1(int a, int b) {
02    return b ? gcd1(b, a % b) : a;
03}
04
05int gcd2(int a, int b) {
06    while (b) {
07        int t = b;
08        b = a % b;
09        a = t;
10    }
11    return a;
12}

在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组 L 和 R 合并回原数组 arr 中。

01void merge(int arr[], int left, int mid, int right) {
02    int n1 = mid - left + 1;
03    int n2 = right - mid;
04    vector<int> L(n1), R(n2);
05    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
06    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
07    int i = 0, j = 0, k = left;
08    while (i < n1 && j < n2) {
09        if (L[i] <= R[j]) arr[k++] = L[i++];
10        else arr[k++] = R[j++];
11    }
12    while (i < n1) arr[k++] = L[i++];
13    while (j < n2) arr[k++] = R[j++];
14}

分治法通常将一个规模较大的问题拆分为若干个规模较小、结构相似的子问题，分别求解后再合并子问题的结果。

贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。

二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持 $O(1)$ 时间内的随机访问。

以下函数 f1 的时间复杂度比函数 f2 的更高。

01void f1(int n) {
02    for (int i = 1; i < n; i *= 2);
03}
04
05void f2(int n) {
06    if (n <= 1) return;
07    f2(n - 1);
08    f2(n - 1);
09}

唯一分解定理表明，任何一个大于 $1$ 的自然数都可以唯一地分解为若干个质数的乘积，如果不考虑质因数的顺序，这种分解方式是唯一的。

归并排序和快速排序在平均情况下的时间复杂度均为 $O(n\log n)$。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。