GESP C++ 6级考试复习资料 & 历年真题考点解析.
- 2026-11-08 08:11:40
QUOTE
六级真正拉开差距的，不是再刷一百道题，而是把树、背包、类练成肌肉记忆。
适用考试：CCF 编程能力等级认证（GESP）C++ 六级。考试时间 180 分钟（比四级、五级多 60 分钟），满分 100 分；单选题 15 题（30 分）、判断题 10 题（20 分）、编程题 2 题（50 分）。
资料按官方六级大纲的 7 大知识块整理，覆盖 2023 年 9 月至 2026 年 6 月共 11 套真题。建议先看：树与遍历怎么还原、0/1 背包为何必须逆序、构造函数为什么不能是虚函数。
SYLLABUS 01
考试大纲总览
六级与五级的区别——“从基础算法到数据结构+面向对象+高级算法”
五级的核心是初等数论、链表、二分算法、递归分治贪心、高精度运算，而六级发生了质的飞跃：
五级：学的是“怎么用算法解决问题” 六级：学的是“怎么用数据结构组织数据 + 用高级算法求解 + 用面向对象编程来设计程序”
六级新增的核心内容：
1. 树与二叉树——数据结构从“线性”升级到“树形”，这是最重要的非线性数据结构
2. 哈夫曼树与编码——数据压缩的经典算法，理解“最优二叉树”
3. DFS与BFS搜索算法——从“遍历数组”到“遍历树/图”，两大核心搜索算法
4. 动态规划——比递推、贪心更强大的算法思想，核心是“最优子结构+重叠子问题”
5. 面向对象编程——从“面向过程”到“面向对象”，类、继承、封装、多态
6. 栈与队列——两种基础而重要的线性数据结构
7. 格雷编码——一种特殊的二进制编码方式
考试内容——7大知识块
根据官方六级大纲（7条知识点详述）和11套真题的统计：
①
知识块：树与二叉树
大纲对应条号：第1、2条
核心知识点：树的定义、构造与遍历（前序/中序/后序/层序）；完全二叉树；二叉排序树（BST）；节点数/深度/性质计算
难度：★★★★★
考试占比：约25%
②
知识块：哈夫曼树与编码
大纲对应条号：第2、3条
核心知识点：哈夫曼树构造、WPL计算、前缀编码、数据压缩
难度：★★★★
考试占比：约12%
③
知识块：搜索算法（DFS/BFS）
大纲对应条号：第4条
核心知识点：深度优先搜索（栈/递归）、广度优先搜索（队列）、遍历顺序、时间复杂度
难度：★★★★
考试占比：约13%
④
知识块：动态规划
大纲对应条号：第5条
核心知识点：最优子结构、重叠子问题、一维线性DP、0/1背包问题、完全背包、状态转移方程
难度：★★★★★
考试占比：约18%
⑤
知识块：面向对象编程（C++类）
大纲对应条号：第6条
核心知识点：类的定义、构造函数/析构函数、封装/继承/多态、虚函数、访问权限、静态成员
难度：★★★★
考试占比：约18%
⑥
知识块：栈与队列
大纲对应条号：第7条
核心知识点：栈（先进后出）、队列（先进先出）、循环队列（判满/判空）、应用场景
难度：★★★
考试占比：约10%
⑦
知识块：格雷编码
大纲对应条号：第3条
核心知识点：格雷码生成规则、性质（相邻仅一位不同）、递归构造
难度：★★★
考试占比：约4%
三大主线：树结构、动态规划、面向对象，缺一不可。
1. 树结构（含哈夫曼树、BST）——覆盖约40%的题目
2. 动态规划（含背包问题）——覆盖约18%的题目，外加编程题
3. 面向对象编程（C++类与特性）——覆盖约18%的题目
KNOWLEDGE 02
各知识点详解
知识块①：树与二叉树——“最重要的非线性数据结构”
1.1 树的基本概念——“从根出发，分层生长”
树是由n（n≥0）个节点组成的有限集合。当n=0时称为空树。树有一个根节点，其他节点分属若干互不相交的子树。
基本术语：
· 根：最顶层的节点，一棵树只有一个根
· 叶子：没有子节点的节点
· 父节点 / 子节点：上下直接相连的节点
· 兄弟节点：同一个父节点的多个子节点
· 深度：从根到该节点的路径上的边数（根深度为0）
· 高度：从该节点到最远叶子的边数（叶子高度为0）
1.2 二叉树——“每个节点最多两个孩子”
二叉树是每个节点最多有两个子树的树结构，分左子树和右子树。非常重要：二叉树不是树的特例，而是一种独立的树结构。
（2025年12月第6题） 练习题： 一棵二叉树中，每个节点最多有几个孩子？
答案：2个。
1.3 二叉树的三种遍历方式——必考！几乎每套题都有
遍历就是按照某种顺序访问树中的每个节点。三种最基本的遍历方式：
前序遍历（先序遍历）
访问顺序：根 → 左 → 右
口诀：“根左右”
记忆法：先访问根
中序遍历
访问顺序：左 → 根 → 右
口诀：“左根右”
记忆法：根在中间
后序遍历
访问顺序：左 → 右 → 根
口诀：“左右根”
记忆法：最后访问根
（2024年3月第12题、2024年9月第8题、2025年6月第8题、2025年9月第7题、2026年3月第7题、2026年6月第8题）
经典题型一：由前序+中序还原二叉树，求后序遍历
这是六级考试中的最经典题型，几乎每套题都会出现。我们用一个例子来逐步讲解：
例题：前序遍历为 ABCDEF，中序遍历为 CBAEDF，求后序遍历。
解题步骤： （这是一道“分治”问题）
第一步： 前序的第一个元素是根。
· 前序：A B C D E F → A是根
第二步： 在中序中找到根A的位置，左边的都是左子树，右边的都是右子树。
· 中序：C B A E D F
· 左子树（中序）：C B（在A左边）
· 右子树（中序）：E D F（在A右边）
第三步： 左子树的前序是 B C，中序是 C B → B是左子树的根，C是B的左孩子
第四步： 右子树的前序是 D E F，中序是 E D F → D是右子树的根，E是D的左孩子，F是D的右孩子
最终树结构：
A
/ \
B D
/ / \
C E F
后序遍历（左右根）： C → B → E → F → D → A
（2026年3月第7题） 练习题： 前序为ABDCEGFHI，中序为DBAEGCHFI，求后序？
· 根A，左子树（前序B D，中序D B），右子树（前序C E G F H I，中序E G C H F I）
· 左子树：B是根，D是B的左孩子
· 右子树：C是根，左子树（前序E G，中序E G）→ G是E的右孩子，右子树（前序F H I，中序H F I）→ F是根，H是F的左孩子，I是F的右孩子
· 后序：BDGEHIFCA
经典题型二：由一种遍历推树结构
（2026年3月第8题） 练习题： 已知中序遍历为D B E A F C G，以下哪种遍历序列组合可以唯一确定二叉树？
· A. 前序+后序 B. 后序+中序 C. 前序+中序 D. 以上都可以
· 答案：B、C。前序+中序或后序+中序都可以唯一确定二叉树。但仅有前序+后序不能唯一确定。
1.4 完全二叉树——“除最后一层外全满，且最后一层节点靠左”
定义： 一棵二叉树中，只有最下面两层的节点可以小于2，且最下一层的节点全部集中在左侧。（2025年6月第6题）
（2025年12月第6题、2026年6月第6题） 练习题： 如何判断一棵树是完全二叉树？
答案：层序遍历，遇到空节点后不应再出现非空节点。
重要性质：
1. 节点数n与高度h的关系： h = ⌊log₂n⌋ + 1（2025年12月判断第10题）
2. 数组存储： 下标为i的节点，左孩子下标为2i，右孩子下标为2i+1（2024年9月第9题、2025年9月第8题）
3. 完全二叉树可以用数组完美存储，空间利用率高（2024年6月判断第7题）
（2024年3月第10题） 练习题：完全二叉树有5个叶子节点，最多有多少个节点？
完全二叉树中，叶子节点数 = 内部节点数 + 1（当度为2的节点数=内部节点数-1时）。最多情况下，最后一层除了叶子还可以有度1的节点。5个叶子，最多可以有 5 + 4 + 1 = 10个节点。.. 实际上需要更精确的计算：完全二叉树中，如果叶子节点数为n，总结点数最多为2n。
1.5 二叉排序树（BST，也称二叉搜索树）——“左小右大”
定义： 左子树所有节点的值 < 根节点的值 < 右子树所有节点的值。左右子树也分别是二叉排序树。（2023年12月判断第8题）
（2025年6月判断第4题） 练习题：二叉排序树的中序遍历结果是什么？
答案：递增有序序列。这是BST最重要的性质之一。
三大操作的时间复杂度：
· 查找： 平均O(log n)，最坏O(n)（退化为链表时，2025年12月第13题）
· 插入： 从根开始，比根小往左，比根大往右，直到空位置插入（2025年6月第13题）
· 删除： 删除有两个孩子的节点时，需要找右子树的最小值（或左子树的最大值）替换（2025年9月第14题）
（2025年6月判断第5题） 练习题： 如果二叉搜索树退化为链表，则查找的时间复杂度为？
答案： O(n)。因为树退化为一条链，查找需要逐个比较。
1.6 满二叉树——“每个节点都有两个孩子”
定义： 所有叶子节点都在同一层，且每个非叶子节点都有两个子节点。
性质： 深度为k的满二叉树共有 2^k - 1 个节点。（2024年6月第10题）
（2024年6月第10题） 练习题： 5层满二叉树有多少个节点？
答案： 2^5 - 1 = 31个节点。
1.7 二叉树深度计算
递归实现——（2023年12月第9题）：
int Depth(TreeNode* root) {
if (root == nullptr) return 0;
return max(Depth(root->left), Depth(root->right)) + 1;
}
1.8 树的存储方式
二叉树可以用数组（完全二叉树用数组存储，下标从1开始，左孩子2i，右孩子2i+1）或链表（结构体+左右指针）存储。（2023年12月第10题）
（2025年6月第7题） 练习题： 用数组表示完全二叉树，下标为i的节点，左孩子下标为多少？
答案： 2i。
知识块②：哈夫曼树与哈夫曼编码——“最优二叉树”
2.1 什么是哈夫曼树？
哈夫曼树（Huffman Tree） 也称最优二叉树，是带权路径长度（WPL）最小的二叉树。（2024年3月第1题）
带权路径长度（WPL）：所有叶子节点的权值 × 路径长度（从根到该叶子的边数）之和。（2026年3月第9题）
2.2 哈夫曼树的构造过程——“贪心算法”
构造步骤（每一步都是贪心选择）：
1. 将所有节点按权值从小到大排序
2. 每次取出权值最小的两个节点合并
3. 新节点的权值为两者之和，重新放入集合
4. 重复直到只剩一个节点（这个节点就是根）
（2024年6月判断第1题） 练习题：哈夫曼编码的构造使用了什么策略？
答案： 贪心策略。
2.3 哈夫曼树的重要性质
1. 哈夫曼树是二叉树（2024年3月判断第1题） ✓
2. 哈夫曼树中没有度为1的节点（2026年3月第10题）
3. 叶子节点数n与总节点数m的关系： m = 2n - 1（2026年3月第10题、2026年6月第10题）
4. 哈夫曼编码不具有唯一性——同一组频率可能有多种不同的哈夫曼树（2025年9月判断第2题）
2.4 哈夫曼编码——“前缀编码”
定义： 用哈夫曼树构造的编码，任意一个字符的编码都不是另一个字符编码的前缀，因此称为“前缀编码”。（2025年6月判断第2题）
性质：
· 变长编码：频率高的字符编码短，频率低的编码长（2025年3月第2题）
· 无损压缩：可以完全还原原始数据（2023年9月判断第7题）
· 解码无需分隔符：因为前缀编码特性，编码可以连续拼接，解码时不会混淆（2026年3月判断第5题）
（2023年12月第7题） 练习题： 对“hello world”进行哈夫曼编码，最少需要多少比特？
统计字符频率→构造哈夫曼树→计算每个字符的编码长度→频率×编码长度之和。
2.5 哈夫曼编码的计算步骤
（2024年6月第8题） 例题： 对字符串“classmycls”进行哈夫曼编码，最少需要多少比特？
解题步骤：
1. 统计字符频率：c:2, l:1, a:1, s:2, m:1, y:1
2. 构造哈夫曼树（每次合并最小的两个）
3. 每个字符的编码长度就是它在树中的深度
4. 最少比特数 = Σ(频率 × 编码长度)
知识块③：搜索算法（DFS与BFS）
3.1 深度优先搜索（DFS）——“一条路走到黑，再回头”
核心思想： 从根节点出发，沿着每个分支路径尽可能深入，直到不能再深入为止，然后回溯到上一个分支点继续探索。（2023年12月判断第4题）
形象理解： 就像走迷宫，选一条路一直走到底，走不通就退回到上一个岔路口，换一条路继续走。
实现方式：
· 递归方式：函数调用自身（最简单）
· 非递归方式：用栈模拟（2025年6月判断第9题、2024年6月判断第9题）
时间复杂度： O(V + E)，V为顶点数，E为边数（2023年9月判断第9题）
DFS的应用： 二叉树遍历（前序/中序/后序都是DFS）、图的遍历、树的深度计算、路径查找、连通性判断。
（2025年12月第11题） 非递归前序遍历（用栈）：
stack<Node*> st;
st.push(root);
while (!st.empty()) {
Node* node = st.top(); st.pop();
cout << node->val; // 访问根
if (node->right) st.push(node->right); // 先右后左（因为栈是后进先出）
if (node->left) st.push(node->left);
}
3.2 广度优先搜索（BFS）——“逐层推进，不抢跑”
核心思想： 从根节点出发，逐层遍历，先访问距离根最近的节点，再访问次近的，依次向外扩展。（2024年3月第8题）
形象理解： 就像投石入水，水波一圈一圈向外扩散——先近后远，逐层推进。
实现方式：队列（先进先出）（2024年12月第12题、2024年6月判断第6题）
时间复杂度： O(n)（2025年9月第12题）
BFS的应用：层序遍历、最短路径、树的右视图（每层最右侧节点，2026年3月第12题）
（2025年3月第11题） BFS实现代码（用队列）：
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front(); q.pop();
// 处理节点
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
3.3 DFS vs BFS 对比表
核心思想
深度优先搜索（DFS）： 沿着分支深入到底再回溯
广度优先搜索（BFS）： 逐层向外扩展
辅助数据结构
深度优先搜索（DFS）： 栈（递归/非递归）
广度优先搜索（BFS）： 队列
遍历顺序
深度优先搜索（DFS）： 按深度优先，一条分支走完才换分支
广度优先搜索（BFS）： 按层，同一层节点全部访问完才到下一层
时间复杂度
深度优先搜索（DFS）： O(V+E)
广度优先搜索（BFS）： O(V+E)
空间复杂度
深度优先搜索（DFS）： 最坏O(V)（递归栈深度）
广度优先搜索（BFS）： 最坏O(V)（队列长度）
适用场景
深度优先搜索（DFS）： 路径搜索、树的遍历、连通性判断
广度优先搜索（BFS）： 最短路径、层序遍历、拓扑排序
知识块④：动态规划——“最优子结构 + 重叠子问题”
4.1 动态规划的核心思想——“大事化小，小事化了”
定义： 将复杂问题分解为若干重叠子问题，通过求解子问题的最优解，逐步构建出原问题的最优解。
两个基本性质——必考！
1. 最优子结构： 问题的最优解包含子问题的最优解（2024年3月第11题、2024年6月第11题）
2. 重叠子问题： 子问题被重复计算，可以通过存储中间结果（如数组）避免重复计算
（2024年6月判断第10题） 练习题：0-1背包问题使用贪心算法可以保证获得最优解吗？
答案： 不能。贪心不一定得到最优解，动态规划才能保证最优解。
4.2 一维线性动态规划——“最简单的DP”
经典例题——不相邻元素最大和（打家劫舍问题）：
（2024年3月第7题、2025年9月第10题、2026年6月第14题）
问题描述： 一排房屋，每个房屋有若干现金，不能偷相邻的房屋，求最多能偷多少钱。
逐步推导：
1. 定义状态： dp[i] 表示前i个房屋能偷到的最大金额
2. 状态转移： 对于第i个房屋，有两种选择：
· 不偷：dp[i] = dp[i-1]
· 偷：dp[i] = dp[i-2] + nums[i]（因为不能偷相邻的，所以前i-2个的最大值+当前）
· 取最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
1. 初始化： dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
int prev2 = nums[0], prev1 = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
int cur = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
4.3 0/1背包问题——必考！几乎每套题都有
问题描述： 有n个物品，每个物品有重量w[i]和价值v[i]，背包容量为C，每个物品最多选1个，求最大价值。
（2025年6月第15题、2025年9月第15题、2025年12月第14题、2026年6月第15题）
二维状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
· dp[i][j]：前i个物品放入容量为j的背包的最大价值
· dp[i-1][j]：不放第i个物品
· dp[i-1][j-w[i]] + v[i]：放第i个物品
一维滚动数组优化（空间从O(nC)降到O(C)）：
// 注意：内层循环必须从大到小（逆序）！
// 因为如果从小到大，物品会被重复使用（变成完全背包）
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = C; j >= w[i]; j--) // 逆序！
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
（2026年3月判断第9题） 练习题：0-1背包一维动态规划中，内层循环为什么必须逆序？
答案： 为了保证每个物品只被选择一次。如果正序，dp[j-w[i]]可能已经包含了当前物品，导致物品被重复使用。
4.4 完全背包——“每个物品可以选无限次”
与0/1背包的唯一区别： 每个物品可以选无限次。
一维滚动数组（内层循环从小到大）：
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= C; j++) // 正序！允许重复使用
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
（2025年6月编程题1、2026年6月编程题1）
4.5 动态规划 vs 贪心算法
决策方式
动态规划： 考虑所有可能的子问题，取最优
贪心算法： 每一步选当前最优，不做“回头看”
子问题重叠
动态规划： 有重叠子问题，需要存储中间结果
贪心算法： 无重叠子问题
最优性保证
动态规划： 保证全局最优
贪心算法： 不一定保证全局最优
适用场景
动态规划：最优子结构+重叠子问题
贪心算法： 局部最优可推出全局最优
知识块⑤：面向对象编程（C++类与对象）
5.1 面向对象三大特性——必考！
1. 封装（Encapsulation）： 将数据和操作数据的方法绑定在一起，对外隐藏内部实现细节，通过访问权限控制外部访问。（2025年3月判断第8题）
2. 继承（Inheritance）： 从已有类派生出新类，子类继承父类的属性和方法。（2024年3月判断第3题）
3. 多态（Polymorphism）： 同一操作作用于不同对象产生不同的执行结果。C++中通过虚函数（virtual）实现运行时多态。（2025年6月第3题）
（2024年6月第1题） 练习题：面向对象编程的三大原则是什么？
答案： 封装、继承、多态。
5.2 类的定义与使用
class Student {
private: // 私有成员，外部不可直接访问
string name;
int age;
public: // 公有成员，外部可访问
// 构造函数（与类名相同，无返回值）
Student(string n, int a) : name(n), age(a) {}
// 成员函数
void display() { cout << name << " " << age; }
};
5.3 构造函数与析构函数——高频考点
构造函数（Constructor）：
· 与类名相同，无返回值，创建对象时自动调用
· 可以有多个构造函数（函数重载）（2025年3月判断第5题）
· 构造函数不能声明为虚函数（2025年6月判断第1题、2026年6月第1题）
· 如果没有定义构造函数，编译器会生成默认构造函数（2023年12月判断第2题）
· 默认构造函数可以被声明为private（2025年3月第6题）
析构函数（Destructor）：
· 名称=~类名，无参数无返回值
· 对象销毁时自动调用
· 基类析构函数通常声明为虚函数，以便通过基类指针正确释放派生类对象（2026年6月第1题）
· 析构函数可以被声明为private（2025年3月第6题）
5.4 访问权限控制
私有
关键字：private
本类内部：✓
派生类（子类）：✗
外部：✗
保护
关键字：protected
本类内部：✓
派生类（子类）：✓
外部：✗
公有
关键字：public
本类内部：✓
派生类（子类）：✓
外部：✓
（2023年12月第1题、2024年9月第2题） 练习题： 派生类能否访问父类的private成员？
答案： 不能。private成员只有本类内部可以访问，派生类也不能访问。
5.5 静态成员
· 静态成员变量： 被所有对象共享，类外初始化（2023年9月第15题）
· 静态成员函数： 只能访问静态成员，不能访问非静态成员（2024年12月判断第2题）
（2023年9月第4题） 练习题： static修饰的静态成员有什么特性？
答案： 被所有对象共享，所有对象访问的是同一个变量。
5.6 虚函数与多态——高频考点
虚函数： 用virtual关键字修饰的成员函数，允许在派生类中重写（override）。
动态绑定： 通过基类指针或引用调用虚函数时，在运行时根据对象的实际类型决定调用哪个版本的函数。（2026年6月第2题）
class Base {
public:
virtual void show() { cout << "Base"; } // 虚函数
virtual ~Base() {} // 虚析构函数
};
class Derived : public Base {
public:
void show() override { cout << "Derived"; } // 重写
};
int main() {
Base* p = new Derived();
p->show(); // 输出 "Derived"（动态绑定，运行时决定）
delete p; // 正确调用Derived的析构函数
}
5.7 类与结构体的区别
在C++中，class和struct的区别仅在于默认访问权限：class默认private，struct默认public。（2026年3月第1题）
知识块⑥：栈与队列
6.1 栈（Stack）——“先进后出，后进先出”
定义： 只允许在一端（栈顶）进行插入（push）和删除（pop）操作。（2024年6月第5题）
（2024年6月第5题） 练习题： 栈的基本特性是什么？
答案：先进后出（FILO），后进先出（LIFO）。
应用场景：
· 函数调用管理（递归调用栈，2025年12月判断第5题）
· 括号匹配（2025年3月第14题）
· 文本编辑器撤销操作（2025年12月第4题、2026年6月第4题）
· DFS非递归实现（2024年6月第14题）
· 十进制转二进制（2024年6月第6题）
栈的合法性判断（2024年9月第3题）： 给定入栈序列，判断出栈序列是否合法。这是一道经典题，需要模拟入栈出栈过程来验证。
C++ STL栈：std::stack，push()入栈，pop()出栈（不返回栈顶元素，2025年9月判断第4题），top()取栈顶元素。
6.2 队列（Queue）——“先进先出，排队办事”
定义： 只允许在一端（队尾）插入（enqueue），在另一端（队头）删除（dequeue）。（2024年3月第3题）
（2024年3月第3题） 练习题： 队列的基本特性是什么？
答案：先进先出（FIFO）。
应用场景：
· BFS（广度优先搜索）实现（2024年6月第13题）
· 任务调度、打印机队列
· 缓冲区管理
C++ STL队列：std::queue，push()入队，pop()出队（不返回队头），front()取队头元素。
6.3 循环队列——“数组模拟队列，空间复用”
定义： 用数组实现队列，通过取模运算实现队头队尾指针循环移动，避免“假溢出”。（2024年6月第7题）
关键操作：
· 入队：rear = (rear + 1) % maxSize
· 出队：front = (front + 1) % maxSize
· 判空：front == rear
· 判满：(rear + 1) % maxSize == front（空一格判满，2025年6月第5题）
（2025年3月第9题、2026年3月第4题） 练习题：循环队列的判满条件是什么？
答案： (rear + 1) % maxSize == front。循环队列通常空出一个位置来区分队空和队满。
应用场景： 生产者和消费者问题中的共享缓冲区（2026年3月第5题）
知识块⑦：格雷编码
7.1 什么是格雷码？
格雷码（Gray Code）： 一种二进制编码方式，相邻两个编码之间只有一位不同。（2024年3月第6题、2025年3月第2题）
性质： 首尾两个编码之间也只有一位不同（循环码）。
7.2 格雷码的生成
（2025年9月第10题） 递归生成方式： n位格雷码由n-1位格雷码先按顺序生成，再按逆序生成，并在前半部分前面加0，后半部分前面加1。
举例： 2位格雷码 → 3位格雷码
· 2位：00, 01, 11, 10
· 3位：
· 前半部分（加0）：000, 001, 011, 010
· 后半部分（加1，逆序）：110, 111, 101, 100
· 结果：000, 001, 011, 010, 110, 111, 101, 100
迭代生成公式：gray(i) = i ^ (i >> 1)
7.3 格雷码的应用
· 数字通信中的错误检测
· 模数转换器（ADC）
· 卡诺图化简
STATISTICS 03
历年真题考点总览
基于2023年9月~2026年6月共11套GESP C++六级真题，以下是各知识块在真题中的出现频率统计和考点分布总览。
各知识块在11套真题中的出现频率
树与二叉树
出现套数：11/11套
覆盖率：100%
每套平均题量：4~5题
重要程度：⭐⭐⭐⭐⭐
面向对象编程
出现套数：11/11套
覆盖率：100%
每套平均题量：3~4题
重要程度：⭐⭐⭐⭐⭐
动态规划
出现套数：11/11套
覆盖率：100%
每套平均题量：3~4题
重要程度：⭐⭐⭐⭐⭐
栈与队列
出现套数：11/11套
覆盖率：100%
每套平均题量：2~3题
重要程度：⭐⭐⭐⭐
哈夫曼树与编码
出现套数：10/11套
覆盖率：约91%
每套平均题量：1~2题
重要程度：⭐⭐⭐⭐
搜索算法（DFS/BFS）
出现套数：10/11套
覆盖率：约91%
每套平均题量：1~2题
重要程度：⭐⭐⭐⭐
格雷编码
出现套数：7/11套
覆盖率：约64%
每套平均题量：1题
重要程度：⭐⭐⭐
考点分布总体分析
单选题（15题，共30分）考点分布规律
第1~3题
常见考点：面向对象基础（类、继承、多态、封装）
说明：几乎每套题的前3题必有
第4~5题
常见考点：栈与队列（基本操作、循环队列判满）
说明：稳定出现
第6~7题
常见考点：树的性质（完全二叉树、满二叉树、BST）
说明：类型判断、性质计算
第8~9题
常见考点：二叉树遍历（前序+中序求后序）、哈夫曼编码
说明：高频考点
第10~11题
常见考点：格雷码、DFS/BFS
说明：交替出现
第12~13题
常见考点：DFS/BFS代码填空、BST操作
说明：代码理解题
第14~15题
常见考点：动态规划概念、0/1背包
说明：必考
判断题（10题，共20分）考点分布规律
面向对象
平均题量：2~3题
常见陷阱：构造函数/析构函数性质、虚函数、访问权限
树与二叉树
平均题量：2~3题
常见陷阱：完全二叉树判断、BST性质、遍历顺序
哈夫曼编码
平均题量：1~2题
常见陷阱：唯一性、有损/无损、贪心策略
DFS/BFS
平均题量：1题
常见陷阱：辅助数据结构（栈vs队列）
栈与队列
平均题量：1题
常见陷阱：pop()是否返回、单向链表实现
动态规划
平均题量：1题
常见陷阱：最优子结构、0/1背包内循环顺序
TRAPS 04
判断题高频陷阱
第1名：构造函数/析构函数相关（出现约10次）
“构造函数可以声明为virtual。”（2025年6月判断第1题、2026年6月第1题）
答案：×。构造函数不能是虚函数，因为对象还没构造完成，虚函数表还没建立。
“基类析构函数通常声明为虚函数。”（2026年6月第1题）
答案：√。通过基类指针正确释放派生类对象，必须将析构函数声明为虚函数。
“C++类的定义中，可以没有构造函数，会给出默认的构造函数。”（2023年12月判断第2题）
答案：√。如果程序员没有定义任何构造函数，编译器会自动生成一个默认构造函数。
“类的默认构造函数只能有一个。”（2025年3月判断第5题）
答案：√。无参构造函数只能有一个，否则编译器无法区分。
第2名：哈夫曼编码相关（出现约9次）
“哈夫曼编码具有唯一性，因此有确定的压缩率。”（2023年12月判断第5题）
答案：×。同一组频率可能有多种不同的哈夫曼树，编码不唯一。（2025年9月判断第2题）
“哈夫曼编码属于有损数据压缩。”（2024年3月判断第7题）
答案：×。哈夫曼编码是无损压缩，可以完全还原原始数据。（2023年9月判断第7题）
“哈夫曼编码的构造使用了贪心策略。”（2024年6月判断第1题）
答案：√。每次合并权值最小的两个节点，正是贪心策略的体现。
第3名：DFS/BFS 相关（出现约8次）
“深度优先搜索的辅助数据结构是队列。”（2024年6月判断第9题）
答案：×。DFS用栈（或递归，递归本质上也是栈），BFS用队列。（2025年3月判断第3题）
“广度优先搜索的辅助数据结构是栈。”（2024年9月判断第8题）
答案：×。BFS用队列。
“深度优先搜索的过程是每个节点只能访问一次。”（2023年12月判断第4题）
答案：√。在树或图的遍历中，每个节点只访问一次。
第4名：二叉排序树（BST）相关（出现约7次）
“二叉搜索树查找的平均时间复杂度为O(log N)。”（2023年12月判断第7题）
答案：√。平均情况下，BST查找复杂度O(log n)。
“如果某二叉搜索树退化为链表，则查找的时间复杂度为O(n)。”（2025年6月判断第5题）
答案：√。退化为链表后查找退化为线性时间。
“左节点树的值都小于根节点的值，右节点树的值都大于根节点的值。”（2023年12月判断第8题）
答案：√。这是BST的基本定义——左小右大。
第5名：动态规划相关（出现约6次）
“0-1背包问题使用贪心算法可以保证获得最优解。”（2024年6月判断第10题）
答案：×。贪心不保证最优解，动态规划才能保证。
“动态规划的两个重要性质是最优子结构和重叠子问题。”（2024年3月第11题、2024年6月第11题）
答案：√。这是动态规划的两个基本性质。
“动态规划版斐波那契数列时间复杂度为O(2ⁿ)。”（2025年9月判断第9题）
答案：×。动态规划版（用数组存储中间结果）时间复杂度是O(n)。O(2ⁿ)是纯递归版的时间复杂度。
第6名：栈/队列相关（出现约5次）
“适合用单向链表实现栈。”（2024年12月判断第3题）
答案：√。栈的插入删除都在栈顶，用单向链表即可。
“用双向链表实现栈和队列的插入和删除操作的时间复杂度为O(1)。”（2025年3月判断第10题）
答案：√。双向链表头尾操作都是O(1)。
“C++ STL中std::stack的pop()操作会返回栈顶元素。”（2025年9月判断第4题）
答案：×。pop()不返回栈顶元素，需要用top()先取再pop()。
第7名：完全二叉树/二叉树性质（出现约4次）
“完全二叉树可以用数组存储，空间利用率高。”（2024年6月判断第7题）
答案：√。完全二叉树适合用数组按层序存储。
“字符频率相同时，哈夫曼树一定是完全二叉树。”（2026年3月判断第4题）
答案：×。频率相同不一定是完全二叉树。
TEMPLATES 05
编程题全分析
各套真题编程题一览
2023年9月
编程题1：小杨买饮料
考点：0/1背包DP
编程题2：小杨的握手问题
考点：逆序对、归并排序
2023年12月
编程题1：闯关游戏
考点：线性DP
编程题2：工作沟通
考点：树结构、DFS
2024年3月
编程题1：游戏
考点：计数DP、取模
编程题2：好斗的牛
考点：排列枚举、贪心
2024年6月
编程题1：计算得分
考点：字符串DP
编程题2：二叉树
考点：树DFS、颜色标记
2024年9月
编程题1：小杨和整数拆分
考点：完全平方数DP
编程题2：算法学习
考点：贪心、排序
2024年12月
编程题1：树上游走
考点：完全二叉树、模拟
编程题2：运送物资
考点：贪心、排序
2025年3月
编程题1：树上漫步
考点：树DFS、二分图染色
编程题2：环线
考点：最大子段和、单调队列
2025年6月
编程题1：学习小组
考点：完全背包DP
编程题2：最大因数
考点：质因数分解、树
2025年9月
编程题1：划分字符串
考点：DP+位运算
编程题2：货物运输
考点：树DFS、树的直径
2025年12月
编程题1：路径覆盖
考点：树形DP
2026年3月
编程题1：选数
考点：线性DP
编程题2：完全二叉树
考点：树DFS、完全二叉树判定
2026年6月
编程题1：条形蛋糕
考点：完全背包DP
编程题2：满二叉树
考点：树DFS、满二叉树判定
编程题高频考点总结
动态规划
出现次数：约8次
占比：约67%
说明：0/1背包、线性DP、完全背包、树形DP、状态压缩DP
树结构遍历（DFS）
出现次数：约6次
占比：约50%
说明：树上DFS、完全二叉树判定、满二叉树判定、树形染色
贪心算法
出现次数：约3次
占比：约25%
说明：排序+贪心策略、可行性判断
排序算法
出现次数：约2次
占比：约17%
说明：归并排序求逆序对、贪心排序
编程必会模板
模板1：二叉树前序遍历（递归）
void preorder(TreeNode* root) {
if (root == nullptr) return;
cout << root->val; // 访问根
preorder(root->left); // 遍历左子树
preorder(root->right); // 遍历右子树
}
模板2：二叉树前序遍历（非递归，用栈）
void preorder(TreeNode* root) {
stack<TreeNode*> st;
if (root) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); st.pop();
cout << node->val;
if (node->right) st.push(node->right); // 先右后左
if (node->left) st.push(node->left);
}
}
模板3：二叉树层序遍历（BFS，用队列）
void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
cout << node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
模板4：0/1背包（一维滚动数组）
// dp[j] 表示容量为j的背包能装的最大价值
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = C; j >= w[i]; j--) // 逆序！保证每个物品只选一次
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
模板5：完全背包（一维滚动数组）
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= C; j++) // 正序！允许重复使用物品
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
模板6：不相邻元素最大和（打家劫舍）
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
int prev2 = nums[0], prev1 = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
int cur = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
模板7：由前序+中序还原二叉树
TreeNode* build(vector<int>& pre, int preL, int preR,
vector<int>& in, int inL, int inR) {
if (preL > preR) return nullptr;
TreeNode* root = new TreeNode(pre[preL]);
int k = inL;
while (in[k] != pre[preL]) k++;
int leftLen = k - inL;
root->left = build(pre, preL + 1, preL + leftLen, in, inL, k - 1);
root->right = build(pre, preL + leftLen + 1, preR, in, k + 1, inR);
return root;
}
模板8：完全二叉树判断（层序遍历）
bool isComplete(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
bool flag = false; // 是否遇到过空节点
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (node == nullptr) {
flag = true;
} else {
if (flag) return false; // 空节点后又出现非空节点
q.push(node->left);
q.push(node->right);
}
}
return true;
}
TACTICS 06
复习建议与考场技巧
复习时间规划（距考试3周）
第1周：基础打牢——“先把概念吃透”
第1天
学习内容：树与二叉树（一）
重点：前序/中序/后序遍历、由前序+中序还原二叉树（必考！）
第2天
学习内容：树与二叉树（二）
重点：完全二叉树、二叉排序树（BST）、满二叉树
第3天
学习内容：哈夫曼树与编码 + 格雷编码
重点：构造WPL、前缀编码、格雷码生成规则
第4天
学习内容：DFS/BFS搜索算法
重点：递归/非递归实现、栈vs队列、时间复杂度
第5天
学习内容：动态规划（一）
重点：最优子结构、重叠子问题、线性DP、打家劫舍
第6天
学习内容：动态规划（二）
重点：0/1背包（逆序！）、完全背包（正序！）
第7天
学习内容：面向对象编程
重点：类、构造函数/析构函数、继承、多态、虚函数
第2周：真题训练——“把知识变成分数”
第1天
学习内容：做2023年两套真题（9月+12月），限时180分钟完成
第2天
学习内容：对照答案分析错题，重点复习树遍历和面向对象
第3天
学习内容：做2024年两套真题（3月+6月），限时完成
第4天
学习内容：分析错题，重点复习动态规划和BST
第5天
学习内容：做2025年两套真题（3月+6月），限时完成
第6天
学习内容：编程题专项训练：DP + 树DFS（这两个是编程题主力）
第7天
学习内容：做2026年最新真题，检验学习效果
第3周：查漏补缺——“哪里不会补哪里”
· 复习“判断题高频陷阱”部分——判断题的送分题和陷阱题都在这里
· 熟背编程模板（8个必会模板）——考试时直接套用
· 限时模拟一套完整试卷（180分钟）
· 把之前的错题再过一遍
考场技巧
做题顺序建议
单选题
题量：15题
建议用时：约40分钟
策略：不会的先跳过，不要在一道题上花超过3分钟
判断题
题量：10题
建议用时：约20分钟
策略：注意“一定”“总是”“所有”这类绝对化词语
编程题
题量：2题
建议用时：约100分钟
策略：先读懂题目，再动手写代码，最后15分钟检查
单选题常见陷阱提醒
陷阱1：混淆遍历顺序
· 前序=根左右，中序=左根右，后序=左右根
· 记住口诀：“根在哪个位置，就是什么序”
陷阱2：混淆DFS和BFS的辅助数据结构
· DFS用栈（或递归），BFS用队列
· 口诀：“深度用栈，广度用队”
陷阱3：混淆0/1背包和完全背包的循环顺序
· 0/1背包：内层逆序
· 完全背包：内层正序
· 口诀：“01逆序，完全正序”
编程题检查清单
1. 变量类型选对了吗？（int不够用long long？）
2. 数组下标从0还是1开始？
3. 动态规划状态转移方程写对了吗？
4. 0/1背包内层循环是逆序吗？
5. 树遍历时检查了空指针吗？
6. DFS/BFS的辅助数据结构选对了吗？（栈还是队列？）
7. 输入输出格式跟题目要求一样吗？
8. 有没有漏掉 return 0;？
THE END ∞
写在最后
祝各位考生在GESP C++六级考试中取得好成绩！
六级是GESP认证中从“基础算法”跨越到“数据结构+面向对象+高级算法”的关键级别。相比五级的“初等数论+链表+排序”，六级的知识体系更加系统化——树结构、动态规划、面向对象三大支柱缺一不可。
六级考试时间180分钟，比四级/五级多60分钟，题量更大、难度更高。但只要把树的遍历、0/1背包、类与对象、栈与队列这几个核心内容练熟，就能顺利通过考试！
加油，六级见。
DOMIAI
我是 DOMIAI，帮更多孩子成为 AI 时代原住民。
