2026年9月 GESP C++ 五级 真题答案 + 解析

已知尾指针 tail 时,尾插只需 tail->next = s; tail = s; 两步,与链表长度无关,时间复杂度 O(1)。选 A。(若没有 tail 就得从头遍历,才是 O(n)。)

双向链表删中间结点要"接上前后":p->prev->next = p->next; 再 p->next->prev = p->prev;,最后 delete p。选 C。

快慢指针找中点:slow 每次走 1 步,fast 每次走 2 步,即 fast = fast->next->next。循环条件已保证 fast 和 fast->next 非空。选 B。

辗转相除:gcd(105,45) → 105%45=15 → gcd(45,15) → 45%15=0 → 返回 15。选 C。

判质数只需试到 √n,即 i*i <= n;并且 i*i 可能超 int,要用 (long long)i*i <= n 防溢出。C 用 i*i < n 会漏掉 i*i==n 的完全平方情形。选 D。

线性筛保证每个合数只被最小质因子筛一次:当 i % p == 0 时 p 就是 i 的最小质因子,再往后的更大质数会重复筛,故此时 break。选 B。

递归求和:f(4)=4+f(3)=4+3+f(2)=4+3+2+f(1)=4+3+2+1=10。选 D。

找"第一个严格大于 x"的位置(upper_bound):当 a[mid] <= x 时答案在右边,l=mid+1;否则 r=mid。故横线填 a[mid] <= x。选 C。

二分答案求"最小可行载重":check(mid) 成立说明 mid 够用,尝试更小 r=mid;不够则 l=mid+1。选 B。

归并排序要稳定,当两侧元素相等时应优先取左半(下标小的在前),即条件 a[i] <= a[j] 时取左。选 D。

快排划分以 a[right] 为枢轴,把"不大于枢轴"的元素换到左侧:当 a[j] <= pivot 时 i++ 并交换。选 A。

活动选择的经典贪心:按结束时间从早到晚排序,依次选与已选不冲突的活动,才能排最多场。"开始最早/时间最短"都会得到次优解。选 D。

Kadane 算法。对 {-2,3,-1,5,-6,2}:current/best 依次为 3、2、7、1、3,best 最大为 7(即子段 3,-1,5)。选 C。

高精度加法每位:sum = 进位 + a[i] + b[i],本位存 sum%10,新进位是 sum/10。故横线填 carry = sum / 10。选 C。

在已知结点 p 后插入 s:先 s->next = p->next; 再 p->next = s;,只改两个指针,时间 O(1)。顺序也正确(先接后断)。命题正确。

代码先 delete p 再访问 p->next,这是释放后使用(悬空指针),行为未定义。正确做法是先 head = p->next; 再 delete p;。命题错误。

欧几里得算法对 a < b 同样成立:第一轮 r = a%b = a(因 a<b),随后 a=b, b=a 相当于自动交换,后续正常。命题正确。

埃氏筛从 i*i 开始标记:因为 i*2, i*3, …, i*(i-1) 这些较小的倍数,已经被它们更小的质因子(2,3,…)筛过了,无需重复。命题正确。

for(i=1; i<=n; i*=2) 中 i 每次翻倍,循环约执行 log₂n 次,时间复杂度是 O(log n),与命题所给不符。命题错误。

二分查找"最后一个 ≤ x":命中 a[mid] <= x 时记录 ans=mid 并继续向右找更大的;找不到则保持初值 -1。逻辑正确。命题正确。

快排若固定取第一个元素为枢轴,遇到已升序的输入,每次划分都极不平衡(一侧为空),退化为 O(n²),并非理想的 O(n log n)。命题所述复杂度错误。

"每次取最大面值"的贪心不能对任意币值集合求最少硬币数。反例:币值 {1,3,4} 凑 6,贪心得 4+1+1=3 枚,最优是 3+3=2 枚。命题错误。

高精度减法里借位方向写反了:借位时设 borrow=1,下一位却用 a[i]-b[i]+borrow(相当于多加 1)。借出的 1 应从高位减去,正确应是 a[i]-b[i]-borrow(或令 borrow=-1)。命题错误。