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

小杨用单链表保存任务序列，并同时维护头指针head和尾指针tail 。在链表非空且已知tail的情况下，在表尾插入新结点的时间复杂度是（ ）。 1 struct Node { 2 int value; 3 Node *next; 4 }; 6 Node *head; 7 Node *tail;

• A.O(1)
• B.O(log n)
• C.O(n)
• D.O(n log n)

在不带哨兵结点的双向链表中，结点p既不是头结点也不是尾结点。删除p的正确代码是（ ）。 struct Node { int value; Node *prev; Node *next; };

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

下面函数使用快慢指针查找单链表的中间结点。横线处应填写（ ）。 1 struct Node { 2 int value; 3 Node *next; 4 }; 6 Node *middle(Node *head) { 7 Node *slow = head; 8 Node *fast = head; 9 while (fast != nullptr && fast->next != nullptr) { 10 slow = slow->next; 11 ______________________ 12 } 13 return slow; 14 }

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

函数gcd(int a, int b)定义如下，则gcd(105, 45)的结果是（ ）。 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

• A.3
• B.5
• C.15
• D.45

下面函数用于判断正整数n是否为质数。横线处的最佳写法是（ ）。 bool isPrime(int n) { if (n < 2) return false; for (int i = 2; __________________; i++) { if (n % i == 0) return false; } return true; }

• A.i < n
• B.i <= n / 2
• C.i * i < n
• D.(long long) i * i <= n

下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次，横线处应填写（ ）。 1 vector<int> linearSieve(int n) { 2 vector<bool> composite(n + 1, false); 3 vector<int> primes; 5 for (int i = 2; i <= n; i++) { 6 if (!composite[i]) 7 primes.push_back(i); 8 for (int p : primes) { 9 if ((long long)i * p > n) 10 break; 11 composite[i * p] = true; 12 if (__________________) 13 break; 14 } 15 } 16 return primes; 17 }

• A.p % i == 0
• B.i % p == 0
• C.i == p
• D.i * p == n

根据唯一分解定理，整数756的正确质因数分解是（ ）。

• A.2^2 × 3^3 × 7
• B.2^3 × 3^2 × 7
• C.2^2 × 3^2 × 21
• D.2 × 3^3 × 14

函数f(int n)定义如下，则f(4)的结果是（ ）。 int f(int n) { if (n == 1) return 1; return n + f(n - 1); }

• A.4
• B.7
• C.9
• D.10

在升序数组中查找第一个严格大于x的元素位置，下面代码中的横线应填写（ ）。 1 int upperBound(const vector<int> &a, int x) { 2 int l = 0, r = (int)a.size(); 3 while (l < r) { 4 int mid = l + (r - l) / 2; 5 if (__________________) { 6 l = mid + 1; 7 } else { 8 r = mid; 9 } 10 } 11 return l; 12 }

• A.a[mid] < x
• B.a[mid] >= x
• C.a[mid] <= x
• D.a[mid] > x

小杨需要把若干箱货物按原顺序分配到days天中，每天运输连续的若干箱，求能够完成任务的最小载重量。函数check(cap)判断载重量为cap时能否在规定天数内运完。横线处应填写（ ）。 1 long long l = maxWeight; 2 long long r = totalWeight; 4 while (l < r) { 5 long long mid = l + (r - l) / 2; 6 if (check(mid)) { 7 ____________________ 8 } else { 9 ____________________ 10 } 11 } 12 cout << l;

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

下面是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写（ ）。 while (i <= mid && j <= right) { if (__________________) { temp.push_back(a[i++]); } else { temp.push_back(a[j++]); } }

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

下面快速排序的划分函数以a[right]为枢轴，并把不大于枢轴的元素移动到左侧。横线处应填写（ ）。 1 int partition(int a[], int left, int right) { 2 int pivot = a[right]; 3 int i = left - 1; 4 for (int j = left; j < right; j++) { 5 if (__________________) { 6 i++; 7 swap(a[i], a[j]); 8 } 9 } 10 swap(a[i + 1], a[right]); 11 return i + 1; 12 }

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

小杨要在一个教室安排尽可能多场活动，每场活动具有开始时间start和结束时间end 。采用贪心算法时，正确的选择策略是（ ）。 struct Activity { int start; int end; };

• A.每次选择开始时间最早的活动
• B.每次选择持续时间最短的活动
• C.每次选择参与人数最少的活动
• D.按结束时间从早到晚排序，依次选择与已选活动不冲突的活动

下面函数使用迭代方法求最大连续子段和。对于数组{-2, 3, -1, 5, -6, 2} ，函数返回值是（ ）。 int maxSubArray(const vector<int> &a) { int best = a[0]; int current = a[0]; for (int i = 1; i < (int)a.size(); i++) { current = max(a[i], current + a[i]); best = max(best, current); } return best; }

• A.5
• B.6
• C.7
• D.8

数组a和b按低位在前的顺序保存两个非负大整数。下面代码实现高精度加法，横线处应填写（ ）。 1 vector<int> add(const vector<int> &a, const vector<int> &b) { 2 vector<int> c; 3 int carry = 0; 4 int n = max(a.size(), b.size()); 6 for (int i = 0; i < n; i++) { 7 int sum = carry; 8 if (i < a.size()) 9 sum += a[i]; 10 if (i < b.size()) 11 sum += b[i]; 12 c.push_back(sum % 10); 13 ____________________ 14 } 15 if (carry) 16 c.push_back(carry); 17 return c; 18 }

• A.carry = sum % 10;
• B.carry = sum;
• C.carry = sum / 10;
• D.carry = c[i] / 10;

下面代码在已知结点p的情况下，能够以O(1)的时间在单链表的p结点之后插入新结点s 。 s->next = p->next; p->next = s;

下面代码可以安全地删除单链表的头结点，并使head指向删除后的新头结点。 Node *p = head; delete p; head = p->next;

下面欧几里得算法既适用于a > b ，也适用于a < b ，只要a 、 b是正整数。 int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }

下面埃氏筛从i * i开始标记，是因为i * i之前的i的合数倍数已经被更小的质因子标记过。 for (int i = 2; (long long)i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } }

下面程序的时间复杂度为O(m)。。 for (int i = 1; i <= n; i *= 2) { cout << i << endl; }

若数组a已按升序排列，下面函数能够返回最后一个小于等于x的元素下标；如果不存在，则返回-1 。 1 int findLastLE(const vector<int> &a, int x) { 2 int l = 0, r = (int)a.size() - 1; 3 int ans = -1; 4 while (l <= r) { 5 int mid = l + (r - l) / 2; 6 if (a[mid] <= x) { 7 ans = mid; 8 l = mid + 1; 9 } else { 10 r = mid - 1; 11 } 12 } 13 return ans; 14 }

快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为O(nlogn).o。

归并排序的递推式为为= 2T(n/2) + ，对应的时间复杂度为。

下面的贪心代码一定能对任意硬币面值集合coins求出money所需的最少硬币数。 int count = 0; for (int coin : coins) { // coins 按面值从大到小排列 count += money / coin; money %= coin; }

假设两个非负高精度整数分别存储在数组a和b中，且。数组采用低位在前的方式存储，即a[0]表示个位。下面代码中的c可以正确保存a - b的各位数字。 1 int borrow = 0; 2 for (int i = 0; i < len; ++i) { 3 int t = a[i] - b[i] + borrow; 4 if (t < 0) { 5 t += 10; 6 borrow = 1; 7 } else { 8 borrow = 0; 9 } 10 c[i] = t; 11 }

试题名称：哥德巴赫猜想 时间限制：1.0 s　内存限制：512.0 MB 题目描述：众所周知，哥德巴赫猜想是说，任何大于 2 的偶数都能写成两个质数（素数）之和。例如：4 = 2 + 2，6 = 3 + 3，8 = 3 + 5。聪明的你肯定想知道，对于大于 2 的偶数，它有多少种写成两个质数之和的方法。例如，4 和 8 都只有一种方法，10 有两种方法，12 有两种方法。请你编写程序计算这个问题的答案。在本题中，我们认为两种方案不同，当且仅当两种分解方案包含的素数互不相同；即 10 = 3 + 7 和 10 = 7 + 3 是同一种方案，不能重复计数。 输入格式：一行，一个大于 2 的偶数 n。 输出格式：一行，一个整数，表示将 n 写成两个质数之和的方法数。 输入样例1：4 输出样例1：1 输入样例2：10 输出样例2：2 数据范围：对于 40% 的测试点，保证 4 ≤ n ≤ 100。对于所有测试点，保证 4 ≤ n ≤ 10^6。

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

试题名称：饮品调制 时间限制：1.0 s　内存限制：512.0 MB 题目描述：你想调制一份甜度恰到好处的饮品，给你的朋友们品尝。有 n 种原料可供用于调制饮品，第 i 种原料存量有 v_i 升，每升含有 s_i 克糖分。你可以自由选择原料加入饮品，但每种原料的使用量不得超过其剩余存量。也就是说，假设第 i 种原料选用 k_i 升，应当有 0 ≤ k_i ≤ v_i，k_i 可以取 0 到 v_i 之间的任何数字（包括小数）。一份甜度恰到好处的饮品需要保证甜度为 t。最终你调制得到的饮品甜度将为所有加入原料的糖分质量之和除以加入原料的总体积。为了让更多的朋友喝到饮品，请问最多能调制出多少升甜度恰到好处的饮品？如果无法调制出甜度恰到好处的饮品，则认为答案是 0。 输入格式：第一行，两个整数 n, t，分别表示原料种类数量、恰到好处的甜度。接下来 n 行，每行两个整数 v_i, s_i，分别表示第 i 种原料的存量体积、每升含有的糖分质量。 输出格式：一行，一个小数，表示能调制出的甜度恰到好处的饮品最大体积，保留三位小数。 输入样例1：4 2 6 1 5 2 8 5 1 0 输出样例1：14.667 输入样例2：2 5 3 4 5 3 输出样例2：0.000 数据范围：对于 40% 的测试点，保证 n = 2。对于所有测试点，保证 1 ≤ n ≤ 2000，0 ≤ t ≤ 200，1 ≤ v_i ≤ 1000，0 ≤ s_i ≤ 200。

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