Appearance
第1章 GESP 五级考点总览
🎯 本章学习目标
通过本章的学习，你将能够：
- 建立全局视野：清晰了解 GESP 五级考试的 5 大知识模块及其重要程度
- 掌握数论基础：理解素数、GCD/LCM、模运算、筛法等核心概念
- 玩转链表操作：掌握单链表、双链表、循环链表的基本操作
- 攻克高精度：能用数组模拟大整数的加减乘除运算
- 精通二分算法：掌握二分查找和二分答案的思想与实现
- 理解递归本质：掌握递归三要素，理解调用栈和记忆化优化
- 掌握分治思想：理解归并排序、快速排序的分治思路
- 学会贪心策略：掌握区间调度、合并问题等经典贪心模型
- 分析算法复杂度：能估算时间复杂度，根据数据规模选算法
- 制定备考策略：根据各模块考频和自身情况，合理安排复习计划
🗺️ 本章知识图谱
GESP 五级知识体系
├── 初等数论
│ ├── 素数与合数
│ │ ├── 素数判定（试除法）
│ │ ├── 埃氏筛法
│ │ └── 线性筛法（欧拉筛）
│ ├── 约数与倍数
│ │ ├── GCD（辗转相除法）
│ │ ├── LCM
│ │ └── gcd×lcm = a×b
│ ├── 质因数分解
│ │ └── 唯一分解定理
│ ├── 模运算
│ │ ├── 加减乘模性质
│ │ └── 快速幂思想入门
│ └── 奇偶性分析
├── 链表与高精度
│ ├── 链表
│ │ ├── 单链表（创建/插入/删除/遍历/反转）
│ │ ├── 双链表（prev + next）
│ │ └── 循环链表（首尾相连）
│ └── 高精度运算
│ ├── 高精度加法（倒序存储、进位）
│ ├── 高精度减法（借位、大小比较）
│ ├── 高精度乘法（高精×低精/高精×高精）
│ └── 高精度除法（高精÷低精、余数）
├── 二分算法与递归
│ ├── 二分算法
│ │ ├── 二分查找（有序序列）
│ │ ├── 左闭右闭 / 左闭右开
│ │ └── 二分答案（单调性 + check函数）
│ └── 递归
│ ├── 基线条件 + 递归条件
│ ├── 调用栈原理
│ ├── 递归复杂度分析
│ └── 记忆化搜索（Memoization）
├── 分治算法
│ ├── 分治思想（分解→解决→合并）
│ ├── 归并排序
│ │ ├── 二分拆分
│ │ ├── 合并有序数组
│ │ └── 逆序对计数
│ ├── 快速排序
│ │ ├── 选基准 pivot
│ │ ├── partition 分区
│ │ └── 平均 O(n log n)
│ └── 复杂度分析（递归式）
├── 贪心算法
│ ├── 贪心基本要素
│ │ ├── 贪心选择性质
│ │ └── 最优子结构
│ ├── 经典模型
│ │ ├── 区间调度（按右端点排序）
│ │ ├── 合并果子（哈夫曼思想）
│ │ └── 找零问题
│ └── 正确性证明（交换论证/反证法）
└── 复杂度分析
├── 时间复杂度
├── 空间复杂度
├── 递归树分析法
└── 数据规模反推一、写在前面
本书是 《GESP 五级备考白皮书》 的 第 1 章（全书总览），先带你把 五大考点板块 一次看全。
CCF GESP（编程能力等级认证）五级，是 C++ 考级体系中的第五个台阶，标志着从"能写程序"迈向"会用算法"的关键转折。考纲涵盖 8 大知识模块，我们将其归纳为 5 大考点板块（链表与高精度合并、二分与递归合并），帮你快速建立全局视野。
💡 全书结构：第 1 章为总览，第 2~8 章逐模块深入拆解，每章覆盖知识点精讲、典型例题、编程实战与备考策略；附录 A~E 提供考纲对照、速查总表、术语表、备考规划与勘误。
二、📊 五大考点全景总表
我们将 GESP 五级的 8 大知识模块归纳为 5 大考点，一览全局：
| 序号 | 📌 考点模块 | 📖 一句话概括 | ⭐ 考频星级 |
|---|---|---|---|
| ① | 初等数论 | 素数、GCD/LCM、模运算、质因数分解、埃氏筛/线性筛——选择判断的"常客" | ⭐⭐⭐⭐⭐ |
| ② | 链表与高精度运算 | 单/双/循环链表操作 + 数组模拟大整数加减乘除——编程题经典素材 | ⭐⭐⭐⭐⭐ |
| ③ | 二分算法与递归 | 二分查找/二分答案 + 递归思想与记忆化——从暴力到优化的思维跃迁 | ⭐⭐⭐⭐⭐ |
| ④ | 分治算法 | 归并排序、快速排序、逆序对——"分而治之"的算法艺术 | ⭐⭐⭐⭐ |
| ⑤ | 贪心算法 | 贪心选择性质、最优子结构、区间问题——策略对了，代码就短了 | ⭐⭐⭐⭐⭐ |
📌 考频星级说明：基于历年 GESP 五级真题统计分析，⭐越多表示出题频率越高、分值占比越大。算法复杂度估算贯穿所有考点，将在第 8 章专项讲解。
三、🔍 五大考点逐一拆解
下面逐个说明每个考点 "考什么" 和 "怎么考" 。
① 初等数论
🎯 考什么
- 素数与合数：素数判定（试除法）、素数的分布与性质
- 约数与倍数：约数个数、约数和、倍数关系
- 最大公约数（GCD）与最小公倍数（LCM）：欧几里得算法（辗转相除法）、
gcd(a,b) × lcm(a,b) = a × b - 同余与模运算：模的加减乘性质、取模运算规则、快速幂思想入门
- 质因数分解：唯一分解定理（每个正整数可唯一表示为素数乘积）
- 奇偶性分析：奇偶判断、奇偶运算规律
- 素数筛法：
- 埃氏筛法（Eratosthenes）：用素数标记倍数，O(n log log n)
- 线性筛法（欧拉筛）：每个合数只被最小质因子筛掉，O(n)
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | GCD/LCM 计算、模运算结果判断、筛法代码填空、质因数分解结果、素数判定 |
| 判断题 | "1是素数"（错！）、"线性筛比埃氏筛快"（对！）、模运算性质判断 |
| 编程题 | 素数判定与筛法应用题、GCD/LCM 相关计算、利用唯一分解定理解题 |
🔥 真题规律：数论题每场必考，选择+判断中通常有 3~5 题涉及。埃氏筛和线性筛的代码填空题是经典题型，务必能手写两种筛法。编程题中常以"素数计数""因数分解"为背景出现。
② 链表与高精度运算
🎯 考什么 本模块合并了考纲中的"链表"和"C++数组模拟高精度运算"两部分：
链表：
- 单链表：节点结构（data + next）、创建、插入（头插/尾插/指定位置）、删除、遍历、查找、反转
- 双链表：前驱与后继指针（prev + next）、双向遍历、插入与删除操作
- 循环链表：首尾相连、循环遍历的终止条件判断
高精度运算（用数组/字符串模拟大整数）：
- 高精度加法：逐位相加、进位处理
- 高精度减法：逐位相减、借位处理、大小比较
- 高精度乘法：高精度 × 低精度 / 高精度 × 高精度
- 高精度除法：高精度 ÷ 低精度（逐位试商、余数处理）
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 链表插入/删除后指针变化、循环链表终止条件、高精度运算某一步的中间结果 |
| 判断题 | "单链表可以双向遍历"（错！）、"高精度加法需要倒序存储"（对！） |
| 编程题 | 高精度加减乘除计算（大数场景）、链表的创建与基本操作、链表反转 |
🔥 真题规律：高精度运算是编程题的经典考点，尤其加法和乘法出现频率最高。链表更多出现在选择/判断题中，考查指针操作和边界条件。建议至少手写三遍高精度加法和乘法模板，做到"闭着眼也能写对"。
③ 二分算法与递归
🎯 考什么 本模块合并了考纲中的"二分算法"和"递归算法"两部分：
二分算法：
- 二分查找：在有序序列中查找目标值，左闭右闭 / 左闭右开两种写法的边界处理
- 二分答案（二分枚举法）：当答案具有单调性时，二分枚举答案并验证是否可行——"求最大的最小值""求最小的最大值"类问题
递归算法：
- 递归概念：基线条件（递归出口）与递归条件、调用栈的工作原理
- 时间与空间复杂度：递归树分析法、递归深度与栈溢出
- 递归优化：记忆化搜索（Memoization）——用数组/哈希表缓存已计算结果，避免重复计算
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 二分查找边界条件填空、二分答案的可行性判断、递归调用过程追踪、记忆化数组含义 |
| 判断题 | "二分查找要求序列有序"（对！）、"递归一定比循环慢"（不一定！）、记忆化是否改变时间复杂度 |
| 编程题 | 二分答案经典题（砍树、跳石头等变形）、递归+记忆化解题（斐波那契、路径计数等） |
🔥 真题规律：二分答案是编程题的热门考点，核心在于识别问题的单调性并写出正确的 check 函数。递归则是贯穿全卷的基础能力——数论、分治、搜索都离不开递归。记忆化优化常作为选择题中的"进阶考点"出现。
④ 分治算法
🎯 考什么
- 分治思想：将大问题拆成子问题 → 递归求解子问题 → 合并子问题的解
- 归并排序：二分拆分 → 递归排序 → 合并两个有序数组，O(n log n)
- 快速排序：选基准（pivot）→ 分区（partition）→ 递归排序左右两侧，平均 O(n log n)
- 逆序对问题：利用归并排序在合并过程中统计逆序对数量
- 分治算法的时间复杂度分析（递归式复杂度分析）
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 归并/快排的某一轮排序结果、partition 过程分析、时间复杂度判断 |
| 判断题 | "快速排序最坏情况是 O(n²)"（对！）、"归并排序是稳定排序"（对！） |
| 编程题 | 归并排序求逆序对、快速排序实现、分治思想的应用题 |
🔥 真题规律：归并排序和快速排序是排序算法的核心考点，选择/判断题中常考排序过程和复杂度对比。逆序对计数是归并排序的经典应用，在编程题中多次出现，务必掌握其合并时的计数逻辑。
⑤ 贪心算法
🎯 考什么
- 贪心选择性质：每一步做出局部最优选择，最终得到全局最优解
- 最优子结构：问题的最优解包含子问题的最优解
- 经典贪心模型：
- 区间问题：区间选点、最大不相交区间数（按右端点排序）
- 合并型贪心：每次合并最小的两个元素（类似合并果子问题）
- 其他经典问题：找零问题、活动安排、乘船问题等
- 贪心证明：交换论证、反证法——证明贪心策略的正确性
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 判断某问题能否用贪心解决、贪心策略选择、排序方式对结果的影响 |
| 判断题 | "贪心算法总能得到最优解"（错！需满足条件）、贪心与DP的区别 |
| 编程题 | 区间调度、哈夫曼合并、活动安排等经典贪心问题 |
🔥 真题规律：贪心算法的编程题通常代码短但策略难想，关键在于找到正确的贪心策略和排序方式。选择题常考"贪心与动态规划的区别"——贪心要求局部最优即全局最优，而DP考虑所有选择。会证明贪心正确性 = 真正掌握贪心。
四、📈 五级 vs 四级：能力跃迁在哪里？
很多同学考完四级后觉得"五级怎么突然难了"，这不是错觉——五级的考点结构和思维要求确实有质的飞跃：
| 维度 | 四级 | 五级 |
|---|---|---|
| 🧠 思维层次 | 顺序执行、条件分支、循环嵌套 | 算法策略思维（分治、贪心、二分） |
| 🔢 数学基础 | 基本四则运算 | 初等数论（素数、模运算、GCD/LCM） |
| 📦 数据组织 | 一维/二维数组 | 链表（动态数据结构） |
| 🔢 数值范围 | int / long long 够用 | 大到必须用数组模拟（高精度） |
| 🔍 查找方式 | 线性遍历 | 二分查找（O(log n) 的效率飞跃） |
| 🔄 递归深度 | 简单递归（阶乘、斐波那契） | 递归+记忆化，理解递归复杂度 |
| 📊 复杂度意识 | 几乎不涉及 | 大O表示法，能分析多项式/对数复杂度 |
🚀 一句话总结：四级考的是"""能不能写出程序"""，五级考的是"""能不能写出好程序"""——从"能跑"到"高效、正确、优雅"。
五、📝 备考建议：如何高效攻克五级？
1️⃣ 先骨架，后细节
先把五大模块的核心概念过一遍（就像本章给你的全景地图），建立知识框架后，再逐个模块深入。不要一上来就死磕线性筛的代码，结果连什么是素数都没搞清楚。
2️⃣ 选择/判断靠概念，编程题靠手感
- 选择 + 判断（50分）：吃透数论概念、链表操作、排序过程、复杂度分析，配合真题反复练习
- 编程题（50分）：必须动手写！高精度模板 + 二分模板 + 排序模板是必备武器
3️⃣ 真题是最好的复习资料
GESP五级历年真题是最好的备考材料。建议按以下顺序刷题：
- 先按模块分类刷 → 找到自己的薄弱点
- 再按套卷限时练 → 训练时间分配能力
- 最后复盘错题 → 查漏补缺
六、📝 实战练习
练习题 1（判断题）
题目： 1 是素数，因为它只能被 1 和它本身整除。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： 素数的定义是：大于 1 的自然数，除了 1 和它本身之外没有其他因数。1 不满足"大于 1"这个条件，所以 1 既不是素数也不是合数。
💡 记忆口诀：素数从 2 开始，1 是孤家寡人（既不是素数也不是合数）。
练习题 2（单选题）
题目： 已知 gcd(12, 18) = 6，那么 lcm(12, 18) 的值是？（ ）
A. 24
B. 36
C. 72
D. 216
🔑 点击查看答案与解析
答案： B
解析：
利用公式：gcd(a, b) × lcm(a, b) = a × b
代入数值：
- gcd(12, 18) = 6
- lcm(12, 18) = (12 × 18) / 6 = 216 / 6 = 36
选 B。
🔥 高频考点：这个公式非常重要！知道 gcd 就能求 lcm，反之亦然。考试中经常给出一个让你求另一个。
练习题 3（单选题）
题目： 关于单链表，以下说法正确的是（ ）
A. 单链表可以从任意节点出发双向遍历
B. 在单链表中删除一个节点需要知道它的前驱节点
C. 单链表的插入操作时间复杂度是 O(1)（不考虑查找）
D. 单链表的第 n 个节点可以直接通过下标访问
🔑 点击查看答案与解析
答案： B
解析：
- A 错误：单链表只有 next 指针，只能单向遍历，不能回头
- B 正确 ✅：删除节点需要修改前一个节点的 next 指针，所以必须知道前驱节点
- C 表述有歧义：如果已经知道插入位置的前驱节点，插入是 O(1)；但如果要先查找位置，就是 O(n)。相比之下 B 更准确
- D 错误：链表不能随机访问（没有下标），必须从头遍历
🍎 生活比喻：单链表像一列火车，每节车厢只知道后面一节是谁。想删除中间某节车厢，得先找到它前面那节，把挂钩重新接好。
练习题 4（判断题）
题目： 高精度加法中，数字应该倒序存储在数组中（个位存在下标 0 处），这样进位处理更方便。（ ）
🔑 点击查看答案与解析
答案： 正确 ✅
解析： 倒序存储是高精度运算的标准做法。因为加法和乘法的进位都是从低位（个位）向高位进行的，个位存在下标 0 处，进位可以直接追加到数组末尾，非常方便。如果正序存储，进位需要在数组头部插入，效率很低。
💡 记忆技巧：就像列竖式计算——从个位开始算，进位往左边（高位）走。倒序存储就是让数组下标 0 对应个位，下标越大位数越高。
练习题 5（单选题）
题目： 使用二分查找在有序数组 [1, 3, 5, 7, 9, 11, 13] 中查找 9，需要比较几次？（ ）
A. 2 次
B. 3 次
C. 4 次
D. 7 次
🔑 点击查看答案与解析
答案： B
解析：
左闭右闭区间，初始 left=0, right=6：
- 第 1 次：mid = (0+6)/2 = 3，a[3] = 7，7 < 9，目标在右边，left = 4
- 第 2 次：mid = (4+6)/2 = 5，a[5] = 11，11 > 9，目标在左边，right = 4
- 第 3 次：mid = (4+4)/2 = 4，a[4] = 9，找到目标！
共比较 3 次，选 B。
💡 二分查找的精髓：每次比较都排除一半的元素，所以时间复杂度是 O(log n)。7 个元素只需要 3 次比较，1000 个元素也只需要 10 次！
练习题 6（程序阅读题）
题目： 阅读以下递归函数，f(5) 的返回值是？（ ）
cpp
int f(int n) {
if (n <= 1) return 1;
return n * f(n - 1);
}A. 5
B. 15
C. 120
D. 720
🔑 点击查看答案与解析
答案： C
解析：
这是求阶乘的递归函数：f(n) = n!
- f(1) = 1
- f(2) = 2 × f(1) = 2 × 1 = 2
- f(3) = 3 × f(2) = 3 × 2 = 6
- f(4) = 4 × f(3) = 4 × 6 = 24
- f(5) = 5 × f(4) = 5 × 24 = 120
选 C。
递归的三要素：①基线条件（n≤1时返回1）；②递归条件（n×f(n-1)）；③递归向基线靠近（每次n减1）。
练习题 7（单选题）
题目： 关于贪心算法，以下说法正确的是（ ）
A. 贪心算法每一步选局部最优，最终一定能得到全局最优解
B. 贪心算法和动态规划的区别是贪心更快
C. 只要问题具有最优子结构，就一定能用贪心算法
D. 贪心算法需要同时满足贪心选择性质和最优子结构
🔑 点击查看答案与解析
答案： D
解析：
- A 错误：贪心不一定总能得到最优解，必须满足特定条件
- B 错误：核心区别不是速度，而是决策方式——贪心不回头，DP 考虑所有选择
- C 错误：最优子结构是必要条件但不充分，还需要贪心选择性质
- D 正确 ✅：贪心算法的两个基本要素：①贪心选择性质（局部最优导致全局最优）；②最优子结构（大问题最优解包含子问题最优解）
💡 记忆技巧：贪心 = 勇往直前不回头；DP = 三思而后行。贪心需要证明"每步最优 = 全局最优"，而 DP 是枚举所有选择取最优。
练习题 8（单选题）
题目： 归并排序的时间复杂度是？（ ）
A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)
🔑 点击查看答案与解析
答案： B
解析：
归并排序采用分治策略：
- 分解：将数组二分，共 log n 层
- 合并：每层需要 O(n) 的时间合并两个有序数组
- 总时间 = 层数 × 每层时间 = log n × n = O(n log n)
选 B。
💡 常见排序复杂度对比：
- 冒泡/插入/选择排序：O(n²)
- 归并/快速排序（平均）：O(n log n)
- 快速排序最坏：O(n²)（已有序时）
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ GESP 五级 · 核心速记卡 │
├─────────────────────────────────────────────┤
│ 1. 素数定义：大于1，只有1和自身两个因数 │
│ 2. 1既不是素数也不是合数 │
│ 3. gcd(a,b) × lcm(a,b) = a × b │
│ 4. 辗转相除法：gcd(a,b) = gcd(b, a%b) │
│ 5. 埃氏筛：素数标记倍数，O(n log log n) │
│ 6. 线性筛：每个合数被最小质因子筛掉，O(n) │
│ 7. 单链表：单向遍历，删除需找前驱 │
│ 8. 高精度：倒序存储，低位在前 │
│ 9. 二分查找：必须有序，O(log n) │
│ 10. 二分答案：答案有单调性 + check函数 │
│ 11. 递归三要素：基线条件+递归条件+向基线靠近│
│ 12. 记忆化搜索：缓存结果，避免重复计算 │
│ 13. 分治三步曲：分解 → 解决 → 合并 │
│ 14. 归并排序：O(n log n)，稳定 │
│ 15. 贪心两要素：贪心选择性质 + 最优子结构 │
└─────────────────────────────────────────────┘