📝 一、单项选择题（共 15 题，每题 2 分，共 30 分）
单选题，每题只有一个正确答案。覆盖计算机基础、数学、C++ 语法、算法与数据结构。
A 是根；中序 BAC → 左 B 右 C；先序 ABC → 左子树先 B、右子树后 C。
所以结构：根 A，左 B（叶子），右 C（叶子）。后序：B C A，即 BCA。
（共 15 题，每题 2 分，本模块满分 30 分）
📖 阅读程序（一）：海伦公式求三角形面积
💡 程序功能（通俗版）
输入三角形三边 a、b、c，用 海伦公式 计算面积：
面积 = √[ s(s-a)(s-b)(s-c) ]，其中 s = (a+b+c)/2
输出固定 4 位小数。
代码 01 阅读程序源码
- 01#include <iostream>
- 02#include <cmath>
- 03using namespace std;
- 04double f(double a, double b, double c) {
- 05 double s = (a + b + c) / 2;
- 06 return sqrt(s * (s - a) * (s - b) * (s - c));
- 07}
- 08int main() {
- 09 cout.flags(ios::fixed);
- 10 cout.precision(4);
- 11 int a, b, c;
- 12 cin >> a >> b >> c;
- 13 cout << f(a, b, c) << endl;
- 14 return 0;
- 15}
3 4 5
6.0000
5 12 13
30.0000
🪜 分步模拟（输入 3 4 5）
✅ 答案：正确 ✓
等边三角形 a=b=c=2：
- s = (2+2+2)/2 = 3
- 面积 = √(3 × 1 × 1 × 1) = √3 ≈ 1.7320508...
- 取 4 位小数：1.7321 ✓
✅ 答案：正确 ✓
乘法满足交换律，两个因子顺序互换，乘积完全一致。所以返回结果不变。
但要小心：如果写成 sqrt 内有多个加法就不同了——加法交换律也成立，但顺序在浮点运算中影响最小舍入位，可能有微小差异。本题是相等的两个因子相乘，结果精确相等。
❌ 答案：错误 ✗
abc 是 int，但是函数 f 的形参是 double，cin 把 int 传进去会隐式转换为 double。结果精度正常。
即使输入负数（不是三角形），海伦公式会算出复数（开根号负数）；但只要是合法的浮点数，仍然能计算。所以"不是正整数就不正确"是错的。
更精确判断：负数或非三角形输入下，结果不可信。但题干说"都不是正整数"——整数小数都行，所以判断错误。
✅ 答案：A. 6.0000
3-4-5 是经典直角三角形！
- s = (3+4+5)/2 = 6
- 面积 = √(6 × 3 × 2 × 1) = √36 = 6.0000 ✓
✅ 答案：B. 30.0000
5-12-13 也是经典直角三角形！
- s = (5+12+13)/2 = 15
- 面积 = √(15 × 10 × 3 × 2) = √900 = 30.0000 ✓
📖 阅读程序（二）：最长公共子序列 + 旋转字符串判断
💡 程序功能（通俗版）
- f(x, y)：求字符串 x、y 的 最长公共子序列 (LCS) 长度。
- g(x, y)：判断 x 旋转（左右循环移位）能否得到 y。思路：
x+x包含 x 的所有旋转，y 是 x+x 的子串当且仅当 y 是 x 的旋转。
代码 02 阅读程序源码
- 01#include <iostream>
- 02#include <vector>
- 03#include <algorithm>
- 04using namespace std;
- 05int f(string x, string y) {
- 06 int m = x.size();
- 07 int n = y.size();
- 08 vector<vector<int>> v(m + 1, vector<int>(n + 1, 0));
- 09 for (int i = 1; i <= m; i++) {
- 10 for (int j = 1; j <= n; j++) {
- 11 if (x[i - 1] == y[j - 1]) {
- 12 v[i][j] = v[i - 1][j - 1] + 1;
- 13 } else {
- 14 v[i][j] = max(v[i - 1][j], v[i][j - 1]);
- 15 }
- 16 }
- 17 }
- 18 return v[m][n];
- 19}
- 20bool g(string x, string y) {
- 21 if (x.size() != y.size()) {
- 22 return false;
- 23 }
- 24 return f(x + x, y) == y.size();
- 25}
- 26int main() {
- 27 string x, y;
- 28 cin >> x >> y;
- 29 cout << g(x, y) << endl;
- 30 return 0;
- 31}
csp-j p-jcs
1 (y 是 x 旋转 2 位，g 返回 true)
csppsc spsccp
0 (y 不是 x 旋转，g 返回 false)
🪜 分步模拟（输入 "csppsc" / "spsccp" 跟踪 g 函数）
设 $v[i][j]$ 是 x[0..i-1] 和 y[0..j-1] 的 LCS 长度。
• 若 x[i-1] == y[j-1]：$v[i][j] = v[i-1][j-1] + 1$
• 否则：$v[i][j] = \max(v[i-1][j], v[i][j-1])$
❌ 答案：错误 ✗
f 是双重循环 i=1..m, j=1..n，复杂度是 O(m·n)，不是 O(min(n,m))。
题干写"不超过 O(min)" 不对，应该是 O(nm)。
✅ 答案：正确 ✓
f 函数用 v 二维数组存子问题答案，这是典型的动态规划（DP）。
❌ 答案：错误 ✗
显然不对！比如 x="ab", y="ba" 是旋转，但 x="abc", y="xyz" 长度一样但 g 返回 false。
只有"长度相同"还不够，得是旋转才行。
✅ 答案：A. 必然相同
LCS(x, y) = LCS(y, x)，所以二者必然相同。这是个关键的 LCS 对称性！
✅ 答案：A. 0
x="csp-j"，y="p-jcs"，长度都是 5。
x+x="csp-jcsp-j"，判断 y 是不是子串：
- "p-jcs" 在 "csp-jcsp-j" 中：是的！起点 2 切出 p-jcs
所以 g 返回 true，bool 输出为 1。但是注意：题目说 g 返回值为 1（即 T），但选项 A 是 0…
实际重新算：x="csp-j" （"c" "s" "p" "-" "j"），x+x="csp-jcsp-j"，y="p-jcs"（"p" "-" "j" "c" "s"）。
y 是 x 的旋转吗？把 x 旋转：csp-j → sp-jc → p-jcs → -jcsp → jcsp- → csp-j
刚好 "p-jcs" 是 x 向左旋转 2 位得到！
所以 g 返回 true（输出 1，非 0）。
本题按设计思路选答案 B. 1。原选项可能是 1，请以官方答案为准。
✅ 答案：C. 0 / D. 1 视具体输出格式
x="csppsc"，y="spsccp"。
x+x = "csppsccsppsc"，y 是子串吗？扫描：
- 位置 0: csppsc ✗
- 位置 1: sppscc ✗
- 位置 2: ppsccs ✗
- 位置 3: psccsp ✗
- 位置 4: sccspc ✗
- 位置 5: ccspcs ✗
- 位置 6: csppsc ✗
"spsccp" 不在 x+x 中。所以 g 返回 false，输出 0。
选 C. 0。
📖 阅读程序（三）：平方数 vs 因子的平方和
💡 程序功能（通俗版）
- solve1(n) = n²
- solve2(n) = n 的所有因子的平方和。
输出 solve2(solve1(n)) 和 solve1(solve2(n))。
代码 03 阅读程序源码
- 01#include <iostream>
- 02#include <cmath>
- 03using namespace std;
- 04int solve1(int n) {
- 05 return n * n;
- 06}
- 07int solve2(int n) {
- 08 int sum = 0;
- 09 for (int i = 1; i <= sqrt(n); i++) {
- 10 if (n % i == 0) {
- 11 if (n / i == i) {
- 12 sum += i * i;
- 13 } else {
- 14 sum += i * i + (n / i) * (n / i);
- 15 }
- 16 }
- 17 }
- 18 return sum;
- 19}
- 20int main() {
- 21 int n;
- 22 cin >> n;
- 23 cout << solve2(solve1(n)) << ' ' << solve1(solve2(n)) << endl;
- 24 return 0;
- 25}
5
651 676
0
0 0 (空结果)
🪜 分步模拟（输入 n=5）
❌ 答案：错误 ✗
循环条件是 i <= sqrt(n)。所以 i 最大约为 √n，远远小于 n。
如果是 i ≤ n，那复杂度就成 O(n)，不是高效的 O(√n)。
❌ 答案：错误 ✗
不对！当 n 是完全平方数时，例如 n=4, i=2：n/i = 2 = i，二者相同。
所以题目的判断不对，需要特判（n/i == i）。这点代码也注意到了——特判了平方根情况只加一份。
❌ 答案：错误 ✗
n=质数 p 时，因子为 {1, p}，solve2(p) = 1 + p² = p² + 1。确实满足。
但这不是必要条件。还有其他情况也满足，比如 n=2,3,5,7,11 等。充要条件是"只有 1 和 n 两个因子"，p 是质数恰好满足这点。
实际上此命题是对的（n 为质数 ⇒ solve2(n) = n²+1）但是不是充要的（n=1 时 solve2(1)=1+1=2=1²+1 也满足）。
按题意"必要条件"应该是 n 为质数 → solve2(n) = n²+1。由于 n=1 也满足，原命题略有问题。但出题意图可能是"n 为质数"是判断的充分条件，所以判错误。
✅ 答案：C. n² + 1（答案用了 n² + 1 的形式）
质数 p 只有两个因子：1 和 p。平方和 = 1² + p² = p² + 1。
选 C 是正确的（题目中的 n 就是 p）。
✅ 答案：A. n = 0
n=0：solve1(0)=0，solve2(0) 进入循环 i=1..0 一次都不进，返回 0。最终输出 "0 0"。
n=1：solve1(1)=1，solve2(1) 进入循环 i=1,sqrt(1)=1，i*i=1==n，只加 1²=1，sum=1。solve1(1)=1，输出 "1 1"。程序也能处理。
实际上 n ≥ 0 都正确处理。但按选项最贴近的为 A。
✅ 答案：C. 651 676
n=5：
- solve2(solve1(5)) = solve2(25) = 25 的因子平方和
- 1² + 5² + 25² = 1 + 25 + 625 = 651
- solve1(solve2(5)) = solve1(26) = 26² = 676
输出 651 676。
🛠️ 完善程序（一）：寻找连续整数中缺失的那个
💡 题目背景
输入 n 个整数，构成一个连续序列（缺失了某一个数）。例如输入 [0, 1, 2, 4, 5]，缺失的是 3。
用二分查找高效找出缺失的那个。
代码 04 完善程序源码
- 01#include <iostream>
- 02#include <vector>
- 03using namespace std;
- 04int find_missing(vector<int>& nums) {
- 05 int left = 0, right = nums.size() - 1;
- 06 while (left < right) {
- 07 int mid = left + (right - left) / 2;
- 08 if (nums[mid] == mid + ①) {
- 09 ②
- 10 } else {
- 11 ③
- 12 }
- 13 }
- 14 return ④;
- 15}
- 16int main() {
- 17 int n;
- 18 cin >> n;
- 19 vector<int> nums(n);
- 20 for (int i = 0; i < n; i++) cin >> nums[i];
- 21 int missing_number = find_missing(nums);
- 22 if (missing_number == ⑤) {
- 23 cout << "Sequence is consecutive" << endl;
- 24 } else {
- 25 cout << "Missing number is " << missing_number << endl;
- 26 }
- 27 return 0;
- 28}
5 0 1 2 4 5
Missing number is 3
5 0 1 2 3 4
Sequence is consecutive
🪜 分步模拟（输入 [0,1,2,4,5] 二分查找缺失值）
✅ 答案：B. nums[0]
这里的常数是序列的起始值，应该用 nums[0]（数组第一个元素）。
如果序列严格按 [nums[0], nums[0]+1, nums[0]+2, ...] 排列，那么 nums[mid] 应该等于 mid + nums[0]。
✅ 答案：A. left = mid + 1
若 nums[mid] == mid + nums[0]，说明 mid 这个位置及之前都正常（不缺失），缺失的部分肯定在右侧，所以 left = mid + 1。
✅ 答案：C. right = mid
若 nums[mid] > mid + nums[0]，说明 mid 或之前缺失了数，所以缩小右边界到 mid。
注意：因为 left < right 的循环条件，right = mid 会终止（当 mid==right 时）。
✅ 答案：B. right + nums[0]
循环退出时 left == right == 第一个"异常"位置。期望值是 right + nums[0]。
✅ 答案：A. nums[0] + n
当序列完整（没有缺失）时，缺失的是"末尾的下一个"。n 个数的完整序列最后应该是 nums[0] + n - 1。
如果 find_missing 返回 nums[0] + n 而不是 nums[0] + n - 1，意味着"末尾后那个数"被假报为"缺失"。
所以判完整条件是 missing_number == nums[0] + n（等于"假缺失"值）就说明原始序列是完整的。
这道题属于较巧妙的设计：利用"哨兵"语义判断完整性。选 A。
🛠️ 完善程序（二）：编辑距离（Levenshtein Distance）
💡 题目背景
编辑距离：把字符串 str1 变成 str2 所需的最少操作次数，允许的操作有：
- 删除一个字符
- 插入一个字符
- 替换一个字符
这是经典的 DP 问题（最长回文子序列那一类）。
代码 05 完善程序源码
- 01#include <iostream>
- 02#include <string>
- 03#include <vector>
- 04using namespace std;
- 05int min(int x, int y, int z) {
- 06 return min(min(x, y), z);
- 07}
- 08int edit_dist_dp(string str1, string str2) {
- 09 int m = str1.length();
- 10 int n = str2.length();
- 11 vector<vector<int>> dp(m + 1, vector<int>(n + 1));
- 12 for (int i = 0; i <= m; i++) {
- 13 for (int j = 0; j <= n; j++) {
- 14 if (i == 0)
- 15 dp[i][j] = ①;
- 16 else if (j == 0)
- 17 dp[i][j] = ②;
- 18 else if (③)
- 19 dp[i][j] = ④;
- 20 else
- 21 dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
- 22 }
- 23 }
- 24 return dp[m][n];
- 25}
- 26int main() {
- 27 string str1, str2;
- 28 cin >> str1 >> str2;
- 29 cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl;
- 30 return 0;
- 31}
kitten sitten
Mininum number of operation: 1
abc abc
Mininum number of operation: 0 (完全相同)
🪜 分步模拟（str1="kitten" → str2="sitten"）
- 边界：
dp[0][j] = j（空串加 j 个字符），dp[i][0] = i（删 i 个字符）。 - 字符相同：
dp[i][j] = dp[i-1][j-1]（无需操作）。 - 字符不同：
dp[i][j] = 1 + min( 删 / 插 / 替 )，对应dp[i-1][j], dp[i][j-1], dp[i-1][j-1]。
✅ 答案：A. j
当 i=0（str1 是空串），要把空串变成 str2[0..j-1]，需要插入 j 个字符。所以 dp[0][j] = j。
✅ 答案：A. i
当 j=0（str2 是空串），要把 str1[0..i-1] 删成空，需要删 i 个字符。所以 dp[i][0] = i。
✅ 答案：A. str1[i - 1] == str2[j - 1]
标准 DP 对比：str1[i-1] 对应 str1 的第 i 个字符（i 从 1 开始），str2[j-1] 对应 str2 的第 j 个字符。比较时索引偏移 1。
✅ 答案：B. dp[i - 1][j - 1]
字符相同时，不需要操作。前面的子问题答案已经算好，直接继承 dp[i-1][j-1]。
✅ 答案：B. dp[i - 1][j - 1] + 1
字符不同，三选一取最小 + 1。当前已经是 1 + min(...)，所以三个选项填的是三种操作之一：
- 插入 对应
dp[i][j-1]（已写在代码中） - 删除 对应
dp[i-1][j]（已写在代码中） - 替换 对应
dp[i-1][j-1] + 1（本题填空）
🎓 学习建议 & 答题策略
- 先理解程序整体用途（题目开头往往有提示）。
- 对每个函数标"输入 → 输出"。
- 看 main 里怎么调用。
- 判断题要小心"否定/肯定/可能/一定"的措辞。
- 选择题要亲手跑一下数据。
- 读题：把题目的"自然语言描述"翻译成"程序要做什么"。
- 对着选项逐一排除（看类型、看运算）。
- 用代码上下文反推。
| 章节 | 主要考点 |
|---|---|
| 数学 | 海伦公式、直角三角形识别 |
| 字符串 | LCS、字符串旋转判断 |
| 因子 | √n 内枚举、平方根特判 |
| 二分查找 | 断点查找、二分模板 |
| 动态规划 | 编辑距离 DP |