GESP C++六级考试考点解读及练习题单
1. 树
- 核心考点：哈夫曼树、完全二叉树、二叉排序树（BST）的定义、性质及操作（插入、删除、遍历）。
- 考察形式：构造哈夫曼树、计算带权路径长度；完全二叉树的判定；BST的查找、插入和删除操作。
- 洛谷练习题：
- [P1305 新二叉树]（二叉树遍历）
- [P1090 合并果子]（哈夫曼树应用）
- [P5076 【深基16.例7】普通二叉搜索树]（BST基本操作）
2. 基于树的编码
- 核心考点：格雷编码（相邻编码仅一位不同）、哈夫曼编码（最优前缀编码）的生成与应用。
- 考察形式：生成特定长度的格雷码；构造哈夫曼编码并计算压缩效率。
- 洛谷练习题：
- [P5657 格雷码]（格雷编码生成）
- [P2168 荷马史诗]（哈夫曼编码扩展）
3. 搜索算法
- 核心考点：DFS（回溯、剪枝）、BFS（层序遍历、最短路径）、二叉树搜索（前中后序遍历）。
- 考察形式：迷宫路径问题、二叉树遍历、图连通性问题。
- 洛谷练习题：
- [P1605 迷宫]（DFS/BFS基础）
- [P1443 马的遍历]（BFS最短路径）
- [P1030 求先序排列]（二叉树遍历应用）
4. 简单动态规划
- 核心考点：一维DP（斐波那契、爬楼梯）、简单背包问题（0-1背包、完全背包）。
- 考察形式：状态转移方程设计、背包问题的最优解计算。
- 洛谷练习题：
- [P1048 采药]（0-1背包）
- [P1616 疯狂的采药]（完全背包）
- [P1216 数字三角形]（一维DP递推）
5. 面向对象
- 核心考点：类与对象的设计、继承与多态的实现、封装特性。
- 考察形式：设计类结构（如学生管理系统）、实现多态性（虚函数）。
- 洛谷练习题：
- [P5461 赦免战俘]（面向对象思想实现递归分治）
- [P3741 honoka的键盘]（类与方法的封装设计）
6. 栈和队列
- 核心考点：栈（括号匹配、表达式求值）、队列（循环队列实现、BFS应用）。
- 考察形式：栈的FILO特性应用、循环队列的判空/满条件。
- 洛谷练习题：
- [P1739 表达式括号匹配]（栈应用）
- [P1996 约瑟夫问题]（队列模拟）
- [P1449 后缀表达式]（栈实现表达式计算）
综合建议
- 优先练习：树、搜索算法、动态规划是考试高频考点，建议重点突破。
- 面向对象：注意结合实际问题设计类结构，理解多态与继承的应用场景。
- 编码实现：所有题目需手写代码调试，避免依赖模板，熟练掌握STL中
<stack>、<queue>等容器的使用。
文末彩蛋：关注并查看老师的个人主页，学习完整信奥赛系列课程：
https://edu.csdn.net/lecturer/7901
