GESP C++ 编程五级 · 2026 年 3 月卷

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

• A.在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点。
• B.循环链表中一定不存在空指针。
• C.在循环双链表中，尾结点的next指针一定为nullptr 。
• D.在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。

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

• A.s->next = p; p->prev = s; p->next = s; s->prev = p;
• B.s->prev = p; s->next = p->next; p->next->prev = s; p->next = s;
• C.s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s;
• D.s->next = p; s->prev = nullptr; p->prev = s;

下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填（ ）。 1 struct Node{ 2 int val; 3 Node* next; 4 Node(int v):val(v),next(nullptr){} 5 }; 7 Node* eraseAll(Node* head, int x){ 8 Node dummy(0); 9 dummy.next = head; 10 Node* cur = &dummy; 11 while(cur->next){ 12 if(cur->next->val == x){ 13 Node* del = cur->next; 14 ______________________ 15 delete del; 16 }else cur = cur->next; 17 } 18 return dummy.next; 19 }

• A.cur = cur->next;
• B.cur->next = del->next;
• C.del->next = cur->next;
• D.cur->next = nullptr;

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

• A.gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
• B.gcd(48,18) -> gcd(30,18) -> gcd(12,18)
• C.gcd(48,18) -> gcd(18,30) -> gcd(30,6)
• D.gcd(48,18) -> gcd(12,18) -> gcd(6,12)

下面代码实现了欧拉（线性）筛，横线处应填写（ ）。 1 vector<int> euler_sieve(int n) { 2 vector<bool> is_composite(n + 1, false); 3 vector<int> primes; 5 for (int i = 2; i <= n; i++) { 6 if (!is_composite[i]) 7 primes.push_back(i); 9 for (int j = 0; __________________________ && (long long)i * primes[j] <= n; j++) { 10 is_composite[i * primes[j]] = true; 12 if (i % primes[j] == 0) 13 break; 14 } 15 } 16 return primes; 17 }

• A.j <= n
• B.j < sqrt(n)
• C.j < primes.size()
• D.j < i

埃氏筛中将内层循环从j = i*i开始而不是j = 2*i的主要原因是（ ）。 1 vector<int> eratosthenes_sieve(int n) { 2 vector<bool> is_composite(n + 1, false); 3 vector<int> primes; 5 for (int i = 2; i <= n; i++) { 6 if (is_composite[i]) continue; 8 primes.push_back(i); 10 for (long long j = (long long)i * i; j <= n; j += i) 11 is_composite[j] = true; 12 } 13 return primes; 14 }

• A.因为 2*i 一定不是合数
• B.i*i 一定是质数
• C.小于 i*i 的 i 的倍数已被更小质因子筛过
• D.这样可以把时间复杂度降为 O(n)

下面程序的运行结果为（ ）。 1 bool check(int n, int a[], int k, int dist) { 2 int cnt = 1; 3 int last = a[0]; 5 for (int i = 1; i < n; i++) { 6 if (a[i] - last >= dist) { 7 cnt++; 8 last = a[i]; 9 } 10 } 12 return cnt >= k; 13 } 15 int solve(int n, int a[], int k) { 16 std::sort(a, a + n); 18 int l = 0; 19 int r = a[n - 1] - a[0]; 21 while (l < r) { 22 int mid = (l + r + 1) / 2; 24 if (check(n, a, k, mid)) 25 l = mid; 26 else 27 r = mid - 1; 28 } 30 return l; 31 } 33 int main() { 34 int a[] = {1, 2, 8, 4, 9}; 35 int n = 5; 36 int k = 3; 38 std::cout << solve(n, a, k) << std::endl; 40 return 0; 41 }

• A.2
• B.3
• C.4
• D.5

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

• A.r = mid;
• B.r = mid - 1;
• C.l = mid;
• D.l = mid + 1;

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

• A.递归调用层次过深时，可能会耗尽栈空间导致栈溢出
• B.尾递归函数可以通过编译器优化来避免栈溢出
• C.所有递归函数都可以通过循环结构来改写，从而避免栈溢出
• D.栈溢出发生时，程序会抛出异常并可以继续执行后续代码

给定n根木头，第i根长度为a[i] 。要切成不少于m段等长木段，求最大可能长度，则横线上应填写（ ）。 1 const int MAXN = 100005; 2 long long a[MAXN]; 3 int n, m; 5 bool check(long long x){ 6 long long cnt = 0; 7 for(int i = 1; i <= n; i++){ 8 if(x == 0) return true; 9 cnt += a[i] / x; 10 if(cnt >= m) return true; 11 } 12 return false; 13 } 15 int main(){ 16 cin >> n >> m; 17 long long mx = 0; 18 for(int i = 1; i <= n; i++){ 19 cin >> a[i]; 20 mx = max(mx, a[i]); 21 } 23 long long l = 1, r = mx; 24 long long ans = 0; 26 while(l <= r){ 27 long long mid = l + (r - l) / 2; 29 if(check(mid)){ 30 ans = mid; 31 ______________________ 32 }else{ 33 ______________________ 34 } 35 } 37 cout << ans << endl; 38 return 0; 39 }

• A.l = mid + 1; r = mid - 1;
• B.l = mid - 1; r = mid + 1;
• C.l = mid + 1; r = mid;
• D.l = mid; r = mid + 1;

下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。 1 int solve(vector<int>& a, int l, int r){ 2 if(l == r) return a[l]; 4 int mid = l + (r - l) / 2; 6 int left = solve(a, l, mid); 7 int right = solve(a, mid + 1, r); 9 int sum = 0, lmax = INT_MIN; 10 for(int i = mid; i >= l; i--){ 11 sum += a[i]; 12 lmax = max(lmax, sum); 13 } 15 sum = 0; 16 int rmax = INT_MIN; 17 for(int i = mid + 1; i <= r; i++){ 18 sum += a[i]; 19 rmax = max(rmax, sum); 20 } 22 return max({left, right, lmax + rmax}); 23 }

• A.O(n^2)
• B.O(n log n)
• C.O(log n)
• D.O(n)

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。A组： A = {12, 35, 67, 89} ，B组： B = {20, 45, 55, 78} ，下面是归并合并函数的核心循环，横线处应填入（ ）。 1 int i = 0, j = 0; 2 vector<int> result; 4 while (i < A.size() && j < B.size()) { 5 if (___________________) { 6 result.push_back(A[i++]); 7 } else { 8 result.push_back(B[j++]); 9 } 10 } 12 while (i < A.size()) { 13 result.push_back(A[i++]); 14 } 16 while (j < B.size()) { 17 result.push_back(B[j++]); 18 }

• A.A[i] >= B[j]
• B.A[i] <= B[j]
• C.i >= j
• D.i <= j

有 n 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为pivot的快速排序，请问此次排序的时间复杂度是（ ）。 1 void quicksort(vector<int>& a, int l, int r) { 2 if (l >= r) return; 3 int pivot = a[l]; 4 int i = l, j = r; 5 while (i < j) { 6 while (i < j && a[j] >= pivot) j--; 7 while (i < j && a[i] <= pivot) i++; 8 if (i < j) swap(a[i], a[j]); 9 } 10 swap(a[l], a[i]); 11 quicksort(a, l, i - 1); 12 quicksort(a, i + 1, r); 13 }

• A.O(n)
• B.O(n log n)
• C.O(n^2)
• D.O(log n)

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

• A.冒泡排序和插入排序都是稳定的排序算法
• B.快速排序和归并排序都是不稳定的排序算法
• C.冒泡排序和插入排序最好时间复杂度均为 O(n)
• D.归并排序在最好、最坏和平均三种情况的时间复杂度均为 O(n log n)

下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用int表示，则横线处应该填写（ ）。 1 int main(){ 2 string s; 3 int b; 4 cin >> s >> b; 6 vector<int> a; 7 for(char c : s){ 8 a.push_back(c - '0'); 9 } 11 vector<int> c; 12 long long rem = 0; 14 for(int i = 0; i < a.size(); i++){ 15 rem = rem * 10 + a[i]; 16 int q = rem / b; 17 c.push_back(q); 18 ______________________ 19 } 21 int pos = 0; 22 while(pos < c.size() - 1 && c[pos] == 0) pos++; 24 for(int i = pos; i < c.size(); i++){ 25 cout << c[i]; 26 } 28 cout << endl; 29 cout << rem << endl; 30 return 0; 31 }

• A.rem /= b;
• B.rem %= b;
• C.rem = b;
• D.rem = q;

有一个存储了 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; }

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

若某算法满足递推式： 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]内的逆序对总数。 1 long long cnt=0; 2 void merge_count(vector<int>& a, int l, int m, int r){ 3 int i = l, j = m + 1; 4 while(i <= m && j <= r) { 5 if(a[i] <= a[j]) i++; 6 else { 7 cnt += (m - i+ 1); 8 j++; 9 } 10 } 1111}}

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

假设数组o的值域范围是 D，以下程序的时间复杂度是 O(n log n + n log D)。 1 bool check(int n, int a[], int k, int dist) { 2 int cnt = 1; 3 int last = a[0]; 5 for (int i = 1; i < n; i++) { 6 if (a[i] - last >= dist) { 7 cnt++; 8 last = a[i]; 9 } 10 } 12 return cnt >= k; 13 } 15 int solve(int n, int a[], int k) { 16 std::sort(a, a + n); 18 int l = 0; 19 int r = a[n - 1] - a[0]; 21 while (l < r) { 22 int mid = (l + r + 1) / 2; 24 if (check(n, a, k, mid)) 25 l = mid; 26 else 27 r = mid - 1; 28 } 30 return l; 31 } 33 int main() { 34 int a[] = {1, 2, 8, 4, 9}; 35 int n = 5; 36 int k = 3; 38 std::cout << solve(n, a, k) << std::endl; 40 return 0; 41 }

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

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

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

试题名称：有限不循环小数 时间限制：1.0 s　内存限制：512.0 MB 题目描述：若 1/a 可化为一个有限的，不循环的小数，则称 a 为终止数。 请你求出在 L 到 R 中终止数的数量。 输入格式：输入一行，包含两个整数 L, R。 输出格式：输出一行，包含一个整数，表示 L 到 R 中终止数的数量。 输入样例1：2 11 输出样例1：5 样例解释1：在 [2, 11] 终止数有 2、4、5、8、10。 数据范围：保证 1 ≤ L ≤ R ≤ 10^6。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。

试题名称：找数 时间限制：1.0 s　内存限制：512.0 MB 题目描述：给定一个包含 n 个互不相同的正整数的数组 A 与一个包含 m 个互不相同的正整数的数组 B，请你帮忙计算有多少数在数组 A 与数组 B 中均出现。 输入格式：第一行包含两个整数 n, m。 第二行包含 n 个正整数 a_1, a_2, ⋯, a_n 表示数组 A。 第二行包含 m 个正整数 b_1, b_2, ⋯, b_m 表示数组 B。 输出格式：输出一个整数，表示在数组 A 与数组 B 中均出现的数的个数。 输入样例1：3 5 4 2 3 3 1 5 4 6 输出样例1：2 样例解释1：样例 1 中，4、3 在数组 A 与 B 中均出现。 数据范围：对于 40% 的数据，保证 1 ≤ n, m ≤ 1000。 对于 100% 的数据，保证 1 ≤ n, m ≤ 10^5，1 ≤ a_i, b_i ≤ 10^9。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。