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

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

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

3. 下面函数用"哑结点"统一处理删除单向链表中的头结点与中间结点。横线处应填（ ）。 ```cpp 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; } ```

4. 对如下代码实现的欧几里得算法（辗转相除法），执行 gcd(48, 18) 得到的调用序列为（ ）。 ```cpp int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } ```

5. 下面代码实现了欧拉（线性）筛，横线处应填写（ ）。 ```cpp 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; } ```

6. 埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（ ）。 ```cpp 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; } ```

7. 下面程序的运行结果为（ ）。 ```cpp 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; } ```

8. 在升序数组中查找第一个大于等于x的位置，下面循环中横线应填（ ）。 ```cpp 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; } ```

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

10. 给定 n 根木头，第 i 根长度为 a[i]。要切成不少于 m 段等长木段，求最大可能长度，则横线上应填写（ ）。 ```cpp 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; } ```

11. 下面代码用分治求"最大连续子段和"，其时间复杂度为（ ）。 ```cpp 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}); } ```

12. 游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。A组：A = {12, 35, 67, 89}，B组：B = {20, 45, 55, 78}，下面是归并合并函数的核心循环，横线处应填入（ ）。 ```cpp 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++]); } ```

13. 有 n 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（ ）。 ```cpp 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); } ```

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

15. 下面代码实现两个整数除法，其中被除数为一个"大整数"，用字符串表示，除数是一个小整数，用int表示，则横线处应该填写（ ）。 ```cpp 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; } ```

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

2. 若数组 a 已按升序排列，则下面代码可以正确实现"在 a 中查找第一个大于等于 x 的元素的位置"。 ```cpp 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; } ``` ( )

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

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

5. 在一个数组中，如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j]，则 a[i] 和 a[j] 是一个逆序对。 下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。 ```cpp 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++; } } } ``` ( )

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

7. 假设数组 a 的值域范围是 $\[0, n)$，以下程序的时间复杂度是 $O(n \log n)$。 ```cpp 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; } ``` ( )

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

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

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