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

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

• A.newNode->next = head; head->next = newNode;
• B.newNode->next = head->next; head->next = newNode;
• C.head->next = newNode; newNode->next = head->next;
• D.newNode->next = head->next; head = newNode;

下面代码遍历并输出一个循环单链表，其中head指向链表的第一个节点，横线处应填入的是（ ）。[)A. 1 struct Node { 2 int val; 3 Node* next; 4 }; 6 void printList(Node* head) { 7 if (head == nullptr) return; 8 Node* p = head; 9 _______________________ // 在此处填入代码 10 cout << endl; 11 } 1 while (p != nullptr) { 2 cout << p->val << " "; 3 p = p->next; 4 }

• A.1 while (p != nullptr) { 2 cout << p->val << " "; 3 p = p->next; 4 }
• B.1 while (p->next != nullptr) { 2 cout << p->val << " "; 3 p = p->next; 4 }
• C.1 do { 2 cout << p->val << " "; 3 p = p->next; 4 } while (p != head);
• D.1 for (; p; p = p->next) { 2 cout << p->val << " "; 3 }

双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点） p ，下面写法正确的是（ ）。 struct Node { int val; Node* prev; Node* next; };

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

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

• A.gcd(105, 45) -> gcd(45, 60) -> gcd(60, 15) -> gcd(15, 0)
• B.gcd(105, 45) -> gcd(45, 15) -> gcd(15, 0)
• C.gcd(105, 45) -> gcd(60, 45) -> gcd(15, 45)
• D.gcd(105, 45) -> gcd(15, 45) -> gcd(15, 0)

下面代码实现线性筛（欧拉筛），以筛选出 n 以内的所有素数。横线处的代码应为（ ）。 1 vector<int> sieve(int n) { 2 vector<bool> is_prime(n + 1, true); 3 vector<int> primes; 5 if (n >= 0) is_prime[0] = false; 6 if (n >= 1) is_prime[1] = false; 8 for (int i = 2; i <= n; ++i) { 9 if (is_prime[i]) { 10 primes.push_back(i); 11 } 12 for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) { 13 is_prime[i * primes[j]] = false; 14 if (________________) break; // 在此处填入代码 15 } 16 } 17 return primes; 18 }

• A.i % primes[j] == 0
• B.primes[j] % i == 0
• C.i % primes[j] != 0
• D.i == primes[j]

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

• A.每个合数只会被筛掉一次
• B.从每个素数出发，把它的倍数标记为合数
• C.只能判断一个数是不是偶数
• D.不能求出素数表

下面代码实现了计算 x^n 的快速幂算法，该算法体现的编程思想是（ ）。 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; }

• A.枚举
• B.贪心
• C.分治
• D.模拟

下面代码用于统计n中因子2出现了多少次。若n = 40 ，输出是（ ）。 int n = 40; int cnt = 0; while (n % 2 == 0) { cnt++; n /= 2; } cout << cnt;

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

在一个有序数组中查找第一个大于或等于x的元素位置，横线处应填写（ ）。 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; }

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

有若干根木头，长度存于wood 。每切一刀可以把一段木头分成两段。函数check(wood, K, x)返回：用不超过K刀，能否使所有木段长度都不超过x 。下面代码使用二分答案查找最小可行的x ，横线处应填（）。 1 int binary_cut(vector<int>& wood, int K) { 2 int l = 1; 3 int r = 0; 5 for (int len : wood) r = max(r, len); 6 while (l < r) { 7 int mid = l + (r - l) / 2; 8 if (check(wood, K, mid)) 9 ________________; // 在此处填入代码 10 else l = mid + 1; 11 } 12 return l; 13 }

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

下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（ ）。 1 int partition(vector<int>& arr, int low, int high) { 2 int pivot = arr[low]; 3 int i = low, j = high; 4 while (i < j) { 5 while (i < j && arr[j] >= pivot) j--; 6 while (i < j && arr[i] <= pivot) i++; 7 if (i < j) swap(arr[i], arr[j]); 8 } 9 ________________; // 在此处填入代码 10 return i; 11 }

• A.swap(arr[low], arr[high])
• B.swap(arr[low], arr[i])
• C.swap(arr[i], arr[high])
• D.arr[i] = pivot

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

• A.每次选择最小元素放到前面
• B.将数组分成两半分别排序，再合并两个有序部分
• C.相邻元素两两交换
• D.从左到右把元素插入有序区

在对长度为为（ > ）的数组进行归并排序的过程中， mergeArray函数（合并两个有序子数组的操作）被调用的次数是（ ）。]A. 1 const int MAXN = 100005; 3 int a[MAXN]; 4 int tempArr[MAXN]; 6 void mergeArray(int left, int mid, int right) { 7 int i = left; // 左半部分起点 8 int j = mid + 1; // 右半部分起点 9 int k = left; // 临时数组下标 11 while (i <= mid && j <= right) { 12 if (a[i] <= a[j]) { 13 tempArr[k++] = a[i++]; 14 } else { 15 tempArr[k++] = a[j++]; 16 } 17 } 19 while (i <= mid) { 20 tempArr[k++] = a[i++]; 21 } 23 while (j <= right) { 24 tempArr[k++] = a[j++]; 25 } 27 for (int p = left; p <= right; p++) { 28 a[p] = tempArr[p]; 29 } 30 } 32 void mergeSort(int left, int right) { 33 if (left >= right) { 34 return; 35 } 37 int mid = left + (right - left) / 2; 39 mergeSort(left, mid); 40 mergeSort(mid + 1, right); 42 mergeArray(left, mid, right); 43 }

• A.n − 1
• B.log n
• C.n log n
• D.2n

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

• A.l++;
• B.r--;
• C.l++; r--;
• D.boxes--;

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

• A.a[i] += 10
• B.a[i] -= 10
• C.b[i] += 10
• D.a[i] = a[i+1] + 10

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

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

对任意正整数a 、 b ，以下两种写法的gcd函数返回值完全相同。 1 int gcd1(int a, int b) { 2 return b ? gcd1(b, a % b) : a; 3 } 5 int gcd2(int a, int b) { 6 while (b) { 7 int t = b; 8 b = a % b; 9 a = t; 10 } 11 return a; 12 }

在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组L和R合并回原数组arr中。 1 void merge(int arr[], int left, int mid, int right) { 2 int n1 = mid - left + 1; 3 int n2 = right - mid; 4 vector<int> L(n1), R(n2); 6 for (int i = 0; i < n1; i++) L[i] = arr[left + i]; 7 for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; 8 int i = 0, j = 0, k = left; 9 while (i < n1 && j < n2) { 10 if (L[i] <= R[j]) arr[k++] = L[i++]; 11 else arr[k++] = R[j++]; 12 } 13 while (i < n1) arr[k++] = L[i++]; 14 while (j < n2) arr[k++] = R[j++]; 15 }

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

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

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

以下函数f1的时间复杂度比函数f2的更高。 1 void f1(int n) { 2 for (int i = 1; i < n; i *= 2); 3 } 5 void f2(int n) { 6 if (n <= 1) return; 7 f2(n - 1); 8 f2(n - 1); 9 }

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

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

试题名称：排排坐 时间限制：1.0 s　内存限制：512.0 MB 题目描述：老师正在和小朋友们分糖果。小朋友们先在自己的手上写一个数字，然后坐成一排。老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。现在小朋友们都已经在自己手上写上了数字。请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。 输入格式：输入 2 行，第一行为一个正整数 n，表示小朋友的个数；第二行为 n 个正整数 a_1, a_2, …, a_n，表示小朋友们手上的数字，整数之间以空格分隔。 输出格式：输出一个整数，表示小朋友们可能分到的最大糖果总数量。 输入样例1：5 7 5 8 9 3 输出样例1：111 样例解释1：小朋友安排座位后从左向右每人手上数字依次是：9, 8, 7, 5, 3。这时可以得到最多的糖果：(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111。 数据范围：1 ≤ n ≤ 1000，1 ≤ a_i ≤ 1000。

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

试题名称：晚宴 时间限制：1.0 s　内存限制：512.0 MB 题目描述：小明去参加晚宴。晚宴中有 n 个菜肴，每个菜肴都有一个美味度，第 i 个菜肴的美味度为 v_i。晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 1）。请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。 输入格式：输入 2 行，第一行为一个正整数 n，表示菜肴的个数；第二行为 n 个整数 v_1, v_2, …, v_n，表示菜肴的美味度，整数之间以空格分隔。 输出格式：输出一个整数，表示两道互质菜肴美味度之和的最大值。 输入样例1：5 3 5 7 35 105 输出样例1：38 样例解释1：最优选择是 3 和 35。注意到，105 与其他任意菜肴的最大公约数都大于 1，因此无法参与合法选择。 数据范围：2 ≤ n ≤ 1000，1 ≤ v_i ≤ 1000000。 数据保证不存在相同美味度的菜肴。 数据保证至少存在一种选取两道菜肴的方案。

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