GESP C++ 五级 · 2026 年 6 月认证理论卷

1. 假设 head != nullptr，下⾯是实现单向循环链表在头节点后插⼊新节点的代码，横线处应填⼊（ ）。 ```cpp struct Node { int val; Node* next; }; void insertAfterHead(Node* head, int x) { Node* newNode = new Node; newNode->val = x; ______________________ // 在此处填入代码 } ```

2. 下⾯代码遍历并输出⼀个循环单链表，其中 head 指向链表的第⼀个节点，横线处应填⼊的是（ ）。 ```cpp struct Node { int val; Node* next; }; void printList(Node* head) { if (head == nullptr) return; Node* p = head; _______________________ // 在此处填入代码 cout << endl; } ```

3. 双链表结点定义如下，若要删除双链表中的中间结点（⾮⾸尾节点）p，下⾯写法正确的是（ ）。 ```cpp struct Node { int val; Node* prev; Node* next; }; ```

4. 使⽤如下欧⼏⾥得算法求 `gcd(105, 45)` 时，函数 `gcd(a, b)` 的递归调⽤序列正确的是（ ）。 ```cpp int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } ```

5. 下⾯代码实现线性筛（欧拉筛），以筛选出 $n$ 以内的所有素数。横线处的代码应为（ ）。 ```cpp vector<int> sieve(int n) { vector<bool> is_prime(n + 1, true); vector<int> primes; if (n >= 0) is_prime[0] = false; if (n >= 1) is_prime[1] = false; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { primes.push_back(i); } for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) { is_prime[i * primes[j]] = false; if (________________) break; // 在此处填入代码 } } return primes; } ```

6. 下⾯关于埃⽒筛法的说法正确的是（ ）。

7. 下⾯代码实现了计算 $x^n$ 的快速幂算法，该算法体现的编程思想是（ ）。 ```cpp long long power(long long x, int n) { if (n == 0) return 1; long long res = power(x, n / 2); if (n % 2 == 0) return res * res; else return res * res * x; } ```

8. 下⾯代码⽤于统计 n 中因⼦ 2 出现了多少次。若 n = 40，输出是（ ）。 ```cpp int n = 40; int cnt = 0; while (n % 2 == 0) { cnt++; n /= 2; } cout << cnt; ```

9. 在⼀个有序数组中查找第⼀个⼤于或等于 x 的元素位置，横线处应填写（ ）。 ```cpp int lowerBound(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; } ```

10. 有若⼲根⽊头，长度存于 wood。每切⼀⼑可以把⼀段⽊头分成两段。函数 `check(wood, K, x)` 返回：⽤不超过 K ⼑，能否使所有⽊段长度都不超过 x。下⾯代码使⽤⼆分答案查找最⼩可⾏的 x，横线处应填（ ）。 ```cpp int binary_cut(vector<int>& wood, int K) { int l = 1; int r = 0; for (int len : wood) r = max(r, len); while (l < r) { int mid = l + (r - l) / 2; if (check(wood, K, mid)) ________________; // 在此处填入代码 else l = mid + 1; } return l; } ```

11. 下⾯代码段实现了快速排序的划分操作（以⾸元素为基准），横线处代码应填⼊（ ）。 ```cpp int partition(vector<int>& arr, int low, int high) { int pivot = arr[low]; int i = low, j = high; while (i < j) { while (i < j && arr[j] >= pivot) j--; while (i < j && arr[i] <= pivot) i++; if (i < j) swap(arr[i], arr[j]); } ________________; // 在此处填入代码 return i; } ```

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

13. 在对长度为 $n$（$n \ge 1$）的数组进⾏归并排序的过程中，`mergeArray` 函数（合并两个有序⼦数组的操作）被调⽤的次数是（ ）。 ```cpp const int MAXN = 100005; int a[MAXN]; int tempArr[MAXN]; void mergeArray(int left, int mid, int right) { int i = left; // 左半部分起点 int j = mid + 1; // 右半部分起点 int k = left; // 临时数组下标 while (i <= mid && j <= right) { if (a[i] <= a[j]) { tempArr[k++] = a[i++]; } else { tempArr[k++] = a[j++]; } } while (i <= mid) { tempArr[k++] = a[i++]; } while (j <= right) { tempArr[k++] = a[j++]; } for (int p = left; p <= right; p++) { a[p] = tempArr[p]; } } void mergeSort(int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(left, mid); mergeSort(mid + 1, right); mergeArray(left, mid, right); } ```

14. ⼩杨在学校义卖会上负责打包"零⾷盲盒"。每个盲盒重量不同，快递盒最多承重 limit 克，每个快递盒最多装两个盲盒。为了尽量少⽤快递盒，他采⽤如下策略： （1）每次把最轻的盲盒和最重的盲盒尝试放在⼀起； （2）如果两者重量之和不超过 limit，就⼀起装； （3）否则，只能让最重的盲盒单独装⼀盒。 下⾯代码⽤于计算最少需要多少个快递盒，则横线处应填⼊的是（ ）。 ```cpp int minBoxes(vector<int>& w, int limit) { sort(w.begin(), w.end()); int l = 0, r = w.size() - 1; int boxes = 0; while (l <= r) { if (w[l] + w[r] <= limit) { __________; // 在此处填入代码 } else { r--; } boxes++; } return boxes; } ```

15. ⾼精度减法中，假设两个⾼精度数按低位在前存储，且已经保证被减数不⼩于减数。下⾯处理借位逻辑代码中横线处应填⼊（ ）。 ```cpp if (a[i] < b[i]) { a[i + 1]--; ________________; } t = a[i] - b[i]; ```

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

2. 带哨兵头尾节点的双向循环链表，在表头插⼊节点 p，以下四步操作⽆论什么顺序执⾏结果都正确。 ```cpp ① p->next = head->next; ② p->prev = head; ③ head->next->prev = p; ④ head->next = p; ```

3. 对任意正整数 a、b，以下两种写法的 gcd 函数返回值完全相同。 ```cpp int gcd1(int a, int b) { return b ? gcd1(b, a % b) : a; } int gcd2(int a, int b) { while (b) { int t = b; b = a % b; a = t; } return a; } ```

4. 在归并排序的合并操作中，如下代码⽚段可以正确地将两个已排序的⼦数组 L 和 R 合并回原数组 arr 中。 ```cpp void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; vector<int> L(n1), R(n2); for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } ```

5. 分治法通常将⼀个规模较⼤的问题拆分为若⼲个规模较⼩、结构相似的⼦问题，分别求解后再合并⼦问题的结果。

6. 贪⼼算法只要每⼀步选择当前最优解，就⼀定能得到全局最优解。

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

8. 以下函数 f1 的时间复杂度⽐函数 f2 的更⾼。 ```cpp void f1(int n) { for (int i = 1; i < n; i *= 2); } void f2(int n) { if (n <= 1) return; f2(n - 1); f2(n - 1); } ```

9. 唯⼀分解定理表明，任何⼀个⼤于 1 的⾃然数都可以唯⼀地分解为若⼲个质数的乘积，如果不考虑质因数的顺序，这种分解⽅式是唯⼀的。

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