# CSP-J 第一轮（初赛）通关集训 · 第四天

---

# Day 4 上午：链表、栈、队列与表达式转换专项（3小时）

## 第一部分：核心知识精讲与考点速记

### 1. 线性数据结构对比与链表指针操作
*   **三大线性结构对比表**：

*   **链表指针核心操作代码（初赛必考选择题）**：
    1.  **单链表在节点 $p$ 之后插入节点 $s$**：
        ```cpp
        s->next = p->next; // 步骤一：新节点 s 指向原 p 的后继
        p->next = s;       // 步骤二：节点 p 指向新节点 s（顺序绝不能颠倒！）
        ```
    2.  **单链表头插法（新节点 $s$ 成为链表首节点）**：
        ```cpp
        s->next = head;
        head = s;
        ```
    3.  **单链表删除节点 $p$ 的后继节点**：
        ```cpp
        Node *q = p->next;
        p->next = q->next;
        delete q;
        ```
    4.  **双向循环链表在节点 $p$ 之后插入节点 $s$**：
        ```cpp
        s->next = p->next;
        s->prev = p;
        p->next->prev = s;
        p->next = s;
        ```

---

### 2. 栈（Stack）的性质、出栈合法性与卡特兰数
*   **出栈序列合法性手推法则（必拿分口诀）**：
    *   **判定口诀**：“**对于已经入栈但尚未出栈的所有元素，后入栈的一定先出栈**；若某元素已出栈，则原先排在它前面且尚未出栈的元素，出栈时必然呈现**严格倒序**。”
    *   *排查技巧*：如果某个较早入栈的元素在某个较晚入栈的元素**之前**出栈，且此时它们都在栈内等待，则该序列非法！
*   **卡特兰数（Catalan Number）与出栈方案总数**：
    *   $n$ 个不同元素依次入栈，所有可能的合法出栈序列总数为第 $n$ 项卡特兰数：
        $$C\_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$
    *   **前 5 项数值必须死记硬背**：
        $$C\_1 = 1, \quad C\_2 = 2, \quad C\_3 = 5, \quad C\_4 = 14, \quad C\_5 = 42$$
    *   *典型模型*：出栈序列数、二叉树不同形态数、凸多边形三角剖分方案数、括号合法匹配序列数。

---

### 3. 前缀、中缀与后缀表达式互相转换（表达式二叉树法）
*   **概念辨析**：
    *   **中缀表达式**：操作符位于两个操作数中间，如 `a + (b - c) * d`（人类常规习惯，依赖括号和优先级）。
    *   **前缀表达式（波兰表达式）**：操作符位于操作数之前，如 `+ a * - b c d`（无括号）。
    *   **后缀表达式（逆波兰表达式）**：操作符位于操作数之后，如 `a b c - d * +`（计算机最易通过栈计算，无括号）。
*   **万能解题神器——“二叉表达式树法”**：
    *   **步骤 1（建树）**：根据人类算术优先级，将表达式画成一棵二叉树（**叶子节点是操作数，非叶节点是运算符**）。
    *   **步骤 2（遍历）**：
        *   **前序遍历（根-左-右）** $\to$ **前缀表达式**。
        *   **中序遍历（左-根-右）** $\to$ **中缀表达式**（加必要括号）。
        *   **后序遍历（左-右-根）** $\to$ **后缀表达式**。
    *   *实战示例*：中缀表达式 `a * (b + c) - d`
        *   树结构：根为 `-`；左子树根为 `*`（左叶 `a`，右子树为以 `+` 为根、叶为 `b, c`）；右叶为 `d`。
        *   前序遍历：`- * a + b c d`
        *   后序遍历：`a b c + * d -`
*   **后缀表达式的手工栈求值机制**：
    *   从左到右扫描：遇到操作数则**压栈**；遇到运算符则从栈顶弹出两个操作数（先弹出的为右操作数，后弹出的为左操作数），完成计算后将结果**重新压栈**。

---

## 第二部分：上午精选真题实战（1~20题）

1. 下列关于单链表特性的描述中，链表**不具备**的特点是（ ）。
   A. 插入和删除节点不需要移动其他元素
   B. 可以根据下标 $O(1)$ 随机访问任意节点
   C. 不需要预先估计分配存储空间大小
   D. 存储空间大小与线性表的长度成正比

2. 线性表采用链表存储结构时，各个节点在内存中的物理存储地址（ ）。
   A. 必须是完全连续的
   B. 部分节点的地址必须连续
   C. 一定是不连续的
   D. 连续或不连续均可

3. 在一个双向链表中查找数值为 $k$ 的节点，在最坏情况下的时间复杂度为（ ）。
   A. $O(1)$
   B. $O(\log n)$
   C. $O(n)$
   D. $O(n \log n)$

4. 在单链表中将新节点 $s$ 插入到头指针 `head` 之前成为链表的首个有效节点，正确的操作序列是（ ）。
   A. `s->next = head; head = s;`
   B. `head->data = s->data;`
   C. `head->next = s;`
   D. `head = s; s->next = head;`

5. 在双向循环链表中，指针 $p$ 指向某已知节点，要在 $p$ 之后插入新节点 $s$，下列操作序列中正确的是（ ）。
   A. `p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;`
   B. `s->next = p->next; p->next = s; s->prev = p; p->next->prev = s;`
   C. `p->next = s; s->prev = p; s->next = p->next; p->next->prev = s;`
   D. `s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;`

6. 设有栈 $S$，初始为空。依次对元素进行操作：`push(a)`, `push(b)`, `pop()`, `push(c)`, `push(d)`, `pop()`，此时栈顶元素是（ ）。
   A. d
   B. c
   C. a
   D. b

7. 在链式栈的栈顶指针 `hs` 处插入新节点 $s$，应执行的语句是（ ）。
   A. `hs->next = s;`
   B. `s->next = hs; hs = s;`
   C. `s->next = hs->next; hs->next = s;`
   D. `s->next = hs; hs = hs->next;`

8. 元素按 $a, b, c, d, e, f, g$ 的顺序依次进入一个初始为空的栈中，下列出栈序列中**不可能**出现的是（ ）。
   A. $a, b, c, d, e, f, g$
   B. $a, d, c, b, e, g, f$
   C. $a, d, b, c, g, f, e$
   D. $g, f, e, d, c, b, a$

9. 下列关于队列特性的描述中，正确的是（ ）。
   A. 队列是一种后进先出（LIFO）的线性数据结构
   B. 队列允许在表的两端同时进行插入和删除操作
   C. 队列是一种先进先出（FIFO）的线性数据结构
   D. 广度优先搜索算法通常使用栈来实现

10. 栈中当前从底到顶依次为 $a, b, c$，已知元素 $d$ 已经完成出栈，则元素 $a, b, c, d$ 最初可能的入栈顺序是（ ）。
    A. $a, d, c, b$
    B. $b, a, c, d$
    C. $a, c, b, d$
    D. $d, a, b, c$

11. 前缀表达式 `+ 3 * 2 + 5 12` 的最终计算值是（ ）。
    A. 23
    B. 25
    C. 37
    D. 65

12. 元素 $R\_1, R\_2, R\_3, R\_4, R\_5$ 依次入栈，若第一个出栈的元素是 $R\_3$，则第五个出栈的元素**绝对不可能是**（ ）。
    A. $R\_1$
    B. $R\_2$
    C. $R\_4$
    D. $R\_5$

13. 元素按 $F, E, D, C, B, A$ 的顺序依次入栈，下列出栈序列中**不可能**出现的是（ ）。
    A. $E, D, C, F, A, B$
    B. $D, E, C, A, B, F$
    C. $C, D, F, E, B, A$
    D. $B, C, D, A, E, F$

14. 中缀表达式 `a * (b + c) - d` 对应的后缀表达式是（ ）。
    A. `a b c d * + -`
    B. `a b c + * d -`
    C. `a b c * + d -`
    D. `- + * a b c d`

15. 元素按 $a, b, c, d, e, f$ 顺序入栈，若要得到出栈序列 $b, d, f, e, c, a$，则该栈的容量至少应为（ ）。
    A. 6
    B. 5
    C. 4
    D. 3

16. 计算机系统在处理函数递归调用、保存局部变量与返回地址时，底层必须使用的数据结构是（ ）。
    A. 队列
    B. 多维数组
    C. 循环双向链表
    D. 栈

17. 元素按 $a, b, c, d, e$ 的顺序依次入栈，下列出栈序列中**非法**的是（ ）。
    A. $a, b, c, d, e$
    B. $e, d, c, b, a$
    C. $b, a, c, d, e$
    D. $c, d, a, e, b$

18. 中缀表达式 `a + (b - c) * d` 对应的前缀表达式是（ ）。
    A. `* + a - b c d`
    B. `+ a * - b c d`
    C. `a b c - d * +`
    D. `a b c - + d *`

19. 后缀表达式 `6 2 3 + - 3 8 2 / + * 2 ^ 3 +` 对应的中缀表达式是（ ）。
    A. `((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3`
    B. `6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3`
    C. `(6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3`
    D. `6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3`

20. 元素 $1 \sim 6$ 依次入栈，下列出栈序列中**不可能**出现的是（ ）。
    A. $6, 5, 4, 3, 2, 1$
    B. $1, 6, 5, 4, 3, 2$
    C. $2, 4, 6, 5, 3, 1$
    D. $1, 3, 5, 2, 4, 6$

---

## 第三部分：上午真题解析与答案速查

1. **【答案】B**  
   **【解析】** 链表节点物理内存不连续，无法像数组一样通过首地址加偏移量进行 $O(1)$ 随机访问，必须从表头开始顺序遍历，查找为 $O(n)$。
2. **【答案】D**  
   **【解析】** 链表通过指针域链接各个离散节点，各个节点在内存中的分配完全由操作系统决定，连续或不连续均可。
3. **【答案】C**  
   **【解析】** 双向链表即使知道双向指针，查找特定数值仍需从头或尾逐个比对，最坏情况下遍历整个链表，时间复杂度为 $O(n)$。
4. **【答案】A**  
   **【解析】** 标准单链表头插法：新节点的 `next` 指向当前头节点 `head`，随后更新 `head` 指向新节点 `s`。
5. **【答案】D**  
   **【解析】** 插入节点 $s$ 需建立 4 条指针连线：先将 $s$ 的前后指针接好（`s->next = p->next; s->prev = p;`），再将原后继的 `prev` 指向 $s$（`p->next->prev = s;`），最后将 $p$ 的 `next` 指向 $s$（`p->next = s;`）。
6. **【答案】B**  
   **【解析】** 手工追踪栈内变化：  
   `push(a)` $\to [a]$；`push(b)` $\to [a, b]$；`pop()` $\to [a]$；`push(c)` $\to [a, c]$；`push(d)` $\to [a, c, d]$；`pop()` $\to [a, c]$。此时栈顶元素为 $c$。
7. **【答案】B**  
   **【解析】** 链式栈头插即压栈操作：新节点 $s$ 指向原栈顶 `hs`，随后栈顶指针更新为 $s$。
8. **【答案】C**  
   **【解析】** 针对 C 选项 $a, d, b, c, g, f, e$：当 $d$ 出栈后，此时已入栈且未出栈的元素自底向上为 $b, c$。出栈时必须先出 $c$ 再出 $b$，绝不可能先出 $b$ 后出 $c$，故 C 非法。
9. **【答案】C**  
   **【解析】** 队列的本质特性就是 FIFO（First In First Out，先进先出），在队尾插入、队头删除；BFS 基于队列实现。
10. **【答案】D**  
    **【解析】** 栈内自底向上为 $a, b, c$，且 $d$ 已出栈。D 选项入栈顺序为 $d, a, b, c$：$d$ 入栈后立即出栈，随后 $a, b, c$ 依次入栈，此时栈内恰好从底到顶为 $a, b, c$，完全吻合。
11. **【答案】C**  
    **【解析】** 前缀表达式从右往左手算：  
    1. 最右侧 `+ 5 12` 算出 $5 + 12 = 17$；  
    2. 代回变为 `+ 3 * 2 17`；  
    3. 计算 `* 2 17` 得到 $2 \times 17 = 34$；  
    4. 计算 `+ 3 34` 得到 $3 + 34 = 37$。
12. **【答案】B**  
    **【解析】** 第一个出栈的是 $R\_3$，说明此时 $R\_1, R\_2$ 已经在栈底（$R\_1$ 在最底，$R\_2$ 在其上方）。只要 $R\_2$ 未出栈，$R\_1$ 绝不可能在 $R\_2$ 之前出栈；故最后一个出栈的必须是栈底的 $R\_1$（或 $R\_5$ 等），$R\_2$ 出栈必然早于 $R\_1$，因此第五个出栈绝对不可能是 $R\_2$。
13. **【答案】C**  
    **【解析】** C 选项中 $C, D$ 出栈后，栈内剩余 $F, E$（$F$ 在底，$E$ 在上）。若要出 $F$，栈顶的 $E$ 必须先出，绝不可能跳过 $E$ 先出 $F$。
14. **【答案】B**  
    **【解析】** 运算优先级：先算括号内 $(b+c) \to bc+$；再算乘法 $a * (bc+) \to abc+*$；最后算减法 $(abc+*) - d \to abc+*d-$。
15. **【答案】C**  
    **【解析】** 跟踪栈内元素数量峰值：  
    * 进 $a, b$（栈内 2 个）$\to$ 出 $b$（剩 1）；  
    * 进 $c, d$（栈内 3 个）$\to$ 出 $d$（剩 2）；  
    * 进 $e, f$（**栈内达峰值 4 个**）$\to$ 出 $f, e, c, a$。  
    因此栈容量至少需要 4。
16. **【答案】D**  
    **【解析】** 函数递归调用的参数传递、返回地址保存及局部变量分配完全依赖操作系统在内存中维护的**调用栈（Call Stack）**。
17. **【答案】D**  
    **【解析】** D 选项中 $c, d$ 先后出栈，此时栈内自底向上留存有 $a, b$。后续出栈时栈顶为 $b$，必须先出 $b$ 再出 $a$，序列中写为 $a, e, b$ 违反了 LIFO 原则。
18. **【答案】B**  
    **【解析】** 中缀表达式 $a + (b - c) * d$：根运算符为最后计算的 `+`，左操作数是 `a`，右操作数是 `* - b c d`，前缀组合即为 `+ a * - b c d`。
19. **【答案】A**  
    **【解析】** 将后缀表达式逐步还原加括号：  
    `6 2 3 + -` $\to (6 - (2 + 3))$；  
    `3 8 2 / +` $\to (3 + 8 / 2)$；  
    `*` $\to ((6 - (2 + 3)) * (3 + 8 / 2))$；  
    `2 ^` $\to ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2$；  
    `3 +` $\to ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3$。选项 A 正确。
20. **【答案】D**  
    **【解析】** D 选项 $1, 3, 5, 2, 4, 6$：1 出栈；入 2, 3，3 出栈（栈内剩 2）；入 4, 5，5 出栈（栈内剩 2, 4，栈顶为 4）。此时若要出栈，必须先出栈顶的 4，绝不可能跳过 4 直接出栈底的 2。

---
---

# Day 4 下午：初等数论与离散排列组合专项（3小时）

## 第一部分：核心知识精讲与考点速记

### 1. 初等数论四大金牌考点
*   **整除与模运算性质**：
    *   $(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m$
    *   $(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$
*   **最大公约数（欧几里得算法 / 辗转相除法）**：
    *   核心定理：$\gcd(a, b) = \gcd(b, a \bmod b)$（边界：$\gcd(a, 0) = a$）。
    *   *手算示例*：求 $\gcd(377, 319)$：
        $$\gcd(377, 319) = \gcd(319, 58) = \gcd(58, 29) = \gcd(29, 0) = 29$$
*   **质数判定与欧拉函数**：
    *   $100$ 以内最大的质数是 **$97$**。
    *   **欧拉函数 $\phi(n)$**（小于等于 $n$ 且与 $n$ 互质的正整数个数）：
        若 $n = p\_1^{k\_1} p\_2^{k\_2} \dots p\_m^{k\_m}$，则：
        $$\phi(n) = n \left(1 - \frac{1}{p\_1}\right)\left(1 - \frac{1}{p\_2}\right)\dots\left(1 - \frac{1}{p\_m}\right)$$
        *   *例*：$10000 = 2^4 \times 5^4 \implies \phi(10000) = 10000 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right) = 4000$。

---

### 2. 排列组合基础与杨辉三角
*   **排列数（有序，区分先后位置）**：
    $$A\_n^m = \frac{n!}{(n-m)!} = n \times (n-1) \times \dots \times (n-m+1)$$
*   **组合数（无序，只选不排）**：
    $$\binom{n}{m} = C\_n^m = \frac{A\_n^m}{m!} = \frac{n!}{m!(n-m)!}$$
    *   **对称性**：$C\_n^m = C\_n^{n-m}$（如 $C\_{10}^7 = C\_{10}^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$）。
    *   **递推公式（杨辉三角本质）**：$C\_n^m = C\_{n-1}^m + C\_{n-1}^{m-1}$。
    *   **组合恒等式**：$\sum\_{i=0}^n C\_n^i = 2^n$（$n$ 元集合的所有子集总数为 $2^n$）。

---

### 3. 计数 4 大经典模型解题套路（初中生提分王炸）

```
         ┌── 元素必须相邻 ──────> 【捆绑法】（打包视作单元素，内部全排列）
         ├── 元素不能相邻 ──────> 【插空法】（先排其余元素，空隙中插入）
计数模型 ┼── 相同球入不同盒 ────> 【隔板法】（n 个球分 m 盒非空：C(n-1, m-1)）
         └── 出现“至少/至多” ───> 【反面排除法】（合法数 = 总数 - 不合法数）
```

1.  **捆绑法（相邻问题）**：
    *   *例*：5 男 3 女站一排，3 女必须相邻。
    *   *解*：将 3 女打包为 1 个整体，与 5 男共 6 个对象全排列为 $A\_6^6 = 720$；3 女内部全排列 $A\_3^3 = 6$。总数为 $720 \times 6 = 4320$ 种。
2.  **插空法（不相邻问题）**：
    *   *例*：5 男 3 女站一排，3 女互不相邻。
    *   *解*：先排 5 男（$A\_5^5 = 120$ 种），产生 6 个空位；在 6 个空位中选 3 个插入 3 女（$A\_6^3 = 120$ 种）。总数为 $120 \times 120 = 14400$ 种。
3.  **隔板法（相同元素分配问题）**：
    *   $n$ 个完全相同的小球放入 $m$ 个不同的盒子，**每盒至少 1 个球**：
        $$\text{方案数} = \binom{n-1}{m-1}$$
    *   若**允许盒子为空**（转化为每盒至少 1 个球）：借 $m$ 个球后共有 $n+m$ 个球，方案数为 $\binom{n+m-1}{m-1}$。
4.  **反面排除法（至少问题）**：
    *   *例*：10 男 12 女选 3 人，**至少有 1 名女生**。
    *   *解*：总方案数 $\binom{22}{3} = \frac{22 \times 21 \times 20}{6} = 1540$；全男方案数 $\binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$。至少 1 女方案数 $= 1540 - 120 = 1420$ 种。
5.  **鸽巢原理（抽屉原理）**：
    *   把 $n+1$ 个苹果放进 $n$ 个抽屉，至少有 1 个抽屉放了 $\ge 2$ 个苹果。
    *   **最不利原则**：若要保证有 $m$ 个对象同属性（如花色），最坏情况下让每种属性都先取到 $m-1$ 个，再加上 1 个即可确保满足：
        $$\text{最少抽取数} = k \times (m - 1) + 1 \quad (k \text{ 为属性种类数})$$

---

## 第二部分：下午精选真题实战（1~20题）

1. 甲、乙、丙 3 名同学选课，现有 4 门不同选修课供选择。若甲选 2 门，乙选 3 门，丙选 3 门，则不同的选课方案共有（ ）种。
   A. 36
   B. 48
   C. 96
   D. 192

2. 一个包含 10 个互不相同元素的集合，其大小为 7 的子集个数为 $T$，所有子集的总个数为 $S$，则 $T / S$ 的值为（ ）。
   A. $5 / 32$
   B. $15 / 128$
   C. $1 / 8$
   D. $21 / 128$

3. 在不超过 10000 的正整数中，与 10000 互质的正整数共有（ ）个。
   A. 2000
   B. 4000
   C. 6000
   D. 8000

4. 100 以内的所有正整数中，最大的素数（质数）是（ ）。
   A. 89
   B. 97
   C. 91
   D. 93

5. 正整数 319 和 377 的最大公约数是（ ）。
   A. 27
   B. 33
   C. 29
   D. 31

6. 一副标准扑克牌（共 52 张，去除大小王，包含 4 种花色各 13 张），从中任意抽取 13 张牌，其中至少有（ ）张牌的花色必然是一致的。
   A. 4
   B. 2
   C. 3
   D. 5

7. 5 个小朋友排成一排照相，其中一对双胞胎兄弟必须相邻站在一起，共有（ ）种不同的排法。
   A. 48
   B. 36
   C. 24
   D. 72

8. 将 10 个完全相同的“三好学生”名额分配到 7 个不同班级，要求每个班级至少分得 1 个名额，不同的分配方案共有（ ）种。
   A. 84
   B. 72
   C. 56
   D. 504

9. 抽屉里有 5 副不同颜色的手套（共 10 只，每副手套分左右手各 1 只）。从中任意取出 6 只手套，恰好能配成 2 副完整手套的取法共有（ ）种。
   A. 120
   B. 180
   C. 150
   D. 30

10. 欧几里得算法（辗转相除法）的核心计算目标是求解两个正整数的（ ）。
    A. 最小公倍数
    B. 最大公约数
    C. 最大公共质因子
    D. 算术平均数

11. 6 名同学两人一组分成 3 个小组进行辩论赛（不区分小组的编号顺序），不同的分组方法共有（ ）种。
    A. 10
    B. 15
    C. 30
    D. 20

12. 由数字 1, 1, 2, 2, 3 组合构成的互不相同的三位数共有（ ）个。
    A. 18
    B. 15
    C. 12
    D. 24

13. 某兴趣小组有 10 名男生和 12 名女生，现需选出 3 人参加比赛，要求选出的代表中至少有 1 名女生，不同的选拔组合共有（ ）种。
    A. 1420
    B. 1770
    C. 1540
    D. 2200

14. 某公司 10 名员工分别属于 3 个部门（部门人数分别为 4 人、3 人、3 人）。现要从这 10 人中选出 4 人组成委员会，要求每个部门至少选出 1 人，不同的选法共有（ ）种。
    A. 120
    B. 126
    C. 132
    D. 238

15. 5 名男生和 3 名女生排成一列，要求 3 名女生必须排在一起，不同的排队方案共有（ ）种。
    A. 4320
    B. 5040
    C. 3600
    D. 2880

16. 5 名男生和 4 名女生中选拔 4 人参加志愿活动，要求男女生都必须有人入选，不同的选拔方法共有（ ）种。
    A. 126
    B. 121
    C. 120
    D. 100

17. 在 $8 \times 8$ 的方格棋盘上，质点从左上角坐标 $(1, 1)$ 出发移动到坐标 $(4, 5)$，每次只能向右或向下移动 1 格，则不同的最短移动路径共有（ ）条。
    A. 20
    B. 35
    C. 56
    D. 70

18. 一家四口人（父母及两个孩子），假设每人生日在各月份是等可能的，则至少有两人生日在同一个月份的概率是（ ）。
    A. $1 / 12$
    B. $1 / 144$
    C. $41 / 96$
    D. $3 / 4$

19. 某五位数字车牌，若将车牌倒过来（旋转 $180^\circ$）看仍然是一个合法的车牌且数字恰好与原来完全相同（已知可在倒转后保持数字意义的数为 0, 1, 6, 8, 9，其中 6 与 9 倒转互换，0, 1, 8 倒转为其自身），满足条件的车牌最多有（ ）个。
    A. 60
    B. 125
    C. 75
    D. 100

20. 将 8 个完全相同的苹果分放到 5 个相同的盘子中（允许有的盘子为空），不同的放法共有（ ）种。
    A. 22
    B. 24
    C. 18
    D. 20

---

## 第三部分：下午真题解析与答案速查

1. **【答案】C**  
   **【解析】** 独立分步乘法原理：甲的选法为 $\binom{4}{2} = 6$ 种；乙的选法为 $\binom{4}{3} = 4$ 种；丙的选法为 $\binom{4}{3} = 4$ 种。总方案数为 $6 \times 4 \times 4 = 96$ 种。
2. **【答案】B**  
   **【解析】** 大小为 7 的子集数 $T = \binom{10}{7} = \binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$；包含 10 个元素的集合所有子集总数 $S = 2^{10} = 1024$。则 $T / S = 120 / 1024 = 15 / 128$。
3. **【答案】B**  
   **【解析】** $10000 = 2^4 \times 5^4$。与 10000 互质即不含质因数 2 和 5。利用欧拉函数或容斥原理：$10000 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right) = 10000 \times \frac{1}{2} \times \frac{4}{5} = 4000$ 个。
4. **【答案】B**  
   **【解析】** 100 以内的最大素数是 97（91 不是素数，$91 = 7 \times 13$；93 不是素数，$93 = 3 \times 31$；89 虽是素数但小于 97）。
5. **【答案】C**  
   **【解析】** 辗转相除法：  
   $377 \div 319 = 1$ 余 58；  
   $319 \div 58 = 5$ 余 29；  
   $58 \div 29 = 2$ 余 0。  
   因此最大公约数为 29。
6. **【答案】A**  
   **【解析】** 扑克牌共 4 种花色。根据鸽巢原理（抽屉原理）：将 13 张牌放入 4 个花色抽屉中，$\lceil 13 / 4 \rceil = \lceil 3.25 \rceil = 4$。因此至少有 4 张牌花色一致。
7. **【答案】A**  
   **【解析】** 捆绑法：双胞胎视为 1 个复合元素，与其余 3 个小朋友共 4 个对象全排列为 $A\_4^4 = 24$ 种；双胞胎内部两人相对顺序有 $A\_2^2 = 2$ 种。总排法 $= 24 \times 2 = 48$ 种。
8. **【答案】A**  
   **【解析】** 隔板法：10 个完全相同的小球排成一列产生 9 个内部空隙，插入 $7 - 1 = 6$ 块隔板分为 7 份且每份非空，方案数为 $\binom{10 - 1}{7 - 1} = \binom{9}{6} = \binom{9}{3} = \frac{9 \times 8 \times 7}{6} = 84$ 种。
9. **【答案】A**  
   **【解析】** 分步计数：  
   1. 从 5 副手套中选出 2 副完整的：$\binom{5}{2} = 10$ 种；  
   2. 需从剩下的 3 副（6 只）手套中选出 2 只**不能配对**的手套：从 3 副中选 2 副各出 1 只，方案数为 $\binom{3}{2} \times \binom{2}{1} \times \binom{2}{1} = 3 \times 2 \times 2 = 12$ 种。  
   总方案数 $= 10 \times 12 = 120$ 种。
10. **【答案】B**  
    **【解析】** 欧几里得算法（Euclidean algorithm）用于计算两个正整数的最大公约数（Greatest Common Divisor, GCD）。
11. **【答案】B**  
    **【解析】** 均等分组除以排列数：$\frac{\binom{6}{2} \times \binom{4}{2} \times \binom{2}{2}}{3!} = \frac{15 \times 6 \times 1}{6} = 15$ 种。
12. **【答案】A**  
    **【解析】** 按选取数字分类讨论：  
    1. 选 3 个不同数字 $\{1, 2, 3\}$：排列数为 $A\_3^3 = 6$ 种；  
    2. 选 2 个 1 和 1 个其他数（$\{1, 1, 2\}$ 或 $\{1, 1, 3\}$）：每组构成的三位数有 $\frac{3!}{2!} = 3$ 种，共 $2 \times 3 = 6$ 种；  
    3. 选 2 个 2 和 1 个其他数（$\{2, 2, 1\}$ 或 $\{2, 2, 3\}$）：同理有 $2 \times 3 = 6$ 种。  
    总数 $= 6 + 6 + 6 = 18$ 个。
13. **【答案】A**  
    **【解析】** 反面排除法：总选法 $\binom{22}{3} = \frac{22 \times 21 \times 20}{6} = 1540$ 种；全男选法 $\binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$ 种。至少 1 名女生的方案数 $= 1540 - 120 = 1420$ 种。
14. **【答案】B**  
    **【解析】** 选 4 人满足 3 个部门各至少 1 人，则各部门人数分布必为 $2, 1, 1$。分类：  
    * 部门 A 出 2 人，B 出 1 人，C 出 1 人：$\binom{4}{2} \binom{3}{1} \binom{3}{1} = 6 \times 3 \times 3 = 54$ 种；  
    * 部门 A 出 1 人，B 出 2 人，C 出 1 人：$\binom{4}{1} \binom{3}{2} \binom{3}{1} = 4 \times 3 \times 3 = 36$ 种；  
    * 部门 A 出 1 人，B 出 1 人，C 出 2 人：$\binom{4}{1} \binom{3}{1} \binom{3}{2} = 4 \times 3 \times 3 = 36$ 种。  
    总选法 $= 54 + 36 + 36 = 126$ 种。
15. **【答案】A**  
    **【解析】** 捆绑法：3 名女生视为整体与 5 名男生共 6 个元素全排列 $A\_6^6 = 720$ 种；3 名女生内部全排列 $A\_3^3 = 6$ 种。总方案数 $= 720 \times 6 = 4320$ 种。
16. **【答案】C**  
    **【解析】** 反面排除法：9 人选 4 人总数 $\binom{9}{4} = \frac{9 \times 8 \times 7 \times 6}{24} = 126$ 种；全为男生 $\binom{5}{4} = 5$ 种；全为女生 $\binom{4}{4} = 1$ 种。男女都有 $= 126 - 5 - 1 = 120$ 种。
17. **【答案】B**  
    **【解析】** 从 $(1, 1)$ 到 $(4, 5)$，需向下移动 $4 - 1 = 3$ 格，向右移动 $5 - 1 = 4$ 格，总共移动 $3 + 4 = 7$ 步。在 7 步中选择 3 步向下，总路径数 $= \binom{7}{3} = \frac{7 \times 6 \times 5}{6} = 35$ 条。
18. **【答案】C**  
    **【解析】** 反面法：四人生日全在不同月份的概率为 $\frac{12 \times 11 \times 10 \times 9}{12^4} = \frac{11 \times 10 \times 9}{12^3} = \frac{990}{1728} = \frac{55}{96}$。至少两人生日同月的概率 $= 1 - \frac{55}{96} = \frac{41}{96}$。
19. **【答案】C**  
    **【解析】** 设 5 位车牌为 $d\_1 d\_2 d\_3 d\_4 d\_5$。对折对称：$d\_1, d\_2$ 决定 $d\_5, d\_4$。  
    * $d\_1 \in \{0, 1, 6, 8, 9\}$（5 种选法，对应 $d\_5$ 唯一确定）；  
    * $d\_2 \in \{0, 1, 6, 8, 9\}$（5 种选法，对应 $d\_4$ 唯一确定）；  
    * 中间位 $d\_3$ 倒转后必须等于自身 $\implies d\_3 \in \{0, 1, 8\}$（3 种选法）。  
    总可能数 $= 5 \times 5 \times 3 = 75$ 个。
20. **【答案】C**  
    **【解析】** 整数拆分（将 8 拆分为不超过 5 个正整数之和）：  
    * 拆成 1 份：$(8)$ $\to 1$ 种；  
    * 拆成 2 份：$(7,1), (6,2), (5,3), (4,4)$ $\to 4$ 种；  
    * 拆成 3 份：$(6,1,1), (5,2,1), (4,3,1), (4,2,2), (3,3,2)$ $\to 5$ 种；  
    * 拆成 4 份：$(5,1,1,1), (4,2,1,1), (3,3,1,1), (3,2,2,1), (2,2,2,2)$ $\to 5$ 种；  
    * 拆成 5 份：$(4,1,1,1,1), (3,2,1,1,1), (2,2,2,1,1)$ $\to 3$ 种。  
    总放法 $= 1 + 4 + 5 + 5 + 3 = 18$ 种。

CSP-J 第一轮（初赛）通关集训 · 第四天

Day 4 上午：链表、栈、队列与表达式转换专项（3小时）

第一部分：核心知识精讲与考点速记

1. 线性数据结构对比与链表指针操作

三大线性结构对比表：

数据结构	存储方式	逻辑特性	随机访问性能	插入/删除性能	典型应用场景
数组（顺序表）	物理地址连续	线性序列	$O(1)$	$O(n)$（需搬移元素）	查多改少、前缀和
链表（单/双向）	离散物理节点	线性链式	$O(n)$（需顺序遍历）	$O(1)$（已知节点指针）	频繁插入/删除、动态内存
栈（Stack）	顺序或链式	后进先出（LIFO）	仅栈顶 $O(1)$	栈顶进出 $O(1)$	函数调用、括号匹配、表达式求值
队列（Queue）	顺序或链式	先进先出（FIFO）	仅队头/队尾 $O(1)$	队尾入/队头出 $O(1)$	广度优先搜索（BFS）、任务调度

链表指针核心操作代码（初赛必考选择题）：
1. 单链表在节点 $p$ 之后插入节点 $s$： cpp s->next = p->next; // 步骤一：新节点 s 指向原 p 的后继 p->next = s; // 步骤二：节点 p 指向新节点 s（顺序绝不能颠倒！）
2. 单链表头插法（新节点 $s$ 成为链表首节点）： cpp s->next = head; head = s;
3. 单链表删除节点 $p$ 的后继节点： cpp Node *q = p->next; p->next = q->next; delete q;
4. 双向循环链表在节点 $p$ 之后插入节点 $s$： cpp s->next = p->next; s->prev = p; p->next->prev = s; p->next = s;

2. 栈（Stack）的性质、出栈合法性与卡特兰数

出栈序列合法性手推法则（必拿分口诀）：
- 判定口诀：“对于已经入栈但尚未出栈的所有元素，后入栈的一定先出栈；若某元素已出栈，则原先排在它前面且尚未出栈的元素，出栈时必然呈现严格倒序。”
- 排查技巧：如果某个较早入栈的元素在某个较晚入栈的元素之前出栈，且此时它们都在栈内等待，则该序列非法！
卡特兰数（Catalan Number）与出栈方案总数：
- $n$ 个不同元素依次入栈，所有可能的合法出栈序列总数为第 $n$ 项卡特兰数： $$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$
- 前 5 项数值必须死记硬背： $$C_1 = 1, \quad C_2 = 2, \quad C_3 = 5, \quad C_4 = 14, \quad C_5 = 42$$
- 典型模型：出栈序列数、二叉树不同形态数、凸多边形三角剖分方案数、括号合法匹配序列数。

3. 前缀、中缀与后缀表达式互相转换（表达式二叉树法）

概念辨析：
- 中缀表达式：操作符位于两个操作数中间，如 a + (b - c) * d（人类常规习惯，依赖括号和优先级）。
- 前缀表达式（波兰表达式）：操作符位于操作数之前，如 + a * - b c d（无括号）。
- 后缀表达式（逆波兰表达式）：操作符位于操作数之后，如 a b c - d * +（计算机最易通过栈计算，无括号）。
万能解题神器——“二叉表达式树法”：
- 步骤 1（建树）：根据人类算术优先级，将表达式画成一棵二叉树（叶子节点是操作数，非叶节点是运算符）。
- 步骤 2（遍历）：
  - 前序遍历（根-左-右） $\to$ 前缀表达式。
  - 中序遍历（左-根-右） $\to$ 中缀表达式（加必要括号）。
  - 后序遍历（左-右-根） $\to$ 后缀表达式。
- 实战示例：中缀表达式 a * (b + c) - d
  - 树结构：根为 -；左子树根为 *（左叶 a，右子树为以 + 为根、叶为 b, c）；右叶为 d。
  - 前序遍历：- * a + b c d
  - 后序遍历：a b c + * d -
后缀表达式的手工栈求值机制：
- 从左到右扫描：遇到操作数则压栈；遇到运算符则从栈顶弹出两个操作数（先弹出的为右操作数，后弹出的为左操作数），完成计算后将结果重新压栈。

第二部分：上午精选真题实战（1~20题）

下列关于单链表特性的描述中，链表不具备的特点是（）。 A. 插入和删除节点不需要移动其他元素 B. 可以根据下标 $O(1)$ 随机访问任意节点 C. 不需要预先估计分配存储空间大小 D. 存储空间大小与线性表的长度成正比
线性表采用链表存储结构时，各个节点在内存中的物理存储地址（）。 A. 必须是完全连续的 B. 部分节点的地址必须连续 C. 一定是不连续的 D. 连续或不连续均可
在一个双向链表中查找数值为 $k$ 的节点，在最坏情况下的时间复杂度为（）。 A. $O(1)$ B. $O(\log n)$ C. $O(n)$ D. $O(n \log n)$
在单链表中将新节点 $s$ 插入到头指针 head 之前成为链表的首个有效节点，正确的操作序列是（）。 A. s->next = head; head = s; B. head->data = s->data; C. head->next = s; D. head = s; s->next = head;
在双向循环链表中，指针 $p$ 指向某已知节点，要在 $p$ 之后插入新节点 $s$，下列操作序列中正确的是（）。 A. p->next->prev = s; s->prev = p; p->next = s; s->next = p->next; B. s->next = p->next; p->next = s; s->prev = p; p->next->prev = s; C. p->next = s; s->prev = p; s->next = p->next; p->next->prev = s; D. s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;
设有栈 $S$，初始为空。依次对元素进行操作：push(a), push(b), pop(), push(c), push(d), pop()，此时栈顶元素是（）。 A. d B. c C. a D. b
在链式栈的栈顶指针 hs 处插入新节点 $s$，应执行的语句是（）。 A. hs->next = s; B. s->next = hs; hs = s; C. s->next = hs->next; hs->next = s; D. s->next = hs; hs = hs->next;
元素按 $a, b, c, d, e, f, g$ 的顺序依次进入一个初始为空的栈中，下列出栈序列中不可能出现的是（）。 A. $a, b, c, d, e, f, g$ B. $a, d, c, b, e, g, f$ C. $a, d, b, c, g, f, e$ D. $g, f, e, d, c, b, a$
下列关于队列特性的描述中，正确的是（）。 A. 队列是一种后进先出（LIFO）的线性数据结构 B. 队列允许在表的两端同时进行插入和删除操作 C. 队列是一种先进先出（FIFO）的线性数据结构 D. 广度优先搜索算法通常使用栈来实现
栈中当前从底到顶依次为 $a, b, c$，已知元素 $d$ 已经完成出栈，则元素 $a, b, c, d$ 最初可能的入栈顺序是（）。 A. $a, d, c, b$ B. $b, a, c, d$ C. $a, c, b, d$ D. $d, a, b, c$
前缀表达式 + 3 * 2 + 5 12 的最终计算值是（）。 A. 23 B. 25 C. 37 D. 65
元素 $R_1, R_2, R_3, R_4, R_5$ 依次入栈，若第一个出栈的元素是 $R_3$，则第五个出栈的元素绝对不可能是（）。 A. $R_1$ B. $R_2$ C. $R_4$ D. $R_5$
元素按 $F, E, D, C, B, A$ 的顺序依次入栈，下列出栈序列中不可能出现的是（）。 A. $E, D, C, F, A, B$ B. $D, E, C, A, B, F$ C. $C, D, F, E, B, A$ D. $B, C, D, A, E, F$
中缀表达式 a * (b + c) - d 对应的后缀表达式是（）。 A. a b c d * + - B. a b c + * d - C. a b c * + d - D. - + * a b c d
元素按 $a, b, c, d, e, f$ 顺序入栈，若要得到出栈序列 $b, d, f, e, c, a$，则该栈的容量至少应为（）。 A. 6 B. 5 C. 4 D. 3
计算机系统在处理函数递归调用、保存局部变量与返回地址时，底层必须使用的数据结构是（）。 A. 队列 B. 多维数组 C. 循环双向链表 D. 栈
元素按 $a, b, c, d, e$ 的顺序依次入栈，下列出栈序列中非法的是（）。 A. $a, b, c, d, e$ B. $e, d, c, b, a$ C. $b, a, c, d, e$ D. $c, d, a, e, b$
中缀表达式 a + (b - c) * d 对应的前缀表达式是（）。 A. * + a - b c d B. + a * - b c d C. a b c - d * + D. a b c - + d *
后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是（）。 A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3 B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3 C. (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3 D. 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3
元素 $1 \sim 6$ 依次入栈，下列出栈序列中不可能出现的是（）。 A. $6, 5, 4, 3, 2, 1$ B. $1, 6, 5, 4, 3, 2$ C. $2, 4, 6, 5, 3, 1$ D. $1, 3, 5, 2, 4, 6$

第三部分：上午真题解析与答案速查

【答案】B
【解析】 链表节点物理内存不连续，无法像数组一样通过首地址加偏移量进行 $O(1)$ 随机访问，必须从表头开始顺序遍历，查找为 $O(n)$。
【答案】D
【解析】 链表通过指针域链接各个离散节点，各个节点在内存中的分配完全由操作系统决定，连续或不连续均可。
【答案】C
【解析】 双向链表即使知道双向指针，查找特定数值仍需从头或尾逐个比对，最坏情况下遍历整个链表，时间复杂度为 $O(n)$。
【答案】A
【解析】 标准单链表头插法：新节点的 next 指向当前头节点 head，随后更新 head 指向新节点 s。
【答案】D
【解析】 插入节点 $s$ 需建立 4 条指针连线：先将 $s$ 的前后指针接好（s->next = p->next; s->prev = p;），再将原后继的 prev 指向 $s$（p->next->prev = s;），最后将 $p$ 的 next 指向 $s$（p->next = s;）。
【答案】B
【解析】 手工追踪栈内变化：
push(a) $\to [a]$；push(b) $\to [a, b]$；pop() $\to [a]$；push(c) $\to [a, c]$；push(d) $\to [a, c, d]$；pop() $\to [a, c]$。此时栈顶元素为 $c$。
【答案】B
【解析】 链式栈头插即压栈操作：新节点 $s$ 指向原栈顶 hs，随后栈顶指针更新为 $s$。
【答案】C
【解析】 针对 C 选项 $a, d, b, c, g, f, e$：当 $d$ 出栈后，此时已入栈且未出栈的元素自底向上为 $b, c$。出栈时必须先出 $c$ 再出 $b$，绝不可能先出 $b$ 后出 $c$，故 C 非法。
【答案】C
【解析】 队列的本质特性就是 FIFO（First In First Out，先进先出），在队尾插入、队头删除；BFS 基于队列实现。
【答案】D
【解析】 栈内自底向上为 $a, b, c$，且 $d$ 已出栈。D 选项入栈顺序为 $d, a, b, c$：$d$ 入栈后立即出栈，随后 $a, b, c$ 依次入栈，此时栈内恰好从底到顶为 $a, b, c$，完全吻合。
【答案】C
【解析】 前缀表达式从右往左手算：
1. 最右侧 + 5 12 算出 $5 + 12 = 17$；
2. 代回变为 + 3 * 2 17；
3. 计算 * 2 17 得到 $2 \times 17 = 34$；
4. 计算 + 3 34 得到 $3 + 34 = 37$。
【答案】B
【解析】 第一个出栈的是 $R_3$，说明此时 $R_1, R_2$ 已经在栈底（$R_1$ 在最底，$R_2$ 在其上方）。只要 $R_2$ 未出栈，$R_1$ 绝不可能在 $R_2$ 之前出栈；故最后一个出栈的必须是栈底的 $R_1$（或 $R_5$ 等），$R_2$ 出栈必然早于 $R_1$，因此第五个出栈绝对不可能是 $R_2$。
【答案】C
【解析】 C 选项中 $C, D$ 出栈后，栈内剩余 $F, E$（$F$ 在底，$E$ 在上）。若要出 $F$，栈顶的 $E$ 必须先出，绝不可能跳过 $E$ 先出 $F$。
【答案】B
【解析】 运算优先级：先算括号内 $(b+c) \to bc+$；再算乘法 $a * (bc+) \to abc+$；最后算减法 $(abc+) - d \to abc+*d-$。
【答案】C
【解析】 跟踪栈内元素数量峰值：
- 进 $a, b$（栈内 2 个）$\to$ 出 $b$（剩 1）；
- 进 $c, d$（栈内 3 个）$\to$ 出 $d$（剩 2）；
- 进 $e, f$（栈内达峰值 4 个）$\to$ 出 $f, e, c, a$。
  因此栈容量至少需要 4。
【答案】D
【解析】 函数递归调用的参数传递、返回地址保存及局部变量分配完全依赖操作系统在内存中维护的调用栈（Call Stack）。
【答案】D
【解析】 D 选项中 $c, d$ 先后出栈，此时栈内自底向上留存有 $a, b$。后续出栈时栈顶为 $b$，必须先出 $b$ 再出 $a$，序列中写为 $a, e, b$ 违反了 LIFO 原则。
【答案】B
【解析】 中缀表达式 $a + (b - c) * d$：根运算符为最后计算的 +，左操作数是 a，右操作数是 * - b c d，前缀组合即为 + a * - b c d。
【答案】A
【解析】 将后缀表达式逐步还原加括号：
6 2 3 + - $\to (6 - (2 + 3))$；
3 8 2 / + $\to (3 + 8 / 2)$；
* $\to ((6 - (2 + 3)) * (3 + 8 / 2))$；
2 ^ $\to ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2$；
3 + $\to ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3$。选项 A 正确。
【答案】D
【解析】 D 选项 $1, 3, 5, 2, 4, 6$：1 出栈；入 2, 3，3 出栈（栈内剩 2）；入 4, 5，5 出栈（栈内剩 2, 4，栈顶为 4）。此时若要出栈，必须先出栈顶的 4，绝不可能跳过 4 直接出栈底的 2。

---

Day 4 下午：初等数论与离散排列组合专项（3小时）

第一部分：核心知识精讲与考点速记

1. 初等数论四大金牌考点

整除与模运算性质：
- $(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m$
- $(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$
最大公约数（欧几里得算法 / 辗转相除法）：
- 核心定理：$\gcd(a, b) = \gcd(b, a \bmod b)$（边界：$\gcd(a, 0) = a$）。
- 手算示例：求 $\gcd(377, 319)$： $$\gcd(377, 319) = \gcd(319, 58) = \gcd(58, 29) = \gcd(29, 0) = 29$$
质数判定与欧拉函数：
- $100$ 以内最大的质数是 $97$。
- 欧拉函数 $\phi(n)$（小于等于 $n$ 且与 $n$ 互质的正整数个数）：若 $n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m}$，则： $$\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\dots\left(1 - \frac{1}{p_m}\right)$$
  - 例：$10000 = 2^4 \times 5^4 \implies \phi(10000) = 10000 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right) = 4000$。

2. 排列组合基础与杨辉三角

排列数（有序，区分先后位置）： $$A_n^m = \frac{n!}{(n-m)!} = n \times (n-1) \times \dots \times (n-m+1)$$
组合数（无序，只选不排）： $$\binom{n}{m} = C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$$
- 对称性：$C_n^m = C_n^{n-m}$（如 $C_{10}^7 = C_{10}^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$）。
- 递推公式（杨辉三角本质）：$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$。
- 组合恒等式：$\sum_{i=0}^n C_n^i = 2^n$（$n$ 元集合的所有子集总数为 $2^n$）。

3. 计数 4 大经典模型解题套路（初中生提分王炸）

         ┌── 元素必须相邻 ──────> 【捆绑法】（打包视作单元素，内部全排列）
         ├── 元素不能相邻 ──────> 【插空法】（先排其余元素，空隙中插入）
计数模型 ┼── 相同球入不同盒 ────> 【隔板法】（n 个球分 m 盒非空：C(n-1, m-1)）
         └── 出现“至少/至多” ───> 【反面排除法】（合法数 = 总数 - 不合法数）

捆绑法（相邻问题）：
- 例：5 男 3 女站一排，3 女必须相邻。
- 解：将 3 女打包为 1 个整体，与 5 男共 6 个对象全排列为 $A_6^6 = 720$；3 女内部全排列 $A_3^3 = 6$。总数为 $720 \times 6 = 4320$ 种。
插空法（不相邻问题）：
- 例：5 男 3 女站一排，3 女互不相邻。
- 解：先排 5 男（$A_5^5 = 120$ 种），产生 6 个空位；在 6 个空位中选 3 个插入 3 女（$A_6^3 = 120$ 种）。总数为 $120 \times 120 = 14400$ 种。
隔板法（相同元素分配问题）：
- $n$ 个完全相同的小球放入 $m$ 个不同的盒子，每盒至少 1 个球： $$\text{方案数} = \binom{n-1}{m-1}$$
- 若允许盒子为空（转化为每盒至少 1 个球）：借 $m$ 个球后共有 $n+m$ 个球，方案数为 $\binom{n+m-1}{m-1}$。
反面排除法（至少问题）：
- 例：10 男 12 女选 3 人，至少有 1 名女生。
- 解：总方案数 $\binom{22}{3} = \frac{22 \times 21 \times 20}{6} = 1540$；全男方案数 $\binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$。至少 1 女方案数 $= 1540 - 120 = 1420$ 种。
鸽巢原理（抽屉原理）：
- 把 $n+1$ 个苹果放进 $n$ 个抽屉，至少有 1 个抽屉放了 $\ge 2$ 个苹果。
- 最不利原则：若要保证有 $m$ 个对象同属性（如花色），最坏情况下让每种属性都先取到 $m-1$ 个，再加上 1 个即可确保满足： $$\text{最少抽取数} = k \times (m - 1) + 1 \quad (k \text{ 为属性种类数})$$

第二部分：下午精选真题实战（1~20题）

甲、乙、丙 3 名同学选课，现有 4 门不同选修课供选择。若甲选 2 门，乙选 3 门，丙选 3 门，则不同的选课方案共有（）种。 A. 36 B. 48 C. 96 D. 192
一个包含 10 个互不相同元素的集合，其大小为 7 的子集个数为 $T$，所有子集的总个数为 $S$，则 $T / S$ 的值为（）。 A. $5 / 32$ B. $15 / 128$ C. $1 / 8$ D. $21 / 128$
在不超过 10000 的正整数中，与 10000 互质的正整数共有（）个。 A. 2000 B. 4000 C. 6000 D. 8000
100 以内的所有正整数中，最大的素数（质数）是（）。 A. 89 B. 97 C. 91 D. 93
正整数 319 和 377 的最大公约数是（）。 A. 27 B. 33 C. 29 D. 31
一副标准扑克牌（共 52 张，去除大小王，包含 4 种花色各 13 张），从中任意抽取 13 张牌，其中至少有（）张牌的花色必然是一致的。 A. 4 B. 2 C. 3 D. 5
5 个小朋友排成一排照相，其中一对双胞胎兄弟必须相邻站在一起，共有（）种不同的排法。 A. 48 B. 36 C. 24 D. 72
将 10 个完全相同的“三好学生”名额分配到 7 个不同班级，要求每个班级至少分得 1 个名额，不同的分配方案共有（）种。 A. 84 B. 72 C. 56 D. 504
抽屉里有 5 副不同颜色的手套（共 10 只，每副手套分左右手各 1 只）。从中任意取出 6 只手套，恰好能配成 2 副完整手套的取法共有（）种。 A. 120 B. 180 C. 150 D. 30
欧几里得算法（辗转相除法）的核心计算目标是求解两个正整数的（）。 A. 最小公倍数 B. 最大公约数 C. 最大公共质因子 D. 算术平均数
6 名同学两人一组分成 3 个小组进行辩论赛（不区分小组的编号顺序），不同的分组方法共有（）种。 A. 10 B. 15 C. 30 D. 20
由数字 1, 1, 2, 2, 3 组合构成的互不相同的三位数共有（）个。 A. 18 B. 15 C. 12 D. 24
某兴趣小组有 10 名男生和 12 名女生，现需选出 3 人参加比赛，要求选出的代表中至少有 1 名女生，不同的选拔组合共有（）种。 A. 1420 B. 1770 C. 1540 D. 2200
某公司 10 名员工分别属于 3 个部门（部门人数分别为 4 人、3 人、3 人）。现要从这 10 人中选出 4 人组成委员会，要求每个部门至少选出 1 人，不同的选法共有（）种。 A. 120 B. 126 C. 132 D. 238
5 名男生和 3 名女生排成一列，要求 3 名女生必须排在一起，不同的排队方案共有（）种。 A. 4320 B. 5040 C. 3600 D. 2880
5 名男生和 4 名女生中选拔 4 人参加志愿活动，要求男女生都必须有人入选，不同的选拔方法共有（）种。 A. 126 B. 121 C. 120 D. 100
在 $8 \times 8$ 的方格棋盘上，质点从左上角坐标 $(1, 1)$ 出发移动到坐标 $(4, 5)$，每次只能向右或向下移动 1 格，则不同的最短移动路径共有（）条。 A. 20 B. 35 C. 56 D. 70
一家四口人（父母及两个孩子），假设每人生日在各月份是等可能的，则至少有两人生日在同一个月份的概率是（）。 A. $1 / 12$ B. $1 / 144$ C. $41 / 96$ D. $3 / 4$
某五位数字车牌，若将车牌倒过来（旋转 $180^\circ$）看仍然是一个合法的车牌且数字恰好与原来完全相同（已知可在倒转后保持数字意义的数为 0, 1, 6, 8, 9，其中 6 与 9 倒转互换，0, 1, 8 倒转为其自身），满足条件的车牌最多有（）个。 A. 60 B. 125 C. 75 D. 100
将 8 个完全相同的苹果分放到 5 个相同的盘子中（允许有的盘子为空），不同的放法共有（）种。 A. 22 B. 24 C. 18 D. 20

第三部分：下午真题解析与答案速查

【答案】C
【解析】 独立分步乘法原理：甲的选法为 $\binom{4}{2} = 6$ 种；乙的选法为 $\binom{4}{3} = 4$ 种；丙的选法为 $\binom{4}{3} = 4$ 种。总方案数为 $6 \times 4 \times 4 = 96$ 种。
【答案】B
【解析】 大小为 7 的子集数 $T = \binom{10}{7} = \binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$；包含 10 个元素的集合所有子集总数 $S = 2^{10} = 1024$。则 $T / S = 120 / 1024 = 15 / 128$。
【答案】B
【解析】 $10000 = 2^4 \times 5^4$。与 10000 互质即不含质因数 2 和 5。利用欧拉函数或容斥原理：$10000 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right) = 10000 \times \frac{1}{2} \times \frac{4}{5} = 4000$ 个。
【答案】B
【解析】 100 以内的最大素数是 97（91 不是素数，$91 = 7 \times 13$；93 不是素数，$93 = 3 \times 31$；89 虽是素数但小于 97）。
【答案】C
【解析】 辗转相除法：
$377 \div 319 = 1$ 余 58；
$319 \div 58 = 5$ 余 29；
$58 \div 29 = 2$ 余 0。
因此最大公约数为 29。
【答案】A
【解析】 扑克牌共 4 种花色。根据鸽巢原理（抽屉原理）：将 13 张牌放入 4 个花色抽屉中，$\lceil 13 / 4 \rceil = \lceil 3.25 \rceil = 4$。因此至少有 4 张牌花色一致。
【答案】A
【解析】 捆绑法：双胞胎视为 1 个复合元素，与其余 3 个小朋友共 4 个对象全排列为 $A_4^4 = 24$ 种；双胞胎内部两人相对顺序有 $A_2^2 = 2$ 种。总排法 $= 24 \times 2 = 48$ 种。
【答案】A
【解析】 隔板法：10 个完全相同的小球排成一列产生 9 个内部空隙，插入 $7 - 1 = 6$ 块隔板分为 7 份且每份非空，方案数为 $\binom{10 - 1}{7 - 1} = \binom{9}{6} = \binom{9}{3} = \frac{9 \times 8 \times 7}{6} = 84$ 种。
【答案】A
【解析】 分步计数：
从 5 副手套中选出 2 副完整的：$\binom{5}{2} = 10$ 种；
需从剩下的 3 副（6 只）手套中选出 2 只不能配对的手套：从 3 副中选 2 副各出 1 只，方案数为 $\binom{3}{2} \times \binom{2}{1} \times \binom{2}{1} = 3 \times 2 \times 2 = 12$ 种。
总方案数 $= 10 \times 12 = 120$ 种。
【答案】B
【解析】 欧几里得算法（Euclidean algorithm）用于计算两个正整数的最大公约数（Greatest Common Divisor, GCD）。
【答案】B
【解析】 均等分组除以排列数：$\frac{\binom{6}{2} \times \binom{4}{2} \times \binom{2}{2}}{3!} = \frac{15 \times 6 \times 1}{6} = 15$ 种。
【答案】A
【解析】 按选取数字分类讨论：
1. 选 3 个不同数字 ${1, 2, 3}$：排列数为 $A_3^3 = 6$ 种；
2. 选 2 个 1 和 1 个其他数（${1, 1, 2}$ 或 ${1, 1, 3}$）：每组构成的三位数有 $\frac{3!}{2!} = 3$ 种，共 $2 \times 3 = 6$ 种；
3. 选 2 个 2 和 1 个其他数（${2, 2, 1}$ 或 ${2, 2, 3}$）：同理有 $2 \times 3 = 6$ 种。
  总数 $= 6 + 6 + 6 = 18$ 个。
【答案】A
【解析】 反面排除法：总选法 $\binom{22}{3} = \frac{22 \times 21 \times 20}{6} = 1540$ 种；全男选法 $\binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$ 种。至少 1 名女生的方案数 $= 1540 - 120 = 1420$ 种。
【答案】B
【解析】 选 4 人满足 3 个部门各至少 1 人，则各部门人数分布必为 $2, 1, 1$。分类：
- 部门 A 出 2 人，B 出 1 人，C 出 1 人：$\binom{4}{2} \binom{3}{1} \binom{3}{1} = 6 \times 3 \times 3 = 54$ 种；
- 部门 A 出 1 人，B 出 2 人，C 出 1 人：$\binom{4}{1} \binom{3}{2} \binom{3}{1} = 4 \times 3 \times 3 = 36$ 种；
- 部门 A 出 1 人，B 出 1 人，C 出 2 人：$\binom{4}{1} \binom{3}{1} \binom{3}{2} = 4 \times 3 \times 3 = 36$ 种。
  总选法 $= 54 + 36 + 36 = 126$ 种。
【答案】A
【解析】 捆绑法：3 名女生视为整体与 5 名男生共 6 个元素全排列 $A_6^6 = 720$ 种；3 名女生内部全排列 $A_3^3 = 6$ 种。总方案数 $= 720 \times 6 = 4320$ 种。
【答案】C
【解析】 反面排除法：9 人选 4 人总数 $\binom{9}{4} = \frac{9 \times 8 \times 7 \times 6}{24} = 126$ 种；全为男生 $\binom{5}{4} = 5$ 种；全为女生 $\binom{4}{4} = 1$ 种。男女都有 $= 126 - 5 - 1 = 120$ 种。
【答案】B
【解析】 从 $(1, 1)$ 到 $(4, 5)$，需向下移动 $4 - 1 = 3$ 格，向右移动 $5 - 1 = 4$ 格，总共移动 $3 + 4 = 7$ 步。在 7 步中选择 3 步向下，总路径数 $= \binom{7}{3} = \frac{7 \times 6 \times 5}{6} = 35$ 条。
【答案】C
【解析】 反面法：四人生日全在不同月份的概率为 $\frac{12 \times 11 \times 10 \times 9}{12^4} = \frac{11 \times 10 \times 9}{12^3} = \frac{990}{1728} = \frac{55}{96}$。至少两人生日同月的概率 $= 1 - \frac{55}{96} = \frac{41}{96}$。
【答案】C
【解析】 设 5 位车牌为 $d_1 d_2 d_3 d_4 d_5$。对折对称：$d_1, d_2$ 决定 $d_5, d_4$。
- $d_1 \in {0, 1, 6, 8, 9}$（5 种选法，对应 $d_5$ 唯一确定）；
- $d_2 \in {0, 1, 6, 8, 9}$（5 种选法，对应 $d_4$ 唯一确定）；
- 中间位 $d_3$ 倒转后必须等于自身 $\implies d_3 \in {0, 1, 8}$（3 种选法）。
  总可能数 $= 5 \times 5 \times 3 = 75$ 个。
【答案】C
【解析】 整数拆分（将 8 拆分为不超过 5 个正整数之和）：
- 拆成 1 份：$(8)$ $\to 1$ 种；
- 拆成 2 份：$(7,1), (6,2), (5,3), (4,4)$ $\to 4$ 种；
- 拆成 3 份：$(6,1,1), (5,2,1), (4,3,1), (4,2,2), (3,3,2)$ $\to 5$ 种；
- 拆成 4 份：$(5,1,1,1), (4,2,1,1), (3,3,1,1), (3,2,2,1), (2,2,2,2)$ $\to 5$ 种；
- 拆成 5 份：$(4,1,1,1,1), (3,2,1,1,1), (2,2,2,1,1)$ $\to 3$ 种。
  总放法 $= 1 + 4 + 5 + 5 + 3 = 18$ 种。

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