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

## 第一模块：函数进阶与参数传递

### 1. 知识点拆解
*   **作用域**：全局变量（在所有函数外定义，全程序可见）与局部变量（函数内定义，仅在该函数内有效）。
*   **参数传递**：
    *   **值传递**：将实参的值复制给形参，修改形参不影响实参。
    *   **引用传递**（C++ 特有 `&`）：形参是实参的“别名”，修改形参直接影响实参。
    *   **指针传递**：传递地址。
*   **Python 参数传递**：不可变对象（数字、字符串）类似值传递；可变对象（列表、字典）类似引用传递。

### 2. 具体例子
**例子 1.1**：交换两个数（体现引用传递的重要性）。
```cpp
void swap_ref(int &a, int &b) { // 引用传递
    int temp = a;
    a = b;
    b = temp;
}
int main() {
    int x = 10, y = 20;
    swap_ref(x, y); // x变为20, y变为10
    return 0;
}
```

### 3. 练习巩固
1.  **【简单】对错题**：在 C++ 中，局部变量和全局变量的名字可以相同，在函数内部访问时，局部变量优先。（ ）
2.  **【中等】单选题**：以下关于 C++ 函数参数传递的说法，正确的是（ ）。
    A. 值传递会改变实参的值
    B. 引用传递需要分配额外的内存来存储实参的副本
    C. 引用传递中，对形参的修改会直接作用于实参
    D. 只有指针传递才能返回多个结果
3.  **【困难】阅读程序写结果**：
    ```cpp
    int a = 5;
    void fun(int a, int &b) {
        a += 10;
        b += 10;
    }
    int main() {
        int b = 5;
        fun(a, b);
        cout << a << " " << b;
        return 0;
    }
    ```
    输出：__________

---

## 第二模块：结构体、指针与多维数组

### 1. 知识点拆解
*   **C++ 结构体 (struct)**：将不同类型的数据组合成一个整体。
*   **二维数组**：逻辑上像表格，内存中是连续存储的（行优先）。
    *   访问：`a[i][j]` 表示第 `i` 行第 `j` 列。
*   **指针基础**：`int *p = &a;`（p 存储了 a 的内存地址）。

### 2. 具体例子
**例子 2.1**：定义结构体存储学生信息并计算总分。
```cpp
struct Student {
    string name;
    int score[3]; // 三科成绩
};
Student s1 = {"Alice", {90, 80, 70}};
int total = s1.score[0] + s1.score[1] + s1.score[2];
```

### 3. 练习巩固
1.  **【简单】填空题**：定义 `int a[3][4];`，则该数组一共包含 ______ 个整型元素。
2.  **【中等】单选题**：已知 `int a = 10, *p = &a;`，若执行 `*p = 20;`，则 `a` 的值变为（ ）。
    A. 10  B. 20  C. a的地址  D. 编译错误
3.  **【困难】阅读程序写结果**：
    ```cpp
    int m[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int sum = 0;
    for(int i = 0; i < 2; i++)
        sum += m[i][1]; 
    cout << sum;
    ```
    输出：__________

---

## 第三模块：排序算法与复杂度估算

### 1. 知识点拆解
*   **三大基础排序**：
    *   **冒泡排序**：相邻比较，每轮将最大的“浮”到最后。
    *   **选择排序**：每轮选取最小的放在开头。
    *   **插入排序**：像打扑克牌，将新牌插入已排好序的序列中。
*   **稳定性**：若 `a == b` 且排序前 `a` 在 `b` 前，排序后 `a` 仍能在 `b` 前，则称排序稳定（冒泡、插入是稳定的；选择是不稳定的）。
*   **复杂度 (Big O)**：上述三种排序最坏情况都是 $O(n^2)$。

### 2. 具体例子
**例子 3.1**：冒泡排序一轮模拟。
序列：`[5, 2, 8, 1]`
1. 比较 5,2 -> `[2, 5, 8, 1]`
2. 比较 5,8 -> `[2, 5, 8, 1]`
3. 比较 8,1 -> `[2, 5, 1, 8]` （第一轮结束，最大值 8 已就位）

### 3. 练习巩固
1.  **【简单】单选题**：下列哪个排序算法在最坏情况下的时间复杂度是 $O(n^2)$？
    A. 冒泡排序  B. 插入排序  C. 选择排序  D. 以上都是
2.  **【中等】对错题**：选择排序是一种稳定的排序算法。（ ）
3.  **【困难】填空题**：对序列 `{5, 1, 4, 2}` 进行**插入排序**（升序），第二轮（将第二个元素插入正确位置）后的序列变为 `____________`。

---

## 第四模块：递推算法与文件读写

### 1. 知识点拆解
*   **递推 (Recurrence)**：从初始状态出发，利用公式推导出后续状态。
    *   典型例子：斐波那契数列 $f(n) = f(n-1) + f(n-2)$。
*   **文件操作**：
    *   `freopen("in.txt", "r", stdin);`
    *   `freopen("out.txt", "w", stdout);`
*   **异常处理**：`try { ... } catch (...) { ... }` 捕获运行时错误（如除以0）。

### 2. 具体例子
**例子 4.1**：递推求阶梯问题（一次走1阶或2阶，走n阶有多少种走法）。
```cpp
int f[100];
f[1] = 1; f[2] = 2;
for(int i = 3; i <= n; i++)
    f[i] = f[i-1] + f[i-2];
```

### 3. 练习巩固
1.  **【简单】单选题**：在 C++ 中，使用 `freopen` 进行文件重定向，需要包含哪个头文件？
    A. `<iostream>`  B. `<cstdio>`  C. `<fstream>`  D. `<cmath>`
2.  **【中等】填空题**：已知递推公式 $a_n = 2a_{n-1} + 1$，且 $a_1 = 1$，则 $a_4$ 的值是 ______。
3.  **【困难】阅读程序写结果**：
    ```cpp
    int ans[5] = {0, 1};
    for(int i = 2; i < 5; i++)
        ans[i] = ans[i-1] * i;
    cout << ans[4];
    ```
    输出：__________

---

## 教练参考答案与解析

### 第一模块
1.  **对**。
2.  **C**。值传递才复制副本，引用传递不复制。
3.  **5 15**。`a` 是值传递（且局部变量 `a` 遮蔽了全局 `a`，但注意此题中全局 `a` 并未被函数内操作修改），`b` 是引用传递，所以 `b` 变了，全局 `a` 没变。

### 第二模块
1.  **12**。
2.  **B**。`*p` 是对地址的解引用，修改 `*p` 就是修改 `a`。
3.  **7**。`m[0][1]` 是 2，`m[1][1]` 是 5，$2 + 5 = 7$。

### 第三模块
1.  **D**。
2.  **错**。选择排序不稳定（例如 `5, 5, 2` 排序后两个5的相对顺序会变）。
3.  **{1, 5, 4, 2}**。第一步看 1，插到 5 前面。

### 第四模块
1.  **B**。
2.  **15**。$a_1=1, a_2=3, a_3=7, a_4=15$。
3.  **24**。其实就是 $4!$（4的阶乘）。

---
**教练寄语**：
到了四级，你已经是一名准竞赛选手了！**递推**是动态规划（DP）的雏形，**排序**是数据处理的基础。一定要练习手写排序代码，并理解每一行为什么这么写。加油，未来的省队队员！

GESP 四级编程能力认证讲义

第一模块：函数进阶与参数传递

1. 知识点拆解

作用域：全局变量（在所有函数外定义，全程序可见）与局部变量（函数内定义，仅在该函数内有效）。
参数传递：
- 值传递：将实参的值复制给形参，修改形参不影响实参。
- 引用传递（C++ 特有 &）：形参是实参的“别名”，修改形参直接影响实参。
- 指针传递：传递地址。
Python 参数传递：不可变对象（数字、字符串）类似值传递；可变对象（列表、字典）类似引用传递。

2. 具体例子

例子 1.1：交换两个数（体现引用传递的重要性）。

void swap_ref(int &a, int &b) { // 引用传递
    int temp = a;
    a = b;
    b = temp;
}
int main() {
    int x = 10, y = 20;
    swap_ref(x, y); // x变为20, y变为10
    return 0;
}

3. 练习巩固

【简单】对错题：在 C++ 中，局部变量和全局变量的名字可以相同，在函数内部访问时，局部变量优先。（）
【中等】单选题：以下关于 C++ 函数参数传递的说法，正确的是（）。 A. 值传递会改变实参的值 B. 引用传递需要分配额外的内存来存储实参的副本 C. 引用传递中，对形参的修改会直接作用于实参 D. 只有指针传递才能返回多个结果
【困难】阅读程序写结果： cpp int a = 5; void fun(int a, int &b) { a += 10; b += 10; } int main() { int b = 5; fun(a, b); cout << a << " " << b; return 0; } 输出：____

第二模块：结构体、指针与多维数组

1. 知识点拆解

C++ 结构体 (struct)：将不同类型的数据组合成一个整体。
二维数组：逻辑上像表格，内存中是连续存储的（行优先）。
- 访问：a[i][j] 表示第 i 行第 j 列。
指针基础：int *p = &a;（p 存储了 a 的内存地址）。

2. 具体例子

例子 2.1：定义结构体存储学生信息并计算总分。

struct Student {
    string name;
    int score[3]; // 三科成绩
};
Student s1 = {"Alice", {90, 80, 70}};
int total = s1.score[0] + s1.score[1] + s1.score[2];

3. 练习巩固

【简单】填空题：定义 int a[3][4];，则该数组一共包含 ______ 个整型元素。
【中等】单选题：已知 int a = 10, *p = &a;，若执行 *p = 20;，则 a 的值变为（）。 A. 10 B. 20 C. a的地址 D. 编译错误
【困难】阅读程序写结果： cpp int m[2][3] = {{1, 2, 3}, {4, 5, 6}}; int sum = 0; for(int i = 0; i < 2; i++) sum += m[i][1]; cout << sum; 输出：____

第三模块：排序算法与复杂度估算

1. 知识点拆解

三大基础排序：
- 冒泡排序：相邻比较，每轮将最大的“浮”到最后。
- 选择排序：每轮选取最小的放在开头。
- 插入排序：像打扑克牌，将新牌插入已排好序的序列中。
稳定性：若 a == b 且排序前 a 在 b 前，排序后 a 仍能在 b 前，则称排序稳定（冒泡、插入是稳定的；选择是不稳定的）。
复杂度 (Big O)：上述三种排序最坏情况都是 $O(n^2)$。

2. 具体例子

例子 3.1：冒泡排序一轮模拟。序列：[5, 2, 8, 1] 1. 比较 5,2 -> [2, 5, 8, 1] 2. 比较 5,8 -> [2, 5, 8, 1] 3. 比较 8,1 -> [2, 5, 1, 8] （第一轮结束，最大值 8 已就位）

3. 练习巩固

【简单】单选题：下列哪个排序算法在最坏情况下的时间复杂度是 $O(n^2)$？ A. 冒泡排序 B. 插入排序 C. 选择排序 D. 以上都是
【中等】对错题：选择排序是一种稳定的排序算法。（）
【困难】填空题：对序列 {5, 1, 4, 2} 进行插入排序（升序），第二轮（将第二个元素插入正确位置）后的序列变为 ____________。

第四模块：递推算法与文件读写

1. 知识点拆解

递推 (Recurrence)：从初始状态出发，利用公式推导出后续状态。
- 典型例子：斐波那契数列 $f(n) = f(n-1) + f(n-2)$。
文件操作：
- freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);
异常处理：try { ... } catch (...) { ... } 捕获运行时错误（如除以0）。

2. 具体例子

例子 4.1：递推求阶梯问题（一次走1阶或2阶，走n阶有多少种走法）。

int f[100];
f[1] = 1; f[2] = 2;
for(int i = 3; i <= n; i++)
    f[i] = f[i-1] + f[i-2];

3. 练习巩固

【简单】单选题：在 C++ 中，使用 freopen 进行文件重定向，需要包含哪个头文件？ A. <iostream> B. <cstdio> C. <fstream> D. <cmath>
【中等】填空题：已知递推公式 $a_n = 2a_{n-1} + 1$，且 $a_1 = 1$，则 $a_4$ 的值是 ______。
【困难】阅读程序写结果： cpp int ans[5] = {0, 1}; for(int i = 2; i < 5; i++) ans[i] = ans[i-1] * i; cout << ans[4]; 输出：____

教练参考答案与解析

第一模块

对。
C。值传递才复制副本，引用传递不复制。
5 15。a 是值传递（且局部变量 a 遮蔽了全局 a，但注意此题中全局 a 并未被函数内操作修改），b 是引用传递，所以 b 变了，全局 a 没变。

第二模块

12。
B。*p 是对地址的解引用，修改 *p 就是修改 a。
7。m[0][1] 是 2，m[1][1] 是 5，$2 + 5 = 7$。

第三模块

D。
错。选择排序不稳定（例如 5, 5, 2 排序后两个5的相对顺序会变）。
{1, 5, 4, 2}。第一步看 1，插到 5 前面。

第四模块

B。
15。$a_1=1, a_2=3, a_3=7, a_4=15$。
24。其实就是 $4!$（4的阶乘）。

教练寄语：到了四级，你已经是一名准竞赛选手了！递推是动态规划（DP）的雏形，排序是数据处理的基础。一定要练习手写排序代码，并理解每一行为什么这么写。加油，未来的省队队员！

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