# 信息学奥赛（CSP-J）零基础启蒙培训讲义

## 第10天：错综复杂的网、递归思维与初赛终极冲刺（图论基础、组合数学与真题模考）

* **总时长**：6 小时（上午 3 小时，下午 3 小时）
* **培训目标**：通过生动的生活化比喻，帮助零基础学生掌握图论基本概念（顶点、边、度数）、图的遍历（DFS 与 BFS）、排列组合与计数原理、递归思想的本质，并通过综合全真模考为 CSP-J 初赛画上圆满句号。

---

## 📅 上午场：图论基础与图的遍历（09:00 - 12:00）

### 一、 什么是图？（Graph）

#### 1. 生活中的比喻

* 树是上下级、单向延伸的阶层关系。但现实生活中，人与人之间的关系、城市与城市之间的交通网，是**你中有我、我中有你、错综复杂的网状结构**。
* 在计算机科学中，这种网状结构就叫做**图（Graph）**。

#### 2. 图的核心要素

* **顶点（Vertex / Node）**：图里的“路口”或“人”（比如：各个城市、社交网站上的用户）。
* **边（Edge）**：顶点与顶点之间的“连线”（比如：城市之间的公路、好友关系）。
* **有向图 vs 无向图**：
  * **无向图（Undirected Graph）**：边是双向的，没有箭头。比如微信好友，你加我我也加你。
  * **有向图（Directed Graph）**：边是有单向箭头的。比如微博关注，你关注了某明星，明星可没回关你。

---

### 二、 握手定理（图论第一大考点）

#### 1. 什么是顶点的度（Degree）？

* 在**无向图**中，和某个顶点直接相连的边的条数，叫做这个顶点的**度**。
* 在**有向图**中，度被细分为：
  * **入度（In-degree）**：有多少条边指向该顶点（比如微博被多少人关注）。
  * **出度（Out-degree）**：有多少条边从该顶点出发（比如你关注了多少人）。

#### 2. 握手定理（The Handshaking Lemma）

> **💡 初赛必考结论**：
>
> 1. **在无向图中，所有顶点的度数之和，等于边数的 2 倍**。
>    $$\sum \text{度数} = 2 \times \text{边数}$$
>    *(原因很简单：一条边连接两个顶点，每条边会被两端的顶点各贡献一次度数)*
> 2. **在有向图中，所有顶点的入度之和 = 所有顶点的出度之和 = 边数**。

---

### 三、 图的遍历：DFS 与 BFS

要在庞大的迷宫或交通网中把所有点都走一遍，有两种经典的探索策略：

#### 1. 深度优先搜索（DFS - Depth-First Search）

* **生活比喻**：“不撞南墙不回头，一条路走到黑”。
* 每次挑一条没走过的路一直往前走，直到无路可走了，再退回上一个路口，换一条新路继续走。
* **底层支撑**：由于具有“回溯”特性，它天生依赖**栈（Stack）**（系统递归栈）来实现。

#### 2. 广度优先搜索（BFS - Breadth-First Search）

* **生活比喻**：“水波纹扩散”或“人际关系网（先看一度好友，再看二度好友）”。
* 从起点出发，先把身边的所有直接邻居看完，然后再一层一层向外扩张。
* **底层支撑**：为了保证“先看到的先扩展”，它必须使用**队列（Queue）**来实现。

---

## 📅 下午场：计数原理、递归思维与结营模考（14:00 - 17:00）

### 一、 计数原理：排列与组合

在CSP-J初赛中，数学计数题（排列组合、抽屉原理）几乎每年必考 2~3 道。

#### 1. 加法原理与乘法原理

* **加法原理（分类）**：做一件事情有 $n$ 类独立的方法，第 1 类有 $m_1$ 种，第 2 类有 $m_2$ 种……总方法数就是 $m_1 + m_2 + \dots$。
* **乘法原理（分步）**：做一件事情需要分 $n$ 个步骤，第 1 步有 $m_1$ 种，第 2 步有 $m_2$ 种……总方法数就是各个步骤相乘：$m_1 \times m_2 \times \dots$。

#### 2. 排列数 $A(n, m)$ 与 组合数 $C(n, m)$

* **排列（Permutation - 有顺序要求）**：从 $n$ 个不同元素中取出 $m$ 个排成一列。
  $$A(n, m) = n \times (n-1) \times \dots \times (n-m+1) = \frac{n!}{(n-m)!}$$
* **组合（Combination - 不讲究顺序）**：从 $n$ 个不同元素中取出 $m$ 个组成一组（不管先后顺序）。
  $$C(n, m) = \frac{A(n, m)}{m!} = \frac{n!}{m!(n-m)!}$$

#### 3. 经典解题模型

* **捆绑法（要求相邻）**：把必须相邻的几个人“绑”成一个人看待。
* **插空法（要求不相邻）**：先把没有要求的元素排好，然后在空隙中把不相邻的元素“插”进去。
* **抽屉原理（鸽巢原理）**：把 $n+1$ 个物体放进 $n$ 个抽屉里，那么至少有一个抽屉里会放着**至少 2 个**物体。

---

### 二、 递归思维的本质（Recursion）

#### 1. 经典故事

* “从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙……’”
* 这就是一个典型的**无限递归**。而在计算机里，合法的递归必须要有**边界条件（出口）**，否则会引发“系统栈空间溢出（Stack Overflow）”。

#### 2. 递归的精髓

* **大化小**：把一个复杂的大问题，拆解成结构完全相同、但规模更小的小问题来解决。
* 经典的递归例子：求阶乘 $n!$、斐波那契数列（Fibonacci）。

---

### 三、 结营综合全真模考

*(下午 15:30 - 16:30，进行 60 分钟限时模拟测试，题型全真对标 CSP-J 初赛选择题，查漏补缺)*

---

## 📝 第10天结营模考与强化练习卷（学生版）

**班级**：______________  **姓名**：______________  **得分**：______________

### 一、 选择题（共 10 题）

1. 在一个无向图中，所有顶点的度数之和等于（ ）。
   A. 图的边数
   B. 图的边数的两倍
   C. 图的顶点数
   D. 图的顶点数的两倍

2. 设无向图 $G$ 有 16 条边，且每个顶点的度数都是 2，则图 $G$ 有（ ）个顶点。
   A. 8
   B. 12
   C. 16
   D. 32

3. 广度优先搜索（BFS）在遍历图的时候，需要用到的核心数据结构是（ ）。
   A. 栈
   B. 队列
   C. 散列表
   D. 向量

4. 5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法？
   A. 24
   B. 36
   C. 48
   D. 72

5. 从 5 位男生和 4 位女生中选出 4 人组成一个学习小组，要求学习小组中男生和女生都有，共有多少种不同的选法？（ ）
   A. 100
   B. 120
   C. 126
   D. 140

6. 下列关于有向图的说法中，正确的是（ ）。
   A. 所有顶点的入度之和等于所有顶点的出度之和
   B. 所有顶点的入度之和是边数的 2 倍
   C. 有向图不可能存在强连通分量
   D. 拓扑排序只适用于无向图

7. 递归调用在运行时如果层数过多，最容易引发的系统错误是（ ）。
   A. 系统分配的堆空间溢出
   B. 系统分配的栈空间溢出
   C. 磁盘存储空间不足
   D. CPU 缓存溢出

8. 某公司有 10 名员工，分为 3 个部门：A 部门 4 名，B 部门 3 名，C 部门 3 名。现从中选出 4 人组成一个工作组，且**每个部门至少要有 1 人**，有多少种选择方式？（ ）
   A. 120
   B. 126
   C. 132
   D. 238

9. 有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点，一次最多坐两个人。四个人独自过河时间分别为 1, 2, 4, 8（分钟），两个人过河时间为较大者。让四个人全部过河到 B 点的**最短时间**是（ ）分钟。
   A. 14
   B. 15
   C. 16
   D. 17

10. 下列关于算法时间复杂度的描述中，错误的是（ ）。
    A. 冒泡排序在最坏情况下的时间复杂度为 $O(n^2)$
    B. 长度为 $n$ 的有序数组进行折半查找（二分查找）的最坏时间复杂度为 $O(\log_2 n)$
    C. 基于比较的排序算法，其时间复杂度的下限是 $O(n \log_2 n)$
    D. 顺序查找（线性查找）的时间复杂度在任何情况下都是 $O(1)$

---

*(注：教师答案与详细解析页在下方，建议打印前单独切分)*

\newpage

---

## 📖 结营模考练习卷 —— 标准答案与详细解析

1. **正确答案：B**

* **详细解析**：
     * 根据图论中的**握手定理**：在无向图中，所有顶点的度数之和等于边数的 2 倍。

2. **正确答案：D**

* **详细解析**：
     * 设顶点数为 $V$。根据握手定理：$V \times 2 = 16 \times 2$，$2V = 32$，解得 $V = 16$。故选 D。

3. **正确答案：B**

* **详细解析**：
     * 广度优先搜索（BFS）层序扩展时依赖队列（Queue）的先进先出特性。

4. **正确答案：C**

* **详细解析**：
     * 采用捆绑法：把双胞胎看作一个整体，此时总共看作 4 个元素进行全排列，$A_4^4 = 24$ 种；双胞胎内部可以互换位置，有 $2! = 2$ 种。总方案数 $24 \times 2 = 48$ 种。

5. **正确答案：B**

* **详细解析**：
     * 分类讨论（男生和女生都有）：
       * 1男3女：$C_5^1 \times C_4^3 = 5 \times 4 = 20$
       * 2男2女：$C_5^2 \times C_4^2 = 10 \times 6 = 60$
       * 3男1女：$C_5^3 \times C_4^1 = 10 \times 4 = 40$
       * 总和：$20 + 60 + 40 = 120$ 种。故选 B。

6. **正确答案：A**

* **详细解析**：
     * 在有向图中，每条边有一个起点（贡献一个出度）和一个终点（贡献一个入度），因此所有顶点的入度之和恒等于所有顶点的出度之和，且都等于图的边数。故选 A。

7. **正确答案：B**

* **详细解析**：
     * 函数调用和递归的参数、返回地址统一保存在系统的**调用栈（Call Stack）**中。递归层数过多会导致栈空间耗尽，即**栈溢出（Stack Overflow）**。

8. **正确答案：B**

* **详细解析**：
     * 4人组合且每部门至少1人，只有两种部门人数分配结构：(2, 1, 1) 或没有其他（由于各部门人数分别为4, 3, 3）。
     * 分配方案用组合数计算：$C(4,2)C(3,1)C(3,1) + C(4,1)C(3,2)C(3,1) + C(4,1)C(3,1)C(3,2)$。计算得结果为 126 种。

9. **正确答案：B**

* **详细解析**：

* 经典过河贪心策略：

1. 1和2过河（耗时2）
       2. 1回（耗时1）
       3. 4和8过河（耗时8）
       4. 2回（耗时2）
       5. 1和2过河（耗时2）

* 总耗时：$2 + 1 + 8 + 2 + 2 = 15$ 分钟。故选 B。

10. **正确答案：D**

* **详细解析**：
      * 选项 D 错误：顺序查找在最好情况下（要找的元素刚好在第一个位置）时间复杂度为 $O(1)$，但在最坏情况下需要找遍全部元素，时间复杂度为 $O(n)$，并非“任何情况下都是 $O(1)$”。

信息学奥赛（CSP-J）零基础启蒙培训讲义

第10天：错综复杂的网、递归思维与初赛终极冲刺（图论基础、组合数学与真题模考）

总时长：6 小时（上午 3 小时，下午 3 小时）
培训目标：通过生动的生活化比喻，帮助零基础学生掌握图论基本概念（顶点、边、度数）、图的遍历（DFS 与 BFS）、排列组合与计数原理、递归思想的本质，并通过综合全真模考为 CSP-J 初赛画上圆满句号。

📅 上午场：图论基础与图的遍历（09:00 - 12:00）

一、什么是图？（Graph）

1. 生活中的比喻

树是上下级、单向延伸的阶层关系。但现实生活中，人与人之间的关系、城市与城市之间的交通网，是你中有我、我中有你、错综复杂的网状结构。
在计算机科学中，这种网状结构就叫做图（Graph）。

2. 图的核心要素

顶点（Vertex / Node）：图里的“路口”或“人”（比如：各个城市、社交网站上的用户）。
边（Edge）：顶点与顶点之间的“连线”（比如：城市之间的公路、好友关系）。
有向图 vs 无向图：
无向图（Undirected Graph）：边是双向的，没有箭头。比如微信好友，你加我我也加你。
有向图（Directed Graph）：边是有单向箭头的。比如微博关注，你关注了某明星，明星可没回关你。

二、握手定理（图论第一大考点）

1. 什么是顶点的度（Degree）？

在无向图中，和某个顶点直接相连的边的条数，叫做这个顶点的度。
在有向图中，度被细分为：
入度（In-degree）：有多少条边指向该顶点（比如微博被多少人关注）。
出度（Out-degree）：有多少条边从该顶点出发（比如你关注了多少人）。

2. 握手定理（The Handshaking Lemma）

💡 初赛必考结论：

在无向图中，所有顶点的度数之和，等于边数的 2 倍。 $$\sum \text{度数} = 2 \times \text{边数}$$ (原因很简单：一条边连接两个顶点，每条边会被两端的顶点各贡献一次度数)

在有向图中，所有顶点的入度之和 = 所有顶点的出度之和 = 边数。

三、图的遍历：DFS 与 BFS

要在庞大的迷宫或交通网中把所有点都走一遍，有两种经典的探索策略：

1. 深度优先搜索（DFS - Depth-First Search）

生活比喻：“不撞南墙不回头，一条路走到黑”。
每次挑一条没走过的路一直往前走，直到无路可走了，再退回上一个路口，换一条新路继续走。
底层支撑：由于具有“回溯”特性，它天生依赖栈（Stack）（系统递归栈）来实现。

2. 广度优先搜索（BFS - Breadth-First Search）

生活比喻：“水波纹扩散”或“人际关系网（先看一度好友，再看二度好友）”。
从起点出发，先把身边的所有直接邻居看完，然后再一层一层向外扩张。
底层支撑：为了保证“先看到的先扩展”，它必须使用队列（Queue）来实现。

📅 下午场：计数原理、递归思维与结营模考（14:00 - 17:00）

一、计数原理：排列与组合

在CSP-J初赛中，数学计数题（排列组合、抽屉原理）几乎每年必考 2~3 道。

1. 加法原理与乘法原理

加法原理（分类）：做一件事情有 $n$ 类独立的方法，第 1 类有 $m_1$ 种，第 2 类有 $m_2$ 种……总方法数就是 $m_1 + m_2 + \dots$。
乘法原理（分步）：做一件事情需要分 $n$ 个步骤，第 1 步有 $m_1$ 种，第 2 步有 $m_2$ 种……总方法数就是各个步骤相乘：$m_1 \times m_2 \times \dots$。

2. 排列数 $A(n, m)$ 与组合数 $C(n, m)$

排列（Permutation - 有顺序要求）：从 $n$ 个不同元素中取出 $m$ 个排成一列。 $$A(n, m) = n \times (n-1) \times \dots \times (n-m+1) = \frac{n!}{(n-m)!}$$
组合（Combination - 不讲究顺序）：从 $n$ 个不同元素中取出 $m$ 个组成一组（不管先后顺序）。 $$C(n, m) = \frac{A(n, m)}{m!} = \frac{n!}{m!(n-m)!}$$

3. 经典解题模型

捆绑法（要求相邻）：把必须相邻的几个人“绑”成一个人看待。
插空法（要求不相邻）：先把没有要求的元素排好，然后在空隙中把不相邻的元素“插”进去。
抽屉原理（鸽巢原理）：把 $n+1$ 个物体放进 $n$ 个抽屉里，那么至少有一个抽屉里会放着至少 2 个物体。

二、递归思维的本质（Recursion）

1. 经典故事

“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙……’”
这就是一个典型的无限递归。而在计算机里，合法的递归必须要有边界条件（出口），否则会引发“系统栈空间溢出（Stack Overflow）”。

2. 递归的精髓

大化小：把一个复杂的大问题，拆解成结构完全相同、但规模更小的小问题来解决。
经典的递归例子：求阶乘 $n!$、斐波那契数列（Fibonacci）。

三、结营综合全真模考

(下午 15:30 - 16:30，进行 60 分钟限时模拟测试，题型全真对标 CSP-J 初赛选择题，查漏补缺)

📝 第10天结营模考与强化练习卷（学生版）

班级：__ 姓名：__ 得分：__

一、选择题（共 10 题）

在一个无向图中，所有顶点的度数之和等于（）。 A. 图的边数 B. 图的边数的两倍 C. 图的顶点数 D. 图的顶点数的两倍
设无向图 $G$ 有 16 条边，且每个顶点的度数都是 2，则图 $G$ 有（）个顶点。 A. 8 B. 12 C. 16 D. 32
广度优先搜索（BFS）在遍历图的时候，需要用到的核心数据结构是（）。 A. 栈 B. 队列 C. 散列表 D. 向量
5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（）种不同排列方法？ A. 24 B. 36 C. 48 D. 72
从 5 位男生和 4 位女生中选出 4 人组成一个学习小组，要求学习小组中男生和女生都有，共有多少种不同的选法？（） A. 100 B. 120 C. 126 D. 140
下列关于有向图的说法中，正确的是（）。 A. 所有顶点的入度之和等于所有顶点的出度之和 B. 所有顶点的入度之和是边数的 2 倍 C. 有向图不可能存在强连通分量 D. 拓扑排序只适用于无向图
递归调用在运行时如果层数过多，最容易引发的系统错误是（）。 A. 系统分配的堆空间溢出 B. 系统分配的栈空间溢出 C. 磁盘存储空间不足 D. CPU 缓存溢出
某公司有 10 名员工，分为 3 个部门：A 部门 4 名，B 部门 3 名，C 部门 3 名。现从中选出 4 人组成一个工作组，且每个部门至少要有 1 人，有多少种选择方式？（） A. 120 B. 126 C. 132 D. 238
有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点，一次最多坐两个人。四个人独自过河时间分别为 1, 2, 4, 8（分钟），两个人过河时间为较大者。让四个人全部过河到 B 点的最短时间是（）分钟。 A. 14 B. 15 C. 16 D. 17
下列关于算法时间复杂度的描述中，错误的是（）。 A. 冒泡排序在最坏情况下的时间复杂度为 $O(n^2)$ B. 长度为 $n$ 的有序数组进行折半查找（二分查找）的最坏时间复杂度为 $O(\log_2 n)$ C. 基于比较的排序算法，其时间复杂度的下限是 $O(n \log_2 n)$ D. 顺序查找（线性查找）的时间复杂度在任何情况下都是 $O(1)$

(注：教师答案与详细解析页在下方，建议打印前单独切分)

\newpage

📖 结营模考练习卷 —— 标准答案与详细解析

正确答案：B
详细解析：
- 根据图论中的握手定理：在无向图中，所有顶点的度数之和等于边数的 2 倍。
正确答案：D
详细解析：
- 设顶点数为 $V$。根据握手定理：$V \times 2 = 16 \times 2$，$2V = 32$，解得 $V = 16$。故选 D。
正确答案：B
详细解析：
- 广度优先搜索（BFS）层序扩展时依赖队列（Queue）的先进先出特性。
正确答案：C
详细解析：
- 采用捆绑法：把双胞胎看作一个整体，此时总共看作 4 个元素进行全排列，$A_4^4 = 24$ 种；双胞胎内部可以互换位置，有 $2! = 2$ 种。总方案数 $24 \times 2 = 48$ 种。
正确答案：B
详细解析：
- 分类讨论（男生和女生都有）：
- 1男3女：$C_5^1 \times C_4^3 = 5 \times 4 = 20$
- 2男2女：$C_5^2 \times C_4^2 = 10 \times 6 = 60$
- 3男1女：$C_5^3 \times C_4^1 = 10 \times 4 = 40$
- 总和：$20 + 60 + 40 = 120$ 种。故选 B。
正确答案：A
详细解析：
- 在有向图中，每条边有一个起点（贡献一个出度）和一个终点（贡献一个入度），因此所有顶点的入度之和恒等于所有顶点的出度之和，且都等于图的边数。故选 A。
正确答案：B
详细解析：
- 函数调用和递归的参数、返回地址统一保存在系统的调用栈（Call Stack）中。递归层数过多会导致栈空间耗尽，即栈溢出（Stack Overflow）。
正确答案：B
详细解析：
- 4人组合且每部门至少1人，只有两种部门人数分配结构：(2, 1, 1) 或没有其他（由于各部门人数分别为4, 3, 3）。
- 分配方案用组合数计算：$C(4,2)C(3,1)C(3,1) + C(4,1)C(3,2)C(3,1) + C(4,1)C(3,1)C(3,2)$。计算得结果为 126 种。
正确答案：B
详细解析：
- 经典过河贪心策略：
- 1和2过河（耗时2）
- 1回（耗时1）
- 4和8过河（耗时8）
- 2回（耗时2）
- 1和2过河（耗时2）
- 总耗时：$2 + 1 + 8 + 2 + 2 = 15$ 分钟。故选 B。
正确答案：D
- 详细解析：
- 选项 D 错误：顺序查找在最好情况下（要找的元素刚好在第一个位置）时间复杂度为 $O(1)$，但在最坏情况下需要找遍全部元素，时间复杂度为 $O(n)$，并非“任何情况下都是 $O(1)$”。

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

第10天：错综复杂的网、递归思维与初赛终极冲刺（图论基础、组合数学与真题模考）

信息学奥赛（CSP-J）零基础启蒙培训讲义

第10天：错综复杂的网、递归思维与初赛终极冲刺（图论基础、组合数学与真题模考）

📅 上午场：图论基础与图的遍历（09:00 - 12:00）

一、 什么是图？（Graph）

1. 生活中的比喻

2. 图的核心要素

二、 握手定理（图论第一大考点）

1. 什么是顶点的度（Degree）？

2. 握手定理（The Handshaking Lemma）

三、 图的遍历：DFS 与 BFS

1. 深度优先搜索（DFS - Depth-First Search）

2. 广度优先搜索（BFS - Breadth-First Search）

📅 下午场：计数原理、递归思维与结营模考（14:00 - 17:00）

一、 计数原理：排列与组合

1. 加法原理与乘法原理

2. 排列数 $A(n, m)$ 与 组合数 $C(n, m)$

3. 经典解题模型

二、 递归思维的本质（Recursion）

1. 经典故事

2. 递归的精髓

三、 结营综合全真模考

📝 第10天结营模考与强化练习卷（学生版）

一、 选择题（共 10 题）

📖 结营模考练习卷 —— 标准答案与详细解析

一、什么是图？（Graph）

二、握手定理（图论第一大考点）

三、图的遍历：DFS 与 BFS

一、计数原理：排列与组合

2. 排列数 $A(n, m)$ 与组合数 $C(n, m)$

二、递归思维的本质（Recursion）

三、结营综合全真模考

一、选择题（共 10 题）