GESP C++ 5级考试复习资料, 历年真题考点解析.(详细版)
- 2026-11-08 12:45:44
五级只会背模板？
数论到链表一条线
11 套真题讲透
数论 · 复杂度 · 链表 · 二分 · 递归 · 分治 · 贪心 · 高精度
DOMIAI · GESP 复习
📦 5 Parts
👉 左右滑动
PART 01
大纲总览
8 大块
PART 02
知识点
数论到高精度
PART 03
真题分析
11 套
PART ///
写在最后
冲刺计划
适用考试：CCF 编程能力等级认证（GESP）C++ 五级
考试时间：120分钟 | 满分：100分
题型：单选题15题（30分）+ 判断题10题（20分）+ 编程题2题（50分）
资料基于 官方五级大纲 和 2023年9月～2026年6月共11套真题 整理
链表和数论，是五级拉开分差的关键
01
PART
考试大纲总览
OUTLINE · 大纲
一、考核目标
掌握初等数论知识点，能够使用辗转相除法（欧几里得算法）、素数表的埃氏筛法和线性筛法、唯一分解定理等相关知识解决相应的问题。掌握单链表、双链表、循环链表的基本操作方法。掌握算法复杂度估算方法（含多项式、对数），熟悉二分法、分治法、贪心算法和递归算法的算法思想，能够根据实际情况选择合适的算法并完成解决相应的问题。C++掌握使用数组模拟高精度加法、减法、乘法和除法的知识。
五级比四级多了什么？
初等数论——素数、合数、最大公约数、唯一分解定理，数学基础
算法复杂度分析——学会分析程序快慢，O(n)、O(n²)、O(log n) 等
链表——动态数据结构，单链表、双链表、循环链表
二分算法——二分查找、二分答案，高效搜索和求解
递归算法——函数调用自身，理解递归思想和栈结构
分治算法——归并排序、快速排序，大事化小
贪心算法——每一步选当前最优，但不一定全局最优
C++高精度运算——用数组模拟超大整数的加减乘除
二、考试内容——8大知识块
根据官方大纲，C++五级考试共考核 8个知识块：
①
知识块：初等数论
核心知识点：素数/合数、最大公约数/最小公倍数、唯一分解定理、质因数分解、欧几里得算法、埃氏筛法、线性筛法
难度：★★★★
考试占比：约20%
②
知识块：算法复杂度
核心知识点：多项式时间复杂度、对数时间复杂度、空间复杂度估算
难度：★★★
考试占比：约10%
③
知识块：链表
核心知识点：单链表/双链表/循环链表的创建、插入、删除、遍历、反转
难度：★★★★
考试占比：约15%
④
知识块：二分算法
核心知识点：二分查找、二分答案（二分枚举法）
难度：★★★
考试占比：约10%
⑤
知识块：递归算法
核心知识点：递归原理、递归时间复杂度、递归优化策略
难度：★★★
考试占比：约10%
⑥
知识块：分治算法
核心知识点：归并排序、快速排序
难度：★★★★
考试占比：约15%
⑦
知识块：贪心算法
核心知识点：最优子结构、局部最优 vs 全局最优、区间调度等
难度：★★★
考试占比：约10%
⑧
知识块：C++高精度运算
核心知识点：用数组模拟加法、减法、乘法、除法
难度：★★★
考试占比：约10%
难度最高的知识点： 初等数论（综合性强）和链表（指针操作容易出错）
出现频率最高的知识点：链表、排序算法（归并/快排）、初等数论（几乎每套题都有）
02
PART
各知识点详解
KNOWLEDGE · 知识点
知识块①：初等数论
·1.1 素数与合数
素数（质数）：大于1的自然数中，除了1和它本身以外不再有其他因数。如：2, 3, 5, 7, 11...
合数：大于1的自然数中，除了1和它本身以外还有其他因数。如：4, 6, 8, 9, 10...
注意：1既不是素数也不是合数。
判断一个数是否为素数——枚举到√n：
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) // 注意：是 i*i <= n，不是 i*i < n
if (n % i == 0) return false;
return true;
}
（2024年3月第9题：循环条件应该是 i*i <= n 还是 i*i < n？答案是 <=）
为什么只需要检查到√n？ 如果n有大于√n的因子a，那么n/a一定小于√n，所以只需要检查到√n即可。
·1.2 最大公约数与最小公倍数
最大公约数： 两个或多个整数共有的约数中最大的那个。记为 gcd(a, b)。
最小公倍数： 两个或多个整数共有的倍数中最小的那个。记为 lcm(a, b)。
关系公式：gcd(a, b) × lcm(a, b) = a × b
·1.3 欧几里得算法（辗转相除法）——必考！
原理： gcd(a, b) = gcd(b, a % b)，直到余数为0。
递归实现：
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
（2025年6月判断第1题：a大于b还是小于b都适用，正确）
迭代实现：
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
（2024年6月第5题）
练习题： gcd(48, 18) 的调用序列？
解析： gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0) → 返回6（2026年3月第4题）
练习题： gcd(105, 45) 的调用序列？
解析： gcd(105,45) → gcd(45,15) → gcd(15,0) → 返回15（2026年6月第4题）
欧几里得算法的时间复杂度： O(log n)（2025年6月第6题）
·1.4 唯一分解定理（算术基本定理）
定义： 任何一个大于1的自然数，都可以唯一地分解成有限个质数的乘积，不考虑顺序。（2024年3月第1题、2025年6月第8题）
例如： 30 = 2 × 3 × 5，20 = 2² × 5
易错判断题： “任何一个大于1的整数都可以唯一地分解为素数之和。”（2024年9月判断第3题）
答案：×。是分解为素数乘积，不是和。
·1.5 质因数分解
例题： 将正整数N分解为质因数乘积（2023年9月编程题1）
for (long long p = 2; p * p <= N; p++) {
if (N % p != 0) continue;
int cnt = 0;
while (N % p == 0) { cnt++; N /= p; }
// 输出 p 和 cnt（指数）
}
if (N > 1) { /* 处理剩余的质因子 */ }
·1.6 埃氏筛法（Eratosthenes筛法）
原理： 从2开始，每找到一个素数，就把它的所有倍数标记为合数。
vector<int> eratosthenes_sieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (int j = i * i; j <= n; j += i) // 从 i*i 开始，不是 2*i
is_prime[j] = false;
}
}
for (int i = sqrt(n) + 1; i <= n; i++)
if (is_prime[i]) primes.push_back(i);
return primes;
}
（2024年9月第5题：从j=i*i开始，不是j=i）
为什么从i²开始？ 因为小于i²的i的倍数（如2i, 3i, ...）已经被更小的质因子筛过了。（2026年3月第6题）
时间复杂度： O(n log log n)
·1.7 线性筛法（欧拉筛）——效率更高！
原理： 每个合数只被它的最小质因子筛掉一次，保证O(n)时间复杂度。
vector<int> linear_sieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) primes.push_back(i);
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) break; // 关键：保证每个合数只被最小质因子筛掉
}
}
return primes;
}
（2024年6月第7题、第8题：线性筛时间复杂度O(n)）
线性筛 vs 埃氏筛：
埃氏筛：一个合数可能被多个质数重复标记，如6会被2和3各标记一次
线性筛：每个合数只被其最小质因子筛掉一次（2024年12月判断第2题）
线性筛时间复杂度O(n)，低于埃氏筛的O(n log log n)（2024年9月判断第2题）
知识块②：算法复杂度
·2.1 时间复杂度
时间复杂度衡量算法运行时间随输入规模增长的速度。
常见复杂度从快到慢：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
O(1)： 常数时间，如数组随机访问 arr[i]
O(log n)： 对数时间，如二分查找
O(n)： 线性时间，如遍历数组
O(n log n)： 如归并排序、快速排序平均情况
O(n²)： 如冒泡排序、选择排序
O(2ⁿ)： 指数时间，如朴素递归斐波那契
·2.2 常见代码的时间复杂度分析
斐波那契数列——递归 vs 迭代：
朴素递归fiboB()：O(2ⁿ)（大量重复计算）（2024年3月第6题）
循环迭代 fiboA()：O(n)（2023年12月第1题）
判断素数——枚举到n vs 枚举到√n：
枚举到n：O(n)（2023年9月第11题）
枚举到√n：O(√n)（效率更高）
快速幂算法： O(log n)（2024年9月第8题）
·2.3 空间复杂度
空间复杂度衡量算法运行所需额外内存空间。
O(1)：原地排序，如冒泡排序、选择排序
O(n)：需要额外数组，如归并排序
知识块③：链表——“动态的数据结构”
·3.1 什么是链表？
链表是由一系列结点组成的线性数据结构，每个结点包含数据域和指针域。结点之间通过指针连接，不需要连续的内存空间。（2024年6月判断第3题、2026年6月判断第1题）
数组 vs 链表：
（2024年9月第1题、2025年6月第1题）
·3.2 单链表
结构体定义：
struct Node {
int val;
Node* next;
};
在头部插入新节点（2026年6月第1题）：
newNode->next = head->next;
head->next = newNode;
删除指定节点（已知头结点，2025年12月第3题）：
// 单链表删除指定节点需要先找到前驱节点
SNode* prev = head;
while (prev->next != node) prev = prev->next;
prev->next = node->next;
delete node;
// 时间复杂度：O(n)
·3.3 双链表
结构体定义：
struct DNode {
int val;
DNode* prev;
DNode* next;
};
在头部插入（2024年6月第4题）：
p->prev = nullptr;
p->next = head;
if (head != nullptr) head->prev = p;
head = p;
删除中间节点（2026年6月第3题）：
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
// 时间复杂度：O(1) —— 已知节点指针情况下
（2025年12月第3题：双链表删除指定节点是O(1)，单链表是O(n)）
·3.4 循环链表
循环单链表遍历（2025年12月第1题）：
// 循环单链表的遍历——用 do-while
Node* p = head;
do {
cout << p->data << " ";
p = p->next;
} while (p != head); // 注意：不是 p != nullptr
循环链表判空（2026年3月第1题）：
在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。
约瑟夫问题（循环链表经典应用，2025年6月第4题）：
用循环链表模拟n个人围成一圈，每次数到第k个人出圈。
知识块④：二分算法
·4.1 二分查找——“在有序数组中快速找目标”
原理： 每次取中间元素，与目标比较，缩小一半搜索范围。
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
（2025年3月第12题）
时间复杂度： O(log n)
前提条件： 数组必须是有序的（2024年3月判断第3题）
·4.2 二分查找的变体
查找第一个大于等于x的位置（lower_bound）：
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;
}
（2026年3月第8题、2026年6月第9题）
·4.3 二分答案（二分枚举法）
原理： 当问题的答案具有单调性时，可以对答案进行二分，用check函数验证。
经典例题：切木头（2025年12月第12题、2026年6月第10题）
bool check(int L, int K, int x) {
int cuts = (L - 1) / x;
return cuts <= K;
}
经典例题：在 [1,100] 内猜数，最多需要猜几次？→ 7次（log₂100 ≈ 7，2025年3月第11题）
知识块⑤：递归算法
·5.1 递归的概念
递归就是函数调用自身。一个递归函数必须包含终止条件，否则会无限递归导致栈溢出。
int factorial(int n) {
if (n <= 1) return 1; // 终止条件
return n * factorial(n - 1); // 递归调用
}
（2024年3月第3题、第14题）
·5.2 递归的优缺点
优点： 代码简洁，符合数学定义，易于理解（如斐波那契数列）
缺点：
递归调用占用栈空间，层数过多会导致栈溢出（2025年3月第7题）
函数调用有额外开销，效率低于循环
递归通常比迭代更耗费内存空间（2024年12月判断第10题）
·5.3 递归 vs 迭代
斐波那契数列——递归实现（2023年12月第1题）：
int fiboA(int N) { // 递归，O(2ⁿ)
if (N == 1 || N == 2) return 1;
return fiboA(N - 1) + fiboA(N - 2);
}
斐波那契数列——循环实现：
int fiboB(int N) { // 循环，O(n)
if (N == 1 || N == 2) return 1;
int last2 = 1, last1 = 1, nowVal = 0;
for (int i = 2; i < N; i++) {
nowVal = last1 + last2;
last2 = last1;
last1 = nowVal;
}
return nowVal;
}
结论： 循环实现效率更高，递归实现更直观。（2023年12月第1题）
·5.4 递归的优化
尾递归优化： 如果递归调用是函数的最后一个操作，编译器可以优化，避免栈溢出。
记忆化递归： 用数组记录已经算过的结果，避免重复计算。
知识块⑥：分治算法
·6.1 分治的思想
分治： 将一个大问题分解成多个规模较小、结构相似的子问题，分别求解，再合并结果。（2024年6月第10题）
·6.2 归并排序
思想： 将数组分成两半，分别排序，再合并两个有序数组。（2024年6月第13题）
void mergeSort(int arr[], int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right); // 合并两个有序数组
}
合并操作： 双指针依次比较，将较小的放入结果数组（2026年3月第12题）
时间复杂度： 最好/最坏/平均都是 O(n log n)（2024年12月第10题）
空间复杂度： O(n)（需要额外数组存储合并结果）
稳定性： 稳定排序
merge函数被调用的次数： 对长度为n的数组，merge被调用 n-1 次（2026年6月第13题）
·6.3 快速排序
思想： 选择一个基准值（pivot），将数组分为小于pivot和大于pivot两部分，再递归排序。（2024年12月第9题）
void quickSort(vector<int>& arr, int low, int high) {
if (low >= high) return;
int pi = partition(arr, low, high); // 划分
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
时间复杂度：
平均：O(n log n)
最坏：O(n²)（数组已有序且每次选第一个元素为pivot，2024年9月第9题）
最好：O(n log n)
稳定性： 不稳定（2025年3月第9题）
如何避免最坏情况？ 随机选择pivot（2025年6月第14题），或三数取中法（2025年12月判断第6题）
·6.4 归并排序 vs 快速排序
知识块⑦：贪心算法
·7.1 贪心的核心思想
贪心算法： 在每一步选择中都选择当前状态下最优的选择（局部最优解），希望通过一系列局部最优选择达到全局最优。（2024年3月第2题）
注意： 贪心算法不一定能得到全局最优解！（2024年3月判断第4题、2024年9月判断第4题）
·7.2 最优子结构
最优子结构： 一个问题的最优解包含了其子问题的最优解。
「最优子结构」是贪心可以用到的前提，但满足最优子结构不意味着贪心一定能得到最优解。（2026年3月判断第8题）
·7.3 经典贪心问题
硬币找零（2024年6月第2题、2025年6月第13题）：
// 贪心：每次选当前最大面额的硬币
sort(coins.begin(), coins.end(), greater<int>());
for (int coin : coins) {
int num = amount / coin;
result[i] = num;
amount -= num * coin;
}
过河问题（2024年9月第11题）： 最轻的和最重的尝试一起过河
分饼干（2024年12月第13题）： 按利润从高到低排序，尽量安排
任务调度（2025年12月第14题）： 按利润从高到低，尽量安排
知识块⑧：C++高精度运算
·8.1 为什么需要高精度？
C++中的int（约±21亿）和long long（约±9×10¹⁸）能表示的整数范围有限。当需要处理上百位的超大整数时，需要用数组模拟。
·8.2 高精度加法
原理： 按位相加，处理进位。数组低位在前（个位在索引0）。
vector<int> add(vector<int> a, vector<int> b) {
vector<int> c;
int carry = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
c.push_back(carry % 10); // 存当前位
carry /= 10; // 进位
}
if (carry) c.push_back(carry); // 处理最高位进位
return c;
}
（2023年12月第11题、2025年12月第15题）
·8.3 高精度减法
原理： 按位相减，处理借位。保证被减数不小于减数。
vector<int> subtract(vector<int> a, vector<int> b) {
vector<int> c;
for (int i = 0; i < a.size(); i++) {
int digitB = (i < b.size()) ? b[i] : 0;
if (a[i] < digitB) {
a[i + 1]--; // 向高位借1
a[i] += 10; // 当前位加10
}
c.push_back(a[i] - digitB);
}
while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去除前导0
return c;
}
（2024年6月第12题、2024年12月第15题、2026年6月第15题）
·8.4 高精度乘法
原理： 逐位相乘，累加进位。
vector<int> multiply(vector<int>& a, vector<int>& b) {
vector<int> c(a.size() + b.size(), 0);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
c[i + j] += a[i] * b[j];
int carry = 0;
for (int k = 0; k < c.size(); k++) {
int temp = c[k] + carry; // 当前位 + 进位
c[k] = temp % 10;
carry = temp / 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
（2025年3月第15题）
·8.5 高精度除法（大数除以小数）
原理： 从高位到低位，逐位试商。
// 大整数（字符串表示）除以小整数（int）
vector<int> c;
long long rem = 0;
for (int i = 0; i < a.size(); i++) {
rem = rem * 10 + a[i];
int q = rem / b;
c.push_back(q);
rem %= b; // 余数
}
（2026年3月第15题）
03
PART
历年真题分析
EXAMS · 真题
一、单选题考点分布统计（11套真题，共165道）
| 链表 | ||
| 初等数论 | ||
| 排序算法 | ||
| 二分算法 | ||
| 递归算法 | ||
| 贪心算法 | ||
| 高精度运算 | ||
| 算法复杂度 |
二、各套真题单选题逐题分析
·2023年9月试卷
计算机常识★★
手写板属于输入设备
表达式判断★★★
(a == 3 * b)判断a是b的3倍
逗号表达式★★★
(a=6,b=3*(7+8)/2,b+=a)=28
递归vs迭代★★★★
输入100000时递归会栈溢出
递归字符串反转★★★★
选A：最后一个字符+反转剩余部分
汉诺塔递归★★★★
选B：Hanoi(B,A,C,N-1)
函数指针+sort★★★★
compare和isOdd作为函数名传递
函数指针调用★★★
执行后输出1
函数指针类型匹配★★★★
Square不匹配bool(*)(int)，编译错误
递归执行过程★★★★★
时间复杂度★★★★
isPrimeA O(n)，isPrimeB O(√n)
归并排序merge调用次数★★★★
7个元素，merge被调用6次
分治算法识别★★★
归并排序是分治算法
归并排序思想★★★
分成两个子数组，分别排序后再合并
链表类型判断★★★★
最后一个节点指向第一个节点，构成循环链表
·2023年12月试卷
斐波那契递归vs迭代★★★★
fiboA代码量少但执行效率低
归并排序递归★★★★
选C：mergeSort(SList,T2,s,m,len)和mergeSort(SList,T2,m+1,t,len)
递归执行过程★★★★
输出1->120<=>1->2->3->4->5->120
排序条件★★★★
偶数在前奇数在后，选!isEven && isEven
双向链表插入★★★★★
有前驱节点时需要处理prev指针
欧几里得算法★★★★
foo求最大公约数，rc统计递归次数
快速排序★★★★
返回qSort(less)+pivot+qSort(greater)
时间复杂度★★★★
isPrimeA O(N/2)，isPrimeB O(√N)
二分查找识别★★★
不是动态规划，是递归+分治
二分时间复杂度★★★
O(log N)
高精度加法★★★★
选D：c.push_back(t%10), t=t/10
链表类型判断★★★★
双向链表（有prev和next）
通信常识★★
通讯卫星起到信号中继的作用
方法选择★★★★
二分答案不适合判断素数
排序特点★★★★
快速排序不能保证选出最大或最小
·2024年3月试卷
唯一分解定理★★★
每个合数可以唯一分解为素数乘积
贪心算法核心★★★
每一步选择当前最优解
递归阶乘★★
return n * factorial(n - 1)
双向链表删除★★★★
current->prev->next = current->next
辗转相除法★★
也称欧几里德算法
斐波那契递归复杂度★★★★
O(2ⁿ)
高精度加法★★★★
result = to_string(sum % 10) + result
二分查找次数★★★★
查找82不在数组中，需要4次循环
素数判断★★★
循环条件改为i*i <= num
埃氏筛外循环范围★★★★
选C：for(int i=2; i<=sqrt(n); ++i)
线性筛时间复杂度★★★
O(n)
归并排序思想★★★
分治
快速排序pivot影响★★★
选择pivot影响时间复杂度
递归终止条件★★★
必须有终止条件
链表查找★★
找到5返回1
·2024年6月试卷
算法识别★★
循环实现斐波那契是迭代算法
贪心算法识别★★★
最少硬币组合是贪心算法
链表查找时间复杂度★★★
O(n)
双向链表头部插入★★★★
head->prev = p
欧几里得算法★★★
求最大公约数
递归vs迭代效率★★★★
递归版效率并不更高
线性筛代码填空★★★★
for(int j=0;j<primes.size()&&i*primes[j]<=n;j++)
线性筛时间复杂度★★★
O(n)
快速排序循环条件★★★★
while(i <= j)
分治算法概念★★★
分治将问题分成子问题解决
二分查找比较序列★★★★
39,79,90,81
高精度减法借位★★★★
a[i+1]--
归并排序比较次数★★★★
2n-1
递归函数值★★★★
fun(7) = -11
递归输出序列★★★★
4 2 3 1 2
·2024年9月试卷
数组vs链表★★★
存储相同数目整数，数组比链表所需内存少
双向循环链表插入★★★★
s->next->prev = s等四步操作
递归vs迭代效率★★★★
SumB效率并不比sumA高
欧几里得算法★★★
fun(20,12)=4
埃氏筛代码填空★★★★
for(int j=i*i; j<=n; j+=i)
线性筛代码填空★★★★
for(int j=0; j<primes.size() && i*primes[j]<=n; j++)
质因数分解复杂度★★★★
O(√n log n)
快速幂复杂度★★★★
O(log n)
快排最坏情况★★★★
已排序数组+选第一个元素→O(n²)
归并排序merge调用★★★★
O(n)次
贪心算法识别★★★
过河问题是贪心算法
分治算法概念★★★
分治将问题分成子问题解决
二分查找次数★★★★
查找31在10个元素中需要2次
高精度运算概念★★★
高精度乘法时间与两数位数都有关
递归求值★★★★
fun(7)=210
·2024年12月试卷
链表特性★★★
链表插入删除效率高，时间复杂度O(1)
循环单链表★★★
最后一个节点指向第一个节点
虚拟头节点删除★★★★
dummyHead->next=head; cur=dummyHead
斐波那契复杂度★★★★
fibA O(n)，fibB O(2ⁿ)
欧几里得调用顺序★★★★
gcd(24,36)→gcd(24,12)
质因数分解★★★★
for(int i=3; i*i<=n; i+=2)
埃氏筛理解★★★★
从i²开始标记，减少重复标记
线性筛理解★★★★
时间复杂度O(n)
快速排序★★★★
通过递归对子问题求解
归并排序★★★★
最优/最差/平均都是O(n log n)
二分查找递归★★★★
递归终止条件包括left>right
二分查找左边界★★★★
right = middle
贪心分饼干★★★
result++; index--
分治算法★★★
冒泡排序不是分治
高精度减法★★★★
数字以倒序存储
·2025年3月试卷
链表特点★★★
链表不能随机访问
双向链表删除★★★★
选A：p->next->prev = p->next 有误，正确答案是B
双向循环链表初始化★★★★
head->next=tail, tail->prev=head
欧几里得算法步骤★★★
gcd(84,60)→gcd(60,24)→gcd(24,12)→gcd(12,0)
唯一分解定理★★★
30=2×3×5正确
线性筛循环条件★★★★
j<primes.size() && i*primes[j]<=n
递归栈溢出★★★
系统分配的栈空间溢出
递归vs迭代★★★
factorialB是迭代不是递归
排序稳定性★★★
选择排序不稳定
快速排序partition★★★★
if(arr[j]<pivot) { i++; swap(arr[i],arr[j]); }
二分猜数次数★★★
log₂100≈7次
二分mid计算★★
int mid = left + (right - left) / 2
贪心核心特征★★★
总是选择当前最优解
分治求最大值★★★★
选D：正确实现分治
高精度乘法进位★★★★
int temp = c[k] + carry
·2025年6月试卷
链表优势★★★
在已知位置插入或删除节点效率高
双向链表判空★★★
不能使用head.data==0（可能head为nullptr）
双向链表尾部插入★★★★
tail->next=newNode; newNode->prev=tail; tail=newNode
约瑟夫问题★★★★
选A：先改指针再删除
质数判断算法★★★★★
6k±1形式是正确前提
欧几里得算法★★★★
gcd0 O(log n)，gcd1 O(n)
筛法效率比较★★★★
埃氏筛并不比线性筛效率高
唯一分解定理★★★
大于1的合数可以唯一分解为质数乘积
分治算法识别★★★
不是贪心算法
迭代算法★★★
不涉及递归
二分查找最后出现★★★★★
处理重复元素，能正确返回最后一个
二分法求平方根★★★★
浮点数比较可以用于循环条件
贪心算法识别★★★
硬币找零是贪心算法
快速排序稳定性★★★★
快速排序不是稳定排序
高精度除法★★★★★
高精度除法代码填空
·2025年12月试卷
循环链表遍历★★★★
do-while + p != head
区块链插入★★★★
tail = newBlock
链表删除时间复杂度★★★★
双链表O(1)，单链表O(n)
同余概念★★★
38-14=24，24不能被9整除
欧几里得算法★★★
递归版效率并不更高
唯一分解定理★★★
大于1的合数可以唯一分解
线性筛代码★★★★
for(int j=0; j<primes.size() && i*primes[j]<=n; j++)
排序稳定性★★★
归并排序通常是稳定的
归并排序特性★★★★
最坏情况也是O(n log n)
快排最坏复杂度★★★
O(n²)
lower_bound实现★★★★
逻辑正确
二分答案★★★★
if(check) r=mid else l=mid+1
递归vs迭代时空复杂度★★★★
时间复杂度相同O(n)，空间复杂度不同
贪心任务调度★★★★
slot[t]=true; totalProfit+=task.profit
高精度加法★★★★
c.push_back(carry%10); carry/=10
·2026年3月试卷
循环链表判空★★★★
头结点next指向自身
双向循环链表插入★★★★
选C：s->next=p; s->prev=p->prev; p->prev->next=s; p->prev=s
虚拟头节点删除★★★★
cur->next = del->next
欧几里得调用序列★★★
gcd(48,18)→gcd(18,12)→gcd(12,6)→gcd(6,0)
线性筛条件★★★★
j < primes.size()
埃氏筛i²原因★★★★
小于i²的倍数已被更小质因子筛过
二分答案★★★★
输出3
lower_bound★★★★
r = mid
递归栈溢出★★★★
栈溢出时程序会终止，不能继续执行
二分答案★★★★
选C
分治复杂度★★★★
O(n log n)
归并排序合并★★★
A[i] <= B[j]
快排最坏复杂度★★★★
已排序+首元素pivot→O(n²)
排序比较★★★★
归并排序是稳定的，快排不稳定
高精度除法★★★★
rem %= b
·2026年6月试卷
循环链表插入★★★★
newNode->next=head->next; head->next=newNode
循环链表遍历★★★★
do-while + p != head
双链表删除★★★★
p->prev->next=p->next; p->next->prev=p->prev
欧几里得调用序列★★★
gcd(105,45)→gcd(45,15)→gcd(15,0)
线性筛break条件★★★★
i % primes[j] == 0
埃氏筛理解★★★
从每个素数出发，标记倍数
快速幂分治★★★
分治思想
因子2的个数★★★
40=2³×5，输出3
lower_bound★★★★
r = mid
二分答案★★★★
r = mid
快排partition★★★★
swap(arr[low], arr[i])
归并排序思想★★★
分两半分别排序再合并
merge调用次数★★★★
n-1次
贪心盲盒打包★★★★
l++; r--
高精度减法借位★★★★
a[i] += 10
三、判断题高频陷阱汇总
·第1名：贪心算法（出现约10次）
“贪心算法通过每一步选择局部最优解，从而一定能获得全局最优解。”（2024年3月判断第4题、2024年9月判断第4题、2025年3月判断第4题、2025年12月判断第10题、2026年6月判断第6题）
答案：×。贪心算法不一定能得到全局最优解。
“贪心算法可以应用于所有问题的通用解决方案。”（2024年3月判断第8题）
答案：×。贪心算法不是通用解决方案。
“贪心算法的解可能不是最优解。”（2023年9月判断第6题）
答案：√。正确。
·第2名：排序算法稳定性（出现约8次）
“快速排序是稳定排序”（2025年12月第8题、2025年6月第14题）
答案：×。快速排序是不稳定的。
“归并排序是不稳定的”（2026年6月判断第10题）
答案：×。归并排序是稳定的。
“插入排序是不稳定排序”（2025年12月第8题）
答案：×。插入排序是稳定的。
“冒泡排序算法优于归并排序。”（2023年9月判断第7题）
答案：×。归并排序通常优于冒泡排序。
·第3名：链表概念（出现约7次）
“链表存储线性表时要求内存中可用存储单元地址是连续的。”（2025年3月判断第2题）
答案：×。链表可以存储在不连续的内存中。
“链表的优点是插入删除不需要移动元素，并且能随机查找。”（2025年12月判断第1题）
答案：×。链表不能随机查找（随机访问是O(n)）。
“单链表只支持在表头进行插入和删除操作。”（2024年12月判断第1题）
答案：×。单链表可以在任何位置插入和删除，只是需要遍历。
·第4名：初等数论（出现约6次）
“唯一分解定理表明任何一个大于1的自然数都可以唯一地分解为若干个质数的乘积。”（2024年9月判断第3题、2024年12月判断第3题、2026年6月判断第9题）
答案：×关键是“考虑顺序”或“乘积”（不是“和”）。
“线性筛法比埃氏筛法效率更高。”（2024年9月判断第2题、2024年12月判断第2题）
答案：√。线性筛O(n)，埃氏筛O(n log log n)。
·第5名：递归（出现约5次）
“递归函数必须有一个明确的结束条件，否则会导致无限递归并可能引发栈溢出。”（2024年12月判断第5题、2025年3月判断第5题、2025年12月判断第9题）
答案：√。这是递归的基本要求。
“在C++语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。”（2024年9月判断第9题）
答案：√。递归占用栈空间。
·第6名：二分查找（出现约4次）
“二分查找要求被搜索的序列是有序的，否则无法保证正确性。”（2024年3月判断第3题、2024年9月判断第8题）
答案：√。二分查找必须有序。
“二分查找适用于对无序数组和有序数组的查找。”（2025年3月判断第8题）
答案：×。只适用于有序数组。
“二分查找仅适用于数组而不适合链表，因为二分查找需要跳跃式访问元素，链表中执行跳跃式访问的效率低。”（2024年12月判断第8题）
答案：√。链表不支持随机访问。
·第7名：分治算法（出现约3次）
“分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。”（2024年3月判断第5题）
答案：√。这是分治算法的定义。
“归并排序算法体现了分治算法。”（2025年3月判断第10题）
答案：√。
·第8名：其他（出现约3次）
“C++语言中的qsort库函数是不稳定排序。”（2023年9月判断第8题）
答案：×。qsort是不稳定的，但题目说“不”稳定，所以是×。
“对于已经定义好的标准数学函数sin(x)，应用程序中的语句y=sin(sin(x))是一种递归调用。”（2024年9月判断第10题）
答案：×。这是嵌套调用，不是递归（递归要求函数调用自身）。
四、编程题全分析（11套真题）
·各套真题编程题一览
2023年9月
编程题1：因数分解
考点：质因数分解、数论
编程题2：巧夺大奖
考点：贪心算法、任务调度
2023年12月
编程题1：小杨的幸运数
考点：筛法、数论、预处理
编程题2：烹饪问题
考点：位运算、分治
2024年3月
编程题1：成绩排序
考点：排序、结构体排序
编程题2：B-smooth数
考点：线性筛、数论
2024年6月
编程题1：黑白格
考点：二维数组、模拟
编程题2：小杨的幸运数字
考点：数论、筛法
2024年9月
编程题1：小杨的武器
考点：贪心、模拟
编程题2：挑战怪物
考点：数论、质数判断
2024年12月
编程题1：奇妙数字
考点：质因数分解、数论
编程题2：武器强化
考点：贪心、排序
2025年3月
编程题1：平均分配
考点：贪心、排序
编程题2：原根判断
考点：数论、快速幂
2025年6月
编程题1：（待补充）
考点：链表/数论
编程题2：（待补充）
考点：数论/排序
2025年9月
编程题1：（待补充）
考点：链表/数论
编程题2：（待补充）
考点：排序/二分
2025年12月
编程题1：数字移动
考点：二分答案、贪心
编程题2：相等序列
考点：质因数分解、数论
2026年3月
编程题1：有限不循环小数
考点：数论、质因数分解
编程题2：（待补充）
考点：数论
2026年6月
编程题1：排排坐
考点：排序、前缀和
编程题2：晚宴
考点：枚举、最大公约数
·编程题高频考点总结
| 初等数论 | ||
| 贪心算法 | ||
| 排序算法 | ||
| 二分答案 | ||
| 链表操作 |
·编程题必会模板
模板1：欧几里得算法（递归）
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
模板2：线性筛（欧拉筛）
vector<int> sieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) primes.push_back(i);
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) break;
}
}
return primes;
}
模板3：质因数分解
for (long long p = 2; p * p <= n; p++) {
if (n % p == 0) {
int cnt = 0;
while (n % p == 0) { cnt++; n /= p; }
// p^cnt 是一个质因数项
}
}
if (n > 1) { /* 剩余的质因子 */ }
模板4：二分查找（lower_bound）
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;
}
模板5：归并排序
void mergeSort(int arr[], int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r); // 合并两个有序数组
}
模板6：高精度加法
vector<int> add(vector<int> a, vector<int> b) {
vector<int> c;
int carry = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
c.push_back(carry % 10);
carry /= 10;
}
if (carry) c.push_back(carry);
return c;
}
04
PART
高频易错题精选
TRAPS · 易错
一、单选题精选
1. 关于单链表、双链表和循环链表，下列说法正确的是（ ）。（2026年3月第1题）
A. 在单链表中，若已知任意结点的指针，可以在O(1)时间内删除该结点
B. 循环链表中一定不存在空指针
C. 在循环双链表中，尾结点的next指针一定为nullptr
D. 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身
答案：D。A：单链表删除需要知道前驱节点；B：空循环链表中头结点next指向自身，不是空指针；C：循环链表尾结点next指向头结点。
2. 下面关于链表和数组的描述，错误的是（ ）。（2024年9月第1题）
A. 数组大小固定，链表大小可动态调整
B. 数组支持随机访问，链表只能顺序访问
C. 存储相同数目的整数，数组比链表所需的内存多
D. 数组插入和删除元素效率低，链表插入和删除元素效率高
答案：C。数组只需要存储数据本身，链表还需要存储指针，链表需要更多内存。
3. 唯一分解定理描述的内容是（ ）。（2024年3月第1题）
A. 任意整数都可以分解为素数的乘积
B. 每个合数都可以唯一分解为一系列素数的乘积
C. 两个不同的整数可以分解为相同的素数乘积
D. 以上都不对
答案：B。注意：1不是合数也不是素数，所以“任意整数”不对。
4. 下述代码实现素数表的线性筛法，横线上应填的最佳代码是（ ）。（2024年6月第7题）
A. for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
B. for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)
C. for (int j = 0; j <= n; j++)
D. for (int j = 1; j <= sqrt(n); j++)
答案：A。线性筛需要遍历所有已找到的素数，且不超过n。
5. 下面关于排序的说法，正确的是（ ）。（2025年12月第8题）
A. 快速排序是稳定排序
B. 归并排序通常是稳定的
C. 插入排序是不稳定排序
D. 冒泡排序不是原地排序
答案：B。归并排序是稳定的。快速排序不稳定，插入排序稳定，冒泡排序是原地排序。
6. 贪心算法的核心思想是（ ）。（2024年3月第2题）
A. 在每一步选择中都做当前状态下的最优选择
B. 在每一步选择中都选择局部最优解
C. 在每一步选择中都选择全局最优解
D. 以上都对
答案：A（或B，两者意思相同）。核心是局部最优，不一定是全局最优。
二、判断题精选
1. 贪心算法通过每一步选择局部最优解，从而一定能获得全局最优解。（ ）
答案：×。贪心算法不一定能得到全局最优解，这是最常考的判断题之一。
2. 快速排序和归并排序的平均时间复杂度均为O(n log n)，且都是稳定排序。（ ）（2024年12月判断第6题）
答案：×。归并排序稳定，但快速排序不稳定。
3. 线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。（ ）（2024年12月判断第2题）
答案：√。这是线性筛的核心优势。
4. 使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。（ ）（2025年12月判断第10题）
答案：×。再次强调，贪心不一定得到全局最优解。
5. 二分查找仅适用于数组而不适合链表，因为二分查找需要跳跃式访问元素，链表中执行跳跃式访问的效率低。（ ）（2024年12月判断第8题）
答案：√。链表不支持随机访问。
6. 唯一分解定理表明任何一个大于1的整数都可以唯一地分解为素数之和。（ ）（2024年9月判断第3题）
答案：×。是分解为素数乘积，不是和。
///
LAST
复习建议
PLAN · 冲刺
一、复习时间规划（距考试3周）
·第1周：基础打牢
| 初等数论（一） | ||
| 初等数论（二） | ||
| 链表 | ||
| 排序算法 | ||
| 二分 + 递归 | ||
| 贪心 + 分治 | ||
| 高精度运算 |
·第2周：真题训练
·第3周：查漏补缺
复习“判断题高频陷阱”部分，确保不再掉坑
熟背编程模板（6个必会模板）
限时模拟一套完整试卷（120分钟）
把之前的错题再过一遍
二、考场技巧
·做题顺序建议
单选题（15道，约30分钟）——不会的先跳过，不要在一道题上花太多时间
判断题（10道，约15分钟）——注意“一定”“总是”“所有”这种绝对化的词语，通常是错的
编程题（2道，约60分钟）——先读懂题目，再动手写代码
·编程题检查清单
☐ 变量都初始化了吗？
☐ 数组下标有没有越界？
☐ 欧几里得算法的终止条件写对了吗？（b == 0）
☐ 埃氏筛是从i²开始标记的吗？
☐ 线性筛的break条件写对了吗？（i % primes[j] == 0）
☐ 链表操作时检查了空指针吗？
☐ 二分查找的区间是左闭右闭还是左闭右开？
☐ 高精度运算的进位/借位处理对了吗？
☐ 有没有漏掉 return 0;？
DOMIAI
我是 DOMIAI，帮更多孩子成为 AI 时代原住民。
如果有收获，欢迎点赞、在看、转发三连，我们下篇见。
THANKS FOR READING
