# 信息学奥赛（CSP-J/NOIP）核心考点通关讲义
> **授课对象：** 零基础/初级信息学学生  
> **全天规划：** 上午场（结构化数据：栈、队列、链表） ｜ 下午场（核心算法：函数、递归、回溯、递推）

---

## 上午场：线性数据结构（栈、队列、链表）

### 一、 栈 (Stack) —— “单向死胡同 / 弹夹”

#### 1. 核心概念
* **特点：** **后进先出（LIFO - Last In, First Out）**。数据只能从同一端（栈顶）进出。
* **生活类比：** 
  * 弹夹：最后一颗压进去的子弹，反而第一个打出来。
  * 叠盘子：洗好的盘子只能往上叠（压栈），取盘子时只能从最上面拿（弹栈）。
* **真题考点警示：** 考试必考“非法的出栈序列”。若入栈顺序是 `1, 2, 3`，`3` 先出来，说明 `1` 和 `2` 还在栈里且 `2` 在上面，因此下一个只能出 `2`，不能直接出 `1`。

#### 2. 代码实现思路（C++）
```cpp
int stk[105], top = 0; // stk是栈数组，top是栈顶指针

void push(int x) {     // 压栈
    stk[++top] = x; 
}

void pop() {           // 出栈
    top--; 
}

int getTop() {         // 取栈顶
    return stk[top]; 
}  
```

---

### 二、 队列 (Queue) —— “排队买票”

#### 1. 核心概念
* **特点：** **先进先出（FIFO - First In, First Out）**。从队尾进，从队头出。
* **生活类比：** 食堂排队打饭，先排的人先打到饭离开，后去的人只能排在队伍最后。
* **真题考点警示：** 它是图的**广度优先搜索（BFS）**算法的底层核心数据结构。

#### 2. 代码实现思路（C++ STL）
```cpp
#include <queue>
using namespace std;

queue<int> q;
// q.push(x);  // 元素 x 从队尾入队
// q.pop();    // 队头元素出队
// q.front();  // 查看当前队头元素
// q.empty();  // 检查队列是否为空
```

---

### 三、 链表 (Linked List) —— “寻宝游戏 / 纸条传话”

#### 1. 核心概念
* **特点：** **物理地址不连续**。数组在内存里像一排连体别墅，而链表像是在公园里散落的宝箱，靠指针线索串联。
* **节点结构：** 每个节点包含两部分——**数据域**（存什么）和**指针域**（下一个宝箱在哪里）。
* **优缺点对比：**
  * **数组：** 查找快（下标随机访问），但插删慢（中间删一个，后面全得往前挪）。
  * **链表：** 插删快（只需改指针，不挪动其他元素），但**不能随机访问**（想找第10个，必须从头顺着指针一个一个往下数）。

#### 2. 结构体定义
```cpp
struct Node {
    int data;     // 数据域
    Node* next;   // 指针域（指向下一个节点）
};
```

---

### ☕ 上午场课堂巩固练习
1. **[栈]** 元素入栈顺序为 `1, 2, 3, 4, 5`，下列哪个是**合法**的出栈序列？  
   A. `5, 4, 3, 2, 1`  B. `4, 5, 3, 1, 2`  C. `3, 1, 4, 2, 5`  D. `2, 3, 1, 5, 4`  
   *(答案：A)*
2. **[队列]** 下列算法中，通常必须借助“队列”来实现的是：  
   A. 深度优先搜索 (DFS)  B. 广度优先搜索 (BFS)  C. 快速排序  D. 二分查找  
   *(答案：B)*
3. **[链表]** 与顺序存储（数组）相比，链表不具有的特点是：  
   A. 插入和删除元素时不需要移动大量元素  
   B. 不必事先估计存储空间的大小  
   C. 所需空间与线性表长度成正比  
   D. 可以通过下标随机访问任意一个元素  
   *(答案：D)*

---
---

## ☀️ 下午场：函数、递归与递推算法

### 一、 函数与调用机制 —— “子任务代办处”

#### 1. 核心概念
* **函数调用：** 把一段经常使用的代码封装起来。主函数叫“主调函数”，被调用的叫“被调函数”。
* **参数传递：**
  * **传值调用（Value）：** 传递的是复印件。函数里改了参数，外面的原变量**不受影响**。
  * **传引用调用（Reference，加 `&`）：** 传递的是原件钥匙。函数里改了参数，外面的原变量**跟着一起变**。
* **系统栈内存：** 每次发生函数调用，系统都会在内存的**栈区**开辟一块空间（栈帧）用来存放局部变量和返回地址。如果函数调用无限嵌套且不返回，就会导致**栈溢出（Stack Overflow）**。

---

### 二、 函数递归 (Recursion) —— “俄罗斯套娃”

#### 1. 核心概念
* **什么是递归？** 一个函数在它的函数体内**调用它自己**。
* **递归的两大黄金法则（缺一不可）：**
  1. **递归出口（边界条件）：** 什么时候必须停下来？（没有出口会导致无限递归，直接爆栈）。
  2. **递归表达式（缩小规模）：** 如何把大问题拆解成形式完全相同的小问题？

#### 2. 经典例子：求阶乘 $n!$
```cpp
int factorial(int n) {
    if (n == 1) return 1;          // 1. 递归出口
    return n * factorial(n - 1);   // 2. 缩小规模，自调用
}
```

---

### 三、 回溯算法 (Backtracking) —— “走迷宫与试错”

#### 1. 核心概念
* **本质：** 一种系统化的**枚举搜索、试探与纠错**策略。
* **核心口诀：** “一条路走到黑，撞了南墙再回头”。当发觉当前选择不满足条件时，立刻**撤销上一步的选择（回溯）**，退回上一层尝试其他分支。
* **剪枝优化：** 在搜索过程中，如果发现某个分支无论如何也走不到头（不合法），就提前把它“剪掉”，不再浪费时间搜索。

---

### 四、 递推与线性递推 (Recurrence) —— “站在巨人的肩膀上”

#### 1. 核心概念
* **与递归的区别：** 递归是**自顶向下**想（顺着逻辑往下拆，最后由底向上返回）；递推是**自底向上**算（从已知的最小边界开始，一步步往前推导直到目标）。
* **线性递推公式：** 后一项由前一项或前几项通过固定的数学关系推导出来。例如大名鼎鼎的**斐波那契数列**：
  $$f(1)=1, \quad f(2)=1, \quad f(n) = f(n-1) + f(n-2)$$

#### 2. 空间优化（滚动变量）
如果计算第 $n$ 项时，只依赖于前面紧挨着的两项，我们就不需要开辟一个巨大的数组把所有历史数据存起来，只需用两个临时变量滚动更新即可，将空间复杂度从 $O(n)$ 降到 **$O(1)$**。

---

### ☕ 下午场课堂巩固练习
1. **[函数参数]** 若希望在自定义函数内部修改主函数里的变量值，形参定义时必须使用：  
   A. 普通变量  B. 常量 (const)  C. 引用类型 (`&`)  D. 全局变量  
   *(答案：C)*
2. **[递归理解]** 阅读代码：
   ```cpp
   int f(int n) {
       if (n == 0) return 1;
       return n * f(n - 1);
   }
   ```
   请问 `f(4)` 的返回值是：  
   A. 4  B. 12  C. 24  D. 10  
   *(答案：C，计算 $4 \times 3 \times 2 \times 1 = 24$)*
3. **[回溯概念]** 回溯算法在搜索解空间的过程中，当发现当前选择无法得到满足条件的解时，通过退回一步来寻找别的可能，这种策略属于：  
   A. 贪心算法  B. 动态规划  C. 枚举与试探纠错  D. 二分搜索  
   *(答案：C)*
4. **[递推计算]** 某人爬楼梯，一次可以走 1 阶或 2 阶。走到第 5 阶楼梯共有多少种不同的走法？（已知 $f(1)=1, f(2)=2, f(3)=3, f(4)=5$）  
   A. 5 种  B. 8 种  C. 13 种  D. 21 种  
   *(答案：B，满足斐波那契规律：$f(5) = f(4) + f(3) = 5 + 3 = 8$)*

信息学奥赛（CSP-J/NOIP）核心考点通关讲义

授课对象： 零基础/初级信息学学生
全天规划： 上午场（结构化数据：栈、队列、链表）｜下午场（核心算法：函数、递归、回溯、递推）

上午场：线性数据结构（栈、队列、链表）

一、栈 (Stack) —— “单向死胡同 / 弹夹”

1. 核心概念

特点： 后进先出（LIFO - Last In, First Out）。数据只能从同一端（栈顶）进出。
生活类比：
弹夹：最后一颗压进去的子弹，反而第一个打出来。
叠盘子：洗好的盘子只能往上叠（压栈），取盘子时只能从最上面拿（弹栈）。
真题考点警示： 考试必考“非法的出栈序列”。若入栈顺序是 1, 2, 3，3 先出来，说明 1 和 2 还在栈里且 2 在上面，因此下一个只能出 2，不能直接出 1。

2. 代码实现思路（C++）

int stk[105], top = 0; // stk是栈数组，top是栈顶指针

void push(int x) {     // 压栈
    stk[++top] = x; 
} 

void pop() {           // 出栈
    top--; 
}              

int getTop() {         // 取栈顶
    return stk[top]; 
}

二、队列 (Queue) —— “排队买票”

1. 核心概念

特点： 先进先出（FIFO - First In, First Out）。从队尾进，从队头出。
生活类比： 食堂排队打饭，先排的人先打到饭离开，后去的人只能排在队伍最后。
真题考点警示： 它是图的广度优先搜索（BFS）算法的底层核心数据结构。

2. 代码实现思路（C++ STL）

#include <queue>
using namespace std;

queue<int> q;
// q.push(x);  // 元素 x 从队尾入队
// q.pop();    // 队头元素出队
// q.front();  // 查看当前队头元素
// q.empty();  // 检查队列是否为空

三、链表 (Linked List) —— “寻宝游戏 / 纸条传话”

1. 核心概念

特点： 物理地址不连续。数组在内存里像一排连体别墅，而链表像是在公园里散落的宝箱，靠指针线索串联。
节点结构： 每个节点包含两部分——数据域（存什么）和指针域（下一个宝箱在哪里）。
优缺点对比：
数组： 查找快（下标随机访问），但插删慢（中间删一个，后面全得往前挪）。
链表： 插删快（只需改指针，不挪动其他元素），但不能随机访问（想找第10个，必须从头顺着指针一个一个往下数）。

2. 结构体定义

struct Node {
    int data;     // 数据域
    Node* next;   // 指针域（指向下一个节点）
};

☕ 上午场课堂巩固练习

[栈] 元素入栈顺序为 1, 2, 3, 4, 5，下列哪个是合法的出栈序列？
A. 5, 4, 3, 2, 1 B. 4, 5, 3, 1, 2 C. 3, 1, 4, 2, 5 D. 2, 3, 1, 5, 4
(答案：A)
[队列] 下列算法中，通常必须借助“队列”来实现的是：
A. 深度优先搜索 (DFS) B. 广度优先搜索 (BFS) C. 快速排序 D. 二分查找
(答案：B)
[链表] 与顺序存储（数组）相比，链表不具有的特点是：
A. 插入和删除元素时不需要移动大量元素
B. 不必事先估计存储空间的大小
C. 所需空间与线性表长度成正比
D. 可以通过下标随机访问任意一个元素
(答案：D)

---

☀️ 下午场：函数、递归与递推算法

一、函数与调用机制 —— “子任务代办处”

1. 核心概念

函数调用： 把一段经常使用的代码封装起来。主函数叫“主调函数”，被调用的叫“被调函数”。
参数传递：
传值调用（Value）： 传递的是复印件。函数里改了参数，外面的原变量不受影响。
传引用调用（Reference，加 &）： 传递的是原件钥匙。函数里改了参数，外面的原变量跟着一起变。
系统栈内存： 每次发生函数调用，系统都会在内存的栈区开辟一块空间（栈帧）用来存放局部变量和返回地址。如果函数调用无限嵌套且不返回，就会导致栈溢出（Stack Overflow）。

二、函数递归 (Recursion) —— “俄罗斯套娃”

1. 核心概念

什么是递归？ 一个函数在它的函数体内调用它自己。
递归的两大黄金法则（缺一不可）：
递归出口（边界条件）： 什么时候必须停下来？（没有出口会导致无限递归，直接爆栈）。
递归表达式（缩小规模）： 如何把大问题拆解成形式完全相同的小问题？

2. 经典例子：求阶乘 $n!$

int factorial(int n) {
    if (n == 1) return 1;          // 1. 递归出口
    return n * factorial(n - 1);   // 2. 缩小规模，自调用
}

三、回溯算法 (Backtracking) —— “走迷宫与试错”

1. 核心概念

本质： 一种系统化的枚举搜索、试探与纠错策略。
核心口诀： “一条路走到黑，撞了南墙再回头”。当发觉当前选择不满足条件时，立刻撤销上一步的选择（回溯），退回上一层尝试其他分支。
剪枝优化： 在搜索过程中，如果发现某个分支无论如何也走不到头（不合法），就提前把它“剪掉”，不再浪费时间搜索。

四、递推与线性递推 (Recurrence) —— “站在巨人的肩膀上”

1. 核心概念

与递归的区别： 递归是自顶向下想（顺着逻辑往下拆，最后由底向上返回）；递推是自底向上算（从已知的最小边界开始，一步步往前推导直到目标）。
线性递推公式： 后一项由前一项或前几项通过固定的数学关系推导出来。例如大名鼎鼎的斐波那契数列： $$f(1)=1, \quad f(2)=1, \quad f(n) = f(n-1) + f(n-2)$$

2. 空间优化（滚动变量）

如果计算第 $n$ 项时，只依赖于前面紧挨着的两项，我们就不需要开辟一个巨大的数组把所有历史数据存起来，只需用两个临时变量滚动更新即可，将空间复杂度从 $O(n)$ 降到 $O(1)$。

☕ 下午场课堂巩固练习

[函数参数] 若希望在自定义函数内部修改主函数里的变量值，形参定义时必须使用：
A. 普通变量 B. 常量 (const) C. 引用类型 (&) D. 全局变量
(答案：C)
[递归理解] 阅读代码： cpp int f(int n) { if (n == 0) return 1; return n * f(n - 1); } 请问 f(4) 的返回值是：
A. 4 B. 12 C. 24 D. 10
(答案：C，计算 $4 \times 3 \times 2 \times 1 = 24$)
[回溯概念] 回溯算法在搜索解空间的过程中，当发现当前选择无法得到满足条件的解时，通过退回一步来寻找别的可能，这种策略属于：
A. 贪心算法 B. 动态规划 C. 枚举与试探纠错 D. 二分搜索
(答案：C)
[递推计算] 某人爬楼梯，一次可以走 1 阶或 2 阶。走到第 5 阶楼梯共有多少种不同的走法？（已知 $f(1)=1, f(2)=2, f(3)=3, f(4)=5$）
A. 5 种 B. 8 种 C. 13 种 D. 21 种
(答案：B，满足斐波那契规律：$f(5) = f(4) + f(3) = 5 + 3 = 8$)

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

上午场：线性数据结构（栈、队列、链表）

信息学奥赛（CSP-J/NOIP）核心考点通关讲义

上午场：线性数据结构（栈、队列、链表）

一、 栈 (Stack) —— “单向死胡同 / 弹夹”

1. 核心概念

2. 代码实现思路（C++）

二、 队列 (Queue) —— “排队买票”

1. 核心概念

2. 代码实现思路（C++ STL）

三、 链表 (Linked List) —— “寻宝游戏 / 纸条传话”

1. 核心概念

2. 结构体定义

☕ 上午场课堂巩固练习

---

☀️ 下午场：函数、递归与递推算法

一、 函数与调用机制 —— “子任务代办处”

1. 核心概念

二、 函数递归 (Recursion) —— “俄罗斯套娃”

1. 核心概念

2. 经典例子：求阶乘 $n!$

三、 回溯算法 (Backtracking) —— “走迷宫与试错”

1. 核心概念

四、 递推与线性递推 (Recurrence) —— “站在巨人的肩膀上”

1. 核心概念

2. 空间优化（滚动变量）

☕ 下午场课堂巩固练习

一、栈 (Stack) —— “单向死胡同 / 弹夹”

二、队列 (Queue) —— “排队买票”

三、链表 (Linked List) —— “寻宝游戏 / 纸条传话”

一、函数与调用机制 —— “子任务代办处”

二、函数递归 (Recursion) —— “俄罗斯套娃”

三、回溯算法 (Backtracking) —— “走迷宫与试错”

四、递推与线性递推 (Recurrence) —— “站在巨人的肩膀上”