# GESP 六级编程能力认证讲义

## 第一模块：栈、队列与循环队列

### 1. 知识点拆解
*   **栈 (Stack)**：后进先出 (LIFO)。核心操作：`push` (入栈), `pop` (出栈), `top` (栈顶)。
*   **队列 (Queue)**：先进先出 (FIFO)。核心操作：`push` (入队), `pop` (出队), `front` (队头)。
*   **循环队列**：利用数组模拟，通过取模运算 `%` 连接首尾，解决“假溢出”问题。
    *   队满条件：`(tail + 1) % maxSize == head`。
    *   队空条件：`tail == head`。

### 2. 具体例子
**例子 1.1**：判断出栈序列合法性。
若入栈顺序为 `1, 2, 3`，则出栈序列 `3, 1, 2` 是**非法**的。因为 3 出栈意味着 1 和 2 都在栈内，此时 2 必须在 1 之前出栈。

### 3. 练习巩固
1.  **【简单】单选题**：一个栈的初始状态为空，现将元素 `A, B, C, D` 依次入栈，则不可能的出栈序列是（ ）。
    A. A, B, C, D  B. D, C, B, A  C. C, A, B, D  D. B, A, D, C
2.  **【中等】对错题**：在循环队列中，为了区分队满和队空，通常会浪费一个数组单元不用。（ ）
3.  **【困难】填空题**：已知循环队列的存储空间为 `0..n-1`，队头指针为 `front`，队尾指针为 `rear`，则当前队列中的元素个数计算公式为：`____________________`。

---

## 第二模块：树与二叉树（定义、遍历与哈夫曼）

### 1. 知识点拆解
*   **二叉树遍历**：
    *   **先序**：根 -> 左 -> 右。
    *   **中序**：左 -> 根 -> 右。
    *   **后序**：左 -> 右 -> 根。
*   **特殊二叉树**：
    *   **完全二叉树**：除最后层外全是满的，且最后层节点集中在左侧。
    *   **二叉排序树 (BST)**：左子树 < 根 < 右子树。
*   **哈夫曼树**：带权路径长度 (WPL) 最短的树。用于**哈夫曼编码**（最优前缀编码）。

### 2. 具体例子
**例子 2.1**：已知二叉树先序为 `ABDCE`，中序为 `BDAEC`。
1. 先序首位 `A` 是根。
2. 中序中 `A` 左侧是 `BD`（左子树），右侧是 `EC`（右子树）。
3. 递归推导，可得出后序为 `DBECA`。

### 3. 练习巩固
1.  **【简单】单选题**：若一棵完全二叉树共有 10 个节点，则其叶子节点数为（ ）。
    A. 4  B. 5  C. 6  D. 7
2.  **【中等】对错题**：哈夫曼编码是一种非等长编码，出现频率高的字符编码较短。（ ）
3.  **【困难】阅读程序写结果**：
    ```cpp
    // 假设 BST 插入顺序为 5, 3, 7, 2, 4
    // 问：该树的中序遍历结果是？
    ```
    输出：__________

---

## 第三模块：搜索算法（DFS 与 BFS）

### 1. 知识点拆解
*   **DFS（深度优先搜索）**：
    *   核心：**递归/栈**。
    *   特点：一路走到底，不撞南墙不回头。适合求“所有解”或路径搜索。
*   **BFS（宽度优先搜索）**：
    *   核心：**队列**。
    *   特点：层层推进。适合求“最短路”或“最小步数”。

### 2. 具体例子
**例子 3.1**：在 $N \times M$ 迷宫中找起点到终点的最短路径。
使用 BFS，将起点放入队列。每次弹出队头，将四周可达点入队并标记步数，最先到达终点的路径即为最短。

### 3. 练习巩固
1.  **【简单】对错题**：DFS 算法通常使用队列作为辅助数据结构。（ ）
2.  **【中等】单选题**：在一个无权图中，求 A 点到 B 点经过最少边数的路径，应首选（ ）。
    A. DFS  B. BFS  C. 哈夫曼算法  D. 递推
3.  **【困难】阅读程序填空（回溯逻辑）**：
    ```cpp
    void dfs(int step) {
        if(step > n) { output(); return; }
        for(int i = 1; i <= n; i++) {
            if(!vis[i]) {
                vis[i] = true;
                path[step] = i;
                dfs(__________); // 填入下一步
                vis[i] = false;  // 回溯，取消标记
            }
        }
    }
    ```

---

## 第四模块：简单动态规划（DP）

### 1. 知识点拆解
*   **核心思想**：将大问题拆解为子问题，通过保存子问题的解（记忆化）来避免重复计算。
*   **三要素**：
    1.  **状态定义**：`dp[i]` 代表什么含义。
    2.  **状态转移方程**：`dp[i]` 如何从前面的 `dp` 值推导出来。
    3.  **边界条件**：初始值。
*   **0/1 背包**：$N$ 件物品，容量 $M$。每件物品只有“选”或“不选”两种状态。

### 2. 具体例子
**例子 4.1**：采药问题（0/1背包）。
`dp[j]` 表示容量为 `j` 时的最大价值。
方程：`dp[j] = max(dp[j], dp[j - w[i]] + v[i])`。
注意：为了保证每件物品只选一次，容量 `j` 需**逆序**枚举。

### 3. 练习巩固
1.  **【简单】单选题**：动态规划算法与递推算法的主要区别在于，动态规划通常涉及（ ）。
    A. 递归  B. 循环  C. 最优化选择  D. 随机数
2.  **【中等】填空题**：已知 `dp[i]` 表示爬 `i` 级台阶的方案数，每次可走 1 或 2 级。则转移方程为 `dp[i] = ______________`。
3.  **【困难】阅读程序写结果**：
    ```cpp
    int dp[11] = {0}, w[3]={2,3,5}, v[3]={6,10,18};
    for(int i=0; i<3; i++)
        for(int j=10; j>=w[i]; j--)
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    cout << dp[10];
    ```
    输出：__________

---

## 第五模块：面向对象与格雷码

### 1. 知识点拆解
*   **面向对象 (OOP)**：将数据和处理数据的方法封装在“类 (Class)”中。
    *   **对象**：类的实例。
    *   **成员变量与方法**：`public` (公开), `private` (私有)。
*   **格雷码 (Gray Code)**：相邻两个编码之间只有一位二进制数不同。
    *   3位格雷码：`000, 001, 011, 010, 110, 111, 101, 100`。

### 2. 具体例子
**例子 5.1**：定义一个简单的类。
```cpp
class Rectangle {
public:
    int w, h;
    int getArea() { return w * h; } // 成员方法
};
```

### 3. 练习巩固
1.  **【简单】对错题**：格雷码的主要特点是任意两个相邻的码值之间只有一位二进制数不同。（ ）
2.  **【中等】单选题**：在 C++ 的类中，如果没有指定访问修饰符，默认的访问权限是（ ）。
    A. public  B. protected  C. private  D. static
3.  **【困难】填空题**：4 位二进制数 `1000` 对应的格雷码是 ______。（提示：$G_i = B_i \oplus B_{i+1}$）

---

## 教练参考答案与解析

### 第一模块
1.  **C**。根据栈 LIFO，C 出栈后，栈内剩余 A、B。B 必须比 A 先出，故 C, A 顺序错误。
2.  **对**。通常用 `(tail+1)%size == head` 判满，此时空间未填满。
3.  **(rear - front + n) % n**。

### 第二模块
1.  **B**。第 1 层 1 个，第 2 层 2 个，第 3 层 4 个，第 4 层 3 个。叶子结点在 3、4 层，计算得 5 个。
2.  **对**。
3.  **2 3 4 5 7**。BST 的中序遍历永远是有序序列。

### 第三模块
1.  **错**。DFS 使用栈（递归系统栈），BFS 使用队列。
2.  **B**。
3.  **step + 1**。

### 第四模块
1.  **C**。DP 核心在于决策（max/min）。
2.  **dp[i-1] + dp[i-2]**。
3.  **34**。选择物品 1 (w=2, v=6) 和 物品 3 (w=5, v=18) 总价值 24；或者物品 2 和 3，总重 8 价值 28。此处最优解是选物品 2 和 3？不对，再看：5+3+2=10，全选！$6+10+18=34$。

### 第五模块
1.  **对**。
2.  **C**。
3.  **1100**。计算规则：最高位不变，后续位为原码当前位与前一位的异或。

---
**教练寄语**：
六级是 OI 生涯的第一个高峰。**树**决定了你的逻辑深度，**搜索**决定了你的解题广度，而**动态规划**决定了你的天花板高度。多画状态转移表，多手绘树的结构，加油！

GESP 六级编程能力认证讲义

第一模块：栈、队列与循环队列

1. 知识点拆解

栈 (Stack)：后进先出 (LIFO)。核心操作：push (入栈), pop (出栈), top (栈顶)。
队列 (Queue)：先进先出 (FIFO)。核心操作：push (入队), pop (出队), front (队头)。
循环队列：利用数组模拟，通过取模运算 % 连接首尾，解决“假溢出”问题。
- 队满条件：(tail + 1) % maxSize == head。
- 队空条件：tail == head。

2. 具体例子

例子 1.1：判断出栈序列合法性。若入栈顺序为 1, 2, 3，则出栈序列 3, 1, 2 是非法的。因为 3 出栈意味着 1 和 2 都在栈内，此时 2 必须在 1 之前出栈。

3. 练习巩固

【简单】单选题：一个栈的初始状态为空，现将元素 A, B, C, D 依次入栈，则不可能的出栈序列是（）。 A. A, B, C, D B. D, C, B, A C. C, A, B, D D. B, A, D, C
【中等】对错题：在循环队列中，为了区分队满和队空，通常会浪费一个数组单元不用。（）
【困难】填空题：已知循环队列的存储空间为 0..n-1，队头指针为 front，队尾指针为 rear，则当前队列中的元素个数计算公式为：____________________。

第二模块：树与二叉树（定义、遍历与哈夫曼）

1. 知识点拆解

二叉树遍历：
- 先序：根 -> 左 -> 右。
- 中序：左 -> 根 -> 右。
- 后序：左 -> 右 -> 根。
特殊二叉树：
- 完全二叉树：除最后层外全是满的，且最后层节点集中在左侧。
- 二叉排序树 (BST)：左子树 < 根 < 右子树。
哈夫曼树：带权路径长度 (WPL) 最短的树。用于哈夫曼编码（最优前缀编码）。

2. 具体例子

例子 2.1：已知二叉树先序为 ABDCE，中序为 BDAEC。 1. 先序首位 A 是根。 2. 中序中 A 左侧是 BD（左子树），右侧是 EC（右子树）。 3. 递归推导，可得出后序为 DBECA。

3. 练习巩固

【简单】单选题：若一棵完全二叉树共有 10 个节点，则其叶子节点数为（）。 A. 4 B. 5 C. 6 D. 7
【中等】对错题：哈夫曼编码是一种非等长编码，出现频率高的字符编码较短。（）
【困难】阅读程序写结果： cpp // 假设 BST 插入顺序为 5, 3, 7, 2, 4 // 问：该树的中序遍历结果是？ 输出：____

第三模块：搜索算法（DFS 与 BFS）

1. 知识点拆解

DFS（深度优先搜索）：
- 核心：递归/栈。
- 特点：一路走到底，不撞南墙不回头。适合求“所有解”或路径搜索。
BFS（宽度优先搜索）：
- 核心：队列。
- 特点：层层推进。适合求“最短路”或“最小步数”。

2. 具体例子

例子 3.1：在 $N \times M$ 迷宫中找起点到终点的最短路径。使用 BFS，将起点放入队列。每次弹出队头，将四周可达点入队并标记步数，最先到达终点的路径即为最短。

3. 练习巩固

【简单】对错题：DFS 算法通常使用队列作为辅助数据结构。（）
【中等】单选题：在一个无权图中，求 A 点到 B 点经过最少边数的路径，应首选（）。 A. DFS B. BFS C. 哈夫曼算法 D. 递推
【困难】阅读程序填空（回溯逻辑）： cpp void dfs(int step) { if(step > n) { output(); return; } for(int i = 1; i <= n; i++) { if(!vis[i]) { vis[i] = true; path[step] = i; dfs(__________); // 填入下一步 vis[i] = false; // 回溯，取消标记 } } }

第四模块：简单动态规划（DP）

1. 知识点拆解

核心思想：将大问题拆解为子问题，通过保存子问题的解（记忆化）来避免重复计算。
三要素：
1. 状态定义：dp[i] 代表什么含义。
2. 状态转移方程：dp[i] 如何从前面的 dp 值推导出来。
3. 边界条件：初始值。
0/1 背包：$N$ 件物品，容量 $M$。每件物品只有“选”或“不选”两种状态。

2. 具体例子

例子 4.1：采药问题（0/1背包）。 dp[j] 表示容量为 j 时的最大价值。方程：dp[j] = max(dp[j], dp[j - w[i]] + v[i])。注意：为了保证每件物品只选一次，容量 j 需逆序枚举。

3. 练习巩固

【简单】单选题：动态规划算法与递推算法的主要区别在于，动态规划通常涉及（）。 A. 递归 B. 循环 C. 最优化选择 D. 随机数
【中等】填空题：已知 dp[i] 表示爬 i 级台阶的方案数，每次可走 1 或 2 级。则转移方程为 dp[i] = ______________。
【困难】阅读程序写结果： cpp int dp[11] = {0}, w[3]={2,3,5}, v[3]={6,10,18}; for(int i=0; i<3; i++) for(int j=10; j>=w[i]; j--) dp[j] = max(dp[j], dp[j-w[i]]+v[i]); cout << dp[10]; 输出：____

第五模块：面向对象与格雷码

1. 知识点拆解

面向对象 (OOP)：将数据和处理数据的方法封装在“类 (Class)”中。
- 对象：类的实例。
- 成员变量与方法：public (公开), private (私有)。
格雷码 (Gray Code)：相邻两个编码之间只有一位二进制数不同。
- 3位格雷码：000, 001, 011, 010, 110, 111, 101, 100。

2. 具体例子

例子 5.1：定义一个简单的类。

class Rectangle {
public:
    int w, h;
    int getArea() { return w * h; } // 成员方法
};

3. 练习巩固

【简单】对错题：格雷码的主要特点是任意两个相邻的码值之间只有一位二进制数不同。（）
【中等】单选题：在 C++ 的类中，如果没有指定访问修饰符，默认的访问权限是（）。 A. public B. protected C. private D. static
【困难】填空题：4 位二进制数 1000 对应的格雷码是 _。（提示：$Gi = B_i \oplus B_{i+1}$）

教练参考答案与解析

第一模块

C。根据栈 LIFO，C 出栈后，栈内剩余 A、B。B 必须比 A 先出，故 C, A 顺序错误。
对。通常用 (tail+1)%size == head 判满，此时空间未填满。
(rear - front + n) % n。

第二模块

B。第 1 层 1 个，第 2 层 2 个，第 3 层 4 个，第 4 层 3 个。叶子结点在 3、4 层，计算得 5 个。
对。
2 3 4 5 7。BST 的中序遍历永远是有序序列。

第三模块

错。DFS 使用栈（递归系统栈），BFS 使用队列。
B。
step + 1。

第四模块

C。DP 核心在于决策（max/min）。
dp[i-1] + dp[i-2]。
34。选择物品 1 (w=2, v=6) 和物品 3 (w=5, v=18) 总价值 24；或者物品 2 和 3，总重 8 价值 28。此处最优解是选物品 2 和 3？不对，再看：5+3+2=10，全选！$6+10+18=34$。

第五模块

对。
C。
1100。计算规则：最高位不变，后续位为原码当前位与前一位的异或。

教练寄语：六级是 OI 生涯的第一个高峰。树决定了你的逻辑深度，搜索决定了你的解题广度，而动态规划决定了你的天花板高度。多画状态转移表，多手绘树的结构，加油！

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com