Appearance
第1章 GESP 六级考点总览
🎯 本章学习目标
通过本章的学习，你将能够：
- 建立全局视野：清晰了解 GESP 六级考试的 6 大知识模块及其重要程度
- 掌握树的基础：理解树的基本概念，掌握二叉树的四种遍历方式
- 理解特殊树：掌握哈夫曼树、完全二叉树、二叉排序树的特点
- 精通搜索算法：掌握 DFS 和 BFS 的思想与实现
- 入门动态规划：理解 DP 的基本思想，掌握一维 DP 和简单背包
- 理解面向对象：掌握封装、继承、多态三大特性
- 掌握栈与队列：理解先进后出和先进先出的原理，会实现循环队列
- 识别考点频率：知道各模块的出题频率和常见题型
- 制定备考策略：根据自身情况合理安排复习计划
- 为深入学习打基础：建立知识框架，为后续各模块深入学习做好准备
🗺️ 本章知识图谱
GESP 六级知识体系
├── 树的基本概念与遍历
│ ├── 树的基本术语
│ │ ├── 根、叶子、父/子节点
│ │ ├── 深度、高度、度
│ │ └── 二叉树定义
│ ├── 二叉树构造
│ │ ├── 前序+中序 → 还原树
│ │ └── 后序+中序 → 还原树
│ └── 四种遍历
│ ├── 前序（根左右）
│ ├── 中序（左根右）
│ ├── 后序（左右根）
│ └── 层序（队列实现）
├── 特殊树与编码
│ ├── 哈夫曼树
│ │ ├── 带权路径长度 WPL
│ │ └── 哈夫曼编码（前缀编码）
│ ├── 完全二叉树
│ │ ├── 性质
│ │ └── 数组存储
│ ├── 二叉排序树 BST
│ │ ├── 左小右大
│ │ └── 中序遍历有序
│ └── 格雷编码
├── 搜索算法
│ ├── DFS 深度优先搜索
│ │ ├── 递归实现
│ │ ├── 栈实现
│ │ └── 回溯思想
│ ├── BFS 广度优先搜索
│ │ ├── 队列实现
│ │ └── 层序遍历
│ └── 二叉树搜索
├── 简单动态规划
│ ├── DP 基本思想
│ │ ├── 最优子结构
│ │ └── 重叠子问题
│ ├── 一维 DP
│ │ ├── 爬楼梯
│ │ └── 最大子段和
│ └── 背包问题
│ ├── 01背包
│ └── 完全背包
├── 面向对象编程
│ ├── 封装（类与对象）
│ ├── 继承（派生类）
│ ├── 多态（虚函数）
│ ├── 构造函数与析构函数
│ └── 访问控制（public/protected/private）
└── 栈与队列
├── 栈 Stack
│ ├── 先进后出 FILO
│ ├── push/pop/top
│ └── 应用：DFS、括号匹配
├── 队列 Queue
│ ├── 先进先出 FIFO
│ ├── push/pop/front
│ └── 应用：BFS、层序遍历
└── 循环队列
├── 数组模拟
├── front/rear 指针
└── 取模运算一、🎯 写在前面
这是 《GESP 六级备考白皮书》的第1章，也是全书的起点——六大考点全景总览。
CCF GESP（编程能力等级认证）六级，是 C++ 考级体系中的第六个台阶，标志着从基础编程迈向数据结构与算法思维的关键一跃。六级考纲涵盖 7 大知识模块，我们将其归纳为 6 大考点板块（模块二与三合并），方便你快速建立全局视野。
💡 本书结构：本章是总览篇，后续第2~7章将逐模块深入拆解，每章覆盖知识点精讲、典型例题、编程实战与备考策略。
二、📊 六大考点全景总表
我们将 GESP 六级的 7 大知识模块归纳为 6 大考点，一览全局：
| 序号 | 📌 考点模块 | 📖 一句话概括 | ⭐ 考频星级 |
|---|---|---|---|
| ① | 树的基本概念与遍历 | 树的定义、构造方法、前/中/后序/层序遍历——所有"树题"的地基 | ⭐⭐⭐⭐⭐ |
| ② | 特殊树与编码 | 哈夫曼树/完全二叉树/二叉排序树 + 哈夫曼编码/格雷编码——概念辨析重灾区 | ⭐⭐⭐⭐⭐ |
| ③ | 搜索算法 | DFS深搜、BFS宽搜、二叉树搜索——编程题高频考点 | ⭐⭐⭐⭐⭐ |
| ④ | 简单动态规划 | 一维DP、简单背包问题——编程题的"半壁江山" | ⭐⭐⭐⭐⭐ |
| ⑤ | 面向对象编程 | 封装、继承、多态、类的创建——选择/判断题必考 | ⭐⭐⭐⭐ |
| ⑥ | 栈、队列与循环队列 | 先进后出、先进先出、循环队列的数组模拟——概念+模拟操作 | ⭐⭐⭐⭐ |
📌 考频星级说明：基于历年 GESP 六级真题统计分析，⭐越多表示出题频率越高、分值占比越大。
三、🔍 六大考点逐一拆解
下面逐个说明每个考点 "考什么" 和 "怎么考"。
① 树的基本概念与遍历
🎯 考什么
- 树的基本术语：根节点、叶子节点、父/子节点、深度、高度、度
- 树的构造：给定前序+中序（或后序+中序）遍历序列还原二叉树
- 四种遍历方式：前序遍历、中序遍历、后序遍历、层序遍历
- 递归遍历与非递归遍历的代码实现
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 给定遍历序列判断结果、根据遍历还原树结构、判断遍历性质 |
| 判断题 | 判断遍历说法的正误（如"前序遍历一定是先根后左再右"） |
| 编程题 | 实现遍历算法、根据遍历序列重建树、统计节点/叶子数 |
🔥 真题规律：几乎每次考试必考遍历代码填空题，通常出现在单选或判断题中，分值2~4分。编程题中也可能涉及树的遍历作为子任务。
② 特殊树与编码
🎯 考什么
本模块合并了考纲中的"特殊树"和"编码"两部分：
特殊树：
- 哈夫曼树：构建过程（每次选权值最小的两个节点合并）、带权路径长度(WPL)计算
- 完全二叉树：节点编号规律（父节点 i 的子节点为 2i 和 2i+1）、数组存储方式
- 二叉排序树（BST）：左小右大的性质、查找/插入/中序遍历的有序性
编码：
- 哈夫曼编码：前缀编码的构造、WPL最优性、编码与解码过程
- 格雷编码：相邻码字仅一位不同、二进制与格雷码的相互转换
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 哈夫曼树构建后求WPL、判断完全二叉树性质、BST操作（查找/插入）代码填空、哈夫曼编码的前缀性质判断、格雷码转换 |
| 判断题 | 哈夫曼编码是否定长编码（否！）、完全二叉树是否一定是满二叉树（否！）、BST中序遍历是否有序（是！） |
| 编程题 | 构建哈夫曼树、BST的查找/插入实现 |
🔥 真题规律：哈夫曼树和 BST 是高频概念辨析题，几乎每场考试都有1~3道选择/判断涉及此模块。哈夫曼编码的"前缀性质"和格雷码的"相邻差异"是经典考点。
③ 搜索算法（DFS / BFS / 二叉树搜索）
🎯 考什么
- 深度优先搜索（DFS）：递归实现、回溯思想、在树/图上的应用
- 宽度优先搜索（BFS）：队列实现、层次遍历、最短路径（无权图）
- 二叉树的搜索算法：在BST中查找、范围搜索、最近公共祖先等
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | DFS/BFS代码填空、判断搜索顺序、队列/栈在搜索中的使用 |
| 判断题 | "BFS可以用栈实现"（错！用队列）、"DFS一定用递归"（错！可用栈模拟） |
| 编程题 | 用DFS/BFS解决实际问题（如路径搜索、连通性判断、树的染色等） |
🔥 真题规律：搜索算法是编程题的重灾区！真题中常以"树上的路径覆盖""树的染色"等场景出题，需要综合运用 DFS + 动态规划。建议至少掌握两种搜索的代码模板。
④ 简单动态规划（一维DP + 背包问题）
🎯 考什么
- 一维动态规划：状态定义、状态转移方程、初始化与边界条件
- 经典模型：斐波那契数列、爬楼梯、最大子段和、最长递增子序列（LIS）入门
- 简单背包问题：0/1背包（一维数组优化）、完全背包基础
- 动态规划的核心思想：最优子结构、无后效性、重叠子问题
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 状态转移方程填空、DP数组含义判断、时间/空间复杂度分析 |
| 判断题 | 判断问题是否满足DP条件、一维DP数组遍历方向（正序vs逆序） |
| 编程题 | 完整实现DP解题（如背包变形、切割问题等），通常占25分 |
🔥 真题规律：动态规划是编程题的绝对主角！2025年12月六级编程第2题就是经典的 0/1 背包变形题。选择题也常考状态转移方程的代码填空。掌握 DP 模板 = 拿下半壁江山。
⑤ 面向对象编程（OOP）
🎯 考什么
- 封装：类的定义、成员变量与成员函数、访问控制（public / private / protected）
- 继承：派生类、父类与子类的关系、构造/析构函数的调用顺序
- 多态：虚函数（virtual）、运行时多态、函数重写（override）
- 类的创建：构造函数、析构函数、成员初始化
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 虚函数与多态的代码分析、继承关系中的构造/析构调用顺序、访问权限判断 |
| 判断题 | 判断OOP概念说法正误（如"析构函数可以被重载"等） |
| 编程题 | 一般不单独出OOP编程题，但可能作为背景知识出现在代码阅读中 |
🔥 真题规律：OOP 几乎每次都出1~2道单选 + 1~2道判断，属于"送分模块"——概念清晰就能拿满，概念模糊就丢分。特别注意虚函数、多态、构造析构顺序这三个高频考点。
⑥ 栈、队列与循环队列
🎯 考什么
- 栈（Stack）：先进后出（LIFO），push / pop / top 操作，数组模拟实现
- 队列（Queue）：先进先出（FIFO），enqueue / dequeue 操作
- 循环队列：数组模拟、front 和 rear 指针的移动规则、队空/队满判断条件
- 栈和队列的应用场景：括号匹配、表达式求值、层次遍历等
📝 怎么考
| 题型 | 出题方式 |
|---|---|
| 单选题 | 给定入栈/出栈序列判断结果、循环队列 front/rear 指针计算、栈和队列的应用判断 |
| 判断题 | "栈可以用数组实现"（对）、"循环队列队满条件唯一"（需看具体实现） |
| 编程题 | 一般不单独出栈/队列编程题，但 DFS 用栈、BFS 用队列是搜索算法的基础 |
🔥 真题规律：循环队列的 front/rear 指针计算是经典必考题，几乎每场都有。题目给出操作序列，要求计算最终的 front 和 rear 值——务必熟练掌握取模运算！
四、📈 备考建议：如何高效攻克六级？
1️⃣ 先骨架，后细节
先把六大模块的核心概念过一遍（就像本文给你的全景地图），建立知识框架后，再逐个模块深入。不要一上来就啃哈夫曼编码的细节，结果连树的基本遍历都没搞明白。
2️⃣ 选择/判断靠概念，编程题靠手感
- 选择 + 判断（50分）：吃透概念 + 刷真题，重点是代码阅读填空
- 编程题（50分）：必须动手写！DFS/BFS模板 + DP模板是必备武器
3️⃣ 真题是最好的复习资料
GESP六级历年真题是最好的备考材料。建议按以下顺序刷题：
- 先按模块分类刷 → 找到自己的薄弱点
- 再按套卷限时练 → 训练时间分配能力
- 最后复盘错题 → 查漏补缺
五、📝 实战练习
练习题 1（单选题）
题目： 已知二叉树的前序遍历为 ABCDE，中序遍历为 BADCE，则后序遍历为？（ ）
A. BDECA
B. ABCED
C. EDCBA
D. BDEC A
🔑 点击查看答案与解析
答案： A
解析： 前序（根左右）：A B C D E → A 是根 中序（左根右）：B A D C E → 左子树 B，右子树 DCE
前序右子树：C D E → C 是右子树的根 中序右子树：D C E → D 是左孩子，E 是右孩子
树结构：
A
/ \
B C
/ \
D E后序遍历（左右根）：B → D → E → C → A = BDECA
选 A。
🔥 高频考点：给前序+中序求后序，或给后序+中序求前序。关键：前/后序找根，中序分左右。
练习题 2（判断题）
题目： 栈的特点是先进先出（FIFO），队列的特点是先进后出（FILO）。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： 正好说反了！
- 栈 Stack：先进后出 FILO（First In Last Out）
- 队列 Queue：先进先出 FIFO（First In First Out）
🍎 生活比喻：
- 栈 = 叠盘子：最后放上去的第一个被拿走
- 队列 = 排队：先来的先服务
练习题 3（单选题）
题目： 有 4 个叶子节点，权值分别为 1, 2, 3, 4。构造的哈夫曼树的带权路径长度（WPL）是？（ ）
A. 10
B. 19
C. 20
D. 24
🔑 点击查看答案与解析
答案： B
解析： 哈夫曼树构造过程（每次选最小的两个合并）：
- 合并 1+2=3，剩余 [3, 3, 4]
- 合并 3+3=6，剩余 [4, 6]
- 合并 4+6=10，剩余 [10]
树结构：
10
/ \
4 6
/ \
3 3
/ \
1 2WPL = 各叶子权值 × 深度之和
- 权值 4：深度 1 → 4×1 = 4
- 权值 3：深度 2 → 3×2 = 6
- 权值 1：深度 3 → 1×3 = 3
- 权值 2：深度 3 → 2×3 = 6
WPL = 4 + 6 + 3 + 6 = 19
选 B。
💡 快速计算：哈夫曼树 WPL = 所有非叶子节点的权值之和 = 3 + 6 + 10 = 19。（每次合并产生的新节点就是非叶子节点）
练习题 4（单选题）
题目： 深度优先搜索（DFS）通常用什么数据结构实现？广度优先搜索（BFS）通常用什么数据结构实现？（ ）
A. 栈，队列
B. 队列，栈
C. 数组，链表
D. 链表，数组
🔑 点击查看答案与解析
答案： A
解析：
- DFS 深度优先搜索：用栈（或递归，本质也是栈）实现。一条路走到黑，走不通再回头。
- BFS 广度优先搜索：用队列实现。一层一层往外扩散，先访问离起点近的。
选 A。
🍎 生活比喻：
- DFS = 走迷宫，遇到岔路选一条走到底，碰壁了退回来选另一条
- BFS = 水波纹，从起点一圈一圈往外扩散
练习题 5（判断题）
题目： 动态规划的两个基本要素是"最优子结构"和"重叠子问题"。（ ）
🔑 点击查看答案与解析
答案： 正确 ✅
解析： 动态规划的两个核心要素：
- 最优子结构：大问题的最优解包含子问题的最优解
- 重叠子问题：求解大问题时会反复用到相同的子问题的解
没有最优子结构 → 不能用 DP 没有重叠子问题 → 用 DP 没有优势（和分治一样）
💡 对比记忆：
- 贪心 = 最优子结构 + 贪心选择性质
- DP = 最优子结构 + 重叠子问题
- 分治 = 最优子结构 + 子问题独立
练习题 6（单选题）
题目： 面向对象编程的三大特性是？（ ）
A. 封装、继承、多态
B. 封装、抽象、重载
C. 继承、多态、模板
D. 封装、继承、友元
🔑 点击查看答案与解析
答案： A
解析： 面向对象的三大特性：
- 封装：把数据和操作数据的方法打包在一起，隐藏内部实现
- 继承：子类继承父类的属性和方法，实现代码复用
- 多态：同一接口，不同实现（通过虚函数实现）
选 A。
🍎 生活比喻：
- 封装 = 电视机：你只需要按遥控器，不用知道内部电路怎么工作
- 继承 = 儿子像爸爸：继承了爸爸的一些特征
- 多态 = 同样是"叫"，猫"喵"狗"汪"：同一个行为，不同表现
练习题 7（单选题）
题目： 一棵有 10 个节点的完全二叉树，其深度是？（根节点深度为 1）（ ）
A. 3
B. 4
C. 5
D. 6
🔑 点击查看答案与解析
答案： B
解析： 完全二叉树的性质：深度为 k 的完全二叉树，节点数范围是 2^(k-1) ≤ n ≤ 2^k - 1
验证：
- k=3 时：4 ≤ n ≤ 7 → 10 不在范围内
- k=4 时：8 ≤ n ≤ 15 → 10 在范围内 ✅
所以深度为 4，选 B。
💡 快速计算：完全二叉树的深度 = ⌊log₂n⌋ + 1 log₂10 ≈ 3.32，向下取整 = 3，加 1 = 4
练习题 8（单选题）
题目： 关于 01 背包问题，下列说法正确的是？（ ）
A. 每个物品可以选多次
B. dp[i][j] 表示前 i 个物品装入容量 j 的背包的最大价值
C. 空间优化后内层循环从小到大
D. 时间复杂度是 O(n)
🔑 点击查看答案与解析
答案： B
解析：
- A 错误：01 背包每个物品只能选 0 次或 1 次（这就是"01"的含义）。能选多次的是"完全背包"
- B 正确 ✅：这是 01 背包 DP 状态的标准定义
- C 错误：空间优化后内层循环要从大到小（防止物品被重复使用）
- D 错误：时间复杂度是 O(n × W)，n 是物品数，W 是背包容量
💡 01背包 vs 完全背包：
- 01背包：每个物品最多拿1个 → 空间优化后内层逆序
- 完全背包：每个物品可拿无限个 → 空间优化后内层顺序
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ GESP 六级 · 核心速记卡 │
├─────────────────────────────────────────────┤
│ 1. 二叉树遍历：前根左右、中左根右、后左右根│
│ 2. 求树结构：前/后找根，中序分左右 │
│ 3. 哈夫曼树：每次合最小，WPL非叶节点和 │
│ 4. 完全二叉树：节点编号连续，从1开始存数组 │
│ 5. 二叉排序树：左小右大，中序遍历升序 │
│ 6. DFS：栈/递归，一条路走到黑 │
│ 7. BFS：队列，一层一层扩散 │
│ 8. DP两要素：最优子结构 + 重叠子问题 │
│ 9. 01背包：每个物品0或1次，空间优化逆序 │
│ 10. 完全背包：物品可多次拿，空间优化顺序 │
│ 11. 面向对象三大特性：封装、继承、多态 │
│ 12. 栈：先进后出 FILO；队列：先进先出 FIFO │
│ 13. 循环队列：front指向队头，rear指向队尾的下一个空位（队尾元素在 rear 前一格） │
│ 14. 循环队列入队：rear=(rear+1)%size │
│ 15. DFS用栈、BFS用队列、层序遍历用队列 │
└─────────────────────────────────────────────┘