GESP 专题 · CCF 编程能力等级认证（C++）

专题说明：本页按 CCF GESP 官方《编程能力等级认证标准（一级至八级）》整理 1-8 级核心考点与易错点，并挂载 CCF 官方真题（2024 年 3/6/9/12、2025 年 3/6/9/12、2026 年 3/6/9 月共 11 场次，选择/判断可作答，编程题附参考程序）。左侧导航点击直达各级，页面滚动自动同步高亮。每道真题均可点击作答：选择题点选选项、判断题点选对/错，提交后显示对错与解析。内容与本站 01-20 章节页互相补充，考纲与考点均可在章节页查证。

知识点直达

直达学习点击下方章节链接直接进入对应章节页的具体知识点小节；「页内」链接可快速跳到本级核心考点。

GESP 考试体系速览

考试形式全国统一线下机考，每年约 4 次（3 月、6 月、9 月、12 月）；每级满分 100 分，60 分及以上通过；1 级为必考级别，单次成绩 ≥ 90 分可跨一级报考（以 CCF 当年公告为准）。

说明：级别与章节对应关系参考 CCF GESP 官方考纲整理；报名时间、网址与具体规则以 CCF 官网当年公告为准。级别定位口诀：1-3 级语法筑基、4-6 级算法突破、7-8 级综合建模。

GESP 1 级 · 入门启蒙

一级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）了解计算机的基本构成（CPU，内存，I/O 设备等），了解 Windows、Linux 等操作系统基本概念和常见操作，了解计算机的历史及在现代社会中的常见应用。
2. （2）熟悉集成开发环境使用（例如 Dev C++）：创建文件、编辑文件、保存文件、编译、解释、调试。
3. （3）掌握基础的 cin 语句、scanf 语句、cout 语句、printf 语句，赋值语句等。
4. （4）掌握标识符、关键字、常量、变量、表达式的概念。
5. （5）掌握常量与变量的命名、定义、作用、初始化与赋值以及变量的自加与自减运算。
6. （6）掌握基础算术表达式：加、减、乘、除、整除、求余。
7. （7）掌握逻辑运算与（&&）、或（||）、非（！）。
8. （8）掌握关系运算：大于、大于等于、小于、小于等于、等于、不等于。
9. （9）掌握基础的数据类型的定义和使用（整型、实数型、字符型、布尔型）。
10. （10）掌握顺序结构程序的编写。
11. （11）掌握分支结构程序的编写，掌握 if 语句、if-else 语句、switch 语句，了解三目运算。
12. （12）掌握循环结构程序的编写，掌握 for、while、do-while 循环语句的使用以及 continue 语句和 break 语句在循环中的应用。
13. （13）理解程序的注释和调试的概念。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：120 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 1 级是零基础起点，考察计算机基础与编程环境、变量的定义与使用、基本数据类型（整型、浮点型、字符型、布尔型）、基本运算（算术、关系、逻辑）以及输入输出语句。命题约 30% 为本级知识点、70% 为更基础常识，属于「背了就有分」的入门级别。

知识目标掌握顺序、循环、分支的简单程序结构，可以使用集成开发环境进行编程与调试，完成单一功能的程序设计。

核心考点

• 计算机基础与编程环境：C++ 属于编译型语言，程序需先编译再运行；机考使用在线评测系统，平时把「新建文件 → 写码 → 编译 → 运行」流程练成肌肉记忆。
• 变量定义与使用：先声明后使用，变量名规则（字母/数字/下划线、不能以数字开头），未初始化的局部变量值不确定。
• 基本数据类型：int / long long / float / double / char / bool 的用途与取值范围；char 与 int 互通——'A' 的 ASCII 是 65。
• 输入输出：cin >> 与 cout << 的基本用法，endl 换行；scanf / printf 对应格式（%d、%f、%c）。
• 运算与表达式：算术（+ - * / %）、关系（> < == !=）、逻辑（&& || !）运算符及优先级；整数除法会截断小数。
• 控制结构：顺序、if / else 分支、for / while 循环；循环变量的初值、条件、步进三个要素。

易错点

1. 整型除法直接截断：7 / 2 得 3 而非 3.5，需要浮点要先转 double 再除。
2. 混淆赋值 = 与相等 ==，if (a = 1) 恒真且会改值。
3. 变量未初始化就使用，读程序题要警惕输出不确定值。
4. 循环边界多 1 / 少 1：for (int i = 1; i <= n; i++) 恰好 n 次，写成 i < n 就少一次。
5. cin 与 getline 混用导致读入错位：cin >> 后换行残留需要先清空缓冲区。

GESP 2 级 · 基础进阶

二级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）了解计算机存储的基本概念及分类，了解随机存储器（RAM）、只读存储器（ROM）和高速缓冲存储器（Cache）的功能及区别。
2. （2）了解计算机网络的概念，了解计算机网络的分类（广域网（WAN）、城域网（MAN）、局域网（LAN）），了解计算机网络的层级结构及作用（TCP/IP 四层模型与 OSI 七层模型），了解不同层级的重要协议，了解 IP 地址及子网划分。
3. （3）了解程序设计语言的几大分类及特点（机器语言、汇编语言、高级语言），了解常见的高级语言（C++、Python 等）。
4. （4）了解流程图的概念及基本表示符号，掌握绘制流程图的方法，能正确使用流程图描述程序设计的三种基本结构。
5. （5）了解编码的基本概念，了解 ASCII 编码原理，能识别常用字符的 ASCII 码（空格：32、“0”：48、“A”：65、“a”：97），并掌握 ASCII 码和字符之间相互转换的方法。
6. （6）掌握数据类型的转换：强制类型转换和隐式类型转换。
7. （7）掌握多层分支结构，掌握 if 语句、if...else 语句、switch 语句，及相互嵌套的方法。
8. （8）掌握多层循环结构，掌握 for 语句、while 语句、do...while 语句，及相互嵌套的方法。
9. （9）掌握常用的数学函数：绝对值函数、平方根函数、最大值函数、最小值函数、随机数函数理解相应的算法原理。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：120 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 2 级在 1 级基础上引入计算机的存储与网络常识、程序设计语言的特点、流程图、ASCII 编码、数据类型转换、多层分支与循环嵌套结构，以及常用数学函数（绝对值、平方根、max / min）。

知识目标掌握程序基本设计，能够使用简单数学函数；可以独立完成包含分支语句、循环语句等比较综合的案例，可以使用分支循环嵌套结构。

核心考点

• ASCII 编码：'A'=65、'a'=97、'0'=48；char 与 int 可以互相转换（char ch = 'A'; int k = ch; 得 65）。
• 数据类型转换：隐式转换（int→double 自动）、显式强转 (int)3.9 截断为 3；注意 long long 与 int 的范围边界。
• 多层分支：if / else if / else 的匹配规则（else 就近配对）、switch-case 的 break 语义。
• 循环嵌套：外层循环每转一圈，内层循环完整跑一遍；双重循环总次数 = 外层次数 × 内层次数。
• 常用数学函数：abs（整数绝对值）、fabs（浮点绝对值）、sqrt（平方根）、max / min（取大取小），需 #include <cmath> / <algorithm>。
• 流程图与算法描述：认识开始/结束框、判断框、处理框，会读简单流程图。

易错点

1. char 参与运算默认按 ASCII 值：'A' + 1 得 66（即 'B'），想输出字符需强转 char。
2. 强转只截断不舍入：(int)3.9 得 3，不是 4。
3. 自增自减先后顺序：a++ 先用后加、++a 先加后用，读程序题要画时间线逐变量标注。
4. 嵌套循环中 break 只跳出最近一层循环，不是全部。
5. sqrt 对负数、% 对 0 除数会产生运行时错误，要注意数据范围预判。

GESP 3 级 · 循环与编码

三级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）了解二进制数据编码：原码、反码、补码。
2. （2）掌握数据的进制转换：二进制、八进制、十进制、十六进制。
3. （3）掌握位运算：与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)的基本使用方法及原理。
4. （4）了解算法的概念与描述，熟练运用自然语言、流程图、伪代码方式来描述算法。
5. （5）C++ 一维数组基本应用（不包括变长数组）；Python 列表、字典、元组、集合的基本应用、内置函数以及列表解析的使用。
6. （6）掌握字符串及其函数的使用包括但不限于大小写转换、字符串搜索、分割、替换。
7. （7）理解枚举算法、模拟算法的原理及特点，可以解决实际问题。
8. （8）理解模拟算法、模拟算法的原理及特点，可以解决实际问题。

注：官方原文第（8）条与第（7）条表述重复，此处按原文保留。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：120 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 3 级进入算法启蒙：数据编码（原码、反码、补码）、进制转换（二进制、八进制、十进制、十六进制）、位运算（与 &、或 |、非 ~、异或 ^、左移 <<、右移 >>）、算法描述、一维数组基本应用、字符串及其函数，以及枚举法与模拟法，并首次引入复杂度概念。

知识目标掌握数据编码、进制转换、位运算等知识，掌握一维数组、字符串及函数的使用，能够独立使用模拟法、枚举法解决对应的算法问题。

核心考点

• 进制转换：任意 R 进制按位权展开转十进制；十进制除 R 取余逆序转 R 进制；二↔八按 3 位一组、二↔十六按 4 位一组（8421 法）。必考 10↔2、10↔8、10↔16、2↔16。
• 数据编码：原码 / 反码 / 补码的含义；补码表示负数（-1 的 8 位补码是 11111111）；n 位有符号整数范围 [-2ⁿ⁻¹, 2ⁿ⁻¹-1]。
• 位运算：& 与、| 或、^ 异或（相同为 0、不同为 1）、~ 取反、<< 左移（乘 2）、>> 右移（整除 2）；异或性质：x ^ x = 0、x ^ 0 = x。
• 一维数组：连续内存、同类型、下标从 0 开始；常见操作：遍历、求和、最值、计数。
• 字符串：C 风格字符数组与 string 类型；常用函数 length / substr / find / 拼接；数字字符与数字互转 ch - '0'、大写转小写 ch - 'A' + 'a'。
• 枚举法与模拟法：枚举所有可能情况逐一检验（如穷举两位数的条件判断）；按题意逐步模拟过程（日期推算、报数出列）。
• 复杂度概念引入：单层循环 O(n)、双层 O(n²)、每次翻倍的循环 O(log n)。

易错点

1. 除 R 取余必须「逆序」读余数，顺序读必错。
2. 八进制没有数字 8、二进制没有数字 2、十六进制 A~F 表示 10~15（F 是 15 不是 16）。
3. 位运算优先级低于 ==：if ((x & 1) == 0) 的括号不能省，否则先算 == 再算 &。
4. 左移可能溢出：1 << 31 超出 int 范围，用 long long 或 1LL << 31。
5. 数组下标越界不报错但结果不确定；字符数组要留结束符 \0 的位置。

GESP 4 级 · 函数与排序

四级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）理解 C++ 指针类型的概念，掌握指针类型变量的定义、赋值、解引用。
2. （2）掌握 C++ 结构体、二维及多维数组（不包括变长数组）的基本概念及使用；掌握 Python 复合数据类型的嵌套使用。
3. （3）理解模块化编程思想，掌握函数（不包含匿名函数、类的括号运算符重载）的声明、定义及调用，掌握形参与实参的概念及区别。
4. （4）掌握变量作用域的概念，理解全局变量与局部变量的区别。
5. （5）掌握函数参数的传递方式：C++ 值传递、引用传递、指针传递；Python 值传递、引用传递。
6. （6）掌握递推算法基本思想、递推关系式的推导以及递推问题求解。
7. （7）掌握排序算法的概念，了解内排序和外排序的概念及差别，理解排序算法的时间复杂度、空间复杂度、使用场景以及稳定性。
8. （8）掌握排序算法中的冒泡排序、插入排序、选择排序的算法思想、排序步骤及代码实现。
9. （9）简单算法复杂度的估算，含多项式、指数复杂度。
10. （10）掌握文件操作中的重定向，实现文件读写操作，了解文本文件的分类，掌握写操作、读操作、读写操作。
11. （11）了解异常处理机制，掌握异常处理的常用方法。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：120 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 4 级要求掌握函数的定义与调用、形参与实参、作用域；指针类型的概念及基本应用；函数参数传递（值传递、引用传递、指针传递）；结构体；二维数组与多维数组；递推；排序概念与稳定性及冒泡/插入/选择排序；简单算法复杂度估算（多项式、指数）；文件重定向与文件读写；异常处理。

知识目标掌握函数的定义、调用及参数传递；掌握二维数组与多维数组的使用技巧；掌握常用排序算法、文件读写和异常处理，能够解决递推相关问题。

核心考点

• 函数：定义 / 调用 / 返回值；形参与实参；局部变量与全局变量作用域；默认值传递下改形参不影响实参。
• 参数传递：值传递（拷贝）、引用传递（int &x 直接改实参）、指针传递（int *p 改指向的内容）；const T & 既能避免拷贝又能防误改。
• 结构体：自定义数据类型；结构体数组排序必须自己写 cmp 比较函数，先比主关键字、相等再比次关键字。
• 二维数组：行优先存储；矩阵转置、行列求和、对角线求和、局部最大子矩阵是高频题型，本质是行列下标变换。
• 排序与稳定性：冒泡、插入、归并稳定（相等元素相对顺序不变）；选择、快排不稳定；对几乎有序的数组插入排序最快（O(n)）。
• 递推：由前项推后项（斐波那契、上楼梯方案数、杨辉三角构造），关键是找递推关系与边界。
• 复杂度估算：单层 O(n)、双层 O(n²)、递归二分 O(log n)；会估算多项式与指数级复杂度。
• 文件读写与异常处理：freopen 重定向 / ifstream / ofstream；try-catch 基础。

易错点

1. 值传递改形参不影响实参——读程序题高频陷阱，「形参改名后实参变不变」默认不变。
2. 排序稳定性记反：用「两个相同分数按姓名字典序排」理解，稳定则相对顺序不变。
3. 二维数组行列混淆：a[i][j] 中 i 是行、j 是列，遍历时外层行内层列。
4. 结构体数组排序 cmp 返回 bool 不要写 a > b 写成 a - b（那是 int 比较函数）。
5. 递推忘记边界：f(0)、f(1) 初始化错会导致全盘错。

GESP 5 级 · 数论与分治

五级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）掌握初等数论相关知识的概念和应用，包括素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性等。
2. （2）掌握 C++ 数组模拟高精度加法、减法、乘法和除法的相关知识。
3. （3）掌握链表的创建、插入、删除、遍历和反转操作，理解单链表、双链表、循环链表的区别。
4. （4）掌握辗转相除法（也称欧几里得算法）、素数表的埃氏筛法和线性筛法、唯一分解定理的原理和应用。
5. （5）掌握算法复杂度估算方法（含多项式、对数）。
6. （6）掌握二分查找和二分答案算法（也称二分枚举法）的基本原理，能够在有序数组中快速定位目标值。
7. （7）掌握递归算法的基本原理，能够应用递归解决问题，能够分析递归算法的时间复杂度和空间复杂度，了解递归的优化策略。
8. （8）掌握贪心算法的基本原理，理解最优子结构，能够使用贪心算法解决相关问题。
9. （9）掌握分治算法的基本原理，能够使用归并排序和快速排序对数组进行排序。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：180 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 5 级进入「算法设计」层面：递归；初等数论（辗转相除法、埃氏筛 / 线性筛、唯一分解定理）；数组模拟高精度（加、减、乘、除）；单链表、双链表、循环链表；二分查找 / 二分答案；贪心算法；分治算法（归并排序和快速排序）；算法复杂度估算（多项式、指数、对数）。业内称「四级之前拼勤奋，五级之后拼思维」。

知识目标进入算法设计层面，要求具备设计算法的能力；知识点常交叉，如二分 + 高精度、贪心 + 排序。

核心考点

• 递归：自己调用自己；递归求阶乘、斐波那契、汉诺塔；用「压栈 / 出栈」画图法手推递归执行过程。
• 数论：质数判定（sqrt 试除法）、埃氏筛（标记起点 j = i * i）、线性筛（每个数只被最小质因子筛一次）、辗转相除法求 gcd、唯一分解定理。
• 高精度：n ≤ 10^1000 或结果超过 64 位整数时使用；存储用倒序数组，逐位进位 / 借位模拟四则运算。
• 链表：单链表、双链表、循环链表；插入删除只需改指针、随机访问要顺着找；「随机访问选数组，频繁增删选链表」。
• 二分：二分查找在有序数组定位；二分答案处理「最大…的最小值 / 最小…的最大值」，模板 while (l <= r) + check(mid) 单调判定。
• 贪心：局部最优推导全局最优；区间类贪心统一套路——按右端点升序排序再扫一遍能选就选（活动安排、区间选点）。
• 分治：可拆同类型子问题、子问题互相独立、能合并答案；归并排序与快速排序都是分治思想，归并稳定、快排不稳定。
• 复杂度估算：对数 O(log n)、线性 O(n)、O(n log n)、O(n²)、指数 O(2ⁿ) 的区分与选择。

易错点

1. 埃氏筛起点写成 2 * i 会重复标记，正确起点是 j = i * i。
2. 欧拉筛的 if (i % primes[j] == 0) break; 是保证「最小质因子只筛一次」的关键，读程序题常考。
3. 二分边界：while (l <= r) 时 mid 取 (l + r) / 2 防溢出；区间不收敛会死循环。
4. 贪心必须证明局部最优能推出全局最优，被反例 HACK 就换 DP。
5. 高精度进位 / 借位顺序：先算本位再统一进位；最高位进位要扩展长度。

GESP 6 级 · 树/搜索/DP

六级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）掌握树的基本概念，掌握其构造与遍历的相关算法。
2. （2）掌握哈夫曼树、完全二叉树、二叉排序树的相关概念和应用。
3. （3）理解哈夫曼编码、格雷编码相关原理并能进行简单应用。
4. （4）掌握深度优先搜索算法（DFS）、宽度优先搜索算法（也称广度优先搜索算法，BFS）、二叉树的搜索算法的概念及应用，能够根据现实问题，选择合适的搜索算法。
5. （5）掌握简单动态规划的算法思想，能够使用代码解决相应的一维动态规划问题和简单背包问题。
6. （6）掌握面向对象的思想，了解封装、继承、多态的基本概念，并掌握类的创建和基本的使用方法。
7. （7）掌握栈、队列、循环队列的基本定义，应用场景和常见操作。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：180 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 6 级引入三大核心主题：树（树的定义、构造与遍历；哈夫曼树、完全二叉树、二叉排序树；哈夫曼编码、格雷编码）、搜索（深度优先搜索 DFS、宽度优先搜索 BFS、二叉树的搜索算法）、动态规划（一维动态规划、简单背包问题），同时考察栈、队列、循环队列，以及面向对象的思想、类的创建。动态规划被称为「第一道真正的思维门槛」。

知识目标掌握二叉树与遍历、哈夫曼 / 格雷编码、DFS / BFS、一维 DP 与简单背包、栈与队列（含数组模拟）、OOP 入门。

核心考点

• 树与二叉树：节点、度、深度、叶子等概念；必背公式——叶子数 n0 = 度 2 节点数 n2 + 1；深度 k 的二叉树最多 2^k - 1 个节点。
• 二叉树遍历：先序（根左右）、中序（左根右）、后序（左右根）、层序；还原口诀「先序 / 后序定根，中序分左右」；先序 + 后序不能唯一还原。
• 哈夫曼树与编码：每次合并权值最小的两棵，叶子带权路径和最小；哈夫曼编码是前缀编码。完全二叉树、二叉排序树（BST）的性质。
• 栈与队列：栈 LIFO（递归调用栈、括号匹配、表达式求值、单调栈）；队列 FIFO（BFS 逐层扩散、约瑟夫环）；数组模拟栈 top = -1 为空，数组模拟队列 [head, tail) 左闭右开。
• DFS 与 BFS：DFS 用栈（递归）、求可行解 / 计数 / 全排列；BFS 用队列、求最短步数；记忆化搜索把指数级优化成多项式级。
• 动态规划：定义状态 → 写转移方程 → 设边界 → 填表 / 记忆化；一维 DP（斐波那契、爬楼梯）、简单 0-1 背包（dp[j] = max(dp[j], dp[j-w] + v)）。
• 面向对象入门：类与对象、成员变量与成员函数、构造函数、封装思想。

易错点

1. 公式记混：n0 = n2 + 1 是叶子数与度为 2 节点数的关系；深度 k 满二叉树节点数 2^k - 1（k 从 1 开始计数）。
2. 只有先序 + 后序不能唯一还原二叉树（分不清左右子树）。
3. BFS 忘标记已访问会死循环 / 爆内存；DFS 回溯忘撤销状态导致结果错误。
4. 约瑟夫环手推要先固定起点，报数到 m 出列，别把起点数错。
5. DP 边界设错：求最大用 -INF、求最小用 +INF 初始化，否则取 max / min 被 0 污染。
6. 递归过深爆栈：深度 10^6 级别要用循环 / 显式栈替代递归。

GESP 7 级 · 图论与复杂 DP

七级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）掌握数学库常用函数（三角、对数、指数），三角函数包括 sin(x)，cos(x) 等；对数函数包括 log10(x)：返回 x 以 10 为底的对数，log2(x)：返回 x 以 2 为底的对数；指数函数包括 exp(x)：计算指数函数，返回 x 的以 e 为底的指数函数。
2. （2）掌握复杂动态规划（二维动态规划、动态规划最值优化）。包括区间动态规划、最长上升子序列（LIS）、最长公共子序列（LCS）等内容，理解基于滚动数组等降低动态规划空间复杂度的方法。
3. （3）图的定义及基本图论算法。包括图的定义、图的种类（有向图、无向图），图节点的度的概念。掌握编程时图的数据结构表示，以及基于深度优先搜索（DFS）和广度优先搜索（BFS）的图搜索与遍历方法，图的泛洪（flood fill）算法。
4. （4）掌握哈希表的概念与知识及其应用。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：180 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 7 级图论与高级 DP 登堂入室：图的定义及遍历、图论基本算法（深度优先遍历、广度优先遍历、泛洪算法 Flood Fill）、哈希表；复杂动态规划（二维动态规划、动态规划最值优化）；数学库常用函数（三角、对数、指数）。哈希表成为常用工具。

知识目标掌握图遍历与 Flood Fill、哈希表（unordered_map / unordered_set）、二维 DP 与 LCS / LIS、数学库函数。

核心考点

• 图的定义：顶点、边、有向 / 无向、稠密 / 稀疏；必背边数公式——n 个顶点无向图最多 n(n-1)/2 条边，有向图最多 n(n-1) 条。
• 存图方式：邻接矩阵（稠密图）、邻接表（vector 或数组模拟链表：head[u] 存第一条边编号，to[i] / next[i] 存终点和下一条边）。
• 图遍历：DFS 深搜（求连通块、路径）、BFS 广搜（无权最短路：dist[v] == -1 判断未访问，dist[v] = dist[u] + 1）；BFS 只在边权相同（或为 1）时求最短路。
• 泛洪算法 Flood Fill：从一个起点向四周扩散标记连通区域，可用 BFS / DFS 实现，用于岛屿数量、区域染色等问题。
• 哈希表：unordered_map / unordered_set 平均 O(1) 查找；去重 + 排序 + 查存在三合一场景；哈希冲突与负载因子概念。
• 二维 DP：最长公共子序列 LCS（dp[i][j] 表示 s 前 i 个与 t 前 j 个）、最长上升子序列 LIS（可 O(n log n) 优化）、矩阵路径、数字三角形。
• 最值优化：用单调队列 / 单调栈 / 贪心剪枝降低 DP 复杂度（如滑动窗口最值）。
• 数学库函数：三角函数 sin / cos / tan、对数 log、指数 exp / pow，以及取整函数。

易错点

1. 最大边数公式记反：无向图 n(n-1)/2、有向图 n(n-1)，注意是否允许自环与重边。
2. BFS 不能处理带正权边的最短路（要 Dijkstra）；Dijkstra 不能处理负权边（要 SPFA / Bellman-Ford）。
3. LCS 转移：s[i]==t[j] 时 dp[i][j] = dp[i-1][j-1] + 1，否则取 max(dp[i-1][j], dp[i][j-1])，边界 dp[0][*]=dp[*][0]=0。
4. 哈希容器无序，遍历顺序不保证；用 set / map 才有有序遍历。
5. 邻接表 head 数组要初始化为 -1，idx 从 0 累加，别忘 cnt = 0。

GESP 8 级 · 组合数学与优化

八级考纲 GESP真题下载链接

展开知识点详述与题型分布

（一）知识点详述

1. （1）掌握计数原理。包括加法原理和乘法原理。
2. （2）掌握排列与组合基础知识。包括排列、组合的基本概念，及能实现基础排列和组合编程问题的一般方法。
3. （3）掌握杨辉三角形（又称帕斯卡三角形）的概念。
4. （4）掌握倍增法概念。了解倍增法的时间复杂度。
5. （5）掌握代数与平面几何基础知识（初中数学部分）。包括方程的概念及一元一次方程、二元一次方程的基本求解技巧，求基础平面几何概念、求基本图形（如长方形、三角形、圆形等）的面积等。
6. （6）掌握图论算法及综合应用技巧。包括最小生成树的概念、kruskal 算法、prim 算法，掌握最短路径的概念、单源最短路径的 dijkstra 算法、Floyd 算法等。理解实现同一功能的不同算法的比较，并可以灵活解决相关问题。
7. （7）算法的时间和空间效率分析。能够掌握较为复杂算法的时间和空间复杂度分析方法，能够分析各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及动态规划算法等）的时间和空间复杂度。
8. （8）算法优化。理解不同方法求解一个问题在时间复杂度和空间复杂度上的差异，理解使用数学知识辅助求解问题的技巧（如可以用循环求出等差数列的和，也可以用数学公式求出等差数列的和），掌握一般的算法优化技巧。

（五）题型分布

题型	题数	每题分值	小计
单选题	15	2 分	30 分
判断题	10	2 分	20 分
编程题	2	25 分	50 分
合计	27	—	100 分

考试时间：180 分钟；满分 100 分（60 分及以上通过，以 CCF 当年公告为准）。

级别概述GESP 8 级是综合应用阶段，思维量接近 CSP-S 入门难度：计数原理、排列与组合、杨辉三角；倍增法；代数与平面几何（初中数学部分）；图论算法及综合应用（最小生成树、单源最短路）；较复杂算法的空间和时间效率分析；算法优化。

知识目标综合应用组合数学、图论与算法优化，具备分析复杂算法时空复杂度并选择合适优化手段的能力。

核心考点

• 计数原理：加法原理、乘法原理；排列 P(n,m) = n!/(n-m)!、组合 C(n,m) = n!/(m!(n-m)!)，注意去重与有序 / 无序区分。
• 杨辉三角：递推构造组合数 C(n,k) = C(n-1,k-1) + C(n-1,k)；二项式展开系数。
• 倍增法：预处理 2 的幂次信息，快速跳跃定位；典型应用 ST 表（区间最值）、LCA（最近公共祖先）的倍增跳法。
• 代数与平面几何（初中数学）：平面直角坐标系、两点距离、中点坐标、简单图形面积，用于几何类建模题。
• 最小生成树：Kruskal（边排序 + 并查集，适合稀疏图）、Prim（适合稠密图）；n 个顶点 n-1 条边连通且总权值最小。
• 单源最短路：Dijkstra（堆优化 O((V+E)logV)，不能有负权边）、SPFA / Bellman-Ford（可处理负权）；BFS 仅在边权为 1 时适用。
• 时空效率分析：大 O 记号、最坏 / 平均复杂度、空间换时间（预处理、记忆化、前缀和）、常数优化。
• 算法优化：去冗余计算、滚动数组降维、二分替代线性扫描、预处理查表、IO 读入优化。

易错点

1. 排列与组合混淆：选完还要排顺序用排列（P），只选不排用组合（C）。
2. 组合数直接乘会溢出：C(30,15) 已超 int，用 long long 或杨辉三角递推取模。
3. Kruskal 忘记并查集判环：加入边前要 find(a) != find(b)，否则出现环。
4. Dijkstra 堆优化：优先队列存 pair<dist, node>，更新时 dist[v] > d + w 才入队，否则会重复入队。
5. 倍增边界：跳 2^k 步时 k 从大到小枚举，先处理 k 大的；LCA 先对齐深度再一起跳。
6. 优化不等于炫技：先保证正确性，再考虑常数优化，选错算法复杂度必 TLE。