GESP C++&Python 七级认证考试大纲、课程设计

（一）考核目标

掌握常用数学库函数，了解相关函数概念与定义。掌握复杂动态规划，包括二维动态规划、求LIS、LCS等内容，并掌握利用滚动数组等的优化方法。了解图的定义与广搜和深搜的算法，泛洪算法。了解哈希表的概念和知识。

（二）知识点详述

(1) 掌握数学库常用函数(三角、对数、指数), 三角函数包括 sin(x), cos(x)等; 对数函数包括 log10(x): 返回 x 以 10 为底的对数, log2(x): 返回 x 以 2 为底的对数; 指数函数包括 exp(x): 计算指数函数, 返回 x 的以 e 为底的指数函数。

(2) 掌握复杂动态规划(二维动态规划、动态规划最值优化)。包括区间动态规划、最长上升子序列(LIS)、最长公共子序列(LCS)等内容, 理解基于滚动数组等降低动态规划空间复杂度的方法。

(3) 图的定义及及基本图论算法。包括图的定义、图的种类(有向图、无向图), 图节点的度的概念。掌握编程时图的数据结构表示, 以及基于深度优先搜索(DFS)和广度优先搜索(BFS)的图搜索与遍历方法, 图的泛洪(flood fill)算法。

(4) 掌握哈希表的概念与知识及其应用。

（三）知识块与知识点描述

知识块构成

• • 数学库函数
• • 复杂动态规划
• • 图的定义及遍历
• • 图论算法
• • 哈希表

知识点描述

1. 1. 数学库函数
• • 三角函数
• • 对数函数
• • 指数函数
2. 2. 复杂动态规划
• • 二维动态规划、动态规划最值优化
• • 区间动态规划
• • 求最长上升子序列 (LIS)
• • 求最长公共子序列 (LCS)
• • 基于滚动数组的动态规划空间复杂度优化
3. 3. 图的定义及遍历
• • 图的概念
• • 图的广度优先遍历
• • 图的深度优先遍历
4. 4. 图论算法
• • 图的泛洪算法 (flood fill)
5. 5. 哈希表
• • 哈希表的概念与知识及其应用

（五）题型分布

• • 单选题：15道 (2分/道)
• • 判断题：10道 (2分/道)
• • 编程题：2道 (25分/道)
• • 考试时间：180分钟

课程总览

本课程旨在帮助学生系统掌握GESP七级考试大纲所要求的全部知识点。课程设计以知识点详述和考核目标为核心，结合知识点描述进行模块化分解，同时参考题型分布进行针对性训练。课程总时长建议为12次课，每次3课时（共180分钟），与考试时间对齐，以模拟真实考试环境。

课程模块与课时分配

模块一：数学库函数详解与应用

课时： 2次课 (共6课时)考核目标对应： 掌握常用数学库函数，了解相关函数概念与定义。

第一课：数学函数基础与三角函数

• • 核心知识点：
• • 数学库的引入与基本使用规范。
• • 三角函数：sin(x), cos(x), tan(x) 的原理、参数（弧度制）与返回值。
• • 反三角函数与角度/弧度转换的简单介绍。
• • 学习目标：
• • 能够正确导入并使用数学库。
• • 理解弧度概念，并能完成角度与弧度的互换计算。
• • 使用三角函数解决简单的几何与周期问题。
• • 课堂练习：
• • 计算特定角度的正弦、余弦值。
• • 已知直角三角形边长，求解角度。
• • 课后作业：
• • 编程实现根据时针和分针位置计算夹角。

第二课：指数函数、对数函数与综合应用

• • 核心知识点：
• • 指数函数 exp(x) 的概念与应用（如计算复利、自然增长）。
• • 对数函数 log10(x), log2(x), log(x)（自然对数）的概念与应用。
• • 对数在复杂度分析、信息论（如分贝计算）中的意义。
• • 学习目标：
• • 掌握指数与对数的互逆关系。
• • 能运用指数/对数函数解决增长、衰减类问题。
• • 理解对数复杂度在实际算法中的体现。
• • 课堂练习：
• • 计算细菌培养的指数增长数量。
• • 利用对数求解方程 2^x = 1024。
• • 课后作业：
• • 编程实现一个简单的数据压缩比计算（利用对数表示信息量）。

模块二：复杂动态规划（DP）精讲

课时： 4次课 (共12课时)考核目标对应： 掌握复杂动态规划，包括二维动态规划、求LIS、LCS等内容，并掌握利用滚动数组等的优化方法。

第三课：动态规划核心思想回顾与二维DP基础

• • 核心知识点：
• • 动态规划“状态定义”、“状态转移方程”、“初始化”、“填表顺序”、“返回值”五步法回顾。
• • 从一维DP过渡到二维DP：状态扩展的思想。
• • 经典入门问题：矩阵中的最短路径（如最小路径和）。
• • 学习目标：
• • 巩固DP思维框架。
• • 能独立定义二维DP状态并推导转移方程。
• • 课堂练习：
• • 分析“最小路径和”问题的DP解法。
• • 课后作业：
• • 编程解决“不同路径”问题。

第四课：序列型动态规划（一）—— 最长上升子序列（LIS）

• • 核心知识点：
• • LIS问题的经典定义。
• • O(n²) 的DP解法：状态定义 dp[i] 表示以 nums[i] 结尾的LIS长度。
• • O(n log n) 的贪心+二分查找优化解法（思路介绍）。
• • 学习目标：
• • 掌握LIS的标准DP解法。
• • 了解优化解法的存在及其优势。
• • 课堂练习：
• • 手动推导给定序列的LIS长度及DP表。
• • 课后作业：
• • 编程实现O(n²)的LIS解法。

第五课：序列型动态规划（二）—— 最长公共子序列（LCS）

• • 核心知识点：
• • LCS问题的经典定义。
• • 二维DP解法：状态定义 dp[i][j] 表示文本1前i个字符与文本2前j个字符的LCS长度。
• • 三种情况的状态转移分析（字符相等、不相等）。
• • 如何回溯构造出具体的LCS。
• • 学习目标：
• • 掌握LCS的二维DP状态设计和转移方程。
• • 能通过DP表反向找出一个最长公共子序列。
• • 课堂练习：
• • 对给定两个字符串，画出完整的DP表。
• • 课后作业：
• • 编程求解LCS长度，并尝试输出一个LCS。

第六课：动态规划优化与区间DP导论

• • 核心知识点：
• • 动态规划最值优化概念引入。
• • 滚动数组优化：将二维DP空间复杂度从O(mn)降至O(n)或O(min(m, n))的原理与实现（以LCS为例）。
• • 区间动态规划简介：定义 dp[i][j] 表示区间 [i, j] 上的最优解，如石子合并问题。
• • 学习目标：
• • 理解空间优化的动机，掌握滚动数组的实现技巧。
• • 了解区间DP的经典模型和循环遍历顺序。
• • 课堂练习：
• • 将上一课的LCS代码改为使用滚动数组实现。
• • 分析石子合并问题的状态转移。
• • 课后作业：
• • 编程实现矩阵链乘法（最优括号化）的区间DP解法。

模块三：图论基础与算法

课时： 4次课 (共12课时)考核目标对应： 了解图的定义与广搜和深搜的算法，泛洪算法。了解哈希表的概念和知识。

第七课：图的基本概念与表示方法

• • 核心知识点：
• • 图的基本定义：顶点、边（有向/无向）、权值。
• • 图的相关概念：度（入度、出度）、连通性、路径、环。
• • 图的编程表示：邻接矩阵、邻接表（C++ vector/ Python list）。
• • 学习目标：
• • 能根据问题描述抽象出图模型。
• • 能根据图的特点（稠密/稀疏）选择合适的存储方式。
• • 课堂练习：
• • 给定一个图，画出其邻接矩阵和邻接表。
• • 课后作业：
• • 实现一个Graph类，支持邻接表存储和添加边的操作。

第八课：图的深度优先搜索（DFS）遍历与应用

• • 核心知识点：
• • 图的深度优先搜索（DFS）递归与栈实现。
• • 通过DFS判断图的连通分量、检测环（有向图与无向图）。
• • 基于DFS的拓扑排序（针对有向无环图）。
• • 学习目标：
• • 掌握图的DFS遍历框架。
• • 能将DFS应用于解决连通性、环检测等问题。
• • 课堂练习：
• • 在上一课的Graph类中实现DFS遍历，并计算连通分量数量。
• • 课后作业：
• • 编程实现有向图的拓扑排序。

第九课：图的广度优先搜索（BFS）遍历与应用

• • 核心知识点：
• • 图的广度优先搜索（BFS）队列实现。
• • BFS在无权图最短路径求解中的应用。
• • BFS与DFS的对比：适用场景分析。
• • 学习目标：
• • 掌握图的BFS遍历框架。
• • 能用BFS求解单源最短路径（边权为1）。
• • 课堂练习：
• • 在Graph类中实现BFS，并求解从某点到其他各点的最短距离。
• • 课后作业：
• • 编程解决迷宫最短路径问题（二维网格上的BFS）。

第十课：图论算法——泛洪算法（Flood Fill）与哈希表初探

• • 核心知识点：
• • 泛洪算法 (Flood Fill)：算法思想，通常使用DFS或BFS实现。
• • 泛洪算法的经典应用：图像连通区域标记、棋盘类游戏（如扫雷）、岛屿问题。
• • 哈希表：概念、原理（键-值映射、哈希函数、冲突处理）。
• • 在C++ (std::unordered_map)和Python (dict)中的基本使用。
• • 学习目标：
• • 理解泛洪算法实质是连通性搜索，并能用DFS/BFS实现。
• • 理解哈希表的核心思想，掌握其基本API操作。
• • 课堂练习：
• • 使用BFS/DFS解决“岛屿数量”问题（Flood Fill）。
• • 使用哈希表统计一段文本中单词出现的频率。
• • 课后作业：
• • 编程解决“湖泊计数”问题。
• • 利用哈希表优化两数之和问题的求解。

模块四：总复习与模拟实战

课时： 2次课 (共6课时)

第十一课：知识体系串讲与高频考点分析

• • 核心内容：
• • 回顾所有知识模块：数学函数、复杂DP、图论、哈希表。
• • 梳理各知识点之间的关联（如DFS在图和Flood Fill中的共用）。
• • 分析七级标准中单选题和判断题可能考察的概念细节。
• • 讲解经典考题的解题思路。
• • 学习目标：
• • 形成系统化的知识网络。
• • 具备解答理论题目的能力。

第十二课：全真模拟考试与题目精讲

• • 核心内容：
• • 进行一次180分钟的模拟考试，严格按大纲题型分布命题（15单选+10判断+2编程）。
• • 模拟考试后立即进行直播或线下讲评。
• • 编程题精讲：重点分析模拟考中两道编程题的解题思路、代码实现、易错点及优化方法。
• • 考试策略与时间分配指导。
• • 学习目标：
• • 体验真实考试节奏和压力。
• • 查漏补缺，定位自身薄弱环节。
• • 获得最终的应试技巧指导。

课程设计说明：

1. 1. 理论与实践结合：每次课均包含理论讲解、课堂随练和课后作业，确保知识点及时巩固。
2. 2. 难度递进：课程遵循从基础到复杂的原则，例如动态规划从二维基础到LIS/LCS，再到优化技巧。
3. 3. 代码驱动：强调动手编程，所有核心算法均要求实现，培养解决实际编程题的能力。
4. 4. 目标导向：最终模拟考试完全对标GESP七级大纲，帮助学生实现从学习到应试的无缝过渡。