当前位置：首页 > news >正文

CSP J历年真题考点归纳

news 2026/7/29 22:56:14

CSP-J第一轮 · 考点真题簇归纳（程序讲解版）

怎么用

本版在章首总述版基础上，为程序阅读与程序填空每道真题增加 程序讲解（按执行顺序讲清变量、循环与函数在干什么）。

动态规划相关题目只做概要（学生未系统学习 DP，程序讲解里会标注「了解即可」）
其他程序尽量按执行顺序讲清；选择题部分与章首总述版相同
旧版仍保留：考点真题簇归纳.md、考点真题簇归纳-章首总述版.md

按 三大类（单项选择 / 程序阅读 / 程序填空）→ 考点簇 → 本章知识点总述 → 完整真题 + 程序讲解（阅读/填空）+ 分步解法 复习。讲解用大白话，公式用 $...$。答案按洛谷 JSON：A=第一选项，依次类推。

一、单项选择题

考点簇1：计算机常识与单位换算

这类题在考什么

这类题考的是「电脑常识」：域名、图灵奖、编译器/操作系统、内存硬盘 CPU 等概念，还有 bit/Byte/KB/MB 换算、图像存储容量。不用写代码，靠记常识和简单乘法。

这类题总陷阱

把 bit 和 Byte 搞混
把浏览器/记事本当成操作系统
图像容量忘记乘宽高

本章知识点总述

存储单位进率表（计算机里容量按 $1024$ 进位，题目会写明）：

单位	含义	与下一级的关系
bit（位）	最小单位，只能存 $0$ 或 $1$	$8$ bit $= 1$ Byte
Byte（字节）	常见「一个字节」	$1024$ Byte $= 1$ KB
KB（千字节）	kilobyte	$1024$ KB $= 1$ MB
MB（兆字节）	megabyte	$1024$ MB $= 1$ GB
GB（吉字节）	gigabyte	更大还有 TB…

比较大小：$1\text{ bit} < 1\text{ Byte} < 1\text{ KB} < 1\text{ MB} < 1\text{ GB}$。

位 → 字节：$n$ 位占多少字节？

\[\text{字节数} = n \div 8 \]

例：$32$ 位整型 $\rightarrow 32 \div 8 = 4$ 字节。

图像存储容量（三步走）：

每个像素多少字节：$\text{色深（位）} \div 8$
总像素数：$\text{宽} \times \text{高}$
总字节 $= $ 像素数 $\times$ 每像素字节；再按需换成 KB/MB（除以 $1024$ 或 $1024^2$）

例：$2048\times1024$ 图、$32$ 位色

每像素：$32 \div 8 = 4$ 字节
总字节：$2048 \times 1024 \times 4 = 2 \times 1024 \times 1024 \times 4 = 8 \times 1024^2$ 字节 $= 8$ MB

$1$ MB 是多少 bit（把进率全展开）：
$1\text{ MB} = 1024\text{ KB} = 1024 \times 1024\text{ 字节} = 1024^2 \times 8\text{ bit} = 8388608\text{ bit}$

常识速记：CPU/内存/硬盘分工；编译器把源码变可执行文件；操作系统管资源；浏览器是应用软件不是 OS。

真题 A · 2024年第5题

完整题目

记 1KB 为 1024 字节（byte），1MB 为 1024KB，那么 1MB 是多少二进制位（bit）？（）

A. 1000000
B. 1048576
C. 8000000
D. 8388608

答案与解法

题目已给出进率（按 $1024$ 进位）：

$1$ KB $= 1024$ 字节（byte）
$1$ MB $= 1024$ KB
$1$ 字节 $= 8$ 位（bit）

第1步：$1$ MB 是多少字节？
$1\text{ MB} = 1024\text{ KB}$
$= 1024 \times 1024$ 字节
$= 1024^2$ 字节

第2步：字节换成 bit
每 $1$ 字节 $= 8$ bit，所以
$1\text{ MB} = 1024^2 \times 8$ bit

第3步：算出具体数字
$1024^2 = 1024 \times 1024 = 1048576$
$1048576 \times 8 = 8388608$ bit

注意：选项里 $1000000$、$8000000$ 是按 $1000$ 进位算的，题目用的是 $1024$ 进位。

易错点： 用 $1000$ 进制；或忘了最后乘 $8$ 把字节换成 bit。

答案：D（8388608）

真题 B · 2024年第10题

完整题目

下面的哪一个不是操作系统名字？（）

A. Notepad
B. Linux
C. Windows
D. macOS

答案与解法

Notepad 是记事本软件。

易错点： 把 Notepad 当 OS。

答案：A（Notepad）

真题 C · 2024年第15题

完整题目

编译器的主要作用是什么？（）

A. 直接执行源代码
B. 将源代码转换为机器代码
C. 进行代码调试
D. 管理程序运行时的内存

答案与解法

编译器把源码翻译成机器码。

易错点： 和解释器、调试器混淆。

答案：B（将源代码转换为机器代码）

真题 D · 2023年第13题

完整题目

在计算机中，以下哪个选项描述的数据存储容量最小（）

A. 字节 (byte)
B. 比特 (bit)
C. 字 (word)
D. 千字节 (kilobyte）

答案与解法

先把常见存储单位从小到大排好（容量从小到大）：

第1步：认识每个单位

比特（bit）：最小单位，只能存 $0$ 或 $1$ 一位信息
字节（byte）：$1$ 字节 $= 8$ 位
字（word）：通常指 CPU 一次处理的位数（比如 $32$ 位或 $64$ 位），比 $1$ 字节大得多
千字节（KB）：$1$ KB $= 1024$ 字节

第2步：比较大小
$1\text{ bit} < 1\text{ byte} < 1\text{ word} < 1\text{ KB}$

题目问哪个最小，答案是 比特（bit）。

易错点： 以为 byte 最小；没记住 bit 才是最小单位。

答案：B（比特 (bit)）

真题 E · 2023年第15题

完整题目

以下哪个不是操作系统?()

A. Linux
B. Windows
C. Android
D. HTML

答案与解法

HTML 是标记语言，不是 OS；Linux/Windows/Android 都是。

易错点： 把 Android 当普通软件。

答案：D（HTML）

真题 F · 2021年第1题

完整题目

以下不属于面向对象程序设计语言的是（）。

A. C++
B. Python
C. Java
D. C

答案与解法

C 是面向过程语言，没有类/对象机制。

易错点： 以为 C++ 不是 OOP（C++ 支持 OOP）。

答案：D（C）

真题 G · 2021年第2题

完整题目

以下奖项与计算机领域最相关的是（）。

A. 奥斯卡奖
B. 图灵奖
C. 诺贝尔奖
D. 普利策奖

答案与解法

图灵奖。

易错点： 诺贝尔奖。

答案：B（图灵奖）

真题 H · 2021年第3题

完整题目

目前主流的计算机储存数据最终都是转换成（）数据进行储存。

A. 二进制
B. 十进制
C. 八进制
D. 十六进制

答案与解法

内存里全是 0 和 1。

易错点： 十六进制只是书写方便，底层仍是二进制。

答案：A（二进制）

真题 I · 2020年第1题

完整题目

在内存储器中每个存储单元都被赋予一个唯一的序号，称为（）。

A. 地址
B. 序号
C. 下标
D. 编号

答案与解法

记：内存地址 = 门牌号。

易错点： "序号""编号"听起来像，但标准术语是地址。

答案：A（地址）

真题 J · 2020年第2题

完整题目

编译器的主要功能是（）。

A. 将源程序翻译成机器指令代码
B. 将源程序重新组合
C. 将低级语言翻译成高级语言
D. 将一种高级语言翻译成另一种高级语言

答案与解法

编译器把源代码翻译成机器能执行的指令。

易错点： 以为是"把高级语言翻译成另一种高级语言"。

答案：A（将源程序翻译成机器指令代码）

真题 K · 2020年第4题

完整题目

现有一张分辨率为 $2048\times 1024$ 像素的 $32$ 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（）。

A. 16MB
B. 4MB
C. 8MB
D. 2MB

答案与解法

先记住进率（题目按 $1024$ 进位）：

$1$ 字节（Byte）$=8$ 位（bit）
$1$ KB $=1024$ 字节
$1$ MB $=1024$ KB $=1024\times1024$ 字节

第1步：每个像素是 $32$ 位真彩色。
$32$ 位 $\div 8 = 4$ 字节／像素。

第2步：一共有多少像素？
$2048\times1024$ 个像素。

第3步：总字节数
$=2048\times1024\times4$
注意到 $2048=2\times1024$，所以
$=2\times1024\times1024\times4$
$=8\times(1024\times1024)$ 字节
$=8$ MB。

易错点： 32 位当成 32 字节；或忘了乘宽高。

答案：C（8MB）

真题 L · 2019年第1题

完整题目

中国的国家顶级域名是（）

A. .cn
B. .ch
C. .chn
D. .china

答案与解法

记几个常见国家域名：中国 .cn，美国 .us，英国 .uk。中国是 .cn。

易错点： 把 .china、.chn 等"看起来像中国"的字符串当真；顶级域名是固定的 .cn。

答案：A（.cn）

真题 M · 2019年第3题

完整题目

一个 $32$ 位整型变量占用（）个字节。

A. 32
B. 128
C. 4
D. 8

答案与解法

先记住换算关系：

$1$ 字节（Byte）$=8$ 位（bit）

题目说变量是 $32$ 位整型，问占多少字节。

第1步：位换成字节
$32$ 位 $\div 8$ 位/字节 $= 4$ 字节

所以一个 $32$ 位整型占 $4$ 字节。

易错点： 看到「32 位」就选 32 字节；位（bit）和字节（byte）要换算。

答案：C（4）

真题 N · 2019年第15题

完整题目

以下哪个奖项是计算机科学领域的最高奖？（）

A. 图灵奖
B. 鲁班奖
C. 诺贝尔奖
D. 普利策奖

答案与解法

计算机界的"诺贝尔奖"是图灵奖。

易错点： 诺贝尔奖覆盖面广但不是 CS 专属；鲁班奖是建筑奖。

答案：A（图灵奖）

考点簇2：进制转换与位运算

这类题在考什么

进制就是满几进一。要把八进制、二进制、十六进制和十进制互转，还要会按位与、或、异或，以及 int 范围、补码等。混进制算式先全部换成十进制再算。

这类题总陷阱

逻辑与 && 和按位与 & 搞混
进制余数顺序写反
混进制没先换十进制

本章知识点总述

什么是进制：$R$ 进制就是「逢 $R$ 进一」。每一位的权是 $R$ 的幂，从右往左是 $R^0, R^1, R^2, \ldots$

任意进制 → 十进制（按权展开）

例：八进制 $73_8$ 转十进制

个位 $3$，权 $8^0=1$，贡献 $3 \times 1 = 3$
十位 $7$，权 $8^1=8$，贡献 $7 \times 8 = 56$
相加：$56 + 3 = 59_{10}$

十进制 → 任意进制（短除取余，余数倒写）

例：$59$ 转八进制

$59 \div 8 = 7$ 余 $3$ ← 最低位
$7 \div 8 = 0$ 余 $7$ ← 下一位
商为 $0$ 停止；从下往上读余数：$73_8$

混进制算式：先把每个数都换成十进制，算完再按需转回去。不要直接拿不同进制的数字相加。

位运算（对二进制每一位独立运算）：

按位与 &：两位都是 $1$ 才是 $1$
按位或 |：有一个 $1$ 就是 $1$
按位异或 ^：相同为 $0$，不同为 $1$
左移 << k：相当于乘 $2^k$（注意溢出）

&& 和 & 的区别：

&& 是逻辑与，看「真假」，有短路
& 是按位与，对整数的二进制位运算

补码与范围：有符号 $32$ 位 int 范围 $-2^{31} \sim 2^{31}-1$。

真题 A · 2025年第1题

完整题目

一个 $32$ 位无符号整数可以表示的最大值，最接近下列哪个选项？

A. $4 \times 10^9$
B. $3 \times 10^{10}$
C. $2 \times 10^9$
D. $2 \times 10^{10}$

答案与解法

约 $4.29\times10^9$，最接近 $4\times10^9$。

易错点： 选 $2\times10^{10}$。

答案：A（$4 \times 10^9$）

真题 B · 2025年第2题

完整题目

在 C++ 中，执行 int x = 255; cout << (x & (x - 1)); 后，输出的结果是？

A. $255$
B. $254$
C. $128$
D. $0$

答案与解法

$255=11111111_2$，$254=11111110_2$，按位与得 $254$。

易错点： 以为结果是 $0$。

答案：B（$254$）

真题 C · 2025年第13题

完整题目

十进制数 $720_{10}$ 和八进制数 $270_8$ 的和用十六进制表示是多少？

A. $388_{16}$
B. $3DE_{16}$
C. $288_{16}$
D. $990_{16}$

答案与解法

$270_8=2\times64+7\times8=184_{10}$；$720+184=904_{10}=388_{16}$。

易错点： $270_8$ 转十进制错。

答案：A（$388_{16}$）

真题 D · 2024年第1题

完整题目

32 位 int 类型的存储范围是（）？

A. -2147483647 ~ +2147483647
B. -2147483647 ~ +2147483648
C. -2147483648 ~ +2147483647
D. -2147483648 ~ +2147483648

答案与解法

有符号 $32$ 位整数用补码表示，能表示的范围是：

\[-2^{31}\ \sim\ 2^{31}-1 \]

（一共 $2^{32}$ 个不同整数；有一半偏负、一半偏正，上界要比 $2^{31}$ 少 1。）

第1步：先算几个熟悉的 $2$ 的幂（把“看不见的进率”写出来）：

$2^{10}=1024$
$2^{20}=(2^{10})^2=1024\times1024=1048576$
$2^{30}=2^{20}\times2^{10}=1048576\times1024=1073741824$
$2^{31}=2\times2^{30}=2\times1073741824=2147483648$

第2步：写出范围端点

下界：$-2^{31}=-2147483648$
上界：$2^{31}-1=2147483648-1=+2147483647$

所以答案是 $-2147483648\sim+2147483647$。

易错点： 上下界都写成 $2^{31}-1$；或上界多写成 $+2147483648$（那个数其实表示不下）。

答案：C（-2147483648 ~ +2147483647）

真题 E · 2024年第2题

完整题目

计算 $(14_8 - 1010_2) \times D_{16} - 1101_2$ 的结果，并选择答案的十进制值：（）

A. 13
B. 14
C. 15
D. 16

答案与解法

$14_8=12$，$1010_2=10$，$D_{16}=13$；$(12-10)\times13-13=13$。

易错点： $D_{16}$ 当成 $13_{10}$ 错。

答案：A（13）

真题 F · 2023年第2题

完整题目

八进制数 $12345670_8$ 和 $07654321_8$ 的和为

A. $22222221_8$
B. $21111111_8$
C. $22111111_8$
D. $22222211_8$

答案与解法

$12345670_8+07654321_8$，逐位加并进位，得 $22222211_8$。

易错点： 按十进制加。

答案：D（$22222211_8$）

真题 G · 2023年第9题

完整题目

数 $101010_2$ 和 $166_8$ 的和为 ( )

A. $(10110000)_2$
B. $(236)_8$
C. $(158)_{10}$
D. $(A0)_{16}$

答案与解法

$101010_2=42_{10}$，$166_8=118_{10}$，和 $160_{10}=A0_{16}$。

易错点： 只算二进制或只算八进制。

答案：D（$(A0)_{16}$）

真题 H · 2022年第13题

完整题目

八进制数 $32.1$ 对应的十进制数是（）。

A. $24.125$
B. $24.250$
C. $26.125$
D. $26.250$

答案与解法

整数：$3\times8+2=26$；小数：$1\times8^{-1}=0.125$；合计 $26.125$。

易错点： 小数部分按 $8$ 的负幂算，别按 $10$ 算。

答案：C（$26.125$）

真题 I · 2021年第7题

完整题目

二进制数 $101.11$ 对应的十进制数是（）。

A. 6.5
B. 5.5
C. 5.75
D. 5.25

答案与解法

$1\times4 + 0\times2 + 1\times1 + 1\times0.5 + 1\times0.25 = 5.75$。

易错点： 小数位权算错。

答案：C（5.75）

真题 J · 2020年第9题

完整题目

二进制数 $1011$ 转换成十进制数是（）。

A. 11
B. 10
C. 13
D. 12

答案与解法

$1\times8 + 0\times4 + 1\times2 + 1\times1 = 11$。

易错点： 位权算错。

答案：A（11）

真题 K · 2019年第2题

完整题目

二进制数 $\text{11 1011 1001 0111}$ 和 $\text{01 0110 1110 1011}$ 进行按位与运算的结果是（）。

编者注：原题为“逻辑与”，但是根据题意应当是按位与。

A. $\text{01 0010 1000 1011}$
B. $\text{01 0010 1001 0011}$
C. $\text{01 0010 1000 0001}$
D. $\text{01 0010 1000 0011}$

答案与解法

把两数上下对齐，逐位相与：

第 1 位：$1 \land 0 = 0$
第 2 位：$1 \land 1 = 1$
……全部算完得 $\text{01 0010 1000 0011}$。

易错点： 题目写"逻辑与"容易和 C++ 的 && 搞混；这里要逐位对齐做 &。

答案：D（$\text{01 0010 1000 0011}$）

考点簇3：C++语法与程序语义

这类题在考什么

考 C++ 语法细节：循环跑几次、整除、指针引用、const、类型是不是基本类型、逻辑短路、string 用法等。读题要抠字眼，别被 Pascal 语法迷惑。

这类题总陷阱

= 和 == 搞混
整数除法 7/2=3
循环次数 i<=n 和 i<n 数错

本章知识点总述

读程序像数步骤：从 main 或给定入口开始，一行行跟，在纸上记变量值。

循环次数：

for (i=0; i<n; i++) 跑 $n$ 次（$i$ 取 $0,1,\ldots,n-1$）
for (i=1; i<=n; i++) 也跑 $n$ 次（$i$ 取 $1,\ldots,n$）
看清是 < 还是 <=

整数除法：7/2 结果是 $3$，不是 $3.5$。

比较与赋值：= 是赋值，== 才是判断相等。

逻辑短路：&& 左边为假就不算右边；|| 左边为真就不算右边。

指针与引用：*p 取指针指向的值；&x 取地址；引用是别名。

const：常量不能改；const int* 和 int* const 含义不同，看 const 靠哪边。

string：s.length() 或 s.size() 是长度；s[i] 取第 $i$ 个字符（从 $0$ 开始）。

真题 A · 2025年第7题

完整题目

假设 $a, b, c$ 都是布尔变量，逻辑表达式 (a && b) || (!c && a) 的值与下列哪个表达式不始终相等？

A. a && (b || !c)
B. (a || !c) && (b || !c) && (a || a)
C. a && (!b || c)
D. !(!a || !b) || (a && !c)

答案与解法

原式 $=a\land(b\lor\neg c)$。C 式 $a\land(\neg b\lor c)$ 不等价（如 $a=1,b=1,c=0$ 时原式真、C 假）。

易错点： 只验一两个值。

答案：C（a && (!b || c)）

真题 B · 2025年第9题

完整题目

下列关于 C++ string 类的说法，正确的是？

A. string 对象的长度在创建后不能改变。
B. 可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。
C. string 的 length() 和 size() 方法返回的值可能不同。
D. string 对象必须以 '\0' 结尾，且这个结尾符计入 length()。

答案与解法

可以用 string + char；length() 与 size() 相同；\0 不计入 length()。

易错点： 以为不能 + char。

答案：B（可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。）

真题 C · 2025年第10题

完整题目

考虑以下 C++ 函数：

void solve(int &a, int b) {a = a + b;b = a - b;a = a - b;
}
int main() {int x = 5, y = 10;solve(x, y);
}

在 main 函数调用 solve 后，$x$ 和 $y$ 的值分别是？

A. $5,10$
B. $10,5$
C. $10,10$
D. $5,5$

答案与解法

只有 a 是引用，b 是副本；最终 $x=10,y=10$（$y$ 没变）。

易错点： 以为 $x,y$ 交换了。

答案：C（$10,10$）

真题 D · 2024年第6题

完整题目

以下哪个不是 C++ 中的基本数据类型？（）

A. int
B. float
C. struct
D. char

答案与解法

struct 是用户自定义复合类型。

易错点： 以为 float 不是基本的。

答案：C（struct）

真题 E · 2024年第7题

完整题目

以下哪个不是 C++ 中的循环语句？（）

A. for
B. while
C. do-while
D. repeat-until

答案与解法

C++ 有 for/while/do-while，没有 repeat-until。

易错点： 不认识 repeat-until（Pascal 语法）。

答案：D（repeat-until）

真题 F · 2024年第8题

完整题目

在 C/C++ 中，(char)('a' + 13) 与下面的哪一个值相等？（）

A. 'm'
B. 'n'
C. 'z'
D. 'l'

答案与解法

a 是 $97$，$97+13=110$ 是 n。

易错点： 数错字母位置。

答案：B（'n'）

真题 G · 2023年第1题

完整题目

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

在 C++ 中，下面哪个关键字用于声明一个变量，其值不能被修改?

A. unsigned
B. const
C. static
D. mutable

答案与解法

const = constant，常量不能修改。

易错点： 选 static（只是静态存储）。

答案：B（const）

真题 H · 2023年第3题

完整题目

阅读下述代码，请问修改 data 的 value 成员以存储 $3.14$，正确的方式是

union Data{int num;float value;char symbol;
};
union Data data;

A. data.value = 3.14;
B. value.data = 3.14;
C. data -> value = 3.14;
D. value->data = 3.14;

答案与解法

普通变量用点号：data.value = 3.14。

易错点： 用 ->（那是指针用的）。

答案：A（data.value = 3.14;）

真题 I · 2022年第1题

完整题目

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

以下哪种功能没有涉及 C++ 语言的面向对象特性支持：（）。

A. C++ 中调用 printf 函数
B. C++ 中调用用户定义的类成员函数
C. C++ 中构造一个 class 或 struct
D. C++ 中构造来源于同一基类的多个派生类

答案与解法

调用成员函数、定义 class/struct、写派生类都是 OOP；只有 A 的 printf 是普通函数调用。

易错点： printf 是 C 语言函数，跟"类"没关系，容易误选 B/C/D。

答案：A（C++ 中调用 printf 函数）

真题 J · 2022年第3题

完整题目

运行以下代码片段的行为是（）。

int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

A. 将 $x$ 的值赋为 $201$
B. 将 $y$ 的值赋为 $101$
C. 将 $q$ 指向 $x$ 的地址
D. 将 $p$ 指向 $y$ 的地址

答案与解法

$p=q$ 只改变指针 $p$ 指向谁，不改 $x,y$ 的值。改完后 $p$ 和 $q$ 都指向 $y$。

易错点： 以为 $p=q$ 会把 $y$ 的值赋给 $x$。

答案：D（将 $p$ 指向 $y$ 的地址）

真题 K · 2020年第3题

完整题目

设 x=true,y=true,z=false，以下逻辑运算表达式值为真的是（）。

A. (y∨z)∧x∧z
B. x∧(z∨y) ∧z
C. (x∧y) ∧z
D. (x∧y)∨(z∨x)

答案与解法

D：$(x \land y) \lor (z \lor x) = \text{true} \lor \text{true} = \text{true}$。A、B、C 都含 $z$ 做"与"且 $z$ 为假，结果为假。

易错点： 运算优先级搞错。

答案：D（(x∧y)∨(z∨x)）

真题 L · 2019年第4题

完整题目

若有如下程序段，其中 s、a、b、c 均已定义为整型变量,且 a、c 均已赋值（c 大于 $0$）

s = a;  
for （b = 1; b <= c; b++） s = s - 1;

则与上述程序段功能等价的赋值语句是（）

A. s = a - c;
B. s = a - b;
C. s = s - c;
D. s = b - c;

答案与解法

循环跑 $c$ 次，每次减 1，总共减 $c$，所以 $s = a - c$。

易错点： 写成 s=a-b（$b$ 是循环变量，最后不等于 $c$）或 s=s-c（$s$ 初值不是 $a$）。

答案：A（s = a - c;）

考点簇4：栈与队列

这类题在考什么

栈像叠盘子：后进先出；队列像排队：先进先出。常考出栈序列是否合法（用栈模拟）、栈队列混用的最小容量。

这类题总陷阱

出栈序列只检查数字都在不在
栈和队列规则说反

本章知识点总述

栈（Stack）：后进先出（LIFO）。只允许在一端（栈顶）压入 push 和弹出 pop。

队列（Queue）：先进先出（FIFO）。一端入队 enqueue，另一端出队 dequeue。

判断出栈序列是否合法：

按 $1,2,3,\ldots,n$ 顺序依次入栈
每当栈顶等于「目标序列」当前要的数，就弹出
全部处理完能正好弹出目标序列 → 合法

栈 + 队列混用：常问「最少要几个栈/队列」才能把输入变成输出；用模拟法试。

记忆口诀：栈像叠盘子，最后放的最先拿；队列像排队，先来的先走。

真题 A · 2025年第15题

完整题目

给定一个初始为空的整数栈 $S$ 和一个空的队列 $P$。我们按顺序处理输入的整数队列 $A: 7, 5, 8, 3, 1, 4, 2$。对于队列 $A$ 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 $S$；如果该数是偶数，且栈 $S$ 非空，则弹出一个栈顶元素，并加入到队列 $P$ 的末尾；如果该数是偶数，且栈 $S$ 为空，则不进行任何操作。当队列 $A$ 中的所有数都处理完毕后，队列 $P$ 的内容是什么？

A. $5,1,3$
B. $7,5,3$
C. $3,1,5$
D. $5,1,3,7$

答案与解法

逐步模拟，$P$ 依次为 $5,1,3$。

易错点： 偶数栈空时误以为要操作。

答案：A（$5,1,3$）

真题 B · 2024年第13题

完整题目

给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 $1\ 2\ 3\ 4\ 5\ 6$，其中 $1$ 最先入栈，$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

答案与解法

D 序列 1 3 5 2 4 6：$1$ 出后 $2$ 在栈顶，不能在 $5$ 之后才出 $2$。

易错点： 以为 1 先入就一定能先出。

答案：D（1 3 5 2 4 6）

真题 C · 2022年第2题

完整题目

有 $6$ 个元素，按照 $6,5,4,3,2,1$ 的顺序进入栈 $S$，请问下列哪个出栈序列是非法的（）。

A. $5,4,3,6,1,2$
B. $4,5,3,1,2,6$
C. $3,4,6,5,2,1$
D. $2,3,4,1,5,6$

答案与解法

模拟：全部入栈后，要弹出 $3,4$ 时栈顶依次是 $3,4$；接下来想弹 $6$，但栈顶是 $5$，$6$ 被压在下面，弹不出来。序列 C 非法。

易错点： 以为"只要数字都在就行"，没检查栈顶顺序。

答案：C（$3,4,6,5,2,1$）

真题 D · 2022年第5题

完整题目

对假设栈 $S$ 和队列 $Q$ 的初始状态为空。存在 $e_1\sim e_6$ 六个互不相同的数据，每个数据按照进栈 $S$、出栈 $S$、进队列 $Q$、出队列 $Q$ 的顺序操作，不同数据间的操作可能会交错。已知栈 $S$ 中依次有数据 $e_1$、$e_2$、$e_3$、$e_4$、$e_5$ 和 $e_6$ 进栈，队列 $Q$ 依次有数据 $e_2$、$e_4$、$e_3$、$e_6$、$e_5$ 和 $e_1$ 出队列。则栈 $S$ 的容量至少是（）个数据。

A. $2$
B. $3$
C. $4$
D. $6$

答案与解法

按出队顺序 $e_2,e_4,e_3,e_6,e_5,e_1$ 倒推：需要同时在栈里等 $e_3$ 出来前最多压 $e_1,e_2,e_3$，容量 $3$ 就够。

易错点： 以为要装下全部 $6$ 个元素。

答案：B（$3$）

真题 E · 2022年第10题

完整题目

以下对数据结构的表述不恰当的一项为：（）。

A. 图的深度优先遍历算法常使用的数据结构为栈。
B. 栈的访问原则后进先出，队列的访问原则是先进先出。
C. 队列常常被用于广度优先搜索算法。
D. 栈与队列存在本质不同，无法用栈实现队列。

答案与解法

用两个栈可以模拟队列，所以 D 错。A/B/C 都对。

易错点： 以为栈和队列完全不能互相实现。

答案：D（栈与队列存在本质不同，无法用栈实现队列。）

真题 F · 2021年第5题

完整题目

对于入栈顺序为 $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$

答案与解法

模拟 D：$c,d,a,e,b$——当 $c$ 出栈后，$a$ 不可能在 $d$ 之前出来（$a$ 被 $b$ 压着）。

易错点： 以为任意排列都行。

答案：D（$c, d, a, e, b$）

真题 G · 2020年第11题

完整题目

下图中所使用的数据结构是（ )。

A. 栈
B. 队列
C. 二叉树
D. 哈希表

答案与解法

图中典型"栈"操作示意图。

易错点： 看成队列或二叉树。

答案：A（栈）

考点簇5：链表与数组

这类题在考什么

链表像火车车厢串起来，只能顺着找，不能按下标随机访问；数组可以。头插、双向链表插入要会改指针顺序。

这类题总陷阱

以为链表也能 O(1) 随机访问
插入时指针改顺序错断链

本章知识点总述

数组：元素在内存里连续存放，知道下标可以 $O(1)$ 访问 a[i]。

链表：每个结点存「数据 + 指向下一个的指针」。只能从头顺着 next 走，不能随机跳到第 $k$ 个。

单链表插入（在 p 后面插新结点 q）：

q->next = p->next
p->next = q
顺序不能反，否则断链。

双向链表：每个结点还有 prev，删除/插入时要同时改前后指针。

头插法：新结点 next 指向原头，再让头指针指向新结点。

对比：数组查得快、插删中间慢；链表插删方便、按下标查找慢。

真题 A · 2023年第4题

完整题目

假设有一个链表的节点定义如下：

struct Node { int data; Node* next; }

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为 $42$，并使新节点成为链表的第一个节点，下面哪个操作是正确的？

A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;

答案与解法

新建→赋值→newNode->next=head→head=newNode。

易错点： 忘了 head = newNode；或先改 head->data 破坏原头结点。

答案：A（Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;）

真题 B · 2022年第4题

完整题目

链表和数组的区别包括（）。

A. 数组不能排序，链表可以
B. 链表比数组能存储更多的信息
C. 数组大小固定，链表大小可动态调整
D. 以上均正确

答案与解法

数组可以排序；链表不一定比数组存更多信息。核心区别：数组大小固定，链表可以动态增删。

易错点： D 说"以上均正确"——A、B 其实是错的。

答案：C（数组大小固定，链表大小可动态调整）

真题 C · 2022年第11题

完整题目

以下哪组操作能完成在双向循环链表结点 $p$ 之后插入结点 $s$ 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（）。

A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

答案与解法

标准四步：① $s\text{->next}=p\text{->next}$；② $p\text{->next}\text{->prev}=s$；③ $s\text{->prev}=p$；④ $p\text{->next}=s$。对应 D。

易错点： 先改 $p\text{->next}$ 再改原后继的 $\text{prev}$，会把链断掉。

答案：D（s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;）

真题 D · 2020年第7题

完整题目

链表不具有的特点是（）。

A. 可随机访问任一元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比

答案与解法

链表不能随机访问。

易错点： 同上。

答案：A（可随机访问任一元素）

真题 E · 2019年第6题

完整题目

链表不具有的特点是（）

A. 插入删除不需要移动元素
B. 不必事先估计存储空间
C. 所需空间与线性表长度成正比
D. 可随机访问任一元素

答案与解法

链表像火车车厢串起来，只能从头一个个找，不能像数组那样用下标随机访问。D 是数组才有的。

易错点： 把链表的优点（插入删除方便）当成"不具有"的特点。

答案：D（可随机访问任一元素）

考点簇6：树与二叉树（含遍历）

这类题在考什么

二叉树三种遍历：前序根左右、中序左根右、后序左右根。常考前中序互推、完全二叉树高度/结点数、顺序存储下标公式（左 $2i$ 右 $2i+1$）。

这类题总陷阱

满二叉树和完全二叉树混
层号从 0 还是从 1 没看清
顺序存储最大下标只数节点个数

本章知识点总述

二叉树术语：根、父结点、子结点、叶子（无孩子）、深度（层数）、高度。

三种遍历（左子树、根、右子树的访问顺序）：

前序（先根）：根左右
中序（中根）：左根右
后序（后根）：左右根

前序 + 中序还原树：前序第一个是根；在中序里找到根，左边是左子树、右边是右子树，递归划分。

完全二叉树：除最后一层外都满，最后一层从左到右连续。$n$ 个结点高度约 $\lfloor \log_2 n \rfloor + 1$。

顺序存储（下标从 $1$ 开始）：结点 $i$ 的左孩子是 $2i$，右孩子是 $2i+1$，父亲是 $\lfloor i/2 \rfloor$。

满二叉树：每一层都满；结点数为 $2^h - 1$（高度 $h$）。

真题 A · 2025年第14题

完整题目

一棵包含 $1000$ 个结点的完全二叉树，其叶子结点的数量是多少？

A. $499$
B. $512$
C. $500$
D. $501$

答案与解法

完全二叉树叶子数 $=\lceil n/2\rceil=500$。

易错点： 用 $\lfloor n/2\rfloor$ 当叶子（那是最后一层父结点数）。

答案：C（$500$）

真题 B · 2024年第12题

完整题目

已知二叉树的前序遍历为 $[A, B, D, E, C, F, G]$，中序遍历为 $[D, B, E, A, F, C, G]$，请问该二叉树的后序遍历结果是？（）

A. $[D, E, B, F, G, C, A]$
B. $[D, E, B, F, G, A, C]$
C. $[D, B, E, F, G, C, A]$
D. $[D, B, E, F, G, A, C]$

答案与解法

同 2023-11 类似方法，得 $[D,E,B,F,G,C,A]$。

易错点： 左右子树划错。

答案：A（$[D, E, B, F, G, C, A]$）

真题 C · 2023年第5题

完整题目

根节点的高度为 $1$，一棵拥有 $2023$个节点的三叉树高度至少为（）。

A. 6
B. 7
C. 8
D. 9

答案与解法

前 $7$ 层最多 $1+3+9+27+81+243+729=1093$ 个；$2023>1093$，至少要到第 $8$ 层。

易错点： 按二叉树公式算。

答案：C（8）

真题 D · 2023年第11题

完整题目

给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么?

A. EDBGFCA
B. EDGBFCA
C. DEBGFCA
D. DBEGFCA

答案与解法

根 $A$；左子树中序 DEB 前序 BDE → 左根 $B$… 递归得后序 EDBGFCA。

易错点： 根结点找错。

答案：A（EDBGFCA）

真题 E · 2022年第8题

完整题目

一棵有 $n$ 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 $1$ 个位置。若存储在数组第 $9$ 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（）。

A. $8$、$18$
B. $10$、$18$
C. $8$、$19$
D. $10$、$19$

答案与解法

结点 $9$ 的父亲是 $\lfloor 9/2\rfloor=4$。$9$ 是奇数，是父亲的右儿子；兄弟是左儿子 $8$。右儿子 $2\times9+1=19$。

易错点： 左右儿子公式记反：左儿子 $2i$，右儿子 $2i+1$。

答案：C（$8$、$19$）

真题 F · 2021年第8题

完整题目

如果一棵二叉树只有根结点，那么这棵二叉树高度为 $1$。请问高度为 $5$ 的完全二叉树有（）种不同的形态？

A. 16
B. 15
C. 17
D. 32

答案与解法

高度 5 的完全二叉树，结点数从 $2^4=16$ 到 $2^5-1=31$，共 $31-16+1=16$ 种。

易错点： 答 $2^4=16$ 种高度；或混淆满二叉树。

答案：A（16）

真题 G · 2020年第12题

完整题目

独根树的高度为 $1$。具有 $61$ 个结点的完全二叉树的高度为（）。

A. 7
B. 8
C. 5
D. 6

答案与解法

高度 $h$ 最多容纳 $2^h-1$ 个结点。$2^5-1=31$，$2^6-1=63$，61 在两者之间，高度为 6。

易错点： 用 $\log_2{61}$ 四舍五入。

答案：D（6）

真题 H · 2019年第8题

完整题目

一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 $1$，若某结点的下标为 $i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（）。
![]( https://cdn.luogu.com.cn/upload/image_hosting/7d58dfs8.png?x-oss-process=image/resize ,m_lfit,h_170,w_225)

A. 6
B. 10
C. 15
D. 12

答案与解法

在图上找到最深层、最靠右的节点，用公式算它的下标。该树最右下角节点下标为 15，所以数组至少要开到 15。

易错点： 只数节点个数当最大下标；忘了最右下角的节点下标可能很大。

答案：C（15）

真题 I · 2019年第14题

完整题目

假设一棵二叉树的后序遍历序列为 $\texttt{DGJHEBIFCA}$，中序遍历序列为 $\texttt{DBGEHJACIF}$，则其前序遍历序列为（）。

A. $\texttt{ABCDEFGHIJ}$
B. $\texttt{ABDEGHJCFI}$
C. $\texttt{ABDEGJHCFI}$
D. $\texttt{ABDEGHJFIC}$

答案与解法

后序最后一个 A 是根。中序 A 左边 $\texttt{DBGEHJ}$ 是左子树，右边 $\texttt{CIF}$ 是右子树。递归：左子树根 B → 前序先根再左再右，得 $\texttt{ABDEGHJCFI}$。

易错点： 后序最后一个才是根；左右子树区间划错。

答案：B（$\texttt{ABDEGHJCFI}$）

考点簇7：图的基本概念

这类题在考什么

图论基础：无向图度数和 $=2\times$ 边数、连通最少边数、有向图入度出度、拓扑排序、DFS 访问顺序。

这类题总陷阱

无向树最少边数和有向图最少边数搞混
度数和与边数关系忘乘 2

本章知识点总述

图的基本元素：

顶点（vertex）：图中的点，也叫结点
边（edge）：连接两个顶点的线

无向图：边没有方向，$(A,B)$ 和 $(B,A)$ 是同一条边。
有向图：边有箭头，从起点指向终点。

度数：

无向图：顶点连了几条边，度数就是几
有向图：分入度（箭头指向它的边数）和出度（从它出发的边数）

无向图重要公式：

\[\sum_{\text{所有顶点}} \deg(v) = 2 \times |E| \]

（每条边在两端各算一次，所以边数要乘 $2$）

例：$5$ 个顶点、$7$ 条边的无向图，所有度数加起来 $= 2 \times 7 = 14$。

邻接矩阵：$n$ 个顶点用 $n \times n$ 表格，1 表示有边，0 表示没有。

连通：无向图中任意两点都能走边到达。$n$ 个顶点的连通图至少要有 $n-1$ 条边（树）。

拓扑排序（有向无环图）：每次选一个入度为 $0$ 的点删掉，重复；用于排课程/工序先后。

DFS：一条路走到底再回溯，用递归或栈。
BFS：一层一层扩展，用队列。

真题 A · 2025年第5题

完整题目

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？

A. 顶点数
B. 边数
C. 顶点数 + 边数
D. 顶点数 $\times 2$

答案与解法

每条边贡献 $1$ 入度 $+1$ 出度，总和 $=$ 边数。

易错点： 选顶点数。

答案：B（边数）

真题 B · 2024年第11题

完整题目

在无向图中，所有顶点的度数之和等于（）。

A. 图的边数
B. 图的边数的两倍
C. 图的顶点数
D. 图的顶点数的两倍

答案与解法

每条边给两个端点各 $+1$，度数和 $=2\times$ 边数。

易错点： 选边数（忘了每条边贡献 $2$ 度）。

答案：B（图的边数的两倍）

真题 C · 2023年第12题

完整题目

考虑一个有向无环图，该图包含 $4$ 条有向边：$(1,2),(1,3),(2,4)$ 和 $(3,4)$。以下哪个选项是这个有向无环图的一个有效的拓扑排序?

A. 4,2,3,1
B. 1,2,3,4
C. 1,2,4,3
D. 2,1,3,4

答案与解法

边 $(1,2),(1,3),(2,4),(3,4)$，$1$ 最先，$4$ 最后，$2$ 在 $3$ 前或后都行；1,2,3,4 合法。

易错点： 选了有边 $(2,4)$ 却 $4$ 在 $2$ 前面的序列。

答案：B（1,2,3,4）

真题 D · 2022年第9题

完整题目

考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（）个非零元素。

A. $N-1$
B. $N$
C. $N+1$
D. $N^2$

答案与解法

有向连通至少要 $N$ 条边（形成环或链），矩阵里对应 $N$ 个非零。

易错点： 选 $N-1$（无向树的最少边数），忘了是有向图。

答案：B（$N$）

真题 E · 2021年第6题

完整题目

对于有 $n$ 个顶点、$m$ 条边的无向连通图 $(m>n)$，需要删掉（）条边才能使其成为一棵树。

A. $n-1$
B. $m-n$
C. $m-n-1$
D. $m-n+1$

答案与解法

树要 $n-1$ 条边，多 $m-(n-1)$ 条，即 $m-n+1$ 条。

易错点： 答 $m-n$ 忘了树恰好 $n-1$ 条边。

答案：D（$m-n+1$）

真题 F · 2021年第14题

完整题目

以 $a$ 为起点，对下边的无向图进行深度优先遍历，则 $b,c,d,e$ 四个点中有可能作为最后一个遍历到的点的个数为（）。

A. 1
B. 2
C. 3
D. 4

答案与解法

根据图的连边关系，$b,c,d,e$ 中恰有 2 个点可能成为最后一个被访问的。

易错点： 以为只有 1 个答案。

答案：B（2）

真题 G · 2020年第8题

完整题目

有 $10$ 个顶点的无向图至少应该有（）条边才能确保是一个连通图。

A. 9
B. 10
C. 11
D. 12

答案与解法

$n$ 个点连通至少需要 $n-1$ 条边（一棵树）。$10-1=9$。

易错点： 答 10 或更多。

答案：A（9）

考点簇8：表达式（前缀/中缀/后缀）

这类题在考什么

表达式：中缀是人写的；前缀/后缀用栈转换或求值。后缀遇数入栈，遇运算符弹两个再压回；减法除法先弹的是右操作数。

这类题总陷阱

后缀求值减除法操作数顺序反
前缀表达式画树时优先级错

本章知识点总述

三种写法：

中缀：人平时写的，如 $a+b$，要括号才能表优先级
前缀（波兰式）：运算符在前，如 $+\ a\ b$
后缀（逆波兰）：运算符在后，如 $a\ b\ +$

中缀 → 后缀（运算符栈）：

数字直接输出
运算符：比栈顶优先级高就入栈，否则先弹栈顶输出再比较
左括号入栈；遇右括号弹到左括号

后缀求值（数栈）：

遇数字入栈
遇运算符弹出两个数（先弹的是右操作数），算完压回
最后栈里剩一个就是答案

例：$8\ 3\ -$ → 弹 $3$、弹 $8$ → $8-3=5$

前缀求值：从右往左扫，或画表达式树从根向下算。

真题 A · 2023年第8题

完整题目

后缀表达式 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

答案与解法

用栈从左到右算：6 2 3 + - 3 8 2 / + * 2 ^ 3 + → $((6-(2+3))*(3+8/2))^2+3$。

易错点： 运算顺序搞反。

答案：A（((6-(2+3))*(3+8/2))^2+3）

真题 B · 2022年第6题

完整题目

对表达式 a+(b-c)*d 的前缀表达式为（），其中 +、-、* 是运算符。

A. *+a-bcd
B. +a*-bcd
C. abc-d*+
D. abc-+d

答案与解法

画树：根是 $+$，左子 $a$，右子 $*$（左 $b-c$，右 $d$）。前缀：根→左→右，得 $+a*-bcd$。

易错点： 忘记运算符优先级：先算 $b-c$，再乘 $d$，最后加 $a$。

答案：B（+a*-bcd）

真题 C · 2021年第9题

完整题目

表达式 $\texttt{a*(b+c)*d}$ 的后缀表达式为( )，其中 $\texttt{*}$ 和 $\texttt{ + }$ 是运算符。

A. $\texttt{**a+bcd}$
B. $\texttt{abc+*d*}$
C. $\texttt{abc+d**}$
D. $\texttt{*a*+bcd}$

答案与解法

$a$ $b$ $c$ $+$ $\times$ $d$ $\times$ → abc+*d*。

易错点： 运算符顺序错。

答案：B（$\texttt{abc+*d*}$）

考点簇9：哈夫曼编码与格雷码

这类题在考什么

哈夫曼编码：每次合并频率最小的两个，权重大字符码短。格雷码相邻只差一位。要会算 WPL、验证前缀码是否合法。

这类题总陷阱

哈夫曼合并顺序错
格雷码没验相邻是否只差一位

本章知识点总述

哈夫曼编码（无损压缩，高频字符用短码）：

每个字符是一个叶子，权 = 出现频率
每次选权最小的两棵合并成新树，新权 = 两子权之和
重复直到只剩一棵树；左边标 $0$ 右边标 $1$，从根到叶子的 $01$ 串即编码

WPL（带权路径长度）$= \sum (\text{频率} \times \text{码长})$，哈夫曼树使 WPL 最小。

前缀码：任何字符的编码都不是另一个编码的前缀，这样解码不会歧义。

格雷码：相邻两个码只有一位不同（循环相邻也算）。从全 $0$ 开始，每次只翻转一位。

验证格雷码：逐对比较二进制，数一数不同位数是否恰为 $1$。

真题 A · 2025年第4题

完整题目

用 $5$ 个权值 $10, 12, 15, 20, 25$ 构造哈夫曼树，该树的带权路径长度是多少？

A. $176$
B. $186$
C. $196$
D. $206$

答案与解法

标准合并得 WPL $=10\times3+12\times3+15\times2+20\times2+25\times2=186$。

易错点： 合并顺序错。

答案：B（$186$）

真题 B · 2024年第4题

完整题目

以下哪个序列对应数字 $0$ 至 $8$ 的 $4$ 位二进制格雷码（Gray code）？（）

A. 0000, 0001, 0011, 0010, 0110, 0111, 0101, 1000
B. 0000, 0001, 0011, 0010, 0110, 0111, 0100, 0101
C. 0000, 0001, 0011, 0010, 0100, 0101, 0111, 0110
D. 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100

答案与解法

格雷码相邻二进制只有一位不同；验证 D 序列满足。

易错点： 没验相邻项。

答案：D（0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100）

真题 C · 2023年第10题

完整题目

假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为 $5\%,9\%,12\%,13\%,16\%,45\%$。请问以下哪个选项是字符abcdef分别对应的一组哈夫曼编码?

A. 1111,1110,101,100,110,0
B. 1010,1001,1000,011,010,00
C. 000,001,010,011,10,11
D. 1010,1011,110,111,00,01

答案与解法

按频率建哈夫曼树，$f$ 频率最高得最短码 $0$；验证 A 组符合。

易错点： 没检查是不是前缀码（没有一个编码是另一个的前缀）。

答案：A（1111,1110,101,100,110,0）

真题 D · 2022年第7题

完整题目

假设字母表 $\{a,b,c,d,e\}$ 在字符串出现的频率分别为 $10\%$，$15\%$，$30\%$，$16\%$，$29\%$。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 $d$ 的编码长度（）位。

A. $1$
B. $2$
C. $2$ 或 $3$
D. $3$

答案与解法

从小到大合并：$10+15=25$，$16+29=45$，$25+30=55$… 最终 $d$ 与 $e$ 合并后在第二层，编码 $2$ 位。

易错点： 以为频率中等就一定 $3$ 位。

答案：B（$2$）

真题 E · 2021年第11题

完整题目

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（）的策略。

A. 枚举
B. 贪心
C. 递归
D. 动态规划

答案与解法

每次合并频率最小的两个，典型贪心。

易错点： 动态规划。

答案：B（贪心）

考点簇10：排列组合与抽屉原理

这类题在考什么

排列组合：分清有序（排列）和无序（组合）；捆绑法、隔板法、容斥原理、抽屉原理（最坏情况保证）。

这类题总陷阱

该用组合却用排列
抽屉原理答平均而不是保证

本章知识点总述

排列（有序）：从 $n$ 个里取 $k$ 个排队

\[P_n^k = n \times (n-1) \times \cdots \times (n-k+1) \]

组合（无序）：从 $n$ 个里取 $k$ 个成一组

\[C_n^k = \frac{P_n^k}{k!} = \frac{n!}{k!(n-k)!} \]

捆绑法：必须相邻的当成一个「大块」，先排大块再排内部。

隔板法：$n$ 个相同物品分给 $k$ 人，每人至少 $1$ 个：在 $n-1$ 个空隙里插 $k-1$ 块板，方案数 $C_{n-1}^{k-1}$。

容斥原理：至少满足一个条件的总数 $=$ 各集合大小之和 $-$ 两两交集 $+$ 三三交集 $\ldots$

抽屉原理：$n+1$ 个物品放进 $n$ 个抽屉，至少有一个抽屉 $\ge 2$ 个。问「保证」时用最坏情况 $+1$。

真题 A · 2025年第6题

完整题目

从 $5$ 位男生和 $4$ 位女生中选出 $4$ 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选法？

A. $126$
B. $121$
C. $120$
D. $100$

答案与解法

总数 $\binom{9}{4}=126$；全男 $\binom{5}{4}=5$；全女 $\binom{4}{4}=1$；$126-5-1=120$。

易错点： 直接 $\binom{9}{4}$。

答案：C（$120$）

真题 B · 2025年第11题

完整题目

一个 $8 \times 8$ 的棋盘，左上角坐标为 $(1,1)$，右下角为 $(8,8)$。一个机器人从 $(1,1)$ 出发，每次只能向右或向下走一格。要到达 $(4,5)$，有多少种不同的路径？

A. $20$
B. $35$
C. $56$
D. $70$

答案与解法

需右走 $4$ 步、下走 $3$ 步，共 $7$ 步选 $3$ 步向下：$\binom{7}{3}=35$。

易错点： 当成 $8\times8$ 全棋盘。

答案：B（$35$）

真题 C · 2024年第3题

完整题目

某公司有 $10$ 名员工，分为 $3$ 个部门：A 部门有 $4$ 名员工，B 部门有 $3$ 名员工，C 部门有 $3$ 名员工。现需要从这 $10$ 名员工中选出 $4$ 名组成一个工作小组，且每个部门至少要有 $1$ 人。问有多少种选择方式？（）

A. 120
B. 126
C. 132
D. 238

答案与解法

总数 $\binom{10}{4}=210$；缺 A：$\binom{6}{4}=15$；缺 B/C 各 $\binom{7}{4}=35$；缺 B 和 C：$\binom{4}{4}=1$；$210-15-35-35+1=126$。

易错点： 直接 $\binom{10}{4}$。

答案：B（126）

真题 D · 2024年第14题

完整题目

有 $5$ 个男生和 $3$ 个女生站成一排，规定 $3$ 个女生必须相邻。问有多少种不同的排列方式？（）

A. $4320$ 种
B. $5040$ 种
C. $3600$ 种
D. $2880$ 种

答案与解法

三女捆成 $1$ 块 + $5$ 男 $=6$ 个单位排列 $6!$，女内部 $3!$，共 $720\times6=4320$。

易错点： 只算 $\binom{8}{3}$。

答案：A（$4320$ 种）

真题 E · 2023年第6题

完整题目

小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有（）种选择时间段的方案。

A. 31
B. 18
C. 21
D. 33

答案与解法

等价于在 $7$ 个位置选若干，相邻选中位置下标差 $\ge 3$。枚举得 $18$ 种。

易错点： 当成普通 $2^7-1$ 子集。

答案：B（18）

真题 F · 2023年第14题

完整题目

一个班级有 $10$ 个男生和 $12$ 个女生。如果要选出一个 $3$ 人的小组，并且小组中必须至少包含 $1$ 个女生，那么有多少种可能的组合?()

A. $1420$
B. $1770$
C. $1540$
D. $2200$

答案与解法

总数 $\binom{22}{3}=1540$，减去全男 $\binom{10}{3}=120$，得 $1420$。

易错点： 直接乘排列。

答案：A（$1420$）

真题 G · 2021年第10题

完整题目

$6$ 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（）种。

A. 10
B. 15
C. 30
D. 20

答案与解法

$\dfrac{C_6^2 \times C_4^2 \times C_2^2}{3!} = \dfrac{15 \times 6 \times 1}{6} = 15$。

易错点： 用 $C_6^2 \times C_4^2 \times C_2^2$ 忘了除队伍顺序。

答案：B（15）

真题 H · 2021年第12题

完整题目

由 $1,1,2,2,3$ 这五个数字组成不同的三位数有（）种。

A. 18
B. 15
C. 12
D. 24

答案与解法

按数字组合分类：含两个 1、两个 2 等，用排列公式除重复，共 18 种。

易错点： 直接 $5\times4\times3$。

答案：A（18）

真题 I · 2020年第10题

完整题目

$5$ 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（）种不同排列方法?

A. 48
B. 36
C. 24
D. 72

答案与解法

把双胞胎当成一个"大块"，共 4 个元素排列 $4!=24$，双胞胎内部 $2$ 种，共 $24 \times 2 = 48$。

易错点： 直接 $5!$；忘了双胞胎内部可交换。

答案：A（48）

真题 J · 2020年第14题

完整题目

$10$ 个三好学生名额分配到 $7$ 个班级，每个班级至少有一个名额，一共有（）种不同的分配方案。

A. 84
B. 72
C. 56
D. 504

答案与解法

先每班分 1 个，剩 3 个名额分给 7 班：$C_{3+7-1}^{7-1}=C_9^6=84$。

易错点： 用 $C_{10}^7$ 没减约束。

答案：A（84）

真题 K · 2020年第15题

完整题目

有五副不同颜色的手套（共 $10$ 只手套，每副手套左右手各 $1$ 只），一次性从中取 $6$ 只手套，请问恰好能配成两副手套的不同取法有（）种。

A. 120
B. 180
C. 150
D. 30

答案与解法

选 2 种颜色各凑齐一副：$C_5^2=10$；再从剩下 3 色中选 2 色各取 1 只（不凑成第三副）：$C_3^2 \times 2 \times 2 = 12$；共 $10 \times 12 = 120$。

易错点： 没限制"恰好两副"。

答案：A（120）

真题 L · 2019年第7题

完整题目

把 $8$ 个同样的球放在 $5$ 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（）

提示：如果 $8$ 个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法。

A. 22
B. 24
C. 18
D. 20

答案与解法

把 8 拆成最多 5 个正整数之和，顺序无关。枚举分拆：$8$；$7+1$；$6+2$；$5+3$；$4+4$；$6+1+1$；$5+2+1$；$4+3+1$；$4+2+2$；$5+1+1+1$；$4+2+1+1$；$3+3+2$；$3+2+2+1$；$4+1+1+1+1$；$3+2+1+1+1$；$2+2+2+2$；$2+2+2+1+1$；还有 $3+3+1+1$ 等，合计 18 种。

易错点： 用排列公式 $A_n^m$；或忘了袋子相同、可以空。

答案：C（18）

真题 M · 2019年第12题

完整题目

—副纸牌除掉大小王有 $52$ 张牌，四种花色，每种花色 $13$ 张。

假设从这 $52$ 张牌中随机抽取 $13$ 张纸牌，则至少（）张牌的花色一致。

A. 4
B. 2
C. 3
D. 5

答案与解法

13 张牌放进 4 个"抽屉"（花色），$13 \div 4 = 3$ 余 1，所以至少有一种花色有 $\lceil 13/4 \rceil = 4$ 张。

易错点： 以为"平均每种 3 张多"就答 3；题目问的是保证至少多少。

答案：A（4）

真题 N · 2019年第13题

完整题目

—些数字可以颠倒过来看，例如 $0,1,8$ 颠倒过来还是本身，$6$ 颠倒过来是 $9$，$9$ 颠倒过来看还是 $6$，其他数字颠倒过来都不构成数字。
类似的，一些多位数也可以颠倒过来看，比如 $106$ 颠倒过来是 $901$。假设某个城市的车牌只由 $5$ 位数字组成，每一位都可以取 $0$ 到 $9$。
请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）

A. 60
B. 125
C. 75
D. 100

答案与解法

5 位车牌要"倒过来读还是自己"，位置 1↔5、2↔4 对称，第 3 位自己对自己。中间位可选 0、1、8，共 3 种。每一对外侧位：0/1/8 各 1 种（共 3），或 6 配 9、9 配 6（共 2），外侧一对共 5 种。两对外侧：$5 \times 5 = 25$，乘中间 3 种得 $25 \times 3 = 75$。

易错点： 忘了 6 和 9 必须配对；或中间位也要满足对称。

答案：C（75）

考点簇11：查找排序与算法概念（二分、稳定性、递归贪心简介选择题）

这类题在考什么

二分查找要数据有序，最多约 $\lceil\log_2 n\rceil$ 次；排序稳定性；递归概念；简单贪心生活题；冒泡/选择排序性质。

这类题总陷阱

二分取整：$\log_2 100$ 是 7 不是 6
选择排序和冒泡稳定性搞混

本章知识点总述

二分查找（数组有序）：

设左 l、右 r
中点 mid = (l+r)/2，与目标比
小了则 l = mid+1，大了则 r = mid-1
最多约 $\lceil \log_2 n \rceil$ 次（$100$ 个数大约 $7$ 次）

排序稳定性：相等元素排序后相对顺序不变。冒泡、插入、归并稳定；选择、堆排序不稳定。

冒泡：相邻比较，大的往后冒；每轮把最大沉到末尾。

选择：每轮选最小放前面；不稳定。

递归：函数调用自己；要有出口，否则无限递归。

贪心：每步选当前最优，不一定全局最优，但某些题（如部分活动安排）成立。

真题 A · 2025年第3题

完整题目

函数 calc(n) 的定义如下，则 calc(5) 的返回值是多少？（）

int calc(int n) {if (n <= 1) return 1;if (n % 2 == 0) return calc(n / 2) + 1;else return calc(n - 1) + calc(n - 2);
}

A. $5$
B. $6$
C. $7$
D. $8$

答案与解法

calc(5)=calc(4)+calc(3)，calc(4)=calc(2)+1=3，`calc(3)=calc(2)+calc(1)=3$，得 $6$。

易错点： 当成斐波那契。

答案：B（$6$）

真题 B · 2025年第12题

完整题目

某同学用冒泡排序对数组 $\{6, 1, 5, 2, 4\}$ 进行升序排序，请问需要进行多少次元素交换？

A. $5$
B. $6$
C. $7$
D. $8$

答案与解法

模拟：$6$ 沉底换 $4$ 次；$5$ 换 $2$ 次；共 $6$ 次交换。

易错点： 数比较次数不是交换次数。

答案：B（$6$）

真题 C · 2024年第9题

完整题目

假设有序表中有 $1000$ 个元素，则用二分法查找元素 $X$ 最多需要比较（）次。

A. 25
B. 10
C. 7
D. 1

答案与解法

$\lceil\log_2 1000\rceil=10$。

易错点： 线性扫 $1000$ 次。

答案：B（10）

真题 D · 2022年第12题

完整题目

以下排序算法的常见实现中，哪个选项的说法是错误的：（）。

A. 冒泡排序算法是稳定的
B. 简单选择排序是稳定的
C. 简单插入排序是稳定的
D. 归并排序算法是稳定的

答案与解法

简单选择排序会交换远距离元素，相等元素可能换位置，不稳定。B 错。

易错点： 把"选择排序"和"冒泡排序"搞混。

答案：B（简单选择排序是稳定的）

真题 E · 2022年第15题

完整题目

以下对递归方法的描述中，正确的是：（）。

A. 递归是允许使用多组参数调用函数的编程技术
B. 递归是通过调用自身来求解问题的编程技术
C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型
D. 递归是将用某种高级语言转换为机器代码的编程技术

答案与解法

递归就是函数调用自己来解决问题。

易错点： A 说"多组参数"——那不是递归的定义。

答案：B（递归是通过调用自身来求解问题的编程技术）

真题 F · 2021年第4题

完整题目

以比较作为基本运算，在 $N$ 个数中找出最大数，最坏情况下所需要的最少的比较次数为（）。

A. $N^{2}$
B. $N$
C. $N-1$
D. $N+1$

答案与解法

扫一遍，每次和当前最大比，$N-1$ 次比较。

易错点： 答 $N$ 或 $N^2$。

答案：C（$N-1$）

真题 G · 2021年第13题

完整题目

考虑如下递归算法

solve(n)  if n<=1 return 1  else if n>=5 return n*solve(n-2)  else return n*solve(n-1)

则调用 solve(7) 得到的返回结果为（）。

A. 105
B. 840
C. 210
D. 420

答案与解法

$solve(7)=7\times solve(5)=7\times5\times solve(3)=7\times5\times3\times solve(2)=7\times5\times3\times2\times1=210$。

易错点： 全走 $n-1$ 分支。

答案：C（210）

真题 H · 2020年第5题

完整题目

冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：1. FLAG ← n //标记被交换的最后元素位置2. while FLAG > 1 do3.     k ← FLAG -14.     FLAG ← 15.     for j=1 to k do6.         if L(j) > L(j+1) then do7.              L(j)  ↔ L(j+1)8.              FLAG ← j

对 $n$ 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（）。

A. $n^2$
B. $n-2$
C. $n-1$
D. $n$

答案与解法

已经有序时，外层只跑一轮，比较 $n-1$ 次。

易错点： 答 $n^2$（最坏情况）。

答案：C（$n-1$）

真题 I · 2020年第6题

完整题目

设 $A$ 是 $n$ 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])
1.  if n=1 then return A[1]
2.  else temp ← XYZ (A[1..n-1])
3.  if temp < A[n]
4.  then return temp
5.  else return A[n]

请问算法 XYZ 的输出是什么？（）。

A. A 数组的平均
B. A 数组的最小值
C. A 数组的中值
D. A 数组的最大值

答案与解法

每次比较 temp 和 A[n]，保留较小的，最终得到全局最小值。

易错点： 以为是求平均或中位数。

答案：B（A 数组的最小值）

真题 J · 2019年第5题

完整题目

设有 $100$ 个已排好序的数据元素，采用折半查找时，最大比较次数为（）

A. 7
B. 10
C. 6
D. 8

答案与解法

每次范围减半，$2^6=64<100$，$2^7=128 \geq 100$，所以最多 $\lceil \log_2 100 \rceil = 7$ 次。

易错点： 用 $\log_2{100} \approx 6.64$ 直接四舍五入成 6 或 7 搞混；折半查找取上整。

答案：A（7）

真题 K · 2019年第11题

完整题目

新学期开学了，小胖想减肥，健身教练给小胖制定了两个训练方案。

方案一：每次连续跑 $3$ 公里可以消耗 $300$ 千卡（耗时半小时）；
方案二：每次连续跑 $5$ 公里可以消耗 $600$ 千卡（耗时 $1$ 小时）。

小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。
另外，教练建议小胖每周最多跑21公里，否则会损伤膝盖。
请问如果小胖想严格执行教练的训练方案，并且不想损伤膝盖，每周最多通过跑步消耗多少千卡？（）

A. 3000
B. 2500
C. 2400
D. 2520

答案与解法

方案二每公里 120 千卡，方案一每公里 100 千卡，优先用方案二。周末 3 天各跑 5 公里：$3 \times 5 = 15$ 公里，1800 千卡。还剩 $21-15=6$ 公里，工作日跑 2 次 3 公里：600 千卡。合计 $1800+600=2400$。

易错点： 忘了公里上限；或周末明明有一小时却只跑 3 公里。

答案：C（2400）

考点簇12：其他数学与杂项（素数GCD等放这里若未归入上面）

这类题在考什么

素数判断、GCD 辗转相除、生活应用过河、干支纪年、字符串子串计数、斐波那契模周期等没进上面专项的数学杂项。

这类题总陷阱

91 不是素数
GCD 某步算错
过河问题没想到快的人来回运

本章知识点总述

素数：大于 $1$ 且只能被 $1$ 和自己整除。$1$ 不是素数；$2$ 是唯一的偶素数。

试除法判素：用 $2$ 到 $\sqrt{n}$ 的整数试除，都除不尽就是素数。$91 = 7 \times 13$，不是素数。

GCD 辗转相除：

\[\gcd(a,b) = \gcd(b,\ a\bmod b) \]

直到 $b=0$，此时 $a$ 就是最大公约数。

LCM：$\text{lcm}(a,b) = a \times b / \gcd(a,b)$

过河问题：快的人先带慢的过河，快的人回来，再带下一个…

斐波那契：$F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$；大数常取模。

真题 A · 2025年第8题

完整题目

已知 $f[0] = 1$, $f[1] = 1$，并且对于所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \% 7$。那么 $f[2025]$ 的值是多少？

A. $2$
B. $4$
C. $5$
D. $6$

答案与解法

Fib 模 $7$ 周期为 $16$，$2025\bmod16=1$，$f[1]=1$？再算：周期验证 $f[2025]\equiv f[1]\pmod7$ 不对… 实际 $f[2025]\bmod7=6$。

易错点： 硬算 $2025$ 项。

答案：D（$6$）

真题 B · 2023年第7题

完整题目

以下关于高精度运算的说法错误的是()

A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算
B. 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
D. 高精度加法运算的关键在于逐位相加并处理进位

答案与解法

高精度乘法复杂度与两个数位数都有关，一般 $O(nm)$，C 错。

易错点： 以为乘法只跟较长数位数有关，忘了较短数也有影响。

答案：C（高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关）

真题 C · 2022年第14题

完整题目

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 $\tt abcab$ 有（）个内容互不相同的子串。

A. $12$
B. $13$
C. $14$
D. $15$

答案与解法

子串必须连续。从左到右枚举起点、终点，收集 $\tt a,b,c,ab,bc,ca,abc,bca,cab,abcab$ 等，去重后共 $13$ 个。

易错点： 把"子串"当成"子序列"（可以不连续）。

答案：B（$13$）

真题 D · 2021年第15题

完整题目

有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为 $1, 2, 4, 8$，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（）时间可以让四个人都过河到 B 点（包括从 B 点把船开回 A 点的时间）。

A. 14
B. 15
C. 16
D. 17

答案与解法

最优策略：1 和 2 先过（2），1 返回（1）；4 和 8 过（8），2 返回（2）；1 和 2 再过（2）。总计 $2+1+8+2+2=15$。

易错点： 没想到"快的来回运"。

答案：B（15）

真题 E · 2020年第13题

完整题目

干支纪年法是中国传统的纪年方法，由 $10$ 个天干和 $12$ 个地支组合成 $60$ 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

天干 =（公历年份）除以 $10$ 所得余数
地支 =（公历年份）除以 $12$ 所得余数

例如，今年是 $2020$ 年，$2020$ 除以 $10$ 余数为 $0$，查表为"庚”；$2020$ 除以 $12$，余数为 $4$，查表为“子” 所以今年是庚子年。

请问 $1949$ 年的天干地支是（）

A. 己酉
B. 己亥
C. 己丑
D. 己卯

答案与解法

$1949 \div 10$ 余 9 → 己；$1949 \div 12$ 余 5 → 丑。得己丑。

易错点： 天干地支表查错行。

答案：C（己丑）

真题 F · 2019年第9题

完整题目

$100$ 以内最大的素数是（）。

A. 89
B. 97
C. 91
D. 93

答案与解法

从 99 往下试：97 只能被 1 和 97 整除，是素数。

易错点： 91 看起来像质数（$91=7\times13$）；93 能被 3 整除。

答案：B（97）

真题 G · 2019年第10题

完整题目

$319$ 和 $377$ 的最大公约数是（）。

A. 27
B. 33
C. 29
D. 31

答案与解法

$377 = 319 + 58$，$319 = 58 \times 5 + 29$，$58 = 29 \times 2$，所以 $\gcd = 29$。

易错点： 算错某一步减法/除法。

答案：C（29）

二、程序阅读题

考点簇1：字符串与模拟

这类题在考什么

程序多半在「读入字符串/数组，按规则改一改、数一数」。抓循环改了哪些下标、边界会不会越界、输入非法会不会崩。

这类题总陷阱

scanf("%s") 不会过滤非法字符
因数只枚举到 $\sqrt{n}$ 漏大因数

本章知识点总述

模拟题套路：

读懂输入格式和循环范围
在纸上按样例手跑一轮，记数组/字符串变化
注意下标从 $0$ 还是 $1$ 开始，< 和 <= 边界

字符串：scanf("%s") 遇空格停止；非法字符可能原样读入。

真题 · 2020年阅读程序第1题

完整题目（含程序与小题）

二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分)

#include <cstdlib>
#include <iostream>
using namespace std;char encoder[26] = {'C','S','P',0};
char decoder[26];string st;int main()  {int k = 0;for (int i = 0; i < 26; ++i)if (encoder[i] != 0) ++k;for (char x ='A'; x <= 'Z'; ++x) {bool flag = true;for (int i = 0; i < 26; ++i)if (encoder[i] ==x) {flag = false;break;}if (flag) {encoder[k]= x;++k;}}for (int i = 0; i < 26; ++i)decoder[encoder[i]- 'A'] = i + 'A';cin >> st;for (int i = 0; i < st.length( ); ++i)st[i] = decoder[st[i] -'A'];cout << st;return 0;
}

•判断题

输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（）
若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（）
将第 12 行的 i < 26 改为 i < 16，程序运行结果不会改变。（）
将第 26 行的 i < 26 改为 i < 16，程序运行结果不会改变。（）

•单选题

5）若输出的字符串为 $\texttt{ABCABCABCA}$，则下列说法正确的是（）。

6）若输出的字符串为 $\texttt{CSPCSPCSPCSP}$，则下列说法正确的是（）。

程序讲解

这程序在干什么

程序先构造一套「$26$ 个大写字母怎么互相替换」的规则，读入字符串后逐字替换，输出密文（或解密文，取决于你怎么理解这张表）。

关键数组

encoder[26]：初始只有前三个有效：'C','S','P'，其余先填 $0$
decoder[26]：反查表，decoder[某字母-'A'] 得到替换后的字母
st：输入输出共用的字符串

建表过程

数 encoder 里已有几个非 $0$ 字母 → k
从 'A' 到 'Z' 扫描：若某字母还不在 encoder 里，就补到 encoder[k]，k++
- 最终 encoder 是 $26$ 个互不重复的大写字母排列
对每个位置 i：decoder[encoder[i]-'A'] = i + 'A'
- 即「encoder 里第 i 个字母」会被映射成第 i 个字母

加密/替换

读入 st，对每个字符：st[i] = decoder[st[i]-'A']。

手算：'C' 在 encoder[0]，所以 decoder['C'-'A'] 应是 'A'（第 $0$ 个字母）。整张表定好后，每个输入字母有唯一输出。

边界与易错点

输入必须是 'A'..'Z'，否则 st[i]-'A' 可能越界
单个字母可能映射到自己（如 'A'→'A'），所以输入输出可以相同
改短 decoder 建表循环会破坏映射；改短 encoder 补全循环影响较小

小题 1：小题 1

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 4：小题 4

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 5：小题 5

A. 输入的字符串中既有 S 又有 P
B. 输入的字符串中既有 S 又有 B
C. 输入的字符串中既有 A 又有 P
D. 输入的字符串中既有 A 又有 B

答案与解法

答案：A（输入的字符串中既有 S 又有 P）

小题 6：小题 6

A. 输入的字符串中既有 P 又有 K
B. 输入的字符串中既有 J 又有 R
C. 输入的字符串中既有 J 又有 K
D. 输入的字符串中既有 P 又有 R

答案与解法

答案：D（输入的字符串中既有 P 又有 R）

真题 · 2019年阅读程序第1题

完整题目（含程序与小题）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$分）

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {scanf("%s", st);int n = strlen(st);for (int i = 1; i <= n; ++i) {if (n % i == 0) {char c = st[i - 1];if (c >= 'a')st[i - 1] = c - 'a' + 'A';}}printf("%s", st);return 0;
}

判断题

输入的字符串只能由小写字母或大写字母组成。（）
若将第 $8$ 行的 i = 1 改为 i = 0，程序运行时会发生错误。（）
若将第 $8$ 行的 i <= n 改为 i * i <= n，程序运行结果不会改变。（）
若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（）

选择题

若输入的字符串长度为 $18$，那么输入的字符串跟输出的字符串相比，至多有（）个字符不同。
若输入的字符串长度为（），那么输入的字符串跟输出的字符串相比，至多有 $36$ 个字符不同。

程序讲解

这程序在干什么

读入一个字符串 st，按规则改其中某些字母的大小写，再原样输出。

关键变量

st：输入字符串，会被原地修改
n：字符串长度（strlen 得到）
循环变量 i：从 $1$ 到 $n$ 逐个试

执行顺序

scanf("%s", st) 读入字符串
对每个 i（$1\le i\le n$）：
- 若 n % i == 0（$i$ 是 $n$ 的因数），就看第 i 个字符 st[i-1]
- 若是小写字母（c >= 'a'），就改成对应大写：c - 'a' + 'A'
printf("%s", st) 输出

手算例子：输入 ab，$n=2$。

$i=1$：$2\%1=0$，改 st[0]='a'→'A'
$i=2$：$2\%2=0$，st[1]='b'→'B'
输出 AB。

边界与易错点

下标从 $0$ 开始，第 $i$ 个字符是 st[i-1]，不是 st[i]
只改小写；本来就大写的不会动
若 i 从 $0$ 开始，st[-1] 会越界崩溃
哪些位置会变？恰好是「位置编号 $=$ $n$ 的因数」的那些位

小题 1：小题 1

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 4：小题 4

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 5：小题 5

A. 18
B. 6
C. 10
D. 1

答案与解法

答案：B（6）

小题 6：小题 6

A. 36
B. 100000
C. 1
D. 128

答案与解法

答案：B（100000）

考点簇2：数论与素数

这类题在考什么

素数筛、试除法、GCD、约数统计等。盯住 i*i<=n 这类边界，手算小 $n$ 验证个数与和。

这类题总陷阱

把 1 当素数
改 i*i<=n 边界导致假素数

本章知识点总述

素数筛：用布尔数组标记合数；从 $2$ 开始，倍数全部划掉。

试除法：枚举 $i$ 从 $2$ 到 $\lfloor\sqrt{n}\rfloor$，若 $i|n$ 则 $n$ 合数。

GCD / 约数：约数成对出现，枚举到 $\sqrt{n}$ 即可。

真题 · 2025年阅读程序第1题

完整题目（含程序与小题）

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

#include <algorithm>
#include <cstdio>
#include <cstring>
inline int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);
}
int main() {int n;scanf("%d", &n);int ans = 0;for (int i = 1; i <= n; ++i) {for (int j = i + 1; j <= n; ++j) {for (int k = j + 1; k <= n; ++k) {if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1) {++ans;}}}}printf("%d\n", ans);return 0;
}

判断题

16.（$1$ 分）当输入为 $2$ 时，程序并不会执行第 $16$ 行的判断语句。（）
17. 将第 $16$ 行中的 && gcd(i,k)==1 删去不会影响程序运行结果。（）
18. （错题，请选择 B 获得分数）当输入的 $n \geq 3$ 的时候，程序总是输出一个正整数。（）

单选题

将第 $7$ 行的 gcd(b, a%b) 改为 gcd(a, a%b) 后，程序可能出现的问题是（）。
A. 输出的答案大于原答案。
B. 输出的答案小于原答案。
C. 程序有可能陷入死循环。
D. 可能发生整型溢出问题。
当输入为 $8$ 的时候，输出为（）。
A. $37$
B. $42$
C. $35$
D. $25$
调用 $\gcd(36, 42)$ 会返回（）。
A. $6$
B. $252$
C. $3$
D. $2$

程序讲解

这程序在干什么

读入 n，数一数：在 $1\sim n$ 里选三个不同的数 i<j<k，且它们两两互质（任意两个的最大公约数都是 $1$）的方案有多少种。

关键函数

gcd(a,b)：辗转相除法求最大公约数
- b==0 时返回 a
- 否则 gcd(b, a%b)
三重循环：i、j、k 从小到大枚举，三个 gcd 都为 $1$ 就 ans++

执行顺序（手算 `n=3`）

只有一组 $(1,2,3)$：

$gcd(1,2)=gcd(2,3)=gcd(1,3)=1$ → ans=1

n=2：凑不出三个数，三重循环根本不进去 → 输出 0

gcd(36,42)：$42\%36=6$，$36\%6=0$ → 返回 $6$

边界与易错点

n<3 时答案一定是 $0$
三个 gcd 条件缺一不可（删掉 gcd(i,k) 会多算）
如果把 gcd(b,a%b) 错写成 gcd(a,a%b)，可能死循环
n=8 时答案是 $25$

小题 1：判断题 16：（$1$ 分）当输入为 $2$ 时，程序并不会执行第 $16$ 行的判断语句。（）

A. 正确
B. 错误

答案与解法

$n=2$ 时 $i=1,j=2,k$ 最小 $3>n$，内层不执行。

易错点： 以为会进入 $k$ 循环。

答案：A（正确）

小题 2：判断题 17：将第 $16$ 行中的 `&& gcd(i,k)==1` 删去不会影响程序运行结果。（）

A. 正确
B. 错误

答案与解法

还需要 $i,k$ 互质，删了会多计数。

易错点： 以为 $i,j$ 互质就够。

答案：B（错误）

小题 3：判断题 18：（错题，请选择 B 获得分数）当输入的 $n \geq 3$ 的时候，程序总是输出一个正整数。（）

A. 正确
B. 错误

答案与解法

按卷面选 B（错误）。

易错点： 选 A。

答案：B（错误）

小题 4：单选题 19：将第 $7$ 行的 `gcd(b, a%b)` 改为 `gcd(a, a%b)` 后，程序可能出现的问题是（）。

A. 输出的答案大于原答案。
B. 输出的答案小于原答案。
C. 程序有可能陷入死循环。
D. 可能发生整型溢出问题。

答案与解法

错误写法可能 $\gcd$ 不变小，答案偏大。

易错点： 以为只是答案变大。

答案：B（输出的答案小于原答案。）

小题 5：单选题 20：当输入为 $8$ 的时候，输出为（）。

A. $37$
B. $42$
C. $35$
D. $25$

答案与解法

枚举得 $25$ 组。

易错点： 漏数或多数。

答案：D（$25$）

小题 6：单选题 21：调用 $\gcd(36, 42)$ 会返回（）。

A. $6$
B. $252$
C. $3$
D. $2$

答案与解法

$\gcd(36,42)=6$。

易错点： 算成 $252$（乘积）。

答案：A（$6$）

真题 · 2024年阅读程序第1题

完整题目（含程序与小题）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

第 1 题

#include <iostream>
using namespace std;bool isPrime(int n) {if (n <= 1) {return false;}for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}int countPrimes(int n) {int count = 0;for (int i = 2; i <= n; i++) {if (isPrime(i)) {count++;}}return count;
}int sumPrimes(int n) {int sum = 0;for (int i = 2; i <= n; i++) {if (isPrime(i)) {sum += i;}}return sum;
}int main() {int x;cin >> x;cout << countPrimes(x) << " " << sumPrimes(x) << endl;return 0;
}

判断题

当输入为 $10$ 时，程序的第一个输出为 $4$ ，第二个输出为 $17$。（）
若将 isPrime(i) 函数中的条件改为 i<=n/2，输入 $20$ 时， countPrimes(20) 的输出将变为 $6$。（）
sumPrimes 函数计算的是从 $2$ 到 $n$ 之间的所有素数之和。

单选题

当输入为 $50$ 时，sumPrimes(50) 的输出为（）。
如果将 for (int i = 2; i * i <= n; i++) 改为 for (int i = 2; i <= n; i++)，输入 $10$ 时，程序的输出（）。

程序讲解

这程序在干什么

读入正整数 x，输出两个数：从 $2$ 到 x 有多少个素数，以及这些素数的总和。

关键函数

isPrime(n)：判断 n 是不是素数
- $n\le 1$ 不是素数
- 从 $2$ 试到 $i^2\le n$，能整除就不是
countPrimes(n)：数一数 $2\sim n$ 里几个素数
sumPrimes(n)：把 $2\sim n$ 的素数加起来

执行顺序（手算 `x=10`）

素数：$2,3,5,7$ → 共 $4$ 个，和 $=17$ → 输出 4 17

x=20：素数 $2,3,5,7,11,13,17,19$ → 共 $8$ 个（不是 $6$ 个！）

边界与易错点

$1$ 不是素数
试除只需到 $\sqrt{n}$（i*i<=n），改 i<=n 结果仍对但极慢
改成 i<=n/2 对 $20$ 仍能得到 $8$ 个素数，不会变成 $6$
如果把 i*i<=n 改成 i<=n，对 n=10 的 isPrime 判断会出错（比如 $9$ 会被误判），整体结果就错了

小题 1：判断题 1：当输入为 $10$ 时，程序的第一个输出为 $4$ ，第二个输出为 $17$。（）

A. 正确
B. 错误

答案与解法

$\le10$ 的素数 $2,3,5,7$：$4$ 个，和 $17$。

易错点： 把 $1$ 当素数。

答案：A（正确）

小题 2：判断题 2：若将 `isPrime(i)` 函数中的条件改为 `i<=n/2`，输入 $20$ 时， `countPrimes(20)` 的输出将变为 $6$。（）

A. 正确
B. 错误

答案与解法

$i\le n/2$ 对 $n=20$ 仍够判断，个数仍 $8$ 不是 $6$。

易错点： 以为范围缩小结果变。

答案：B（错误）

小题 3：判断题 3：`sumPrimes` 函数计算的是从 $2$ 到 $n$ 之间的所有素数之和。

A. 正确
B. 错误

答案与解法

循环从 $i=2$ 开始，描述正确。

易错点： 包含 $1$ 或 $0$。

答案：A（正确）

小题 4：单选题 1：当输入为 $50$ 时，`sumPrimes(50)` 的输出为（）。

A. 1060
B. 328
C. 381
D. 275

答案与解法

$2$ 到 $50$ 素数和 $=328$。

易错点： 漏素数。

答案：B（328）

小题 5：单选题 2：如果将 `for (int i = 2; i * i <= n; i++)` 改为 `for (int i = 2; i <= n; i++)`，输入 $10$ 时，程序的输出（）。

A. 将不能正确计算 $10$ 以内素数个数及其和
B. 仍然输出 $4$ 和 $17$
C. 输出 $3$ 和 $10$
D. 输出结果不变，但运行时间更短

答案与解法

$i\le n$ 时会把合数也判成素数（如 $4,6,8,9,10$），结果错。

易错点： 以为只是变慢。

答案：A（将不能正确计算 $10$ 以内素数个数及其和）

真题 · 2021年阅读程序第3题

完整题目（含程序与小题）

（3）

假设输入的 $x$ 是不超过 $1000$ 的自然数，完成下面的判断题和单选题：

判断题

若输入不为 $\texttt 1$，把第 13 行删去不会影响输出的结果。（）
（2 分）第 25 行的 f[i] / c[i * k]可能存在无法整除而向下取整的情况。（）
（2 分）在执行完 init() 后，f 数组不是单调递增的，但 g 数组是单调递增的。（）

单选题

init 函数的时间复杂度为（）。
在执行完 init() 后，$f[1], f[2], f[3] \dots f[100]$ 中有（）个等于 2。
（4 分）当输入为 $\texttt{1000}$ 时，输出为（）。

程序讲解

这程序在干什么

程序启动时先跑 init()，给每个数 $1\ldots10^5$ 预处理好两个值；再读入 x，输出 f[x] 和 g[x] 两个整数。

数组含义（记结论即可）

a[i]：标记 i 是否为合数
b[]：筛出的质数表
f[i]：i 的约数个数（例如 $12$ 有 $6$ 个约数）
g[i]：i 的约数之和（例如 $12$ 的约数和是 $1+2+3+4+6+12=28$）
c[i], d[i]：辅助递推用的中间量

`init` 大致流程

类似欧拉筛/线性筛的变形：从 i=2 枚举，遇到未标记的质数就更新 f[i]=2, g[i]=i+1；再用已有质数去推合数 i*k 的 f、g 值。若 i 能被质数 k 整除就 break（保证每个合数只被最小质因子推一次）。

`main`

init() 后读 x，输出 f[x] 和 g[x]。
例如 x=1000：$1000=2^3\times5^3$，约数个数 $(3+1)(3+1)=16$，约数和可递推得 $2340$ → 输出 16 2340。

手算 f[1..100] 中等于 $2$ 的：恰是 $100$ 以内质数，共 $25$ 个。

边界与易错点

init 与输入 x 无关，删 main 里「x==1 特殊处理」那行（若存在）对 x≠1 无影响
递推式保证 f[i]/c[i*k] 能整除，不是随便除
f、g 数组都不会整体单调递增

小题 1：判断题 28：若输入不为 $\texttt 1$，把第 13 行删去不会影响输出的结果。（）

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 2：判断题 29：（2 分）第 25 行的 `f[i] / c[i * k]`可能存在无法整除而向下取整的情况。（）

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 3：判断题 30：（2 分）在执行完 `init()` 后，`f` 数组不是单调递增的，但 `g` 数组是单调递增的。（）

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 4：单选题 31：`init` 函数的时间复杂度为（）。

A. $O(n)$
B. $O(n \log n)$
C. $O(n\sqrt{n})$
D. $O(n^2)$

答案与解法

答案：A（$O(n)$）

小题 5：单选题 32：在执行完 `init()` 后，$f[1], f[2], f[3] \dots f[100]$ 中有（）个等于 2。

A. 23
B. 24
C. 25
D. 26

答案与解法

答案：C（25）

小题 6：单选题 33：（4 分）当输入为 $\texttt{1000}$ 时，输出为（）。

A. 15 1340
B. 15 2340
C. 16 2340
D. 16 1340

答案与解法

答案：C（16 2340）

考点簇3：递归与分治

这类题在考什么

递归/分治/DFS：找出口、每层干什么、调用次数、深度。改递归参数或边界时结果怎么变。

这类题总陷阱

递归出口漏看
调用次数和结果搞混

本章知识点总述

递归三要素：出口、递推关系、调用顺序。

手算：画调用树，每层参数和返回值写清楚。

分治：大问题拆成相同结构的小问题，如归并排序、汉诺塔。

真题 · 2024年阅读程序第3题

完整题目（含程序与小题）

第 3 题

#include <iostream>
#include <cmath>
using namespace std;int customFunction(int a, int b) {if (b == 0) {return a;}return a + customFunction(a, b-1);
}int main() {int x, y;cin >> x >> y;int result = customFunction(x, y);cout << pow(result, 2) << endl;return 0;
}

判断题

当输入为 2 3 时，customFunction(2, 3) 的返回值为 $64$。（）
（本题为错题，请同时选择【正确】和【错误】获得对应分数）当 $b$ 为负数时，customFunction(a, b) 会陷入无限递归。（）
（本题为错题，请同时选择【正确】和【错误】获得对应分数）当 $b$ 的值越大，程序的运行时间越长。（）

单选题

当输入为 5 4 时，customFunction(5, 4) 的返回值为（）。
如果输入 x=3 和 y=3，则程序的最终输出为（）。
（4 分）若将 customFunction 函数改为 return a + customFunction(a-1, b-1);，并输入 3 3，则程序的最终输出为（）。

程序讲解

这程序在干什么

读入两个整数 x、y，先递归算一个结果，再把这个结果平方后输出。

关键函数

customFunction(a, b)：
- b==0 时直接返回 a
- 否则返回 a + customFunction(a, b-1)
含义：从 b=0 到 b，一共加了 $(b+1)$ 次 a，所以返回值 $= a\times(b+1)$
main：算完后 pow(result, 2) 输出平方

执行顺序（手算 `2 3`）

customFunction(2,3) = $2+$ f(2,2) = $2+2+$ f(2,1) = $2+2+2+$ f(2,0) = $2+2+2+2=8$
注意：返回值是 $8$，不是 $64$（$64$ 是平方后的数）
输出 pow(8,2)=64

输入 5 4：customFunction(5,4) = $5\times5=25$（加了 $5$ 次）

输入 3 3：customFunction(3,3) = $3\times4=12$，平方 $=144$

边界与易错点

b 为负数时会一直减下去，无限递归（栈溢出）
b 越大，递归层数越多，运行越慢
若改成 a + customFunction(a-1, b-1)，含义完全变了（变成别的递推，不是简单乘法）

小题 1：判断题 1：当输入为 `2 3` 时，`customFunction(2, 3)` 的返回值为 $64$。（）

A. 正确
B. 错误

答案与解法

`customFunction(2,3)=2+2+2+2=8$，不是 $64$。

易错点： 当成 $a^b$。

答案：B（错误）

小题 2：判断题 2：（本题为错题，请同时选择【正确】和【错误】获得对应分数）当 $b$ 为负数时，`customFunction(a, b)` 会陷入无限递归。（）

A. 正确
B. 错误

答案与解法

按说明 AB 都选。

易错点： 只选一个。

答案：A、B

小题 3：判断题 3：（本题为错题，请同时选择【正确】和【错误】获得对应分数）当 $b$ 的值越大，程序的运行时间越长。（）

A. 正确
B. 错误

答案与解法

AB 都选。

易错点： 只选一个。

答案：A、B

小题 4：单选题 1：当输入为 `5 4` 时，`customFunction(5, 4)` 的返回值为（）。

A. 5
B. 25
C. 250
D. 625

答案与解法

$5+5+5+5+5=25$。

易错点： 算成 $5^4$。

答案：B（25）

小题 5：单选题 2：如果输入 `x=3` 和 `y=3`，则程序的最终输出为（）。

A. 27
B. 81
C. 144
D. 256

答案与解法

`customFunction(3,3)=12$？应为 $3\times4=12$，$12^2=144$。

易错点： 忘记平方。

答案：C（144）

小题 6：单选题 3：（4 分）若将 `customFunction` 函数改为 `return a + customFunction(a-1, b-1);`，并输入 `3 3`，则程序的最终输出为（）。

A. 9
B. 16
C. 25
D. 36

答案与解法

新函数等价于二项式相关求和，结果为 $6$，输出 $6^2=36$。

易错点： 仍用旧式子。

答案：D（36）

真题 · 2020年阅读程序第3题

完整题目（含程序与小题）

#include <algorithm>
#include <iostream>
using namespace std;                     int n;                                   
int d[50][2];                            
int ans;                                 void dfs(int n, int sum) {               if (n == 1) {                            ans = max(sum, ans);           return;                                   }                                        for (int i = 1; i < n; ++i) {            int a = d[i - 1][0], b = d[i - 1][1];  int x = d[i][0], y = d[i][1];            d[i - 1][0] = a + x;                     d[i - 1][1] = b + y;                     for (int j = i; j < n - 1; ++j)            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];int s = a + x + abs(b - y);              dfs(n - 1, sum + s);                    for (int j = n - 1; j > i; --j)          d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];d[i - 1][0] = a, d[i - 1][1] = b;        d[i][0] = x, d[i][1] = y;                }                                        
}                                        int main() {                             cin >> n;                                for (int i = 0; i < n; ++i)              cin >> d[i][0];for (int i = 0; i < n;++i)cin >> d[i][1];ans = 0;dfs(n, 0);cout << ans << endl;return 0;
}

假设输入的 $n$ 是不超过 $50$ 的正整数，d[i][0]、d[i][1] 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：

判断题
1. 若输入 $n$ 为 $0$，此程序可能会死循环或发生运行错误。（）
2. 若输入 $n$ 为 $20$，接下来的输入全为 $0$，则输出为 $0$。（）
3. 输出的数一定不小于输入的 d[i][0] 和 d[i][1] 的任意一个。（）
单选题
1. 若输入的 $n$ 为 $20$，接下来的输入是 $20$ 个 $9$ 和 $20$ 个 $0$，则输出为（）。
2. 若输入的 $n$ 为 $30$，接下来的输入是 $30$ 个 $0$ 和 $30$ 个 $5$，则输出为（）。
3. （4 分）若输入的 $n$ 为 $15$，接下来的输入是 $15$ 到 $1$，以及 $15$ 到 $1$，则输出为（）。

程序讲解

这程序在干什么

读入 $n$ 对数 d[i][0], d[i][1]，通过「每次选一对相邻元素合并」的方式，把所有数合成一个，求合并过程能得到的最大总分 ans。

关键变量

d[i][0], d[i][1]：第 i 组的两个数
dfs(n, sum)：当前还剩 n 组，已得分为 sum
ans：全局最大值

DFS 过程（`n > 1` 时）

对每个 i = 1..n-1，尝试合并第 i-1 组和第 i 组：

记下合并前的 a,b 和 x,y
合并到左边：d[i-1][0]=a+x，d[i-1][1]=b+y
把 d[i..n-1] 整体左移一格（删掉第 i 组）
本轮得分 s = a+x + |b-y|，递归 dfs(n-1, sum+s)
回溯：恢复数组

出口：n==1 时 ans = max(ans, sum)。

手算（$n=2$，(9,0) 和 (9,0)$）：合并得分 $9+9+|0-0|=18$，ans=18`。

边界与易错点

必须 DFS + 回溯，因为合并顺序影响总分
n=0 时循环不执行，但题目保证 $n$ 为正
全 $0$ 输入时任何合并得分都是 $0$，ans=0
输出不一定大于每个输入数（若 b 很大且相减抵消）

小题 1：小题 1

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 4：小题 4

A. 1890
B. 1881
C. 1908
D. 1917

答案与解法

答案：B（1881）

小题 5：小题 5

A. 2000
B. 2010
C. 2030
D. 2020

答案与解法

答案：C（2030）

小题 6：小题 6

A. 2440
B. 2220
C. 2240
D. 2420

答案与解法

答案：C（2240）

真题 · 2019年阅读程序第3题

完整题目（含程序与小题）

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {if (l > r)return 0;int min = maxn, mink;for (int i = l; i <= r; ++i) {if (min > a[i]) {min = a[i];mink = i;}}int lres = f(l, mink - 1, depth + 1);int rres = f(mink + 1, r, depth + 1);return lres + rres + depth * b[mink];
}
int main() {cin >> n;for (int i = 0; i < n; ++i)cin >> a[i];for (int i = 0; i < n; ++i)cin >> b[i];cout << f(0, n - 1, 1) << endl;return 0;
}

判断题

如果 $a$ 数组有重复的数字，则程序运行时会发生错误。（）
如果 $b$ 数组全为 $0$，则输出为 $0$。（）

选择题

当 $n=100$ 时，最坏情况下，与第 $12$ 行的比较运算执行的次数最接近的是：（）。
当 $n=100$ 时，最好情况下，与第 $12$ 行的比较运算执行的次数最接近的是：（）。
当 $n=10$ 时，若 $b$ 数组满足，对任意 $0\leq i<n$，都有 b[i] = i + 1，那么输出最大为（）。
（4分）当 $n=100$ 时，若 $b$ 数组满足，对任意 $0 \leq i < n$，都有 b[i]=1，那么输出最小为（）。

程序讲解

这程序在干什么

读入两个数组 a[]、b[]，用递归在 a 的某个区间里反复找最小值，把「当前递归层数 × 该最小值位置的 b 值」累加起来输出。

关键函数 `f(l, r, depth)`

出口：l > r 时返回 $0$
在 a[l..r] 里找最小值 min 及其下标 mink（若有多个相同最小，保留更靠左的那个）
递归左半段 f(l, mink-1, depth+1)
递归右半段 f(mink+1, r, depth+1)
返回：左结果 + 右结果 + depth * b[mink]

`main` 流程

读 n，读 a[0..n-1] 和 b[0..n-1]，输出 f(0, n-1, 1)。

手算（$n=3$，a=[3,1,2]，b=[5,10,1]）：

整段最小在 mink=1，贡献 $1\times10=10$
左段 [3] 贡献 $2\times5=10$；右段 [2] 贡献 $2\times1=2$
总计 $22$

边界与易错点

a 有重复最小值不会出错，只是 mink 取最左
b 全 $0$ 则输出必为 $0$
每层都要扫一遍区间找最小，区间很碎时比较次数接近 $O(n^2)$

小题 1：小题 1

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 3：小题 3

A. 5000
B. 600
C. 6
D. 100

答案与解法

答案：A（5000）

小题 4：小题 4

A. 100
B. 6
C. 5000
D. 600

答案与解法

答案：D（600）

小题 5：小题 5

A. 386
B. 383
C. 384
D. 385

答案与解法

答案：D（385）

小题 6：小题 6

A. 582
B. 580
C. 579
D. 581

答案与解法

答案：B（580）

考点簇4：位运算

这类题在考什么

位运算、无符号/有符号、移位溢出。手算时用二进制展开更稳。

这类题总陷阱

char 移位溢出
有无符号类型差异

本章知识点总述

手算位运算：先把数写成二进制，按位做 & | ^，再转回十进制。

移位：x << 1 等于 $2x$；注意 char 可能溢出变负数。

真题 · 2022年阅读程序第1题

完整题目（含程序与小题）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

(1)

01 #include <iostream>
02
03 using namespace std；
04
05 int main()
06 {
07     unsigned short x, y；
08     cin >> x >> y；
09     x = (x | x << 2)& 0x33；
10     x = (x | x << 1)& 0x55；
11     y = (y | y << 2)& 0x33；
12     y = (y | y << 1)& 0x55；
13     unsigned short z = x | y << 1；
14     cout << z << endl；
15     return 0；
16 }

假设输入的 $x,y$ 均是不超过 $15$ 的自然数，完成下面的判断题和单选题：

判断题

删去第 $7$ 行与第 $13$ 行的 unsigned，程序行为不变。
将第 $7$ 行与第 $13$ 行的 short 均改为 char，程序行为不变。
程序总是输出一个整数“0”。
当输入为 2 2 时，输出为 10。
当输入为 2 2 时，输出为 59。

单选题

当输入为 13 8 时，输出为（）。

程序讲解

这程序在干什么

读入两个不超过 $15$ 的自然数 x、y，对它们做几步位运算「把二进制位拉开」，再把两份结果合并成一个数 z 输出。

对 `x`（`y` 同理）的两步变换

设 x 只有低 $4$ 位有效（输入 $le 15$）：

第一步 x = (x | x<<2) & 0x33
0x33 二进制是 00110011，保留第 $0,1,4,5$ 位。左移 $2$ 再或，相当于把原来的 bit1 挪到 bit3，bit0 挪到 bit2。

第二步 x = (x | x<<1) & 0x55
0x55 是 01010101，只保留偶数位。再把相邻位分散到更开的间隔上。

合并

z = x | (y << 1)：把处理后的 y 左移一位，和 x 按位或，相当于把两组「稀疏位」交错拼在一起。

手算 x=2, y=2（二进制 0010）：
经两步后 x、y 都变成低位稀疏形式，合并后 z 的二进制形如 ...1010（十进制 $10$），不是 $0$ 或 $59$。

手算 x=13, y=8：手算位展开后合并，得 z=209。

边界与易错点

用 unsigned short 可避免中间移位变负；改 char 可能溢出，行为可能变
输入 $0$ 时输出一般也是 $0$，不是「总是 $0$」
掩码 0x33、0x55 是核心，手算时建议写出 $4$ 位二进制

小题 1：小题 1

A. 正确
B. 错误

答案与解法

输入很小，最高位不会变符号位，有无符号结果相同。

易错点： 以为有无符号都一样。

答案：A（正确）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

char 只有 $8$ 位，| x<<2 等操作会溢出，结果和 short 不同。

易错点： 以为 $15$ 以内 char 够用就没事，忽略了中间左移可能溢出。

答案：B（错误）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

程序把 $x,y$ 的位"摊开"到不同位置再合并，输入非零时输出非零。

易错点： 看到掩码 $0x33,0x55$ 以为全清零。

答案：B（错误）

小题 4：小题 4

A. 正确
B. 错误

答案与解法

逐行模拟得 $z=12$，既不是 $10$ 也不是 $59$，故"输出为 $10$"不成立。

易错点： 直接猜数字。

答案：B（错误）

小题 5：小题 5

A. 正确
B. 错误

答案与解法

同上，实际输出为 $12$，"输出为 $59$"也不成立。

易错点： 同上

答案：B（错误）

小题 6：小题 6

A. $0$
B. $209$
C. $197$
D. $226$

答案与解法

分别处理 $x=13,y=8$，最后 $z=x|(y<<1)$，得 $209$。

易错点： 忘记 $y$ 还要左移一位再和 $x$ 合并。

答案：B（$209$）

真题 · 2021年阅读程序第1题

完整题目（含程序与小题）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √ ，错误填 × ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

(1)

判断题

输入的 $n$ 等于 $1001$ 时，程序不会发生下标越界。（）
输入的 $a[i]$ 必须全为正整数，否则程序将陷入死循环。（）
当输入为 5 2 11 9 16 10 时，输出为 3 4 3 17 5。（）
当输入为 1 511998 时，输出为 18。（）
将源代码中 g 函数的定义（$14\sim 17$ 行）移到 main 函数的后面，程序可以正常编译运行。（）

单选题

当输入为 2 -65536 2147483647 时，输出为（）。

A. 65532 33
B. 65552 32
C. 65535 34
D. 65554 33

程序讲解

这程序在干什么

读入 $n$ 个整数，对每个数算两个位运算相关的量并相加输出。

两个核心函数

f(x)：统计 x 的二进制里有几个 $1$（也叫 popcount）
循环 for(; x; x &= x-1) ret++：每次 x &= x-1 会消掉最右边的一个 $1$
g(x)：返回 lowbit，即 x & -x，保留二进制最右边那个 $1$ 以及它后面的 $0$
例如 g(12)=4（1100 → 0100），g(10)=2（1010 → 0010）

`main` 流程

读 n，读 a[0..n-1]，对每个 a[i] 输出 f(a[i]) + g(a[i])，空格分隔。

手算 a[0]=2（二进制 10）：f(2)=1，g(2)=2，输出 3。
a[1]=11（1011）：f=3，g=1，输出 4。

手算单个数 511998：二进制有 $16$ 个 $1$，lowbit 是 $2$ → $16+2=18$。

边界与易错点

a 数组只有 $1000$ 个，n=1001 会越界
负数也能算：计算机用补码存数，f 数的是补码里 $1$ 的个数，不会死循环
g 用在 main 前，若把 g 的定义移到 main 后面且没有提前声明，C++ 编译不过

小题 1：判断题 16：输入的 $n$ 等于 $1001$ 时，程序不会发生下标越界。（）

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 2：判断题 17：输入的 $a[i]$ 必须全为正整数，否则程序将陷入死循环。（）

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 3：判断题 18：当输入为 `5 2 11 9 16 10` 时，输出为 `3 4 3 17 5`。（）

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 4：判断题 19：当输入为 `1 511998` 时，输出为 `18`。（）

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 5：判断题 20：将源代码中 `g` 函数的定义（$14\sim 17$ 行）移到 main 函数的后面，程序可以正常编译运行。（）

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 6：单选题 21：当输入为 `2 -65536 2147483647` 时，输出为（）。

A. 65532 33
B. 65552 32
C. 65535 34
D. 65554 33

答案与解法

答案：B（65552 32）

考点簇5：动态规划

这类题在考什么

DP 填小表：先想状态含义，再手算 $n=2,3$ 的 dp 值。别硬背公式，跟着转移式走。初二可先跳过细节，只看每题 程序讲解 里的概要即可。

这类题总陷阱

没手算小表就猜
转移式改一个字没重算

本章知识点总述

DP 步骤：

定义 dp[i] 或 dp[i][j] 含义
写转移式
填表：先初始化，再按 $i$ 从小到大算
答案在 dp[n] 或表中某个位置

手算 $n=2,3$ 验证转移式。

真题 · 2025年阅读程序第2题

完整题目（含程序与小题）

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int n, k;
int a[200007];
int ans[200007];
int main() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}std::sort(a + 1, a + n + 1);n = std::unique(a + 1, a + n + 1) - a - 1;for (int i = 1, j = 0; i <= n; ++i) {for (; j < i && a[i] - a[j + 1] > k; ++j) ;ans[i] = ans[j] + 1;}printf("%d\n", ans[n]);return 0;
}

判断题

当输入为 3 1 3 2 1 时，输出结果为 $2$。（）
假设输入的 $n$ 为正整数，输出的答案一定小于等于 $n$，大于等于 $1$。（）
将第 14 行的 n = std::unique(a + 1, a + n + 1) - a - 1; 删去后，有可能出现与原本代码不同的输出结果。（）

单选题

假设输入的 $a$ 数组和 $k$ 均为正整数，执行第 18 行代码时，一定满足的条件不包括（）。
A. $j < i$
B. $a[i] - a[j] > k$
C. $j < n$
D. $a[j] < a[i]$
当输入的 $n=100$、$k=2$、$a = \{1, 2, \dots, 100\}$ 时，输出为（）。
A. $34$
B. $100$
C. $50$
D. $33$
假设输入的 $a$ 数组和 $k$ 均为正整数，但 $a$ 数组不一定有序，则若误删去第 13 行的 std::sort(a + 1, a + n + 1);，程序有可能出现的问题有（）。
A. 输出的答案比原本答案更大
B. 输出的答案比原本答案更小
C. 出现死循环行为
D. 以上均可能发生

程序讲解

这程序在干什么

读入 n、k 和 n 个整数，先排序去重，再求：最多能挑多少个数以构成序列，要求相邻两个数的差不超过 k。

关键步骤

排序 + 去重：让数组从小到大、没有重复
ans[i]：以 a[i] 结尾的最长链长度
j 指针：不断右移，保证 a[i]-a[j+1] <= k（太远的就丢掉）
转移：ans[i] = ans[j] + 1

DP 部分（你还没系统学过，了解即可）
可以看成在一维表里填「以当前数结尾的最长合法链有多长」。j 像滑动窗口左边界，只从「离得不太远」的位置接过来。最后 ans[n] 是全局最优。

执行顺序（手算 `3 1 3 2 1`）

排序去重后 a=[1,2,3]，k=1：

ans[1]=1
ans[2]=2（$2$ 接在 $1$ 后面）
ans[3]=2（$3$ 和 $1$ 差 $2>1$，只能单独接在 $2$ 后面）

输出 2

边界与易错点

必须先排序，否则 j 指针逻辑全乱
答案 $le n$，且至少为 $1$（只要 n>0）
去重很重要，重复数会影响窗口判断

小题 1：判断题 22：当输入为 `3 1 3 2 1` 时，输出结果为 $2$。（）

A. 正确
B. 错误

答案与解法

去重后 $\{1,2,3\}$，$k=1$ 最长链 $2$。

易错点： 忘去重。

答案：A（正确）

小题 2：判断题 23：假设输入的 $n$ 为正整数，输出的答案一定小于等于 $n$，大于等于 $1$。（）

A. 正确
B. 错误

答案与解法

至少每个元素自己成链，$\ge1$，且 $\le n$。

易错点： 以为可能 $0$。

答案：A（正确）

小题 3：判断题 24：将第 14 行的 `n = std::unique(a + 1, a + n + 1) - a - 1;` 删去后，有可能出现与原本代码不同的输出结果。（）

A. 正确
B. 错误

答案与解法

按卷面标准答案，该判断为错误（删去后在本题设定下不会改变输出）。

易错点： 直觉认为重复元素一定改变 DP。

答案：B（错误）

小题 4：单选题 25：假设输入的 $a$ 数组和 $k$ 均为正整数，执行第 18 行代码时，一定满足的条件不包括（）。

A. $j < i$
B. $a[i] - a[j] > k$
C. $j < n$
D. $a[j] < a[i]$

答案与解法

退出循环时通常是 $a[i]-a[j+1]\le k$ 或 $j$ 已到边界，不一定 $a[i]-a[j]>k$。

易错点： 以为 $a[i]-a[j]>k$ 一定成立。

答案：B（$a[i] - a[j] > k$）

小题 5：单选题 26：当输入的 $n=100$、$k=2$、$a = \{1, 2, \dots, 100\}$ 时，输出为（）。

A. $34$
B. $100$
C. $50$
D. $33$

答案与解法

最优链每步最多跳 $3$（差 $\le2$），长度 $34$。

易错点： 以为链长 $50$。

答案：A（$34$）

小题 6：单选题 27：假设输入的 $a$ 数组和 $k$ 均为正整数，但 $a$ 数组不一定有序，则若误删去第 13 行的 `std::sort(a + 1, a + n + 1);`，程序有可能出现的问题有（）。

A. 输出的答案比原本答案更大
B. 输出的答案比原本答案更小
C. 出现死循环行为
D. 以上均可能发生

答案与解法

无序时双指针逻辑错，答案只会偏小或错，官方选可能更小。

易错点： 选"均可能"。

答案：B（输出的答案比原本答案更小）

真题 · 2025年阅读程序第3题

完整题目（含程序与小题）

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int f[5007][5007];
int a[5007], b[5007];
int n;
int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}for (int i = 1; i <= n; ++i) {scanf("%d", &b[i]);}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));if (a[i] == b[j]) {f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);}}}printf("%d\n", f[n][n]);return 0;
}

判断题

当输入 4 1 2 3 4 1 3 2 2 时，输出为 2。（）
当程序运行完毕后，对于所有的 $1 \leq i, j \leq n$，都一定有 $f[i][j] \leq f[n][n]$。（）
将第 18 行的 f[i][j] = std::max(f[i][j], std::max(f[i-1][j], f[i][j-1])); 删去后，并不影响程序运行结果。（）

单选题

输出的答案满足的性质有（）。
A. 小于等于 $n$
B. 大于等于 $0$
C. 不一定大于等于 $1$
D. 以上均是
如果在 16 行的循环前加上以下两行：

std::sort(a+1, a+n+1);  
std::sort(b+1, b+n+1);

则答案会（）。
A. 变大或不变
B. 变小或不变
C. 一定变大
D. 不变

（本题在原卷中被删除）如果输入的 $a = \{1, 2, \dots, n\}$，而且 $b$ 数组中数字均为 $1 \sim n$ 中的正整数，则上述代码等价于下面哪个问题：（）。
A. 求 $b$ 数组去重后的长度
B. 求 $b$ 数组的最长上升子序列
C. 求 $b$ 数组的长度
D. 求 $b$ 数组的最大值

程序讲解

这程序在干什么

读入长度 n 和两个数组 a、b，求它们的最长公共子序列（LCS）长度——按原顺序、不要求连续地同时出现在两个数组里的最长数字序列。

关键变量

f[i][j]：a 前 $i$ 个与 b 前 $j$ 个的 LCS 长度
每格先继承 max(f[i-1][j], f[i][j-1])（跳过一边）
若 a[i]==b[j]，还可以从 f[i-1][j-1]+1 更新

DP 部分（你还没系统学过，了解即可）
二维表按行填：每个格子记录「两段前缀能对上的最长长度」。字符/数字相同时从左上角 $+1$，否则从左边或上边取较大。答案在 f[n][n]。

执行顺序（概念小例子）

a=[1,2,3,4]，b=[1,3,2,2]：能对上 $1,3,2$ 或 $1,2$ 等，最长长度 $=2$。

边界与易错点

答案 $ge 0$，$le n$，可能为 $0$（完全对不上）
第 $18$ 行的 max(f[i-1][j], f[i][j-1]) 不能删，否则不相等时格子可能是 $0$
排序 a、b 一般会变大或不变 LCS，因为顺序被打乱了

小题 1：判断题 28：当输入 `4 1 2 3 4 1 3 2 2` 时，输出为 2。（）

A. 正确
B. 错误

答案与解法

LCS 长度 $2$（如 $1,2$ 或 $1,3$）。

易错点： 手算错序列。

答案：A（正确）

小题 2：判断题 29：当程序运行完毕后，对于所有的 $1 \leq i, j \leq n$，都一定有 $f[i][j] \leq f[n][n]$。（）

A. 正确
B. 错误

答案与解法

$f[n][n]$ 是全局最优，任意子问题不会超过它。

易错点： 以为中间可能更大。

答案：A（正确）

小题 3：判断题 30：将第 18 行的 `f[i][j] = std::max(f[i][j], std::max(f[i-1][j], f[i][j-1]));` 删去后，并不影响程序运行结果。（）

A. 正确
B. 错误

答案与解法

不匹配时也要从上方/左方继承，删了会变小。

易错点： 以为匹配分支够。

答案：B（错误）

小题 4：单选题 31：输出的答案满足的性质有（）。

A. 小于等于 $n$
B. 大于等于 $0$
C. 不一定大于等于 $1$
D. 以上均是

答案与解法

LCS $\in[0,n]$，可能为 $0$；A/B/C 都对。

易错点： 以为一定 $\ge1$。

答案：D（以上均是）

小题 5：单选题 32：如果在 16 行的循环前加上以下两行：

A. 变大或不变
B. 变小或不变
C. 一定变大
D. 不变

答案与解法

排序后 LCS 可能变长（变成求公共元素个数类），变大或不变。

易错点： 以为不变。

答案：A（变大或不变）

小题 6：单选题 33：（本题在原卷中被删除）如果输入的 $a = \{1, 2, \dots, n\}$，而且 $b$ 数组中数字均为 $1 \sim n$ 中的正整数，则上述代码等价于下面哪个问题：（）。

A. 求 $b$ 数组去重后的长度
B. 求 $b$ 数组的最长上升子序列
C. 求 $b$ 数组的长度
D. 求 $b$ 数组的最大值

答案与解法

$a$ 递增时 LCS 等价于 $b$ 的最长上升子序列。

易错点： 当成去重。

答案：B（求 $b$ 数组的最长上升子序列）

真题 · 2024年阅读程序第2题

完整题目（含程序与小题）

第 2 题

#include <iostream>
#include <vector>
using namespace std;int compute(vector<int>& cost) {int n = cost.size();vector<int> dp(n+1, 0);dp[1] = cost[0];for (int i = 2; i <= n; i++) {dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1];}return min(dp[n], dp[n-1]);
}int main() {int n;cin >> n;vector<int> cost(n);for (int i = 0; i < n; i++) {cin >> cost[i];}cout << compute(cost) << endl;return 0;
}

判断题

当输入的 cost 数组为 $\{10, 15, 20\}$ 时，程序的输出为 $15$。（）
如果将 dp[i-1] 改为 dp[i-3]，程序可能会产生编译错误。（）
（2 分）程序总是输出 cost 数组中最小的元素。（）

单选题

当输入的 cost 数组为 $\{1, 100, 1, 1, 1, 100, 1, 1, 100, 1\}$ 时，程序的输出为（）。
（4 分）如果输入的 cost 数组为 $\{10, 15, 30, 5, 5, 10, 20\}$，程序的输出为（）。
若将代码中的 min(dp[i-1], dp[i-2]) + cost[i-1] 修改为 dp[i-1] + cost[i-2]，输入 cost 数组为 $\{5, 10, 15\}$ 时，程序的输出为（）。

程序讲解

这程序在干什么

有一串台阶，站在第 $0$ 级，每步可爬 $1$ 或 $2$ 级，踏上第 $i$ 级要付 cost[i-1]。求爬到顶（第 $n$ 级或 $n-1$ 级都行）的最少总花费。

关键变量

dp[i]：爬到第 $i$ 级的最小花费（dp[0]=0）
dp[1]=cost[0]：第一步踩第 $1$ 级要花第一格的钱
转移：dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]

DP 部分（你还没系统学过，了解即可）
想象填一张一维表：每个位置记录「到这里的最低票价」。当前台阶只能从前面一格或两格跳过来，所以取那两个里更便宜的，再加上本级花费。
最后比较 dp[n] 和 dp[n-1]，因为到顶可以停在前一级或前两级。

执行顺序（手算 `cost={10,15,20}`）

dp[1]=10
dp[2]=min(10,0)+15=15（从第 $0$ 级一步跳两级，只付 $15$）
dp[3]=min(15,10)+20=30
答案 min(30,15)=15

边界与易错点

dp[0]=0 很关键，表示起点免费
答案不是 dp[n] alone，要 min(dp[n], dp[n-1])
输出不一定是 cost 里最小的那个数

小题 1：判断题 1：当输入的 `cost` 数组为 $\{10, 15, 20\}$ 时，程序的输出为 $15$。（）

A. 正确
B. 错误

答案与解法

可从阶 $1$ 或 $2$ 免费出发，最优 $0\to2$ 花费 $15$。

易错点： 以为必须走完所有台阶。

答案：A（正确）

小题 2：判断题 2：如果将 `dp[i-1]` 改为 `dp[i-3]`，程序可能会产生编译错误。（）

A. 正确
B. 错误

答案与解法

vector 访问 $i-3$ 只是运行时可能越界，编译能通过。

易错点： 以为一定编译错。

答案：B（错误）

小题 3：判断题 3：（2 分）程序总是输出 `cost` 数组中最小的元素。（）

A. 正确
B. 错误

答案与解法

可能要累加多级，不一定等于最小单个 cost。

易错点： 以为只付最便宜那级。

答案：B（错误）

小题 4：单选题 1：当输入的 `cost` 数组为 $\{1, 100, 1, 1, 1, 100, 1, 1, 100, 1\}$ 时，程序的输出为（）。

A. 6
B. 7
C. 8
D. 9

答案与解法

跳着踩 $1$ 的台阶，总花费 $6$。

易错点： 贪心走便宜台阶。

答案：A（6）

小题 5：单选题 2：（4 分）如果输入的 `cost` 数组为 $\{10, 15, 30, 5, 5, 10, 20\}$，程序的输出为（）。

A. 25
B. 30
C. 35
D. 40

答案与解法

最优总花费 $30$。

易错点： 手算错路径。

答案：B（30）

小题 6：单选题 3：若将代码中的 `min(dp[i-1], dp[i-2]) + cost[i-1]` 修改为 `dp[i-1] + cost[i-2]`，输入 `cost` 数组为 $\{5, 10, 15\}$ 时，程序的输出为（）。

A. 10
B. 15
C. 20
D. 25

答案与解法

新规则下输出 $10$。

易错点： 仍按原 DP 算。

答案：A（10）

真题 · 2023年阅读程序第2题

完整题目（含程序与小题）

2.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int f(string x,string y){int m=x.size();int n=y.size();vector<vector<int>>v(m+1,vector<int>(n+1,0));for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(x[i-1]==y[j-1]){v[i][j]=v[i-1][j-1]+1;}else{v[i][j]=max(v[i-1][j],v[i][j-1]);}}}return v[m][n];
}
bool g(string x,string y){if(x.size() != y.size()){return false;}return f(x+x,y)==y.size();
}
int main(){string x,y;cin>>x>>y;cout<<g(x,y)<<endl;return 0;
}

判断题

f 函数的返回值小于等于 $\min\{n,m\}$。（）
f 函数的返回值等于两个输入字符串的最长公共子串的长度。（）
当输入两个完全相同的字符串时，g 函数的返回值总是 true。（）

单选题

将第19行中的 v[m][n] 替换为 v[n][m]，那么该程序（）。
当输入为 csp-j p-jcs 时，输出为（）。
当输入为 csppsc spsccp 时，输出为（）。

程序讲解

这程序在干什么

读入两个字符串 x、y，判断 y 能不能通过「旋转」变成 x（长度必须相同）。输出 1 表示能，0 表示不能。

关键函数

f(x,y)：用动态规划求两个字符串的最长公共子序列（LCS）长度
g(x,y)：先检查长度是否相等，再把 x 和自己拼成 x+x，看 f(x+x,y) 是否等于 y 的长度

DP 部分（你还没系统学过，了解即可）
f 里有一个二维表 v，按行列一格一格填「前面这段子串的最优答案」。字符相同时从左上角 $+1$，不同时从左边或上边取较大值。最后 v[m][n] 就是 LCS 长度。
做阅读题时只要知道：它是在比较两个字符串有多少字符能按顺序对上，不必背转移方程。

执行顺序（手算小例子）

输入 csppsc 和 spsccp：

长度都是 $6$，可以比
把 csppsc 拼两遍得 csppsccsppsc
f 发现 spsccp 能完整对进 x+x → 返回值 $=6$
$6==y.size()$ → g 返回 true，输出 1

输入 csp-j 和 p-jcs：

长度不同 → g 直接返回 false，输出 0（根本不会调用 f）

边界与易错点

LCS 是子序列（可以不连续），不是子串（必须连续）
f 的返回值 $le \min(m,n)$
如果把 v[m][n] 错写成 v[n][m]，当 $m\neq n$ 时会越界崩溃

小题 1：判断题 1：`f` 函数的返回值小于等于 $\min\{n,m\}$。（）

A. 正确
B. 错误

答案与解法

LCS 最长不超过较短串长度。

易错点： 与子串混淆。

答案：A（正确）

小题 2：判断题 2：`f` 函数的返回值等于两个输入字符串的最长公共子串的长度。（）

A. 正确
B. 错误

答案与解法

$f$ 是子序列，不要求连续；子串要求连续。

易错点： 名字像就以为一样。

答案：B（错误）

小题 3：判断题 3：当输入两个完全相同的字符串时，`g` 函数的返回值总是 `true`。（）

A. 正确
B. 错误

答案与解法

$f(x+x,y)=|y|$ 当且仅当 $y$ 是 $x$ 的旋转；相同串显然成立。

易错点： 忘了要长度相同（相同则满足）。

答案：A（正确）

小题 4：单选题 4：将第19行中的 `v[m][n]` 替换为 `v[n][m]`，那么该程序（）。

A. 行为不变
B. 只会改变输出
C. 一定非正常退出
D. 可能非正常退出

答案与解法

$m,n$ 是两串长度，若 $m\ne n$ 会访问越界，可能崩溃。

易错点： 以为只是值变。

答案：D（可能非正常退出）

小题 5：单选题 5：当输入为 `csp-j p-jcs` 时，输出为（）。

A. 0
B. 1
C. T
D. F

答案与解法

g 判断 $y$ 是否为 $x$ 的旋转（长度须相同，且 $f(x+x,y)=|y|$）。按洛谷卷面标准答案填写。

易错点： 肉眼看觉得像旋转，其实字符组成不同。

答案：B（1）

小题 6：单选题 6：当输入为 `csppsc spsccp` 时，输出为（）。

A. T
B. F
C. 0
D. 1

答案与解法

csppsc 旋转可得 spsccp，g 为 true，输出 1。

易错点： 手动画旋转。

答案：D（1）

真题 · 2022年阅读程序第2题

完整题目（含程序与小题）

（2）

1  #include <algorithm>
2  #include <iostream>
3  #include <limits>
4  
5  using namespace std;
6  
7  const int MAXN = 105;
8  const int MAXK = 105;
9  
10 int h[MAXN][MAXK];
11 
12 int f(int n, int m)
13 {
14     if (m == 1) return n;
15     if (n == 0) return 0;
16 
17     int ret = numeric_limits<int>::max();
18     for (int i = 1; i <= n; i++)
19         ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);
20     return ret;
21 }
22 
23 int g(int n, int m)
24 {
25     for (int i = 1;i <= n; i++)
26         h[i][1]= i;
27     for (int j = 1;j<= m; j++)
28         h[0][j]= 0;
29 
30     for (int i= 1; i <= n; i++){
31         for (int j= 2; j <= m; j++){
32             h[i][j] = numeric_limits<int>::max();
33             for (int k = 1;k <= i;k++)
34             h[i][j]= min(
35                 h[i][j],
36                 max(h[i - k][j],h[k - 1][j - 1]) +1);
37         }
38     }
39 
40     return h[n][m];
41 }
42 
43 int main()
44 {
45     int n,m;
46     cin >> n>> m;
47     cout << f(n, m) << endl << g(n, m)<< endl;
48     return 0;
49 }

假设输入的n、m均是不超过100 的正整数，完成下面的判断题和单选题：

判断题

当输入为 7 3 时，第 $19$ 行用来取最小值的 min 函数执行了 $449$ 次。
输出的两行整数总是相同的。
当 $m$ 为 $1$ 时，输出的第一行总为 $n$。

单选题

算法 $g(n,m)$ 最为准确的时间复杂度分析结果为（）。
当输入为 20 2 时，输出的第一行为（）。
（$4$ 分） 当输入 100 100 时，输出的第一行为（）。

程序讲解

这程序在干什么

读入 n（楼层数）和 m（鸡蛋数），求「最坏情况下最少要试几次」才能确定最高安全楼层。程序用两种方法算同一个答案并各输出一行。

两种做法

f(n,m)：纯递归，对每个分割点 i 试「先在 i 层摔」，取 max(左边子问题, 右边子问题)+1 的最小值
g(n,m)：动态规划填表 h[i][j]，含义与 f 相同，但记住已经算过的 h 值，避免重复递归

动态规划部分（考前知道即可）
这是用表格 h 记住已经算过的结果，叫动态规划。三层循环是在填「多少层、几个蛋」对应的最少次数；内层 k 枚举第一次在哪层摔。细节以后再学，阅读题只要知道：f 和 g 算的是同一个量，g 是加速版。

边界

m==1 时只能一层层试，答案就是 n
n==0 时答案 $0$
两行输出总是相同

小题 1：小题 1

A. 正确
B. 错误

答案与解法

实际模拟或估算，$449$ 次不对。

易错点： 把 $f$ 和 $g$ 的调用次数搞混。

答案：B（错误）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

$f$ 和 $g$ 是同一递推式，结果相同。

易错点： 以为递归一定更慢所以结果不同。

答案：A（正确）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

$f(n,1)$ 直接返回 $n$（代码第 $14$ 行）。

易错点： 忘记 $m=1$ 时只能一层一层试。

答案：A（正确）

小题 4：小题 4

A. $O(n^{3/2}m)$
B. $O(nm)$
C. $O(n^{2}m)$
D. $O(nm^{2})$

答案与解法

外层 $i$、中层 $j$、内层 $k$，共 $O(n^2 m)$。

易错点： 看成 $O(nm)$ 忘了内层还有 $k$。

答案：C（$O(n^{2}m)$）

小题 5：小题 5

A. $4$
B. $5$
C. $6$
D. $20$

答案与解法

$f(20,2)=6$（两层鸡蛋问题经典结果）。

易错点： 直接猜。

答案：C（$6$）

小题 6：小题 6

A. $6$
B. $7$
C. $8$
D. $9$

答案与解法

该 DP 在 $n=m=100$ 时结果为 $7$。

易错点： 以为要手算 $100$ 层。

答案：B（$7$）

考点簇6：数学迭代/开方/精度

这类题在考什么

海伦公式、开方、牛顿迭代、因子平方和等数学计算。注意浮点精度、完全平方判断。

这类题总陷阱

浮点和完全平方判断混
迭代次数和精确值搞混

本章知识点总述

海伦公式（已知三边 $a,b,c$，面积）：

\[p = \frac{a+b+c}{2},\quad S = \sqrt{p(p-a)(p-b)(p-c)} \]

牛顿迭代求平方根：$x_{k+1} = \frac{x_k + n/x_k}{2}$

完全平方：$\sqrt{n}$ 是整数当且仅当 $n = k^2$。

真题 · 2023年阅读程序第1题

完整题目（含程序与小题）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

1.

#include<iostream>
#include<cmath>
using namespace std;double f(double a,double b,double c){double s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c));
}
int main(){cout.flags(ios::fixed);cout.precision(4);int a,b,c;cin>>a>>b>>c;cout<<f(a,b,c)<<endl;return 0;
}

假设输入的所有数都为不超过 $1000$ 的正整数，完成下面的判断题和单选题：

判断题

（2分）当输入为 2 2 2 时，输出为1.7321（）
（2分）将第7行中的 (s-b)*(s-c) 改为 (s-c)*(s-b) 不会影响程序运行的结果（）
（2分）程序总是输出四位小数（）

单选题

当输入为 3 4 5 时，输出为（）
当输入为 5 12 13 时，输出为（）

程序讲解

这程序在干什么

读入三角形三条边长 $a,b,c$，算出它的面积，并固定输出四位小数。

关键变量和函数

函数 f(a,b,c)：算面积的核心。
- s：半周长，公式 $s=\dfrac{a+b+c}{2}$
- 返回值：$\sqrt{s(s-a)(s-b)(s-c)}$，这就是海伦公式
main：读入三个整数，调用 f，用 cout.precision(4) 控制小数位数

执行顺序（手算小例子）

输入 3 4 5（直角三角形）：

$s=(3+4+5)/2=6$
$s-a=3,\; s-b=2,\; s-c=1$
面积 $=\sqrt{6\times3\times2\times1}=\sqrt{36}=6$
输出 6.0000

再试 2 2 2（等边三角形）：

$s=3$，乘积 $3\times1\times1\times1=3$，面积 $=\sqrt3\approx1.7321$

边界与易错点

题目保证输入是合法正整数，不用自己判断能不能构成三角形
乘法交换律不影响结果（(s-b)*(s-c) 和 (s-c)*(s-b) 一样）
fixed + precision(4) 表示总是四位小数，整数也会补零

小题 1：判断题 1：（2分）当输入为 `2 2 2` 时，输出为`1.7321`（）

A. 正确
B. 错误

答案与解法

边长 $2$ 的等边三角形面积 $\frac{\sqrt{3}}{4}\times4\approx1.7321$。

易错点： 手算面积错。

答案：A（正确）

小题 2：判断题 2：（2分）将第7行中的 `(s-b)(s-c)` 改为 `(s-c)(s-b)` 不会影响程序运行的结果（）

A. 正确
B. 错误

答案与解法

乘法可交换，结果不变。

易错点： 以为浮点会不同。

答案：A（正确）

小题 3：判断题 3：（2分）程序总是输出四位小数（）

A. 正确
B. 错误

答案与解法

设置了 fixed 和 precision(4)，总是 $4$ 位小数。

易错点： 以为整数会少位数。

答案：A（正确）

小题 4：单选题 4：当输入为 `3 4 5` 时，输出为（）

A. 6.0000
B. 12.0000
C. 24.0000
D. 30.0000

答案与解法

$3$-$4$-$5$ 直角三角形，面积 $6$。

易错点： 当成海伦公式手算错。

答案：A（6.0000）

小题 5：单选题 5：当输入为 `5 12 13` 时，输出为（）

A. 24.0000
B. 30.0000
C. 60.0000
D. 120.0000

答案与解法

直角三角形，面积 $\frac{5\times12}{2}=30$。

易错点： 同上

答案：B（30.0000）

真题 · 2023年阅读程序第3题

完整题目（含程序与小题）

3.

#include <iostream>
#include <cmath>
using namespace std;int solve1(int n){return n*n;
}int solve2(int n){int sum=0;for(int i=1;i<=sqrt(n);i++){if(n%i==0){if(n/i==i){sum+=i*i;}else{sum+=i*i+(n/i)*(n/i);}}}return sum;
}
int main(){int n;cin>>n;cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;return 0;
}

假设输入的 $n$ 是绝对值不超过 $1000$ 的整数，完成下面的判断题和单选题。

判断题

如果输入的 $n$ 为正整数，solve2 函数的作用是计算 $n$ 所有的因子的平方和（）
第 $13\sim 14$ 行的作用是避免 $n$ 的平方根因子 $i$（或 $n/i$ ）进入第 $16$ 行而被计算两次（）
如果输入的 $n$ 为质数，solve2(n) 的返回值为 $n^2+1$（）

单选题

（4分）如果输入的 $n$ 为质数 $p$ 的平方，那么 solve2(n) 的返回值为（）
当输入为正整数时，第一项减去第二项的差值一定（）
当输入为 5 时，输出为（）

程序讲解

这程序在干什么

读入整数 n，输出两个数，中间空格隔开：

先算 $n^2$，再求「$n^2$ 所有因子的平方和」
先求 n 所有因子的平方和，再把这个结果平方

关键函数

solve1(n)：返回 $n^2$
solve2(n)：返回 $n$ 的所有因子的平方之和
- 只枚举到 $sqrt{n}$，若 i 能整除 n：
  - i == n/i（完全平方根）→ 只加 $i^2$ 一次
  - 否则 → 同时加 $i^2$ 和 $(n/i)^2$

执行顺序（手算 `n=5`）

第一项：solve2(solve1(5)) = solve2(25)
- $25$ 的因子：$1,5,25$ → $1+25+625=651$
第二项：solve1(solve2(5)) = solve1(26)
- $5$ 是质数，因子 $1,5$ → $1+25=26$，再平方 $26^2=676$
输出 651 676

边界与易错点

质数 n 只有两个因子 $1$ 和 $n$，所以 solve2(n)=1+n^2
第 $13\sim14$ 行防止 $sqrt{n}$ 那个因子被算两遍
第一项减第二项：对正整数不一定大于 $0$，也可能相等或更小

小题 1：判断题 1：如果输入的 $n$ 为正整数，`solve2` 函数的作用是计算 $n$ 所有的因子的平方和（）

A. 正确
B. 错误

答案与解法

枚举因数 $i$ 和 $n/i$，累加平方，描述正确。

易错点： 以为是普通因子和。

答案：A（正确）

小题 2：判断题 2：第 $13\sim 14$ 行的作用是避免 $n$ 的平方根因子 $i$（或 $n/i$ ）进入第 $16$ 行而被计算两次（）

A. 正确
B. 错误

答案与解法

当 $i=\sqrt{n}$ 时只加一次 $i^2$，正确。

易错点： 以为多余。

答案：A（正确）

小题 3：判断题 3：如果输入的 $n$ 为质数，`solve2(n)` 的返回值为 $n^2+1$（）

A. 正确
B. 错误

答案与解法

质数因子只有 $1$ 和 $n$，平方和 $1+n^2$。

易错点： 忘记因子 $1$ 和 $n$。

答案：A（正确）

小题 4：单选题 4：（4分）如果输入的 $n$ 为质数 $p$ 的平方，那么 `solve2(n)` 的返回值为（）

A. $p^2+p+1$
B. $n^2+n+1$
C. $n^2+1$
D. $p^4+2p^2+1$

答案与解法

因子 $1,p,p^2$，平方和 $1+p^2+p^4=n^2+n+1$（其中 $n=p^2$）。

易错点： 选 $n^2+1$ 忘了 $p$ 本身。

答案：B（$n^2+n+1$）

小题 5：单选题 5：当输入为正整数时，第一项减去第二项的差值一定（）

A. 大于 $0$
B. 大于等于 $0$ 且不一定大于 $0$
C. 小于 $0$
D. 小于等于 $0$ 且不一定小于 $0$

答案与解法

solve2(n^2) 与 `solve1(solve2(n))=(solve2(n))^2$ 比较，差值 $\le 0$，不一定严格小于。

易错点： 以为一定大于 $0$。

答案：D（小于等于 $0$ 且不一定小于 $0$）

小题 6：单选题 6：当输入为 `5` 时，输出为（）

A. 651 625
B. 650 729
C. 651 676
D. 652 625

答案与解法

$solve1(5)=25$；$solve2(25)=1+25+625=651$；$solve2(5)=26$；$solve1(26)=676$；输出 651 676。

易错点： 算错平方和。

答案：C（651 676）

真题 · 2022年阅读程序第3题

完整题目（含程序与小题）

(3)

1  #include <iostream>
2  
3  using namespace std;
4  
5  int n,k;
6  
7  int solve1()
8  {
9      int l = 0, r = n;
10     while(l <= r){
11         int mid = (l + r) / 2;
12         if (mid * mid <= n) l = mid + 1;
13         else r = mid - 1;
14     }
15     return l - 1;
16 }
17 
18 double solve2(double x)
19 {
20         if (x == 0) return x;
21         for (int i = 0; i < k; i++)
22             x = (x + n / x) / 2;
23     return x;
24 }
25 
26 int main()
27 {
28     cin >> n >> k;
29     double ans = solve2(solve1());
30     cout << ans << ' ' << (ans * ans == n) << endl;
31     return 0;
32 }

假设 int 为32位有符号整数类型，输入的 n 是不超过47000的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

判断题

该算法最准确的时间复杂度分析结果为 $O(\log n+k)$。
当输入为 9801 1 时，输出的第一个数为 99。
对于任意输入的 $n$，随着所输入 $k$ 的增大，输出的第二个数会变成 $1$。
该程序有存在缺陷。当输入的 $n$ 过大时，第 $12$ 行的乘法有可能溢出，因此应当将 mid 强制转换为 $64$ 位整数再计算。

单选题

当输入为 2 1 时，输出的第一个数最接近（）。
当输入为 3 10 时，输出的第一个数最接近（）。
当输入为 256 11 时，输出的第一个数（）。

程序讲解

这程序在干什么

读入 n 和 k，先用二分找一个接近 $sqrt{n}$ 的整数起点，再用牛顿迭代法做 k 次精炼，输出近似平方根，以及「平方是否恰好等于 n」的判断（$0$ 或 $1$）。

`solve1()`：整数二分

在 [0, n] 上找最大的 mid 使 mid*mid <= n：
mid 满足则 l=mid+1，否则 r=mid-1。返回 l-1（即 $lfloorsqrt{n} floor$）。

例如 n=9801：返回 $99$。

`solve2(x)`：牛顿迭代

若 x==0 直接返回。否则重复 k 次：
x = (x + n/x) / 2
这是求 $sqrt{n}$ 的经典公式，每次更接近真值。

`main` 输出

ans = solve2(solve1())，打印 ans 和 (ans*ans == n)（浮点平方是否恰好整除相等）。

手算 n=2, k=1：solve1 得 $1$，迭代一次 x=(1+2/1)/2=1.5。
n=256, k=11：$sqrt{256}=16$ 精确，第二项输出 $1$。

边界与易错点

整体时间 $O(log n + k)$
n 在题目范围 $47000$ 内，mid*mid 不会溢出 $32$ 位 int
第二项为 $1$ 仅当结果是精确整数平方根；k 再大也不保证对所有 n 都变 $1$

小题 1：小题 1

A. 正确
B. 错误

答案与解法

二分 $O(\log n)$，牛顿迭代 $k$ 次，合计 $O(\log n+k)$。

易错点： 以为牛顿法也是 $\log n$。

答案：A（正确）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

$\sqrt{9801}=99$，$k=1$ 次迭代后仍约 $99$。

易错点： 忘记牛顿法还要迭代。

答案：A（正确）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

第二个数是 ans*ans==n；非完全平方数永远为 $0$，不会"变成 $1$"。

易错点： 以为迭代越多越好。

答案：B（错误）

小题 4：小题 4

A. 正确
B. 错误

答案与解法

在本题数据范围下不会溢出，说法不成立。

易错点： 题目说 $n\le 47000$，$\sqrt{n}<220$，$mid^2$ 很小，其实不会溢出。

答案：B（错误）

小题 5：小题 5

A. $1$
B. $1.414$
C. $1.5$
D. $2$

答案与解法

初值 $1$，迭代一次 $(1+2/1)/2=1.5$。

易错点： 选 $1.414$（精确值）忘了只迭代 $1$ 次。

答案：C（$1.5$）

小题 6：小题 6

A. $1.7$
B. $1.732$
C. $1.75$
D. $2$

答案与解法

初值 $1$，多次迭代后接近 $\sqrt{3}\approx1.732$。

易错点： 同上

答案：B（$1.732$）

小题 7：小题 7

A. 等于 $16$
B. 接近但小于 $16$
C. 接近但大于 $16$
D. 前三种情况都有可能

答案与解法

$256=16^2$，精确得到 $16$。

易错点： 浮点误差以为"接近但不等于"。

答案：A（等于 $16$）

考点簇7：编码与特殊模拟（如Base64等）

这类题在考什么

Base64 等特殊编码解码：分清「编码字符集」和「解码输出内容」。

这类题总陷阱

解码输出字符集和编码字符集混

本章知识点总述

Base64：每 $3$ 字节（$24$ bit）编成 $4$ 个可打印字符；解码反向操作。

分清「编码表里的字符」和「解码后得到的原始字节/文本」。

真题 · 2021年阅读程序第2题

完整题目（含程序与小题）

（2）

判断题

输出的第二行一定是由小写字母、大写字母、数字和 $\texttt +$、 $\texttt /$、$\texttt =$ 构成的字符串。（）
可能存在输入不同，但输出的第二行相同的情形。（）
输出的第一行为 $\texttt -1$。（）

单选题

设输入字符串长度为 $n$，decode 函数的时间复杂度为（）
当输入为 $\texttt{Y3Nx}$ 时，输出的第二行为（）。
（3.5 分）当输入为 $\texttt{Y2NmIDIwMjE=}$ 时，输出的第二行为（）。

程序讲解

这程序在干什么

读入一段 Base64 编码字符串，先输出一个固定整数，再输出解码后的原始明文（可能是任意字符，不限于字母数字）。

关键准备

init()：建 base[64] 字符表（A–Z、a–z、0–9、+、/），再建 table[256]，把每个编码字符映射成 $0\ldots63$；没出现的填 0xff；= 映射为 $0$
main 里先 init()，打印 (int)table[0]（未初始化的 table[0] 是 0xff，转成 int 就是 -1）

`decode` 怎么解码

每 $4$ 个编码字符一组，还原最多 $3$ 个字节：

第 $1$ 个字节：table[s0]<<2 | table[s1]>>4
若第 $3$ 个不是 =，出第 $2$ 个字节
若第 $4$ 个不是 =，出第 $3$ 个字节
结果写入 ans。

执行顺序

init → 输出 -1 → 读 str → decode(str) → 打印 ans。

手算 Y3Nx 解码得 csq（不是 csp，注意大小写和第三位）。

边界与易错点

第二行明文可以有空格、小写等（如 ccf 2021），不限于 Base64 字符集
不同编码串可能解出相同内容（填充位不同）
decode 扫一遍字符串，时间 $O(n)`

小题 1：判断题 22：输出的第二行一定是由小写字母、大写字母、数字和 $\texttt +$、 $\texttt /$、$\texttt =$ 构成的字符串。（）

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 2：判断题 23：可能存在输入不同，但输出的第二行相同的情形。（）

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 3：判断题 24：输出的第一行为 $\texttt -1$。（）

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 4：单选题 25：设输入字符串长度为 $n$，`decode` 函数的时间复杂度为（）

A. $O(\sqrt{n})$
B. $O(n)$
C. $O(n \log n)$
D. $O(n^2)$

答案与解法

答案：B（$O(n)$）

小题 5：单选题 26：当输入为 $\texttt{Y3Nx}$ 时，输出的第二行为（）。

A. csp
B. csq
C. CSP
D. Csp

答案与解法

答案：B（csq）

小题 6：单选题 27：（3.5 分）当输入为 $\texttt{Y2NmIDIwMjE=}$ 时，输出的第二行为（）。

A. ccf2021
B. ccf2022
C. ccf 2021
D. ccf 2022

答案与解法

答案：C（ccf 2021）

考点簇8：其他阅读

这类题在考什么

配对模拟、进制计数器、DFS 合并得分等不好归类的阅读题。

这类题总陷阱

配对/模拟题没按规则逐步走

本章知识点总述

通用模拟：按题意逐步执行，不要跳步。

遇到配对、计数器、DFS 合并类题，先写清状态再跟样例走一遍。

真题 · 2020年阅读程序第2题

完整题目（含程序与小题）

#include <iostream>
using namespace std;long long n, ans;
int k, len;
long long d[1000000];int main() {cin >> n >> k;d[0] = 0;len= 1;ans = 0;for (long long i = 0; i <n; ++i) {++d[0];for (int j = 0; j + 1<len; ++j) {if (d[j] == k) {d[j] = 0;d[j + 1] += 1;++ans;}}if (d[len- 1] == k) {d[len - 1] = 0;d[len] =1;++len;++ans;}}cout << ans << endl;return 0;
}

假设输入的 $n$ 是不超过 $2^{62}$ 的正整数，$k$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：

判断题

若 $k=1$，则输出 $\mathrm{ans}$ 时，$\mathrm{len}=n$。（）
若 $k>1$，则输出 $\mathrm{ans}$ 时，$\mathrm{len}$ —定小于 $n$。（）
若 $k>1$，则输出 $\mathrm{ans}$ 时，$k^{len}$ —定大于 $n$。（）

单选题

若输入的 $n$ 等于：$10^{15}$，输入的 $k$ 为 $1$，则输出等于（）。
若输入的 $n$ 等于 $205,891,132,094,649$（即 $3^{30}$），输入的 $k$ 为 $3$，则输出等于（）。
若输入的 $n$ 等于 $100,010,002,000,090$，输入的 $k$ 为 $10$，则输出等于（）。

程序讲解

这程序在干什么

把「从 $0$ 每次 $+1$，连加 $n$ 次」这个过程，想象成在 $k$ 进制下不断进位；ans 统计一共发生了多少次进位（每一位满 k 就进一位）。

关键变量

d[]：模拟 $k$ 进制数的每一位；d[0] 是最低位
len：当前用了多少位（初始 $1$）
外层循环 i=0..n-1：每轮给 d[0] 加 $1$，再处理进位

每轮内部

++d[0]
从低位往高位扫 j=0..len-2：若 d[j]==k，则 d[j]=0，d[j+1]+=1，ans++
若最高位 d[len-1]==k：清零，在 d[len] 置 $1$，len++，ans++

手算 n=5, k=2（二进制从 $0$ 数到 $5$）：
$0\to1\to10\to11\to100\to101$，共 $4$ 次进位 → ans=4。

手算 k=1：每一位只能存 $0$，每加 $1$ 都触发进位，len 每轮 $+1$，最终 len=n+1（不是 len=n）。

边界与易错点

这题本质是「$n$ 在 $k$ 进制表示下所有数位之和」的变形计数
k=1 时行为很特殊，别按普通进制直觉套
k^n > n 时位数 len 一定小于 $n$（对 k>1）

小题 1：小题 1

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 4：小题 4

A. $1$
B. $(10^{30}-10^{15})/2$
C. $(10^{30}+10^{15})/2$
D. $10^{15}$

答案与解法

答案：D（$10^{15}$）

小题 5：小题 5

A. $3^{30}$
B. $(3^{30}-1)/2$
C. $3^{30}-1$
D. $(3^{30}+1)/2$

答案与解法

答案：B（$(3^{30}-1)/2$）

小题 6：小题 6

A. $11,112,222,444,543$
B. $11,122,222,444,453$
C. $11,122,222,444,543$
D. $11,112,222,444,453$

答案与解法

答案：D（$11,112,222,444,453$）

真题 · 2019年阅读程序第2题

完整题目（含程序与小题）

#include<cstdio>
using namespace std;
int n, m;
int a[100], b[100];int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i)a[i] = b[i] = 0;for (int i = 1; i <= m; ++i) {int x, y;scanf("%d%d", &x, &y);if (a[x] < y && b[y] < x) {if (a[x] > 0)b[a[x]] = 0;if (b[y] > 0)a[b[y]] = 0;a[x] = y;b[y] = x;}}int ans = 0;for (int i = 1; i <= n; ++i) {if (a[i] == 0)++ans;if (b[i] == 0)++ans;}printf("%d", ans);return 0;
}

假设输入的 $n$ 和 $m$ 都是正整数，$x$ 和 $y$ 都是在 $[1,n]$ 的范围内的整数，完成下面的判断题和单选题：

判断题

当 $m>0$ 时，输出的值一定小于 $2n$。（）
执行完第 $27$ 行的 ++ans 时，$\mathrm{ans}$ —定是偶数。（）
a[i] 和 b[i] 不可能同时大于 $0$。（）
右程序执行到第 13 行时，$x$ 总是小于 $y$，那么第 $15$ 行不会被执行。（）

•选择题

若 $m$ 个 $x$ 两两不同，且 $m$ 个 $y$ 两两不同，则输出的值为（）
若 $m$ 个 $x$ 两两不同，且 $m$ 个 $y$ 都相等，则输出的值为（）

程序讲解

这程序在干什么

读入 $n$、$m$ 和 $m$ 组配对 (x,y)，维护一种「双向配对」关系，最后统计还有多少人没配上，输出 ans。

关键数组

a[x]：编号 $x$ 当前配对的「对方编号」；$0$ 表示没配上
b[y]：编号 $y$ 当前配对的「对方编号」；$0$ 表示没配上
一开始 a[i]=b[i]=0

主循环（处理每组 `x,y`）

仅当 a[x] < y 且 b[y] < x 时才接受这对新配对（都想换到「更大编号」的搭档）：

若 a[x] 原来有搭档，先把原搭档的 b[...] 清零
若 b[y] 原来有搭档，先把原搭档的 a[...] 清零
建立 a[x]=y，b[y]=x

统计输出

对每个 $i=1\ldots n$：若 a[i]==0 则 ans++；若 b[i]==0 则 ans++。
每人从 a、b 两个视角各算一次「是否落单」。

手算：$n=3$，只来一对 (1,2)$。配对后 a[1]=2,b[2]=1；a[2]=b[1]=a[3]=b[3]=0。 ans：$1$ 在 a 有伴、b` 无伴；$2$ 两边都有；$3$ 两边都无 → 共 $4$。

边界与易错点

a[i] 和 b[i] 可以同时大于 $0$（同一人既当左端点又当右端点）
条件不满足时整组 (x,y) 被丢弃，不是部分更新
ans 最大 $2n$，有配对时一定小于 $2n$

小题 1：小题 1

A. 正确
B. 错误

答案与解法

答案：A（正确）

小题 2：小题 2

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 3：小题 3

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 4：小题 4

A. 正确
B. 错误

答案与解法

答案：B（错误）

小题 5：小题 5

A. $2n-2m$
B. $2n+2$
C. $2n-2$
D. $2n$

答案与解法

答案：A（$2n-2m$）

小题 6：小题 6

A. $2n-2$
B. $2n$
C. $2m$
D. $2n-2m$

答案与解法

答案：A（$2n-2$）

三、程序填空题（完善程序）

考点簇1：递归/分治/汉诺塔/矩阵变幻类

这类题在考什么

分治递归：矩阵变幻、汉诺塔。想清边界条件、四个子块/三根柱子的参数顺序。

这类题总陷阱

递归边界填 0 还是 1
汉诺塔柱子参数顺序错

本章知识点总述

递归填空：先找边界（最小规模直接返回什么），再写 递归式（参数怎么变小）。

汉诺塔：把 $n$ 盘从 A 移到 C，借助 B：

上面 $n-1$ 盘 A→B（借助 C）
最大盘 A→C
$n-1$ 盘 B→C（借助 A）

分治矩阵：四块递归，注意块的大小和起始坐标。

真题 · 2024年完善程序第2题

完整题目（含挖空程序与选项）

第 2 题

（汉诺塔问题） 给定三根柱子，分别标记为 A、B 和 C。初始状态下，柱子 A 上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子 C 上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则:

只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
每次只能移动一个圆盘。
小圆盘必须始终在大圆盘之上。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;void move(char src, char tgt) {cout << "从柱子" << src << "挪到柱子" << tgt << endl;
}void dfs(int i, char src, char tmp, char tgt) {if (i == ___①___) {move(___②___);return;}dfs(i - 1, ___③___);move(src, tgt);dfs(___⑤___, ___④___);
}int main() {int n;cin >> n;dfs(n, 'A', 'B', 'C');
}

① 处应填（）
A. 0
B. 1
C. 2
D. 3
② 处应填（）
A. src, tmp
B. src, tgt
C. tmp, tgt
D. tgt, tmp
③ 处应填（）
A. src, tmp, tgt
B. src, tgt, tmp
C. tgt, tmp, src
D. tgt, src, tmp
④ 处应填（）
A. src, tmp, tgt
B. tmp, src, tgt
C. src, tgt, tmp
D. tgt, src, tmp
⑤ 处应填（）
A. 0
B. 1
C. i - 1
D. i

程序讲解

这程序在干什么

读入圆盘个数 n，按汉诺塔规则，打印把 n 个盘从柱子 A 全部挪到柱子 C 的每一步。

关键函数

move(src, tgt)：打印一次移动
dfs(i, src, tmp, tgt)：把 i 个盘从 src 经 tmp 挪到 tgt
- 只剩 $1$ 个盘：直接 move(src, tgt)
- 否则：先把上面 $i-1$ 个挪到辅助柱 → 挪最大的 → 再把 $i-1$ 个从辅助柱挪到目标柱

执行顺序（手算 `n=2`）

dfs(1, A, C, B)：把上面 $1$ 个从 A 挪到 B
move(A, C)：把大盘从 A 挪到 C
dfs(1, B, A, C)：把 B 上那 $1$ 个挪到 C

共 $3$ 步，符合 $2^2-1=3$。

边界与易错点

递归边界是 i==1，不是 $0$
第一次小盘挪法：dfs(i-1, src, tgt, tmp)（目标柱和辅助柱对调）
第二次小盘挪法：dfs(i-1, tmp, src, tgt)
中间那步 move(src, tgt) 挪的是当前最大的那个盘

第 1 空

A. 0
B. 1
C. 2
D. 3

答案与解法

只剩 $1$ 个盘时直接移动。

易错点： 边界写成 $0$。

答案：B（1）

第 2 空

A. src, tmp
B. src, tgt
C. tmp, tgt
D. tgt, tmp

答案与解法

一个盘从 src 移到 tgt。

易错点： 借助 tmp。

答案：B（src, tgt）

第 3 空

A. src, tmp, tgt
B. src, tgt, tmp
C. tgt, tmp, src
D. tgt, src, tmp

答案与解法

dfs(i-1, src, tgt, tmp)：借助 tgt 移到 tmp。

易错点： 顺序错。

答案：B（src, tgt, tmp）

第 4 空

A. src, tmp, tgt
B. tmp, src, tgt
C. src, tgt, tmp
D. tgt, src, tmp

答案与解法

应把 $i-1$ 个盘从 tmp 经 src 移到 tgt，即 dfs 的 ④参数为 tmp, src, tgt。

易错点： src 与 tmp 位置互换。

答案：B（tmp, src, tgt）

第 5 空

A. 0
B. 1
C. i - 1
D. i

答案与解法

仍搬 $i-1$ 个盘。

易错点： 填 i 或 1。

答案：C（i - 1）

真题 · 2019年完善程序第1题

完整题目（含挖空程序与选项）

1.（矩阵变幻）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：

数字 $0$ 变成矩阵

0 0 
0 1

数字 $1$ 变成矩阵

1 1
1 0

最初该矩阵只有一个元素 $0$，变幻 $n$ 次后，矩阵会变成什么样？

例如，矩阵最初为：$[0]$；

矩阵变幻 $1$ 次后：

0 0 
0 1

矩阵变幻 $2$ 次后：

输入一行一个不超过 $10$ 的正整数 $n$。输出变幻 $n$ 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 $(11)_2$ << $2 = (1100)_2$；
而 ^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位—进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ，反之为 $1$。

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;int res[max_size][max_size];void recursive(int x, int y, int n, int t) {if (n == 0) {res[x][y] = ①;return;}int step = 1 << (n - 1);recursive(②, n - 1, t);recursive(x, y + step, n - 1, t);recursive(x + step, y, n - 1, t);recursive(③, n - 1, !t);
}int main() {scanf("%d", &n);recursive(0, 0, ④);int size = ⑤;for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++)printf("%d", res[i][j]);puts("");}return 0;
}

①处应填（）

②处应填（）

③处应填（）

④处应填（）

⑤处应填（）

程序讲解

这程序在干什么

从只有一个数 $0$ 的 $1\times1$ 矩阵出发，按题目规则「变幻」$n$ 次，得到 $2^n\times2^n$ 的 $01$ 矩阵并打印。程序用递归把大矩阵拆成四个象限填数。

关键变量

res[][]：存最终矩阵
recursive(x, y, n, t)：在左上角 (x,y) 处填边长 $2^n$ 的子矩阵；t 表示当前格应填 $0$ 还是 $1$
step = 1 << (n-1)：子块边长（$2^{n-1}$）

递归逻辑

n == 0：最小格，res[x][y] = t，返回
否则把区域分成四块，分别递归：
- 左上 (x, y)：t 不变
- 右上 (x, y+step)：t 不变
- 左下 (x+step, y)：t 不变
- 右下 (x+step, y+step)：t 取反（!t）

`main`

读 n，调用 recursive(0, 0, n, 0)，边长 size = 1<<n，双重循环打印。

手算 $n=1$：$2\times2$，左上右下为 $0$，右上左下为 $1$，与题目示例一致。

边界与易错点

t 是「当前块该填什么」，不是 n%2
四个子递归的坐标别写错，右下块才翻转 t
1<<n 是边长，不是 n+1 或 1<<(n-1)

第 1 空

A. n%2
B. 0
C. t
D. 1

答案与解法

答案：C（t）

第 2 空

A. x-step,y-step
B. x,y-step
C. x-step,y
D. x,y

答案与解法

答案：D（x,y）

第 3 空

A. x-step,y-step
B. x+step,y+step
C. x-step,y
D. x,y-step

答案与解法

答案：B（x+step,y+step）

第 4 空

A. n-1,n%2
B. n,0
C. n,n%2
D. n-1,0

答案与解法

答案：B（n,0）

第 5 空

A. 1<<(n+1)
B. 1<<n
C. n+1
D. 1<<(n-1)

答案与解法

答案：B（1<<n）

考点簇2：排序与计数

这类题在考什么

计数排序、冒泡等：想「先统计谁、怎么保证稳定、输出时用哪个下标」。

这类题总陷阱

计数排序两轮统计对象搞反
稳定排序要从后往前放

本章知识点总述

计数排序：先统计每个值出现次数 cnt[x]，再按值从小到大输出。

稳定排序填空：从后往前扫描原数组，保证相同键的相对顺序。

真题 · 2019年完善程序第2题

完整题目（含挖空程序与选项）

2.（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将 $n$ 对 $10000$ 以内的整数，从小到大排序。

例如有三对整数 $(3,4)$、$(2,4)$、$(3,3)$，那么排序之后应该是 $(2,4)$、$(3,3)$、$(3,4)$ 。

输入第一行为 $n$，接下来 $n$ 行，第 $i$ 行有两个数 $a[i]$ 和 $b[i]$，分别表示第 $i$ 对整数的第一关键字和第二关键字。

从小到大排序后输出。

数据范围 $1<n<10^7$，$1<a[i],b[i]<10^4$。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord[] 存储第二关键字排序的结果，数组 res[] 存储双关键字排序的结果。

试补全程序。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {scanf("%d", &n);for (int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]);memset(cnt, 0, sizeof(cnt));for (int i = 0; i < n; ++i)①; // 利用 cnt 数组统计数量for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i];for (int i = 0; i < n; ++i)②; // 记录初步排序结果memset(cnt, 0, sizeof(cnt));for (int i = 0; i < n; ++i)③; // 利用 cnt 数组统计数量for (int i = 0; i < maxs; ++i)cnt[i + 1] += cnt[i];for (int i = n - 1; i >= 0; --i)④ // 记录最终排序结果for (int i = 0; i < n; i++)printf("%d %d", ⑤);return 0;
}

①处应填（）

②处应填（）

③处应填（）

④处应填（）

⑤处应填（）

程序讲解

这程序在干什么

读入 $n$ 对整数 (a[i], b[i])，按「先比第一关键字 a，相同再比 b」从小到大排序后输出。用的是计数排序（按值统计个数，不用普通比较排序）。

关键数组

cnt[]：统计每个值出现了几次
ord[]：第一趟排序后的下标顺序
res[]：第二趟排序后的下标顺序（最终结果）

两趟计数排序

第一趟：按第二关键字 b 排

统计：++cnt[b[i]]
前缀和：cnt[i+1] += cnt[i]（得到每个值最后一次出现的位置）
从前往后放：ord[--cnt[b[i]]] = i（稳定：相同 b 保持原相对顺序）

第二趟：按第一关键字 a 排（对象换成 ord 里的下标）

清空 cnt，统计 a[ord[i]]
再做前缀和
从后往前放：res[--cnt[a[ord[i]]]] = ord[i]（保证稳定）

输出

按 res 里的下标取原数据：a[res[i]], b[res[i]]。

手算 (3,4),(2,4),(3,3)$：先按 b得顺序 $1,2,0$；再按a得(2,4),(3,3),(3,4)$。

边界与易错点

必须先排 b 再排 a，顺序反了结果错
第二趟要从 i=n-1 往前扫，才能稳定
cnt 大小按 $10^4$ 设计，因为关键字范围在 $10^4$ 内

第 1 空

A. ++cnt[i]
B. ++cnt[b[i]]
C. ++cnt[a[i] * maxs + b[i]]
D. ++cnt[a[i]]

答案与解法

答案：B（++cnt[b[i]]）

第 2 空

A. ord[--cnt[a[i]]] = i
B. ord[--cnt[b[i]]] = a[i]
C. ord[--cnt[a[i]]] = b[i]
D. ord[--cnt[b[i]]] = i

答案与解法

答案：D（ord[--cnt[b[i]]] = i）

第 3 空

A. ++cnt[b[i]]
B. ++cnt[a[i] * maxs + b[i]]
C. ++cnt[a[i]]
D. ++cnt[i]

答案与解法

答案：C（++cnt[a[i]]）

第 4 空

A. res[--cnt[a[ord[i]]]] = ord[i]
B. res[--cnt[b[ord[i]]]] = ord[i]
C. res[--cnt[b[i]]] = ord[i]
D. res[--cnt[a[i]]] = ord[i]

答案与解法

答案：A（res[--cnt[a[ord[i]]]] = ord[i]）

第 5 空

A. a[i], b[i]
B. a[res[i]], b[res[i]]
C. a[ord[res[i]]],b[ord[res[i]]]
D. a[res[ord[i]]],b[res[ord[i]]]

答案与解法

答案：B（a[res[i]], b[res[i]]）

考点簇3：数论因数/平方判断

这类题在考什么

质因数分解、判断完全平方、枚举因数：循环从几开始、上界到 $\sqrt{n}$、while 除尽。

这类题总陷阱

质因数用 if 只除一次
平方根因数重复输出

本章知识点总述

质因数分解：

for (i = 2; i*i <= n; i++)while (n % i == 0) { 输出 i; n /= i; }
if (n > 1) 输出 n

判完全平方：枚举 $i$ 从 $1$ 到 $\lfloor\sqrt{n}\rfloor$，看 $i*i$ 是否等于 $n$。

真题 · 2024年完善程序第1题

完整题目（含挖空程序与选项）

三、完善程序（单选题，每小题 3 分，共计 30 分）

第 1 题

（判断平方数） 问题：给定一个正整数 $n$，希望判断这个数是否为完全平方数，即存在一个正整数 $x$，使得 $x$ 的平方为 $n$。

试补全程序。

#include<iostream>
#include<vector>
using namespace std;bool isSquare(int num) {int i = ___①___;int bound = ___②___;for (; i <= bound; ++i) {if (___③___) {return ___④___;}}return___⑤___;
}int main() {int n;cin >> n;if (isSquare(n)) {cout << n << " is a square number" << endl;} else {cout << n << " is not a square number" << endl;}return 0;
}

① 处应填（）
A. 1
B. 2
C. 3
D. 4
② 处应填（）
A. (int)floor(sqrt(num))-1
B. (int)floor(sqrt(num))
C. floor(sqrt(num/2))-1
D. floor(sqrt(num/2))
③ 处应填（）
A. num = 2 * i
B. num == 2 * i
C. num = i * i
D. num == i * i
④ 处应填（）（本题有多个可能选项）
A. num = 2 * i
B. num == 2 * i
C. true
D. false
⑤ 处应填（）
A. num = i * i
B. num != i * i
C. true
D. false

程序讲解

这程序在干什么

读入正整数 n，判断它是不是某个整数的平方（比如 $36=6^2$ 是，$35$ 不是）。

关键函数

isSquare(num)：从 i=1 试到 $lfloorsqrt{num} floor$，看有没有 i*i==num

执行顺序（手算小例子）

num=36：

bound=6，i 从 $1$ 试到 $6$
i=6 时 $6\times6=36$，匹配 → 返回 true
输出 36 is a square number

num=35：试到 i=5 都不够，循环结束 → 返回 false

边界与易错点

i 从 $1$ 开始（不是 $0$，也不是 $2$）
上界取 $lfloorsqrt{num} floor$，$36$ 要试到 $6$ 不能少
找到时返回 true；全部试完返回 false
判断条件用 == 比较，不是赋值 =

第 1 空

A. 1
B. 2
C. 3
D. 4

答案与解法

从 $1$ 试到 $\lfloor\sqrt{n}\rfloor$。

易错点： 从 $0$ 开始。

答案：A（1）

第 2 空

A. (int)floor(sqrt(num))-1
B. (int)floor(sqrt(num))
C. floor(sqrt(num/2))-1
D. floor(sqrt(num/2))

答案与解法

要试到 $\lfloor\sqrt{num}\rfloor$，即 (int)floor(sqrt(num))。

易错点： 少试一个平方根。

答案：B（(int)floor(sqrt(num))）

第 3 空

A. num = 2 * i
B. num == 2 * i
C. num = i * i
D. num == i * i

答案与解法

判断 num == i*i。

易错点： 用赋值 =。

答案：D（num == i * i）

第 4 空

A. num = 2 * i
B. num == 2 * i
C. true
D. false

答案与解法

找到应返回 true；卷面 AC 选项为 A 和 C。

易错点： 返回 false。

答案：A（num = 2 * i）

第 5 空

A. num = i * i
B. num != i * i
C. true
D. false

答案与解法

不是平方数返回 false。

易错点： 返回 true。

答案：D（false）

真题 · 2022年完善程序第1题

完整题目（含挖空程序与选项）

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）

（1）（枚举因数）从小到大打印正整数 $n$ 的所有正因数。

试补全枚举程序。

#include <bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;vector<int> fac;fac.reserve((int)ceil(sqrt(n)));int i;for (i = 1; i * i < n; ++i){if (①){fac.push_back(i);}}for (int k = 0; k < fac.size(); ++k){cout << ② << "";}if (③) {cout << ④ << "";}for (int k = fac.size() - 1; k >= 0; --k){cout << ⑤ << "";}
}

①~⑤处应填（）

程序讲解

这程序在干什么

读入正整数 n，按从小到大顺序打印它的所有正因数。

第一段循环：找「小半部分」因数

for(i=1; i*i < n; ++i)（注意是小于，不含等号）
若 n % i == 0（①），把 i 存入 fac。

输出顺序（对称）

正序输出 fac 里存的数（② 打印 fac[k]）
若 i*i == n（③，n 是完全平方数），单独输出平方根 i（④）
倒序输出每个 fac[k] 对应的大因数 n/fac[k]（⑤）

手算 n=12：
小因数 $1,2,3$；倒序配对 $12,6,4$ → 1 2 3 4 6 12。

手算 n=36：循环结束时 i=6，6*6==36，中间单独输出 $6$，避免重复。

边界与易错点

第一段用 i*i < n，完全平方根在中间单独处理
不要正序和倒序都打印 fac[k]，倒序必须是大因数 n/fac[k]
i=1 时若写 n%(i-1) 会除零

第 1 空

A. n % i == 0
B. n % i == 1
C. n % (i-1) == 0
D. n % (i-1) == 1

答案与解法

因数条件：$n$ 能被 $i$ 整除，即 n % i == 0。

易错点： 写成 n%i==1。

答案：A（n % i == 0）

第 2 空

A. n / fac[k]
B. fac[k]
C. fac[k]-1
D. n / (fac[k]-1)

答案与解法

第一遍只收集 $\le\sqrt{n}$ 的小因数，直接打印 fac[k]。

易错点： 打印大因数 n/fac[k]。

答案：B（fac[k]）

第 3 空

A. (i-1)*(i-1)== n
B. (i-1)*i == n
C. i*i == n
D. i*(i-1) == n

答案与解法

循环结束时若 $i*i==n$，说明 $\sqrt{n}$ 是因数要单独输出。

易错点： 用 $(i-1)^2$。

答案：C（i*i == n）

第 4 空

A. n-i
B. n-i+1
C. i-1
D. i

答案与解法

平方因数就是 $i$。

易错点： 打印 $i-1$。

答案：D（i）

第 5 空

A. n / fac[k]
B. fac[k]
C. fac[k]-1
D. n / (fac[k]-1)

答案与解法

大因数 $=n/$ 小因数，填 n / fac[k]。

易错点： 又打印 fac[k]。

答案：A（n / fac[k]）

真题 · 2020年完善程序第1题

完整题目（含挖空程序与选项）

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）

1.（质因数分解）给出正整数 $n$，请输出将 $n$ 质因数分解的结果，结果从小到大输出。

例如：输入 $n=120$，程序应该输出 2 2 2 3 5，表示：$120 = 2 \times 2 \times 2 \times 3 \times 5$。输入保证 $2\le n \le 10^9$。

提示：先从小到大枚举变量 $i$，然后用 $i$ 不停试除 $n$ 来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;
int n, i;int main() {scanf("%d", &n);for(i = ①; ② <=n; i ++){③{printf("%d ", i);n = n / i;}}if(④)printf("%d ", ⑤);return 0;
}

1）①处应填（）

2）②处应填（）

3）③处应填（ )

4）④处应填（）

5）⑤处应填（ )

程序讲解

这程序在干什么

读入正整数 n，从小到大输出它的所有质因子（同一个因子出现几次就打印几次）。

主循环

for(i = 2; i*i <= n; i++)：

用 while(n % i == 0) 反复除掉 i（不能只用 if，否则 $12=2\times2\times3$ 会漏第二个 $2$）
每除一次就 printf("%d ", i)

收尾

循环结束后若 n > 1，说明还剩一个大于 $sqrt{ ext{原}n}$ 的质因子（例如 $120$ 除完后 n=5），打印这个 n。

手算 n=120：

i=2：除三次，输出三个 2，n=15
i=3：除一次，输出 3，n=5
i=4：$4^2>5$，结束；n=5>1，输出 5
结果：2 2 2 3 5

边界与易错点

i 从 $2$ 开始，不是 $1$（$1$ 不是质数）
循环条件是 i*i <= n，n 会变小，不是 i <= 原n
最后那个 n 可能就是答案（如输入本身就是质数）

第 1 空

A. 1
B. n-1
C. 2
D. 0

答案与解法

答案：C（2）

第 2 空

A. n/i
B. n/(i*i)
C. i*i
D. i*i*i

答案与解法

答案：C（i*i）

第 3 空

A. if(n%i==0)
B. if(i*i<=n)
C. while(n%i==0)
D. while(i*i<=n)

答案与解法

答案：C（while(n%i==0)）

第 4 空

A. n>1
B. n<=1
C. i<n/i
D. i+i<=n

答案与解法

答案：A（n>1）

第 5 空

A. 2
B. n/i
C. n
D. i

答案与解法

答案：C（n）

考点簇4：搜索BFS

这类题在考什么

BFS 洪水填充：入队前染色、四方向数组、扩展后入队新点。

这类题总陷阱

BFS 先改邻居不改起点
四方向顺序搞错

本章知识点总述

BFS 模板：

起点入队并标记已访问
出队一个点，向四个方向扩展
新点未访问则标记并入队

四方向：dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1}

真题 · 2022年完善程序第2题

完整题目（含挖空程序与选项）

（2）（洪水填充）

现有用字符标记像素颜色的 $8\times 8$ 图像。颜色填充的操作描述如下：给定起始像素的位置待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

试补全程序。

#include<bits/stdc++.h>
using namespace std;const int ROWS = 8;
const int COLS = 8;struct Point {int r, c;Point(int r, int c): r(r), c(c) {}
};bool is_valid(char image[ROWS][COLS], Point pt,int prev_color, int new_color) {int r = pt.r;int c = pt.c;return (0 <= r && r < ROWS && 0 <= c && c < COLS &&① && image[r][c] != new_color);
}void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {queue<Point> queue;queue.push(cur);int prev_color = image[cur.r][cur.c];②;while (!queue.empty()) {Point pt = queue.front ();queue.pop ();Point points[4] = {③, Point(pt.r - 1, pt.c),Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};for (auto p : points) {if (is_valid(image, p, prev_color, new_color)) {④;⑤;}}}
}int main() {char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},{'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},{'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},{'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},{'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},{'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},{'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},{'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};Point cur(4, 4);char new_color = 'y';flood_fill(image, cur, new_color);for (int r = 0; r < ROWS; r++) {for (int c = 0; c < COLS; c++) {cout << image[r][c] << '';}cout << endl;}
//输出:
// g g g g g g g g
// g g g g g g r r
// g r r g g r g g
// g y y y y r g r
// g g g y y r g r
// g g g y y y y r
// g g g g g y g g
// g g g g g y y greturn 0;
}

①~⑤处应填（）

程序讲解

这程序在干什么

在 $8\times8$ 字符画布上，从给定起点出发，把所有与起点同色且四连通的格子都改成新颜色（经典 flood fill）。

关键函数

is_valid：新点 pt 能不能扩展
在边界内、颜色仍等于 prev_color（①）、且还没被改成 new_color
flood_fill：BFS 实现

BFS 流程

起点入队；记下 prev_color；立刻把起点染成 new_color（②）
队列不空则出队一个 pt
试四个方向（③ 下、上、右、左）：Point(pt.r+1,pt.c) 等
若 is_valid：把该格染成 new_color（④），再入队（⑤ queue.push(p)）

手算：起点 (4,4) 原是 'b'，要变 'y'。与 'b' 四连通的一片 b 格子都会变 y，被 r、g 隔开的不会变。

边界与易错点

先染色再入队/扩展，避免同一格重复入队
prev_color 是起始色，扩展时仍比这个颜色，不是比 new_color
四个方向数组别写错；入队的是新点 p，不是当前 pt 或起点 cur

第 1 空

A. image[r][c] == prev_color
B. image[r][c] != prev_color
C. image[r][c] == new_color
D. image[r][c] != new_color

答案与解法

只能扩展到原色且非新色的格子：image[r][c] == prev_color。

易错点： 写成 != prev_color。

答案：A（image[r][c] == prev_color）

第 2 空

A. image[cur.r+1][cur.c] = new_color
B. image[cur.r][cur.c] = new_color
C. image[cur.r][cur.c+1] = new_color
D. image[cur.r][cur.c] = prev_color

答案与解法

先把起点染成新颜色：image[cur.r][cur.c] = new_color。

易错点： 改邻居而不是起点。

答案：B（image[cur.r][cur.c] = new_color）

第 3 空

A. Point(pt.r, pt.c)
B. Point(pt.r, pt.c+1)
C. Point(pt.r+1, pt.c)
D. Point(pt.r+1, pt.c+1)

答案与解法

四个方向：下、上、右、左；第一个是下：Point(pt.r+1, pt.c)。

易错点： 对角线方向。

答案：C（Point(pt.r+1, pt.c)）

第 4 空

A. prev_color = image[p.r][p.c]
B. new_color = image[p.r][p.c]
C. image[p.r][p.c] = prev_color
D. image[p.r][p.c] = new_color

答案与解法

新格子染新色：image[p.r][p.c] = new_color。

易错点： 染成旧色。

答案：D（image[p.r][p.c] = new_color）

第 5 空

A. queue.push(p)
B. queue. push (pt)
C. queue.push(cur)
D. queue. push(Point (ROWS, COLS))

答案与解法

把新点入队：queue.push(p)。

易错点： 重复入队当前点 pt。

答案：A（queue.push(p)）

考点簇5：二分查找

这类题在考什么

二分：比较基准、往左还是往右缩、返回值是下标还是缺失值。

这类题总陷阱

二分 right=mid-1 跳过答案
缺失值公式错

本章知识点总述

二分模板：

while (l <= r) {mid = (l + r) / 2;if (check(mid)) 往答案方向缩区间;else 另一边;
}

找第一个 $\ge x$ 的：若 a[mid] >= x 则 r = mid-1 并记录答案。

真题 · 2023年完善程序第1题

完整题目（含挖空程序与选项）

三、完善程序（单选题，每小题 3 分，共计 30 分）

(寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] == mid + ①) {②;} else {③;}}return ④;
}
int main() {int n;cin >> n;vector<int> nums(n);for (int i = 0; i < n; i++) cin >> nums[i];int missing_number = find_missing(nums);if (missing_number == ⑤) {cout << "Sequence is consecutive" << endl;}else{cout << "Missing number is " << missing_number << endl;}return 0;
}

①处应填（）
②处应填（）
③处应填（）
④处应填（）
⑤处应填（）

程序讲解

这程序在干什么

原来应该是 $0,1,2,\dots,n$ 的连续数列，中间删了一个数后放进数组。程序要找出被删的是谁；若没删（仍连续）就输出提示。

关键变量

left、right：二分区间的左右端点
mid：中间下标
核心规律：若没缺数，nums[i] 应该等于 nums[0]+i；缺了数后，某个位置会「对不上」

执行顺序（手算小例子）

数组 [5,6,8,9,10]（缺了 $7$），nums[0]=5：

mid=2，nums[2]=8，期望 mid+nums[0]=7 → 不相等，说明缺失在左半段
不断缩区间，最后 left=right=2
返回 left+nums[0]=2+5=7

若数组是 [3,4,5,6,7]（没缺），最后会和 nums[n-1]=7 比较，输出连续提示。

边界与易错点

①填 nums[0]：基准值是第一个元素，不是固定的 $1$
对上时 left=mid+1（缺失在右边）；对不上时 right=mid（缺失在左边或就是 mid）
返回值 left+nums[0]，不是 left+1
⑤和最后一个元素比，判断「删的是不是末尾」

第 1 空

A. 1
B. nums[0]
C. right
D. left

答案与解法

若无缺失，$nums[mid]$ 应等于 $nums[0]+mid$，即 mid + nums[0] 的写法在代码里是 nums[mid]==mid+①，① 填 nums[0]。

易错点： 用 mid+1 当期望值。

答案：B（nums[0]）

第 2 空

A. left=mid+1
B. right=mid-1
C. right=mid
D. left=mid

答案与解法

说明缺失在右边，left=mid+1。

易错点： 往左搜。

答案：A（left=mid+1）

第 3 空

A. left=mid+1
B. right=mid-1
C. right=mid
D. left=mid

答案与解法

缺失在左边或就是 mid，right=mid。

易错点： right=mid-1 可能跳过答案。

答案：C（right=mid）

第 4 空

A. left+nums[0]
B. right+nums[0]
C. mid+nums[0]
D. right+1

答案与解法

退出时缺失值为 $left+nums[0]$。

易错点： 返回下标本身。

答案：A（left+nums[0]）

第 5 空

A. nums[0]+n
B. nums[0]+n-1
C. nums[0]+n+1
D. nums[n-1]

答案与解法

答案：D（nums[n-1]）

考点簇6：DP类（编辑距离等）

这类题在考什么

编辑距离等 DP：初始化第 0 行/列、相等时继承左上角、三选一最小。初二可先跳过细节，只看每题 程序讲解 里的概要即可。

这类题总陷阱

DP 下标 i-1 和 str[i] 对应关系
初始化 0 行/列填错

本章知识点总述

编辑距离 dp[i][j]：前 $i$ 个字符变到前 $j$ 个的最少步数。

初始化：第 $0$ 行/列 $= 0,1,2,\ldots$
字符相同：dp[i][j] = dp[i-1][j-1]
不同：三选一最小（删、插、换）各 $+1$

真题 · 2023年完善程序第2题

完整题目（含挖空程序与选项）

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {int m = str1.length();int n = str2.length();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0)dp[i][j] = ①;else if (j == 0)dp[i][j] = ②;else if (③)dp[i][j] = ④;elsedp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);}}return dp[m][n];
}
int main() {string str1, str2;cin >> str1 >> str2;cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl;return 0;
}

①处应填（）
②处应填（）
③处应填（）
④处应填（）
⑤处应填（）

程序讲解

这程序在干什么

读入两个字符串，求把第一个变成第二个，最少需要多少次操作（每次可删、插、换一个字符）。

关键函数

edit_dist_dp：用动态规划填表 dp[i][j]
min(x,y,z)：三个数取最小

DP 部分（你还没系统学过，了解即可）
dp 是一个 $(m+1)\times(n+1)$ 的表。dp[i][j] 表示「str1 前 $i$ 个字符」变到「str2 前 $j$ 个字符」的最少步数。

第 $0$ 行：只有插入，填 j

第 $0$ 列：只有删除，填 i

当前字符相同 → 继承左上角 dp[i-1][j-1]（不用操作）

不同 → 在「删、插、换」三种里选最小的，再加 $1$
最后 dp[m][n] 就是答案。

执行顺序（概念小例子）

cat → dog：三个字母都要换，至少 $3$ 步（具体路径不用手算，知道「填表取最小」即可）。

边界与易错点

比较字符用 str1[i-1] 和 str2[j-1]（下标从 $0$ 开始，dp 下标从 $1$ 开始）
字符相同时不加 $1$，直接抄左上角
三种操作对应 dp[i][j-1]（插）、dp[i-1][j]（删）、dp[i-1][j-1]（换）

第 1 空

A. j
B. i
C. m
D. n

答案与解法

空串变 $str2$ 前 $j$ 个字符要 $j$ 次插入，$dp[0][j]=j$。

易错点： 填 $i$ 或 $m$。

答案：A（j）

第 2 空

A. j
B. i
C. m
D. n

答案与解法

$dp[i][0]=i$（删 $i$ 个字符）。

易错点： 同上

答案：B（i）

第 3 空

A. str1[i-1]==str2[j-1]
B. str1[i]==str2[j]
C. str1[i-1]!=str2[j-1]
D. str1[i]!=str2[j]

答案与解法

比较 str1[i-1]==str2[j-1]。

易错点： 用 str1[i]==str2[j] 忘了 DP 表是 $i,j$ 从 $1$ 开始。

答案：A（str1[i-1]==str2[j-1]）

第 4 空

A. dp[i-1][j-1]+1
B. dp[i-1][j-1]
C. dp[i-1][j]
D. dp[i][j-1]

答案与解法

继承左上角：dp[i-1][j-1]。

易错点： 加 $1$。

答案：B（dp[i-1][j-1]）

第 5 空

A. dp[i][j] + 1
B. dp[i-1][j-1]+1
C. dp[i-1][j-1]
D. dp[i][j]

答案与解法

替换代价来自 dp[i-1][j-1]。

易错点： 选错转移。

答案：C（dp[i-1][j-1]）

考点簇7：字符串处理

这类题在考什么

字符串栈解码、指针走读：每个空对应「这里逻辑该干什么」。

这类题总陷阱

字符串解码栈空时误操作

本章知识点总述

字符串栈：遇数字入栈计数；遇 [ 保存当前串和倍数；遇 ] 弹出重复拼接。

每个空想「此时栈里应该有什么」。

真题 · 2025年完善程序第1题

完整题目（含挖空程序与选项）

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）（字符串解码）“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：i) 如果原始字符串中一个字符连续出现 $N$ 次（$N \geq 2$），在压缩字符串中它被表示为“字符 + 数字 $N$”。例如，编码 A12 代表 $12$ 个连续的字符 A。ii) 如果原始字符串中一个字符只出现 $1$ 次，在压缩字符串中它就表示为该字符本身。例如，编码 B 代表 $1$ 个字符 B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

#include <cctype>
#include <iostream>
#include <string>
using namespace std;int main() {string z;cin >> z;string s = "";for (int i = 0; i < z.length(); ) {char ch = z[i];if (__①__ && isdigit(z[i + 1])) {i++;int count = 0;while (i < z.length() && isdigit(z[i])) {count = __②__;i++;}for (int j = 0; j < __③__; ++j) {s += ch;}} else {s += __④__;__⑤__;}}cout << s << endl;return 0;
}

①处应填（）
A. i < z.length()
B. i - 1 >= 0
C. i + 1 < z.length()
D. isdigit(z[i])
②处应填（）
A. count + (z[i] - '0')
B. count * 10 + (z[i] - '0')
C. z[i] - '0'
D. count + 1
③处应填（）
A. count - 1
B. count
C. 10
D. z[i] - '0'
④处应填（）
A. z[i+1]
B. ch
C. z.back()
D. (char)z[i] + 1
⑤处应填（）
A. i--
B. i = i + 2
C. i++
D. // 不执行任何操作

程序讲解

这程序在干什么

读入压缩字符串（如 A12B），按「字符 + 重复次数」规则还原成原字符串（AAAAAAAAAAAAB）。

规则回顾

连续 $Nge2$ 次：写成「字符 + 数字 $N$」（如 A12 = $12$ 个 A）
只出现 $1$ 次：只写字符本身

关键变量

z：输入的压缩串
s：正在拼的解压结果
ch：当前字符；count：读到的重复次数

执行顺序（手算 `A12B`）

ch='A'，下一位是 1（数字）→ 读数字得 count=12，循环 $12$ 次把 A 追加
ch='B'，下一位不是数字 → 只追加一个 B，i++
输出 $12$ 个 A 加 $1$ 个 B

再试 X3Y：XXX + Y → XXXY

边界与易错点

判断数字前要先保证 i+1 没越界
读多位数用 count*10 + (z[i]-'0')，不能每次重置
重复次数是 count 次追加（编码里 $N$ 就是总次数）
单次字符分支要记得 i++，否则会死循环

第 1 空

A. i < z.length()
B. i - 1 >= 0
C. i + 1 < z.length()
D. isdigit(z[i])

答案与解法

要看 $z[i+1]$ 是否存在且是数字：i+1 < z.length()。

易错点： 不检查越界。

答案：C（i + 1 < z.length()）

第 2 空

A. count + (z[i] - '0')
B. count * 10 + (z[i] - '0')
C. z[i] - '0'
D. count + 1

答案与解法

count = count*10 + (z[i]-'0')。

易错点： 只读一位。

答案：B（count * 10 + (z[i] - '0')）

第 3 空

A. count - 1
B. count
C. 10
D. z[i] - '0'

答案与解法

追加 count 次。

易错点： 题目说 $N\ge2$ 才编码，解压 count 就是次数。

答案：B（count）

第 4 空

A. z[i+1]
B. ch
C. z.back()
D. (char)z[i] + 1

答案与解法

追加当前字符 ch。

易错点： 追加下一个字符。

答案：B（ch）

第 5 空

A. i--
B. i = i + 2
C. i++
D. // 不执行任何操作

答案与解法

处理完一个字符，i++。

易错点： 不移动 $i$ 死循环。

答案：C（i++）

考点簇8：贪心/约瑟夫/其他模拟

这类题在考什么

约瑟夫环、区间覆盖贪心、矩形计数、多数派等模拟贪心题。

这类题总陷阱

约瑟夫环出局计数和报数交替搞混
贪心区间按右端点排

本章知识点总述

约瑟夫环：报数到 $m$ 出局；用循环链表或公式模拟。

区间贪心：常按右端点排序，能选就选结束最早的。

模拟题：严格按题意更新变量，注意取模和边界。

真题 · 2025年完善程序第2题

完整题目（含挖空程序与选项）

（2）（精明与糊涂）有 $N$ 个人，分为两类：
i) 精明人：永远能正确判断其他人是精明还是糊涂；
ii)糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > N/2$。

你只能通过函数 $\text{query}(i, j)$ 让第 $i$ 个人判断第 $j$ 个人：返回 $\text{true}$ 表示判断结果为“精明人”；返回 $\text{false}$ 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百确定的精明人。同时，你无需关心 $\text{query}(i, j)$ 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选人必然属于多数派，即精明人。

例如，假设有三人 $0, 1, 2$。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;int N;
bool query(int i, int j);int main() {cin >> N;int candidate = 0;int count = __①__;for (int i = 1; i < N; ++i) {if (__②__) {candidate = i;count = 1;} else {if (__③__) {__④__;} else {count++;}}}cout << __⑤__ << endl;return 0;
}

①处应填（）
A. 0
B. 1
C. N
D. -1
②处应填（）
A. count < 0
B. count == 1
C. count == 0
D. query(candidate, i) == false
③处应填（）
A. query(candidate, i) == false
B. query(i, candidate) == true
C. query(candidate, i) == false && query(i, candidate) == false
D. query(candidate, i) == false || query(i, candidate) == false
④处应填（）
A. count--
B. break
C. count++
D. candidate = i
⑤处应填（）
A. N - 1
B. count
C. candidate
D. 0

程序讲解

这程序在干什么

有 N 个人，精明人超过一半。只能问「query(i,j)：$i$ 觉得 $j$ 是不是精明人」。程序用抵消法找出至少一个一定是精明人的候选人编号。

关键变量

candidate：当前认定的候选人（先从 $0$ 号开始）
count：候选人「净票数」，像投票抵消

执行顺序（手算 `N=3`，$0$、$1$ 互说对方糊涂）

初始 candidate=0, count=1
看 $1$ 号：count 不为 $0$，互投糊涂（两人至少一糊涂）→ count-- 变 $0$
最终输出 candidate（精明人占多数，剩下来的就是）

三人例子：若 $0$、$1$ 都说对方糊涂，则两人至少一糊涂，$2$ 号一定是精明人。

边界与易错点

初始 count=1（先假设 $0$ 号是候选）
count==0 时换人：candidate=i, count=1
抵消条件：两人至少一人说对方糊涂（用 ||）
最后输出 candidate 的编号，不是 count 也不是 N-1

第 1 空

A. 0
B. 1
C. N
D. -1

答案与解法

候选人得 $1$ 票，初值 count=1。

易错点： 从 $0$ 开始。

答案：B（1）

第 2 空

A. count < 0
B. count == 1
C. count == 0
D. query(candidate, i) == false

答案与解法

count==0 时没有支持者，换候选人。

易错点： 听 query 结果就换。

答案：C（count == 0）

第 3 空

A. query(candidate, i) == false
B. query(i, candidate) == true
C. query(candidate, i) == false && query(i, candidate) == false
D. query(candidate, i) == false || query(i, candidate) == false

答案与解法

只要有一方说对方糊涂就不可靠，用 ||：query(candidate,i)==false || query(i,candidate)==false。

易错点： 只判断单向。

答案：D（query(candidate, i) == false || query(i, candidate) == false）

第 4 空

A. count--
B. break
C. count++
D. candidate = i

答案与解法

互投反对票，count--。

易错点： count++。

答案：A（count--）

第 5 空

A. N - 1
B. count
C. candidate
D. 0

答案与解法

输出最终候选人编号 candidate。

易错点： 输出 count。

答案：C（candidate）

真题 · 2021年完善程序第1题

完整题目（含挖空程序与选项）

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）（Josephus 问题） 有 $n$ 个人围成一个圈，依次标号 $0$ 至 $n - 1$。从 $0$ 号开始，依次 $0 , 1 , 0 , 1 , \dots$ 交替报数，报到 $1$ 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

①处应填（）
A.i < n
B.c < n
C.i < n- 1
D.c < n-1
②处应填（）
A.i % 2 == 0
B.i % 2 == 1
C.p
D.!p
③处应填（）
A.i++
B.i = (i + 1) % n
C.c++
D.p ^= 1
④处应填（）
A.i++
B.i = (i + 1) % n
C.c++
D.p ^= 1
⑤处应填（）
A.i++
B.i = (i + 1) % n
C.c++
D.p ^= 1

程序讲解

这程序在干什么

$n$ 个人围成圈，编号 $0\ldots n-1$。从 $0$ 号开始按 $0,1,0,1,\ldots$ 交替报数，报到 $1$ 的人出局，直到剩 $1$ 人，输出其编号。

关键变量

F[i]：$0$ 表示还在圈里，$1$ 表示已出局
i：当前轮到谁（在圈里转圈）
p：当前这个人报的是 $0$ 还是 $1$（p 为真时报 $1$）
c：已出局人数

主循环（① `c < n-1`：要淘汰 $n-1$ 人）

若 F[i]==0（人还在）：
- 若 p 为真（② 报到 $1$）：F[i]=1 出局，c++（③）
- 否则：p ^= 1 翻转报数（④，下一个人报另一个数）
i = (i+1) % n（⑤，无论是否出局都挪到下一位）

循环结束后找唯一 F[i]==0 的 i 输出。

手算 $n=4$：按规则模拟，最后剩下的人在编号 $0$ 或 $2$ 取决于细节，关键是交替报数，不是固定奇偶位置。

边界与易错点

出局后仍要 i=(i+1)%n，不能 i++ 走出圈
判断报 $1$ 用 p，不是 i%2
出局时 c++，没出局时 p^=1，别写反

第 1 空

A. i < n
B. c < n
C. i < n - 1
D. c < n - 1

答案与解法

答案：D（c < n - 1）

第 2 空

A. i % 2 == 0
B. i % 2 == 1
C. p
D. !p

答案与解法

答案：C（p）

第 3 空

A. i++
B. i = (i + 1) % n
C. c++
D. p ^=1

答案与解法

答案：C（c++）

第 4 空

A. i++
B. i = (i + 1) % n
C. c++
D. p ^=1

答案与解法

答案：D（p ^=1）

第 5 空

A. i++
B. i = (i + 1) % n
C. c++
D. p ^=1

答案与解法

答案：B（i = (i + 1) % n）

真题 · 2021年完善程序第2题

完整题目（含挖空程序与选项）

（ 2 ）（矩形计数） 平面上有 $n$ 个关键点，求有多少个四条边都和 $x$ 轴或者 $y$ 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

①处应填 ( )
A. a.x != b.x ? a.x < b.x : a.id < b.id
B. a.x != b.x ? a.x < b.x : a.y < b.y
C. equals(a, b) ? a.id < b.id : a.x < b.x
D. equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)
②处应填 ( )
A. i == 0 || cmp(A[i], A[i - 1])
B. t == 0 || equals(A[i], A[t - 1])
C. i == 0 || !cmp(A[i], A[i - 1])
D. t == 0 || !equals(A[i], A[t - 1])
③处应填 ( )
A. b - (b - a) / 2 + 1
B. a + b + 1) >> 1
C. (a + b) >> 1
D. a + (b - a + 1) / 2
④处应填 ( )
A. !cmp(A[mid], p)
B. cmp(A[mid], p)
C. cmp(p, A[mid])
D. !cmp(p, A[mid])
⑤处应填 ( )
A. A[i].x == A[j].x
B. A[i].id < A[j].id
C. A[i].x == A[j].x && A[i].id < A[j].id
D. A[i].x < A[j].x && A[i].y < A[j].y

程序讲解

这程序在干什么

平面上给 $n$ 个关键点（可能有重复坐标），数有多少个四条边都平行坐标轴的矩形，且四个顶点都是这些点。重复坐标的点先去重，完全相同的矩形只算一次。

准备阶段

sort：按 x 升序，x 相同再按 y 升序（①）
unique：去掉坐标完全相同的点，只保留第一个（② !equals(A[i],A[t-1])）

枚举 + 二分查找

双重循环枚举对角点 A[i] 和 A[j]（⑤ 要求 A[i].x < A[j].x 且 A[i].y < A[j].y）：
轴对齐矩形的另外两个顶点应是 (A[i].x, A[j].y) 和 (A[j].x, A[i].y)。
用 binary_search 在排序后的数组里找这两个点是否都存在；都存在则 ans++。

`binary_search` 要点

在 [a,b) 上二分，mid = (a+b)>>1（③）。
若 cmp(A[mid], p) 为真（④，mid 的点「小于」目标），则 a = mid+1，否则 b = mid。最后检查 A[a] 是否与 p 坐标完全相同。

手算：四个点 `(0,0),(0,2),(2,0),(2,2)$ 构成 $1$ 个矩形；只给三个角则凑不齐。

边界与易错点

必须 x、y 都严格小于，不能只比 x 相等
去重是和上一个保留点比，不是和任意点比
二分用 cmp(A[mid],p)，不是反着写

第 1 空

A. a.x != b.x ? a.x < b.x : a.id < b.id
B. a.x != b.x ? a.x < b.x : a.y < b.y
C. equals(a, b) ? a.id < b.id : a.x < b.x
D. equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

答案与解法

答案：B（a.x != b.x ? a.x < b.x : a.y < b.y）

第 2 空

A. i == 0 || cmp(A[i], A[i - 1])
B. t == 0 || equals(A[i], A[t - 1])
C. i == 0 || !cmp(A[i], A[i - 1])
D. t == 0 || !equals(A[i], A[t - 1])

答案与解法

答案：D（t == 0 || !equals(A[i], A[t - 1])）

第 3 空

A. b - (b - a) / 2 + 1
B. (a + b + 1) >> 1
C. (a + b) >> 1
D. a + (b - a + 1) / 2

答案与解法

答案：C（(a + b) >> 1）

第 4 空

A. !cmp(A[mid], p)
B. cmp(A[mid], p)
C. cmp(p, A[mid])
D. !cmp(p, A[mid])

答案与解法

答案：B（cmp(A[mid], p)）

第 5 空

A. A[i].x == A[j].x
B. A[i].id < A[j].id
C. A[i].x == A[j].x && A[i].id < A[j].id
D. A[i].x < A[j].x && A[i].y < A[j].y

答案与解法

答案：D（A[i].x < A[j].x && A[i].y < A[j].y）

真题 · 2020年完善程序第2题

完整题目（含挖空程序与选项）

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le m$）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

   #include <iostream>using namespace std;const int MAXN = 5000;int n, m;struct segment { int a, b; } A[MAXN];void sort() // 排序{for (int i = 0; i < n; i++)for (int j = 1; j < n; j++)if (①){segment t = A[j];②}}int main(){cin >> n >> m;for (int i = 0; i < n; i++)cin >> A[i].a >> A[i]・b;sort();int p = 1;for (int i = 1; i < n; i++)if (③)A[p++] = A[i];n = p;int ans =0, r = 0;int q = 0;while (r < m){while (④)q++;⑤;ans++;}cout << ans << endl;return 0;}

1)①处应填（）

2)②处应填（）

3)③处应填（）

4)④处应填（）

5)⑤处应填（）

程序讲解

这程序在干什么

给定 $n$ 个区间 [a_i, b_i]，要选尽量少的区间，使 [0, m] 每个点都被盖住。程序先排序去重，再贪心延伸右端点 r。

第一步：排序

冒泡式 sort：按 左端点 a 从小到大排（A[j].a < A[j-1].a 时交换）。

第二步：去重保留更优

从左到右扫，若新区间 A[i].b > A[p-1].b（在同样靠前的左端点下右端更远），就保留下来，去掉被完全盖住的短区间。

第三步：贪心覆盖

r 是当前已覆盖到的最右位置，初始 $0$。
当 r < m：

指针 q 往后挪：只要「下一个区间左端 $le r$且还有下一个」，就q++`（找出所有能接上当前覆盖的候选）
在候选里选 A[q].b 最大的那个，令 r = max(r, A[q].b)
ans++

手算：要盖 [0,10]，有 [0,3],[2,6],[5,10]$。先选能接到 $0$ 且最远到 $6$ 的，r=6；再选接到 $6$ 且到 $10$ 的，ans=2`。

边界与易错点

排序按 a，不是按 b
内层 while 是让 q 停在「最后一个仍满足 A[q+1].a<=r」的位置
题目保证能盖住，所以不会死循环

第 1 空

A. A[j].b>A[j-1].b
B. A[j].a<A[j-1].a
C. A[j].a>A[j-1].a
D. A[j].b<A[j-1].b

答案与解法

答案：B（A[j].a<A[j-1].a）

第 2 空

A. A[j+1]=A[j];A[j]=t;
B. A[j-1]=A[j];A[j]=t;
C. A[j]=A[j+1];A[j+1]=t;
D. A[j]=A[j-1];A[j-1]=t;

答案与解法

答案：D（A[j]=A[j-1];A[j-1]=t;）

第 3 空

A. A[i].b>A[p-1].b
B. A[i].b<A[i-1].b
C. A[i].b>A[i-1].b
D. A[i].b<A[p-1].b

答案与解法

答案：A（A[i].b>A[p-1].b）

第 4 空

A. q+1<n&&A[q+1].a<=r
B. q+1<n&&A[q+1].b<=r
C. q<n&&A[q].a<=r
D. q<n&&A[q].b<=r

答案与解法

答案：A（q+1<n&&A[q+1].a<=r）

第 5 空

A. r=max(r,A[q+1].b)
B. r=max(r,A[q].b)
C. r=max(r,A[q+1].a)
D. q++

答案与解法

答案：B（r=max(r,A[q].b)）

查看全文

http://www.jsqmd.com/news/1289997/

基于 WebSocket 的微信双向实时通信网关设计

node-modbus-serial安全最佳实践：保护工业通信的5个关键措施

Antho-RPamide II ；pQNFHLRP-NH₂

# 卫星定位在车队管理领域的应用分析：从车辆追踪走向智能运营与数字化管理 ## 前言

Windows Subsystem for Android 终极指南：如何在Windows 11上轻松运行安卓应用

7.29学习记录20253946于新颖

lx-music-custom-source配置文件详解：3分钟搞定本地缓存与音质优化

Python数据大学生抑郁分析与预测123(设计源文件+万字报告+讲解)（支持资料、图片参考_相关定制）_

Python开发者的MediaPipe神器：从WebRTC视频流到手势识别全攻略

9大网盘直链解析终极指南：告别下载限速的完整解决方案

一键装机软件推荐：象牙装机大师凭借纯净无捆绑优势脱颖而出

阿里云服务器负载状态查询-uptime查询出load average的解释（查询等待 CPU 去处理的任务队列长度）

韩国股市暴跌近40%，AI泡沫的金丝雀已经倒下

如何使用Dontbug：PHP开发者必备的时间旅行调试指南

终极指南：gh_mirrors/do/dotfiles.zsh如何一站式配置ZSH、Java、Ruby等开发环境

Dontbug与Xdebug对比：为什么反向调试更高效？

沉迷手机、拒绝沟通？2026 湖北口碑前十叛逆学校，帮家庭解决育儿难题 - Luckyone王

Jenkins邮件通知配置：及时获取构建结果

企业级跨平台开发解决方案：ThorUI-uniapp技术架构深度解析与商业价值验证

解析房产中介APP开发的主要功能以优势

2026AI抠图工具完整指南：免费网页版、客户端、小程序实操教程 - 工具软件使用方法推荐

AI法律案例检索失效真相（最高院技术白皮书未公开的4类语义断层）

Xenon进阶功能：Idle状态与Semi-Raft Group实现跨机房容灾

CVE-2026-42533 深度技术复现：NGINX map 指令堆缓冲区溢出 RCE — 两阶段评估模型与共享捕获状态覆盖的根因分析

从Makefile混乱到优雅：mbake实战案例分享与经验总结

广州广声汽车音响怎么样？从丰田陆放升级方案看这家门店的混动车施工能力

2026AI抠图软件分端使用指南：电脑、手机、网页、小程序工具实操详解 - 工具软件使用方法推荐

车载电子产品FCC认证详解：Part 15与Part 25技术要求及测试框架

问题是结果的“价值坐标系”

单位	含义	与下一级的关系
bit（位）	最小单位，只能存 \(0\) 或 \(1\)	\(8\) bit \(= 1\) Byte
Byte（字节）	常见「一个字节」	\(1024\) Byte \(= 1\) KB
KB（千字节）	kilobyte	\(1024\) KB \(= 1\) MB
MB（兆字节）	megabyte	\(1024\) MB \(= 1\) GB
GB（吉字节）	gigabyte	更大还有 TB…