第1章 GESP 七级考点总览

🎯 本章学习目标

通过本章的学习，你将能够：

建立全局视野：清晰了解 GESP 七级考试的 5 大知识模块及其重要程度
掌握数学库函数：熟练使用三角函数、对数函数、指数函数，注意弧度制
掌握复杂DP：理解二维DP、LIS、LCS、区间DP等进阶动态规划
理解图的基础：掌握图的存储方式（邻接矩阵/邻接表）和DFS/BFS遍历
掌握泛洪算法：理解Flood Fill思想，能解决岛屿数量、连通块问题
理解哈希表：掌握哈希函数、冲突解决方法和STL中的unordered_map/set
识别考点频率：知道各模块的出题频率和常见题型
制定备考策略：根据自身情况合理安排复习计划
理解滚动数组优化：掌握DP的空间优化技巧
为深入学习打基础：建立知识框架，为后续各模块深入学习做好准备

🗺️ 本章知识图谱

GESP 七级知识体系
├── 数学库函数
│   ├── 三角函数（sin/cos/tan）
│   │   ├── 参数是弧度制
│   │   └── 角度转弧度：π/180
│   ├── 对数函数
│   │   ├── log(x) = 自然对数（底e）
│   │   ├── log10(x) = 以10为底
│   │   └── log2(x) = 以2为底
│   ├── 指数函数
│   │   ├── exp(x) = e^x
│   │   └── pow(a,b) = a^b
│   └── 其他
│       ├── sqrt(x) 开平方
│       ├── abs/fabs 绝对值
│       └── ceil/floor 取整
├── 复杂动态规划
│   ├── 二维DP
│   │   └── 网格路径计数
│   ├── LIS（最长上升子序列）
│   │   ├── O(n²) 基础版
│   │   └── O(n log n) 优化（了解）
│   ├── LCS（最长公共子序列）
│   │   └── dp[i][j] 二维数组
│   ├── 区间DP
│   │   └── 先枚举长度，再枚举起点
│   └── 滚动数组优化
│       ├── 空间从 O(n²) 降到 O(n)
│       └── 注意遍历方向
├── 图的定义及遍历
│   ├── 基本概念
│   │   ├── 顶点、边、度
│   │   ├── 有向图 / 无向图
│   │   └── 连通图 / 非连通图
│   ├── 存储方式
│   │   ├── 邻接矩阵（稠密图）
│   │   └── 邻接表（稀疏图）
│   ├── DFS 深度优先搜索
│   │   ├── 递归/栈实现
│   │   └── visited 标记
│   └── BFS 广度优先搜索
│       ├── 队列实现
│       └── 无权图最短路径
├── 泛洪算法（Flood Fill）
│   ├── 核心思想：连通区域染色
│   ├── 实现方式
│   │   ├── BFS 实现（常用）
│   │   └── DFS 实现
│   ├── 典型应用
│   │   ├── 岛屿数量
│   │   ├── 连通块大小
│   │   └── 图像填充
│   └── 方向数组
│       ├── 四连通（上下左右）
│       └── 八连通（加对角线）
└── 哈希表
    ├── 基本概念
    │   ├── 哈希函数（映射到下标）
    │   ├── 理想时间复杂度 O(1)
    │   └── 键值对存储
    ├── 冲突解决
    │   ├── 链地址法（拉链法）
    │   ├── 开放寻址法
    │   └── 再哈希法
    ├── C++ STL
    │   ├── unordered_map
    │   └── unordered_set
    └── 应用场景
        ├── 快速查找
        ├── 去重
        └── 计数

一、📋 5大模块全景一览

序号	模块名称	一句话概括
1	数学库函数	三角、对数、指数函数的使用与易错
2	复杂动态规划	二维DP、LIS/LCS、区间DP、滚动数组
3	图的定义及遍历	邻接矩阵/表存储，DFS与BFS
4	泛洪算法（Flood Fill）	基于BFS/DFS的连通区域填充
5	哈希表	哈希函数、冲突解决与实际应用

二、📖 各模块简要说明

以下是5大模块的考点速览，帮你快速建立印象。后续每期文章会逐个展开深入讲解，敬请关注。

📐 模块一：数学库函数

考什么： 三角函数、对数函数、指数函数的使用

函数类型	常用函数	说明
三角函数	sin(x), cos(x), tan(x)	参数用弧度制，不是角度
对数函数	log(x), log10(x), log2(x)	log(x)是自然对数（底为e），log10是以10为底
指数函数	exp(x), pow(a,b)	exp(x)返回e的x次方，pow(a,b)返回a的b次方

易错点：

三角函数参数是弧度，角度需转换：弧度 = 角度 × π / 180
注意double和float的精度区别，建议统一用double
log(x)不是以10为底，以10为底要用log10(x)

🧩 模块二：复杂动态规划

考什么： 二维动态规划、区间DP、LIS、LCS、滚动数组优化

1. 二维DP 典型场景：网格路径计数。状态dp[i][j]表示走到第i行第j列的方案数。

2. LIS（最长上升子序列）

// O(n²)写法
for(int i = 0; i < n; i++) {
    dp[i] = 1;
    for(int j = 0; j < i; j++)
        if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
}

3. LCS（最长公共子序列）

// dp[i][j] = a前i个 与 b前j个 的LCS长度
if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

4. 滚动数组优化 当状态转移只依赖上一行/前一个状态时，用两个一维数组交替使用，把空间从O(n²)降到O(n)。

易错点：

滚动数组注意遍历方向，01背包要逆序遍历
区间DP枚举顺序：先枚举区间长度，再枚举起点
DP状态定义要满足最优子结构和无后效性

🕸️ 模块三：图的定义及遍历

考什么： 图的存储、DFS、BFS

图的存储方式：

存储方式	适用场景	空间复杂度
邻接矩阵	稠密图	O(n²)
邻接表	稀疏图	O(n+m)

DFS（深度优先搜索）：

用递归或栈实现
适合：连通性检测、路径搜索
核心模板：标记访问 → 遍历邻接点 → 递归

BFS（广度优先搜索）：

用队列实现
适合：无权图最短路径、层序遍历
核心模板：入队 → 出队访问 → 未访问邻接点入队

易错点：

DFS注意防止重复访问，必须标记visited
BFS求最短路径只适用于无权图
邻接表遍历邻接点时注意边的方向（有向图 vs 无向图）

🌊 模块四：图论算法——泛洪算法（Flood Fill）

考什么： 基于BFS/DFS的连通区域填充

一句话理解： 从一个起点出发，把所有连通的、满足条件的区域全部"染上颜色"。

典型应用：

岛屿数量统计
图像区域填充
连通块大小计算

BFS实现模板：

💻 提示：auto [x, y] 为 C++17 结构化绑定语法；旧版 Dev-C++（TDM-GCC 4.9.2）编译报错时，可改写为 int x = q.front().first, y = q.front().second;（详见六级第 3 章 BFS 模板说明）。

void floodFill(int sx, int sy) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    visited[sx][sy] = true;
    while(!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for(int i = 0; i < 4; i++) {  // 上下左右四个方向
            int nx = x + dx[i], ny = y + dy[i];
            if(合法且未访问) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

易错点：

一般用BFS实现Flood Fill（判断题常考）
注意边界检查，防止数组越界
四连通用上下左右，八连通还要加四个对角方向

🔑 模块五：哈希表

考什么： 哈希表概念、冲突解决、实际应用

核心概念：

哈希函数：将键映射到数组下标
理想情况下查找/插入/删除都是O(1)

冲突解决方案：

方法	说明	特点
链地址法	同一位置用链表串联	空间灵活，常用
开放寻址法	冲突时找下一个空位	实现简单
再哈希法	换一个哈希函数重新映射	减少聚集

C++中的哈希表：

unordered_map — 键值对存储
unordered_set — 只存键，去重利器

易错点：

哈希冲突时不能直接覆盖已有元素（破坏数据完整性）
闭散列法（开放寻址）需要逐个探测空位
选择题常考：哪种方案不能合理解决冲突

三、📊 考点总表

模块	重要程度	出题形式	核心考点	易错点
数学库函数	⭐⭐⭐	选择/判断/编程	三角函数（弧度制）、对数函数、pow/sqrt	弧度不是角度；log是自然对数
复杂动态规划	⭐⭐⭐⭐⭐	编程题/选择	二维DP、LIS、LCS、滚动数组优化	状态定义、转移方程、遍历方向
图的定义及遍历	⭐⭐⭐⭐⭐	选择/编程	邻接矩阵/表、DFS、BFS	visited标记、无权图最短路径
泛洪算法	⭐⭐⭐⭐	编程题/选择	Flood Fill、连通块、岛屿数量	边界检查、四连通vs八连通
哈希表	⭐⭐⭐⭐	选择/判断/编程	哈希函数、冲突解决、unordered_map	冲突不能直接覆盖、链地址法

四、💡 备考建议

复习策略

重点突破动态规划：七级考试中DP占比最高，LIS和LCS是重中之重，务必手写代码
图论要画图：图的问题一定要在草稿纸上画图，邻接表和邻接矩阵要熟练转换
哈希表重概念：哈希表常考概念题（冲突解决方法），要理解每种方法的原理
Flood Fill要模板化：泛洪算法有固定模板，背熟后套模板即可
数学函数要细心：注意弧度制、精度问题，多做练习避免粗心错误

时间规划

第1-2周：复杂动态规划（重点中的重点）
第3周：图的基础 + 泛洪算法
第4周：哈希表 + 数学库函数 + 综合模拟

刷题建议

LIS / LCS 至少各写 3 遍，做到闭卷能写
Flood Fill 模板要背熟，岛屿数量是经典题
哈希表概念题要多做，各种冲突解决方法要清楚
数学函数要自己试一遍，确认输出结果

五、📝 实战练习

练习题 1（单选题）

题目： C++ 中 sin(90) 的值大约是多少？（）

A. 1
B. 0
C. 约 0.89
D. 约 -0.95

🔑 点击查看答案与解析

答案： C

解析： C++ 三角函数的参数是弧度制，不是角度制！

90 弧度 ≈ 90 / (2π) ≈ 14.32 圈，即 90 - 14×2π ≈ 90 - 87.96 = 2.04 弧度
sin(2.04 弧度) ≈ sin(约117度) ≈ 0.89

如果是 90 度，需要转换为弧度：sin(90 * M_PI / 180) = 1

选 C。

🔥 高频考点：三角函数参数是弧度不是角度！每次使用前都要转换。

---

练习题 2（单选题）

题目： 下列哪种方法不能解决哈希冲突？（）

A. 链地址法
B. 开放寻址法
C. 再哈希法
D. 直接覆盖法

🔑 点击查看答案与解析

答案： D

解析： 常见的哈希冲突解决方法：

✅ 链地址法（拉链法）：同一位置的元素用链表串联
✅ 开放寻址法：冲突时找下一个空位（线性探测、二次探测等）
✅ 再哈希法：换一个哈希函数重新计算位置

❌ 直接覆盖法：冲突时直接覆盖已有元素，这会导致数据丢失，不能算"解决"冲突。

选 D。

🔥 高频考点：冲突解决方法的选择题几乎每年都考。

---

练习题 3（单选题）

题目： 对于一个有 n 个顶点、m 条边的稀疏图，最适合的存储方式是？（）

A. 邻接矩阵
B. 邻接表
C. 二维数组
D. 一维数组

🔑 点击查看答案与解析

答案： B

解析：

邻接矩阵：用 n×n 的二维数组，空间复杂度 O(n²)，适合稠密图
邻接表：每个顶点的边用链表/数组存储，空间复杂度 O(n+m)，适合稀疏图

稀疏图（边数少）用邻接表省空间；稠密图（边数多）用邻接矩阵访问快。

选 B。

🍎 生活比喻：邻接矩阵像全班同学的关系表（每个人和每个人的关系都记下来，不管熟不熟）；邻接表像每个人的通讯录（只记自己认识的人）。

---

练习题 4（判断题）

题目： 最长上升子序列（LIS）的 O(n²) 动态规划解法中，dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： LIS 的经典 DP 定义：

dp[i] = 以第 i 个元素结尾的最长上升子序列的长度
转移方程：dp[i] = max(dp[j] + 1)，其中 j < i 且 a[j] < a[i]
初始：dp[i] = 1（每个元素自身就是长度为1的子序列）
答案：max(dp[i])

💡 注意：答案不是 dp[n-1]，而是所有 dp[i] 中的最大值！因为最长上升子序列不一定以最后一个元素结尾。

---

练习题 5（单选题）

题目： Flood Fill（泛洪算法）最适合解决下列哪个问题？（）

A. 排序数组
B. 求最短路径（有权图）
C. 统计岛屿数量
D. 求最大公约数

🔑 点击查看答案与解析

答案： C

解析： Flood Fill 的核心是：从一个起点出发，把所有连通的、满足条件的区域全部"染上颜色"。

典型应用：

✅ 岛屿数量统计（数连通块个数）
✅ 连通块大小计算
✅ 图像区域填充（油漆桶工具）
✅ 迷宫可达性判断

A 是排序算法，B 应该用 Dijkstra 等最短路算法（📚 拓展 · 超纲，七级只要求无权图 BFS），D 是数论问题。

选 C。

💡 Flood Fill 可以用 DFS 或 BFS 实现，BFS 更常用（避免栈溢出）。

---

练习题 6（单选题）

题目： 对于两个字符串 "ABCBDAB" 和 "BDCABA"，它们的最长公共子序列（LCS）长度是？（）

A. 3
B. 4
C. 5
D. 6

🔑 点击查看答案与解析

答案： B

解析： LCS 状态转移方程：

如果 a[i-1] == b[j-1]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

对于 "ABCBDAB" 和 "BDCABA"：

公共子序列可以是 "BCBA"（长度4）或 "BDAB"（长度4）等
最长公共子序列长度为 4

选 B。

⚠️ 注意：子序列不要求连续，子串才要求连续。LCS 是子序列！

---

练习题 7（判断题）

题目： 用邻接表存储有向图时，统计某个顶点的出度需要遍历整个邻接表。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 邻接表中，每个顶点 v 对应一个链表，存储的是从 v 出发的所有边。

所以：

出度：看 v 的链表长度 → O(出度)，不需要遍历整个邻接表
入度：需要遍历所有顶点的链表来找指向 v 的边 → O(n+m)

题目说"统计出度需要遍历整个邻接表"是错的，出度直接看该顶点的链表长度就行。

💡 记忆：邻接表存的是"从这里出发"的边，所以出度好算，入度难算。

---

练习题 8（单选题）

题目： 关于动态规划的滚动数组优化，下列说法正确的是？（）

A. 滚动数组可以把时间复杂度降低一个维度
B. 滚动数组优化后，代码会变得更简单
C. 滚动数组只能优化空间，不能优化时间
D. 所有DP问题都可以用滚动数组优化

🔑 点击查看答案与解析

答案： C

解析：

A 错误 ❌：滚动数组优化的是空间复杂度，不是时间复杂度
B 错误 ❌：滚动数组优化后代码通常更复杂（要注意遍历方向等）
C 正确 ✅：滚动数组只能优化空间，时间复杂度不变
D 错误 ❌：只有当状态转移只依赖上一行/前一状态时才能用滚动数组

💡 滚动数组就像计算器的"内存"键：你只需要上一步的结果，不需要把所有历史都记下来。

---

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│         GESP 七级 · 必背速记卡              │
├─────────────────────────────────────────────┤
│  1. 三角函数参数是弧度，角度×π/180          │
│  2. log(x)是自然对数(底e)，log10是底10      │
│  3. LIS: dp[i]=以i结尾的LIS长度             │
│  4. LIS转移: dp[i]=max(dp[j]+1), a[j]<a[i]  │
│  5. LCS: dp[i][j]=a前i个和b前j个的LCS长度   │
│  6. LCS转移: 相等=左上+1, 不等=max(上,左)    │
│  7. 邻接矩阵适合稠密图，邻接表适合稀疏图     │
│  8. 图的DFS/BFS都要标记visited              │
│  9. BFS求最短路径只适用于无权图             │
│ 10. Flood Fill=连通区域染色，用BFS/DFS      │
│ 11. 哈希冲突解决：链地址法、开放寻址法       │
│ 12. 哈希冲突不能直接覆盖，会丢数据           │
│ 13. unordered_map/set底层是哈希表           │
│ 14. 滚动数组优化空间，不优化时间             │
│ 15. 区间DP：先枚举长度，再枚举起点           │
└─────────────────────────────────────────────┘

第1章 GESP 七级考点总览 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、📋 5大模块全景一览 ​

二、📖 各模块简要说明 ​

📐 模块一：数学库函数 ​

🧩 模块二：复杂动态规划 ​

🕸️ 模块三：图的定义及遍历 ​

🌊 模块四：图论算法——泛洪算法（Flood Fill） ​

🔑 模块五：哈希表 ​

三、📊 考点总表 ​

四、💡 备考建议 ​

复习策略 ​

时间规划 ​

刷题建议 ​

五、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（单选题） ​

练习题 4（判断题） ​

练习题 5（单选题） ​

练习题 6（单选题） ​

练习题 7（判断题） ​

练习题 8（单选题） ​

⭐ 必背速记卡 ​

第1章 GESP 七级考点总览

🎯 本章学习目标

🗺️ 本章知识图谱

一、📋 5大模块全景一览

二、📖 各模块简要说明

📐 模块一：数学库函数

🧩 模块二：复杂动态规划

🕸️ 模块三：图的定义及遍历

🌊 模块四：图论算法——泛洪算法（Flood Fill）

🔑 模块五：哈希表

三、📊 考点总表

四、💡 备考建议

复习策略

时间规划

刷题建议

五、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（单选题）

练习题 4（判断题）

练习题 5（单选题）

练习题 6（单选题）

练习题 7（判断题）

练习题 8（单选题）

⭐ 必背速记卡