2026 GESP C++ 五级真题解析|两道编程题详解
- 2026-11-05 13:42:18
这篇整理的是 2026 年 GESP C++ 五级 的真题。题型和往年一样：15 道单选题、10 道判断题，再加 2 道编程题。
两道编程题的难度一低一高：
- 第 1 题「哥德巴赫猜想」
（普及-）：考质数和埃氏筛，先把质数表筛出来，再做枚举； - 第 2 题「饮品调制」
（普及/提高-）：考贪心、排序和数学推导，思考量明显更大。
每道题都整理了题面，写了解题思路，并给出实测通过的 C++ 代码。建议先自己想一想，再对照解析看。看懂以后关掉文章，自己从头写一遍，这样才算真正掌握。
题目描述
时间限制：1.0 s 内存限制：512.0 MB
众所周知，哥德巴赫猜想是说，任何大于 2 的偶数都能写成两个质数（素数）之和。例如：
4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 10 = 3 + 7 = 5 + 5
聪明的你肯定想知道，对于大于 2 的偶数 n，它有多少种写成两个质数之和的方法。例如 4、6 和 8 都只有一种方法，10 有两种方法。请你编写程序计算这个问题的答案。
在本题中，我们认为两种方案不同，当且仅当两种分解方案包含的素数互不相同；即 10 = 3 + 7 和 10 = 7 + 3 是同一种方案，不能重复计数。
输入格式
一行，一个大于 2 的偶数 n。
输出格式
一行，一个整数，表示将 n 写成两个质数之和的方法数。
样例1 输入
4样例1 输出
1样例2 输入
10样例2 输出
2数据范围
对于 40% 的测试点，保证 4 ≤ n ≤ 100。
对于所有测试点，保证 4 ≤ n ≤ 106。
💡 一句话点题：先筛出质数表，再只枚举较小的那个质数 p ≤ n/2
题意抓重点
给一个偶数 n（4 ≤ n ≤ 106），问能把它写成“质数 + 质数”的方法有几种。3 + 7 和 7 + 3 只算一种，但 5 + 5 这种两个数一样的也算一种。
第一步：把问题变成“枚举”
只要定下其中一个加数 p，另一个就是 n − p，不用再找了。所以只需要枚举 p，看 p 和 n − p 是不是都是质数。
怎样才能不重复？3 + 7 和 7 + 3 是同一种，我们规定 p 当较小（或相等）的那个，也就是 p ≤ n − p，换个写法就是 p ≤ n ÷ 2。这样每种方案只会数一次，5 + 5 这样两个数相等的也刚好数一次。
最小的质数是 2，所以 p 从 2 枚举到 n ÷ 2 就行。
部分分做法：每次试除
判断一个数 x 是不是质数，最直接的办法是“试除”：用 2, 3, …, 一直到 √x 去除它，有一个能整除就不是质数。
n ≤ 100 时这样做完全没问题。可 n 到 106 时，要枚举大约 5 × 105 个 p，每次试除最多要做将近 1000 次，加起来是好几亿次运算，1 秒内比较危险。
正解：先用筛法打一张质数表
我们要反复问“某个数是不是质数”，而这些数都不超过 n。那不如先一次性算出 1 到 n 里每个数是不是质数，存进数组 isPrime[ ]，之后每次只要查表，一步就能得到答案。
打表用的是埃氏筛（埃拉托斯特尼筛法，一种成批找出质数的方法）：
先假设 2 到 n 全都是质数； 从小到大看每个数 i，如果 i 还是质数，就把它的倍数 i×i, i×i+i, i×i+2i, … 全部标成“不是质数”； 做完以后，还标着质数的就都是真的质数。
为什么从 i×i 开始划？因为比 i×i 小的 i 的倍数（比如 2i、3i），在前面处理 2、3 的时候已经划掉了。i 也只需要枚举到 i×i ≤ n 为止。
埃氏筛的运行时间大约是 n × log log n，n = 106 时只要几百万次运算，非常快。
合起来
读入 n，用埃氏筛求出 isPrime[0..n]； p 从 2 枚举到 n ÷ 2，只要 isPrime[p] 和 isPrime[n − p] 都为真，答案就加 1； 输出答案。
拿样例 n = 10 检验一下：p 取 2, 3, 4, 5。p = 2 时 8 不是质数；p = 3 时 7 是质数，算 1 种；p = 4 不是质数；p = 5 时 5 是质数，算 1 种。一共 2 种，和样例一样。
怎么想到的？
两个数的和固定了，定下一个，另一个就跟着定了，所以只要单层枚举； “不能重复计数”就规定大小顺序，这是处理无序对的常用办法； 要很多次判断质数，就先预处理成表，这是筛法最常见的用处。
复杂度：时间 O(n log log n)，空间 O(n)
枚举范围必须是 p ≤ n / 2，枚举到 n 的话每种方案会数两遍（只有 p = n − p 那种不会），结果就错了。 不能写成 p < n / 2，否则 5 + 5、2 + 2 这类两个数相等的方案会漏掉（样例 1 里 4 = 2 + 2 就会变成输出 0）。 0 和 1 不是质数，筛之前要手动标成 false；数组要开到 106 + 1 以上。 埃氏筛里写 i * i ≤ n 时，n 只有 106 不会溢出 int；如果以后范围更大，记得改用 long long。
#include<iostream>usingnamespace std;constint MAXN =1000005;bool isPrime[MAXN]; // isPrime[x] 为 true 表示 x 是质数intmain() {int n; cin >> n;// 第一步：埃氏筛，求出 0 到 n 中每个数是不是质数for (int i =2; i <= n; i++) { isPrime[i] =true; // 先假设都是质数 } isPrime[0] =false; isPrime[1] =false; // 0 和 1 不是质数for (int i =2; i * i <= n; i++) {if (isPrime[i]) {// 把 i 的倍数都划掉，从 i*i 开始即可for (int j = i * i; j <= n; j += i) { isPrime[j] =false; } } }// 第二步：枚举较小的那个加数 p（p <= n - p，即 p <= n / 2）int count =0;for (int p =2; p <= n /2; p++) {if (isPrime[p] && isPrime[n - p]) { count++; // p 和 n-p 都是质数，算一种方案 } } cout << count << endl;return0;}题目描述
时间限制：1.0 s 内存限制：512.0 MB
你想调制一份甜度恰到好处的饮品给你的朋友们品尝。
有 n 种原料可供用于调制饮品。第 i 种原料存量有 vi 升，每升含有 si 克糖分。你可以自由选择原料加入饮品，但每种原料的使用量不得超过其剩余存量。也就是说，假设第 i 种原料选用 ki 升，应当有 0 ≤ ki ≤ vi，ki 可以取 0 到 vi 之间的任何数字（包括小数）。
一份甜度恰到好处的饮品需要保证甜度恰好为 t。最终你调制得到的饮品甜度将为 (∑i=1n ki·si) ÷ (∑i=1n ki)。为了让更多的朋友喝到饮品，请问最多能调制出多少升甜度恰到好处的饮品？如果无法调制出甜度恰到好处的饮品，则认为答案是 0。
输入格式
第一行，两个整数 n, t，分别表示原料种类数量，恰到好处的甜度。
接下来 n 行，每行两个整数 vi, si，分别表示第 i 种原料的存量体积，每升含有的糖分质量。
输出格式
一行，一个小数，表示能调制出的甜度恰到好处的饮品最大体积，保留三位小数。
样例1 输入
4 26 15 28 51 0样例1 输出
14.667样例2 输入
2 53 45 3样例2 输出
0.000数据范围
对于 40% 的测试点，保证 n = 2。
对于所有测试点，保证 1 ≤ n ≤ 2000，0 ≤ t ≤ 200，1 ≤ vi ≤ 100，0 ≤ si ≤ 200。
💡 一句话点题：每种原料减去 t 后分成正负两边，用量较小的一边全部用上，另一边按“偏差小优先”贪心
题意抓重点
有 n 种原料，每种最多用 vi 升（可以用小数升），含糖浓度为 si。要求混合后的平均甜度恰好等于 t，问最多能调出多少升。
第一步：把“平均数等于 t”变成“总和等于 0”
甜度 = (∑ki·si) ÷ (∑ki) = t，两边同乘 ∑ki，再移项：
∑ki·(si − t) = 0
记 di = si − t，叫它“偏差”。这样题目就变成：每升原料 i 带来 di 的偏差，要让总偏差刚好为 0，同时总体积最大。
原料自然分成三类：
- di = 0
（正好是甜度 t）：加多少都不影响平衡，直接全部用上。 - di > 0
（太甜）：会让偏差变大。 - di < 0
（太淡）：会让偏差变小。
太甜的和太淡的必须互相抵消。
第二步：哪一边能全部用完？
算出两边的“偏差总量”：
P = 所有太甜原料的 vi × di 之和； N = 所有太淡原料的 vi × |di| 之和。
结论：总量小的那一边一定可以全部用上。 为什么？假设最优方案里两边都各有一种原料没用完，那就可以两边各再多加一点点、保持抵消，总体积变大了，和“最优”矛盾。所以至少有一边被用完。如果用完的是总量大的那一边，总量小的另一边全加进来也抵消不掉，不可能平衡。所以用完的一定是总量小的那边（两边相等时都能用完）。
比如 N ≤ P 时：太淡的原料全部用上，提供了 N 的“抵消额度”；接下来要从太甜的原料里挑，凑出刚好 N 的正偏差，并且让体积尽量大。
第三步：在大的那一边贪心
现在相当于手里有 N 的“预算”，原料 i 每用 1 升要花掉 |di| 的预算，最多用 vi 升，问最多能买多少升。
很自然：每升越便宜（|di| 越小）越划算，优先用它。 因为可以用小数升，这就是一道“部分背包”：
把这一边的原料按 |di| 从小到大排序； 依次处理：预算够就整瓶用掉（预算减少 vi×|di|）；不够就用 预算 ÷ |di| 升，然后结束。
答案 = 偏差为 0 的体积 + 小的一边全部体积 + 大的一边贪心得到的体积。
验证样例 1
t = 2，偏差分别是 −1（6 升）、0（5 升）、3（8 升）、−2（1 升）。 P = 8×3 = 24，N = 6×1 + 1×2 = 8，N 更小，太淡的全用上：7 升。 太甜一边预算 8，只有偏差 3 的原料，能用 8 ÷ 3 ≈ 2.667 升。 总计 5 + 7 + 2.667 = 14.667 ✔。
样例 2 中两种原料都太淡，没有太甜的可以抵消，P = 0，所以一点都加不了，答案 0。
关于部分分
n = 2 时可以直接分情况：两种一甜一淡就让 k1·d1 = k2·|d2|，一边取满算另一边；有偏差为 0 的单独加上。其实这就是正解的特例，想清楚“抵消”的思路后，推广到 n 种只多了一步排序贪心。
复杂度：时间 O(n log n)（排序），空间 O(n)
别忘了偏差为 0 的原料：它们不影响平衡，要全部加进答案。 如果某一边根本没有原料（比如全都太淡），另一边一点都不能用，答案只剩偏差为 0 的部分；这种情况贪心里预算为 0，会自动处理好。 贪心时要按 |di| 从小到大排，偏差小的原料“性价比”高；排反了会得到偏小的答案。 输出保留三位小数，用 printf("%.3f\n", ans)；偏差总量最多 2000×100×200 = 4×107，用 long long 或 double 都不会溢出。
#include<bits/stdc++.h>usingnamespace std;// 一种原料：体积 volume，偏差的绝对值 diffstruct Item {int volume;int diff;};boolcmpByDiff(const Item &a, const Item &b) {return a.diff < b.diff; // 偏差小的排在前面，更划算}// 用 budget 的“抵消额度”在 items 里贪心，返回最多能用多少升doublegreedyTake(vector<Item>&items, longlong budget) { sort(items.begin(), items.end(), cmpByDiff);double taken =0;for (size_t i =0; i < items.size(); i++) {longlong cost = (longlong)items[i].volume * items[i].diff; // 整瓶用完要花的额度if (cost <= budget) { budget -= cost; taken += items[i].volume; } else { taken += (double)budget / items[i].diff; // 只用一部分break; } }return taken;}intmain() {// freopen("drink.in", "r", stdin);// freopen("drink.out", "w", stdout);int n, t; scanf("%d %d", &n, &t); vector<Item> sweetList, plainList; // 太甜的、太淡的longlong sweetTotal =0, plainTotal =0; // 两边的偏差总量longlong sweetVolume =0, plainVolume =0; // 两边的总体积double answer =0;for (int i =0; i < n; i++) {int v, s; scanf("%d %d", &v, &s);int d = s - t;if (d ==0) { answer += v; // 甜度正好，全部用上 } elseif (d >0) { sweetList.push_back({v, d}); sweetTotal += (longlong)v * d; sweetVolume += v; } else { plainList.push_back({v, -d}); plainTotal += (longlong)v * (-d); plainVolume += v; } }if (plainTotal <= sweetTotal) {// 太淡的一边全部用上，太甜的一边贪心凑出 plainTotal answer += plainVolume; answer += greedyTake(sweetList, plainTotal); } else {// 太甜的一边全部用上，太淡的一边贪心凑出 sweetTotal answer += sweetVolume; answer += greedyTake(plainList, sweetTotal); } printf("%.3f\n", answer);return0;}第1题
题目描述
小杨用单链表保存任务序列，并同时维护头指针 head 和尾指针 tail。在链表非空且已知 tail 的情况下，在表尾插入新结点的时间复杂度是（ ）。
struct Node {int value; Node *next;};Node *head;Node *tail;A. O(1) B. O(log n) C. O(n) D. O(n log n)
答案：A
已经知道尾指针 tail，只需执行 tail->next = s; tail = s;，不用从头遍历链表。操作次数和链表长度无关，所以时间复杂度是 O(1)。
第2题
题目描述
在不带哨兵结点的双向链表中，结点 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;
答案：C
删除 p 时，要让前驱结点的 next 指向 p 的后继，再让后继结点的 prev 指向 p 的前驱，最后释放 p。只有 C 正确改写了两个相邻结点的指针。A 和 D 只改了 p 自己的指针。B 让链表仍然指向 p，delete 之后会出现悬空指针。
第3题
题目描述
下面函数使用快慢指针查找单链表的中间结点。横线处应填写（ ）。
struct Node {int value; Node *next;};Node *middle(Node *head) { Node *slow = head; Node *fast = head;while (fast !=nullptr&& fast->next !=nullptr) { slow = slow->next; ______________________ }return slow;}A. fast = fast->next; B. fast = fast->next->next; C. fast = slow->next; D. fast = head->next;
答案：B
快慢指针法的规则是：慢指针每次走 1 步，快指针每次走 2 步。快指针走到表尾时，慢指针正好在中间。循环条件已经保证 fast->next 不为空，所以写 fast = fast->next->next; 是安全的。
第4题
题目描述
函数 gcd(int a, int b) 定义如下，则 gcd(105, 45) 的结果是（ ）。
intgcd(int a, int b) {return b ==0? a : gcd(b, a % b);}A. 3 B. 5 C. 15 D. 45
答案：C
计算过程：gcd(105, 45) → 105 % 45 = 15 → gcd(45, 15) → 45 % 15 = 0 → gcd(15, 0) = 15。105 = 3 × 5 × 7，45 = 32 × 5，两者的最大公约数也是 15。
第5题
题目描述
下面函数用于判断正整数 n 是否为质数。横线处的最佳写法是（ ）。
boolisPrime(int n) {if (n <2)returnfalse;for (int i =2; __________________; i++) {if (n % i ==0)returnfalse; }returntrue;}A. i < n B. i <= n / 2 C. i * i < n D. (long long) i * i <= n
答案：D
如果 n 是合数，它一定有一个因子 ≤ √n，所以只需枚举到 i × i ≤ n，时间复杂度为 O(√n)。写成 (long long) i * i 可以防止乘法溢出。C 少了等号，会把 9、25 这类质数的平方误判为质数。A、B 结果正确，但效率较低。
第6题
题目描述
下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次，横线处应填写（ ）。
vector<int> linearSieve(int n) { vector<bool> composite(n +1, false); vector<int> primes;for (int i =2; i <= n; i++) {if (!composite[i]) primes.push_back(i);for (int p : primes) {if ((longlong)i * p > n)break; composite[i * p] =true;if (__________________)break; } }return primes;}A. p % i == 0 B. i % p == 0 C. i == p D. i * p == n
答案：B
当 i % p == 0 时，p 就是 i 的最小质因子。如果继续用更大的质数 p' 去筛 i × p'，这个数的最小质因子其实是 p 而不是 p'，就会出现重复筛。所以此时必须 break，才能保证每个合数只被它的最小质因子筛掉一次，整体复杂度为 O(n)。
第7题
题目描述
根据唯一分解定理，整数 756 的正确质因数分解是（ ）。
A. 22 × 33 × 7 B. 23 × 32 × 7 C. 22 × 32 × 21 D. 2 × 33 × 14
答案：A
756 = 4 × 189 = 4 × 27 × 7 = 22 × 33 × 7。B 的值是 8 × 9 × 7 = 504，不等于 756。C 和 D 里出现了 21、14，它们不是质数，所以不是质因数分解。
第8题
题目描述
函数 f(int n) 定义如下，则 f(4) 的结果是（ ）。
intf(int n) {if (n ==1)return1;return n + f(n -1);}A. 4 B. 7 C. 9 D. 10
答案：D
f(n) 计算的是 1 + 2 + … + n。f(4) = 4 + f(3) = 4 + 3 + f(2) = 4 + 3 + 2 + f(1) = 4 + 3 + 2 + 1 = 10。
第9题
题目描述
在升序数组中查找第一个严格大于 x 的元素位置，下面代码中的横线应填写（ ）。
intupperBound(const vector<int>&a, int x) {int l =0, r = (int)a.size();while (l < r) {int mid = l + (r - l) /2;if (__________________) { l = mid +1; } else { r = mid; } }return l;}A. a[mid] < x B. a[mid] >= x C. a[mid] <= x D. a[mid] > x
答案：C
要找第一个严格大于 x 的位置。所以当 a[mid] ≤ x 时，mid 和它左边都不可能是答案，令 l = mid + 1；否则 a[mid] 可能就是答案，令 r = mid。如果填 A（a[mid] < x），得到的是第一个大于等于 x 的位置，也就是 lower_bound。
第10题
题目描述
小杨需要把若干箱货物按原顺序分配到 days 天中，每天运输连续的若干箱，求能够完成任务的最小载重量。函数 check(cap) 判断载重量为 cap 时能否在规定天数内运完。横线处应填写（ ）。
longlong l = maxWeight;longlong r = totalWeight;while (l < r) {longlong mid = l + (r - l) /2;if (check(mid)) { ____________________ } else { ____________________ }}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;
答案：B
这是“二分答案”求最小可行值。check(mid) 为真，说明载重 mid 可以完成，答案 ≤ mid，所以令 r = mid，保留 mid。否则说明 mid 不够，答案 ≥ mid + 1，所以令 l = mid + 1。循环结束时 l 就是最小可行载重。
第11题
题目描述
下面是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写（ ）。
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]
答案：D
稳定排序要求相等的元素保持原来的先后顺序。a[i] 来自左半段，原本排在前面。所以相等时应优先放 a[i]，条件写成 a[i] <= a[j]。如果写成 a[i] < a[j]，相等时会先放右半段的元素，排序就不稳定了。
第12题
题目描述
下面快速排序的划分函数以 a[right] 为枢轴，并把不大于枢轴的元素移动到左侧。横线处应填写（ ）。
intpartition(int a[], int left, int right) {int pivot = a[right];int i = left -1;for (int j = left; j < right; j++) {if (__________________) { i++; swap(a[i], a[j]); } } swap(a[i +1], a[right]);return i +1;}A. a[j] <= pivot B. a[j] > pivot C. a[i] <= pivot D. a[right] < a[j]
答案：A
这是 Lomuto 划分法。i 指向“不大于枢轴区域”的最后一个位置。遍历到 a[j] ≤ pivot 时，把它交换到这个区域的末尾。最后把枢轴放到 i + 1 的位置，左边都 ≤ pivot，右边都 > pivot。
第13题
题目描述
小杨要在一个教室安排尽可能多场活动，每场活动具有开始时间 start 和结束时间 end。采用贪心算法时，正确的选择策略是（ ）。
struct Activity {int start;int end;};A. 每次选择开始时间最早的活动 B. 每次选择持续时间最短的活动 C. 每次选择参与人数最少的活动 D. 按结束时间从早到晚排序，依次选择与已选活动不冲突的活动
答案：D
这是经典的活动选择问题。按结束时间从早到晚选，可以给后面的活动留出最多的剩余时间，用交换论证可以证明这样选是最优的。A、B 都能举出反例，C 和时间安排无关。
第14题
题目描述
下面函数使用迭代方法求最大连续子段和。对于数组 {-2, 3, -1, 5, -6, 2}，函数返回值是（ ）。
intmaxSubArray(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
答案：C
逐步计算 current 和 best：初始都为 -2；a[1] = 3 时 current = 3，best = 3；a[2] = -1 时 current = 2；a[3] = 5 时 current = 7，best = 7；a[4] = -6 时 current = 1；a[5] = 2 时 current = 3。最大子段是 {3, -1, 5}，和为 7。
第15题
题目描述
数组 a 和 b 按低位在前的顺序保存两个非负大整数。下面代码实现高精度加法，横线处应填写（ ）。
vector<int> add(const vector<int>&a, const vector<int>&b) { vector<int> c;int carry =0;int n = max(a.size(), b.size());for (int i =0; i < n; i++) {int sum = carry;if (i < a.size()) sum += a[i];if (i < b.size()) sum += b[i]; c.push_back(sum %10); ____________________ }if (carry) c.push_back(carry);return c;}A. carry = sum % 10; B. carry = sum; C. carry = sum / 10; D. carry = c[i] / 10;
答案：C
当前位保留 sum % 10，进位为 sum / 10。两个一位数加上进位最大是 9 + 9 + 1 = 19，进位只可能是 0 或 1。A 把个位数当成了进位，B 没有除以 10，D 中 c[i] 已经是个位数，除以 10 后恒为 0。
第16题
题目描述
下面代码在已知结点 p 的情况下，能够以 O(1) 的时间在单链表的 p 结点之后插入新结点 s。
s->next = p->next;p->next = s;答案：正确
先让 s 指向 p 原来的后继，再让 p 指向 s，就完成了插入，不需要遍历，时间复杂度为 O(1)。注意这两句顺序不能交换，否则会丢失 p 原来的后继。
第17题
题目描述
下面代码可以安全地删除单链表的头结点，并使 head 指向删除后的新头结点。
Node *p = head;delete p;head = p->next;答案：错误
执行 delete p 之后，p 指向的内存已经释放，再读取 p->next 是未定义行为，不安全。正确写法是先执行 head = head->next;，再 delete p;。
第18题
题目描述
下面欧几里得算法既适用于 a > b，也适用于 a < b，只要 a、b 是正整数。
intgcd(int a, int b) {while (b !=0) {int r = a % b; a = b; b = r; }return a;}答案：正确
如果 a < b，第一轮 r = a % b = a，然后 a = b，b = r，相当于自动交换了 a 和 b。之后就和 a > b 的情况一样，所以对任意正整数都能求出正确的最大公约数。
第19题
题目描述
下面埃氏筛从 i * i 开始标记，是因为 i * i 之前的 i 的合数倍数已经被更小的质因子标记过。
for (int i =2; (longlong)i * i <= n; i++) {if (isPrime[i]) {for (int j = i * i; j <= n; j += i) { isPrime[j] =false; } }}答案：正确
比 i × i 小的 i 的倍数可以写成 i × k，其中 2 ≤ k < i。k 一定有比 i 小的质因子，所以 i × k 在之前处理那个更小的质数时已经被标记了。因此从 i × i 开始标记就够了，不会漏掉。
第20题
题目描述
下面程序的时间复杂度为 O(n)。
for (int i =1; i <= n; i *=2) { cout << i << endl;}答案：错误
i 每次乘 2，循环执行的次数约为 log2 n + 1，所以时间复杂度是 O(log n)，不是 O(n)。
第21题
题目描述
若数组 a 已按升序排列，下面函数能够返回最后一个小于等于 x 的元素下标；如果不存在，则返回 -1。
intfindLastLE(const vector<int>&a, int x) {int l =0, r = (int)a.size() -1;int ans =-1;while (l <= r) {int mid = l + (r - l) /2;if (a[mid] <= x) { ans = mid; l = mid +1; } else { r = mid -1; } }return ans;}答案：正确
每次遇到 a[mid] ≤ x，就把 mid 记为候选答案，然后到右半边继续找更靠后的位置；否则到左半边找。循环结束时，ans 就是最后一个 ≤ x 的下标。如果所有元素都大于 x，ans 保持 -1。
第22题
题目描述
快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为 O(n log n)。
答案：错误
数组已经升序时，用第一个元素作枢轴，每次划分都会极度不平衡：一边是空的，另一边有 n - 1 个元素。递归深度变成 n，总时间复杂度退化为 O(n2)。
第23题
题目描述
归并排序的递推式为 T(n) = 2T(n/2) + O(n)，对应的时间复杂度为 O(n log n)。
答案：正确
归并排序每层的合并总共花费 O(n)，一共有 log n 层。根据主定理或递归树分析，T(n) = 2T(n/2) + O(n) 的解是 O(n log n)。
第24题
题目描述
下面的贪心代码一定能对任意硬币面值集合 coins 求出 money 所需的最少硬币数。
int count =0;for (int coin : coins) { // coins 按面值从大到小排列 count += money / coin; money %= coin;}答案：错误
贪心找零只对部分面值体系成立，例如 1、5、10、20。反例：面值为 {4, 3, 1}，凑 money = 6 时，贪心选 4 + 1 + 1，共 3 枚；最优解是 3 + 3，只要 2 枚。所以“对任意面值都能求出最少硬币数”是错的。
第25题
题目描述
假设两个非负高精度整数分别存储在数组 a 和 b 中，且 a ≥ b。数组采用低位在前的方式存储，即 a[0] 表示个位。下面代码中的 c 可以正确保存 a - b 的各位数字。
int borrow =0;for (int i =0; i < len; ++i) {int t = a[i] - b[i] + borrow;if (t <0) { t +=10; borrow =1; } else { borrow =0; } c[i] = t;}答案：错误
借位应该从当前位减去，正确写法是 t = a[i] - b[i] - borrow。代码里写成了 + borrow，结果会出错。例如 10 - 1：个位 0 - 1 = -1，加 10 得 9，借位记为 1；十位应为 1 - 0 - 1 = 0，代码却算成 1 - 0 + 1 = 2，结果变成 29。
备考建议： 五级的重点是数论基础（质数、筛法）和贪心思想。平时要多做两件事：一是手写埃氏筛，二是用小数据验证贪心策略是否正确。选择题和判断题常考细节，做错的题要回到知识点重新弄清楚，不要只记住答案。
你在哪道题上卡住了？有没有更简洁的写法？欢迎在评论区留言交流。关注「智盛少儿编程」，后续还会继续更新 GESP 各级别的真题解析。
