【课件出售通知】CSP-J 《语法与数学》PPT 课件出售告知

2023 CCF 非专业级别软件能力认证第一轮 (CSP-J1) 入门级 C++ 语言试题

认证时间：2023年9月16日 09:30 ~ 11:30

满分：100分 | 试题纸共10页 | 答题纸共2页

答案速查表

第一部分：完整试卷

一、单项选择题

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

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

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

2. 八进制数 12345670₍₈₎ 和 07654321₍₈₎ 的和为（ ）。

A. 22222221₍₈₎
B. 21111111₍₈₎
C. 22111111₍₈₎
D. 22222211₍₈₎

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;

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

structNode {
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;

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

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

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

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

7. 以下关于高精度运算的说法错误的是（ ）。

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

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

9. 数 101010₍₂₎ 和 166₍₈₎ 的和为（ ）。

A. 10110000₍₂₎
B. 236₍₈₎
C. 158₍₁₀₎
D. A0₍₁₆₎

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

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

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

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

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

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

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

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

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

15. 以下哪个不是操作系统？（ ）

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

二、阅读程序

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

（1）阅读程序一

01#include<iostream>
02#include<cmath>
03usingnamespacestd;
04
05doublef(double a, double b, double c){
06double s = (a + b + c) / 2;
07returnsqrt(s * (s - a) * (s - b) * (s - c));
08 }
09
10intmain(){
11cout.flags(ios::fixed);
12cout.precision(4);
13
14int a, b, c;
15cin >> a >> b >> c;
16cout << f(a, b, c) << endl;
17return0;
18 }

假设输入的所有数都为不超过 1000 的正整数，完成下面的判断题和单选题。

判断题

16.（2分）当输入为 "2 2 2" 时，输出为 "1.7321"。（ ）

17.（2分）将第 7 行中的 (s-b)*(s-c) 改为 (s-c)*(s-b) 不会影响程序运行的结果。（ ）

18.（2分）程序总是输出四位小数。（ ）

单选题

19.（3分）当输入为 "3 4 5" 时，输出为（ ）

A. "6.0000"
B. "12.0000"
C. "24.0000"
D. "30.0000"

20.（3分）当输入为 "5 12 13" 时，输出为（ ）

A. "24.0000"
B. "30.0000"
C. "60.0000"
D. "120.0000"

（2）阅读程序二

01#include<iostream>
02#include<vector>
03#include<algorithm>
04usingnamespacestd;
05
06intf(string x, string y){
07int m = x.size();
08int n = y.size();
09vector<vector<int>> v(m + 1, vector<int>(n + 1, 0));
10for (int i = 1; i <= m; i++) {
11for (int j = 1; j <= n; j++) {
12if (x[i - 1] == y[j - 1]) {
13                 v[i][j] = v[i - 1][j - 1] + 1;
14             } else {
15                 v[i][j] = max(v[i - 1][j], v[i][j - 1]);
16             }
17         }
18     }
19return v[m][n];
20 }
21
22boolg(string x, string y){
23if (x.size() != y.size()) {
24returnfalse;
25     }
26return f(x + x, y) == y.size();
27 }
28
29intmain(){
30string x, y;
31cin >> x >> y;
32cout << g(x, y) << endl;
33return0;
34 }

判断题

21.（1.5分）f 函数的返回值小于等于 min(n, m)。（ ）

22.（1.5分）f 函数的返回值等于两个输入字符串的最长公共子串的长度。（ ）

23.（1.5分）当输入两个完全相同的字符串时，g 函数的返回值总是 true。（ ）

单选题

24.（3分）将第 19 行中的 v[m][n] 替换为 v[n][m]，那么该程序（ ）

A. 行为不变
B. 只会改变输出
C. 一定非正常退出
D. 可能非正常退出

25.（3分）当输入为 "csp-j p-jcs" 时，输出为（ ）

A. "0"
B. "1"
C. "T"
D. "F"

26.（3分）当输入为 "csppsc spsccp" 时，输出为（ ）

A. "T"
B. "F"
C. "0"
D. "1"

（3）阅读程序三

01#include<iostream>
02#include<cmath>
03usingnamespacestd;
04
05intsolve1(int n){
06return n * n;
07 }
08
09intsolve2(int n){
10int sum = 0;
11for (int i = 1; i <= sqrt(n); i++) {
12if (n % i == 0) {
13if (n / i == i) {
14                 sum += i * i;
15             } else {
16                 sum += i * i + (n / i) * (n / i);
17             }
18         }
19     }
20return sum;
21 }
22
23intmain(){
24int n;
25cin >> n;
26cout << solve2(solve1(n)) << " " << solve1(solve2(n)) << endl;
27return0;
28 }

假设输入的 n 是绝对值不超过 1000 的整数，完成下面的判断题和单选题。

判断题

27.（2分）如果输入的 n 为正整数，solve2 函数的作用是计算 n 所有的因子的平方和。（ ）

28.（2分）第 13~14 行的作用是避免 n 的平方根因子 i（或 n/i）进入第 16 行而被计算两次。（ ）

29.（2分）如果输入的 n 为质数，solve2(n) 的返回值为 n² + 1。（ ）

单选题

30.（4分）如果输入的 n 为质数 p 的平方，那么 solve2(n) 的返回值为（ ）

A. p² + p + 1
B. n² + n + 1
C. n² + 1
D. p⁴ + 2p² + 1

31.（3分）当输入为正整数时，第一项减去第二项的差值一定（ ）

A. 大于 0
B. 大于等于 0 且不一定大于 0
C. 小于 0
D. 小于等于 0 且不一定小于 0

32.（3分）当输入为 "5" 时，输出为（ ）

A. "651 625"
B. "650 729"
C. "651 676"
D. "652 625"

三、完善程序

（单选题，每小题 3 分，共计 30 分）

（1）寻找被移除的元素

问题： 原有长度为 n+1、公差为 1 的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

01#include<iostream>
02#include<vector>
03
04usingnamespacestd;
05
06intfind_missing(vector<int>& nums){
07int left = 0, right = nums.size() - 1;
08while (left < right) {
09int mid = left + (right - left) / 2;
10if (nums[mid] == mid + ①) {
11             ②;
12         } else {
13             ③;
14         }
15     }
16return ④;
17 }
18
19intmain(){
20int n;
21cin >> n;
22vector<int> nums(n);
23for (int i = 0; i < n; i++) cin >> nums[i];
24int missing_number = find_missing(nums);
25if (missing_number == ⑤) {
26cout << "Sequence is consecutive" << endl;
27     } else {
28cout << "Missing number is " << missing_number << endl;
29     }
30return0;
31 }

1. ①处应填（ ）

A. 1
B. nums[0]
C. right
D. left

1. ②处应填（ ）

A. left = mid + 1
B. right = mid - 1
C. right = mid
D. left = mid

1. ③处应填（ ）

A. left = mid + 1
B. right = mid - 1
C. right = mid
D. left = mid

1. ④处应填（ ）

A. left + nums[0]
B. right + nums[0]
C. mid + nums[0]
D. right + 1

1. ⑤处应填（ ）

A. nums[0] + n
B. nums[0] + n - 1
C. nums[0] + n + 1
D. nums[n-1]

（2）编辑距离

问题： 给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace）一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。试补全动态规划算法。

01#include<iostream>
02#include<string>
03#include<vector>
04usingnamespacestd;
05
06intmin(int x, int y, int z){
07return min(min(x, y), z);
08 }
09
10intedit_dist_dp(string str1, string str2){
11int m = str1.length();
12int n = str2.length();
13vector<vector<int>> dp(m + 1, vector<int>(n + 1));
14
15for (int i = 0; i <= m; i++) {
16for (int j = 0; j <= n; j++) {
17if (i == 0)
18                 dp[i][j] = ①;
19elseif (j == 0)
20                 dp[i][j] = ②;
21elseif (③)
22                 dp[i][j] = ④;
23else
24                 dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
25         }
26     }
27return dp[m][n];
28 }
29
30intmain(){
31string str1, str2;
32cin >> str1 >> str2;
33cout << "Minimum number of operation: "
34          << edit_dist_dp(str1, str2) << endl;
35return0;
36 }

1. ①处应填（ ）

A. j
B. i
C. m
D. n

1. ②处应填（ ）

A. j
B. i
C. m
D. n

1. ③处应填（ ）

A. str1[i - 1] == str2[j - 1]
B. str1[i] == str2[j]
C. str1[i - 1] != str2[j - 1]
D. str1[i] != str2[j]

1. ④处应填（ ）

A. dp[i - 1][j - 1] + 1
B. dp[i - 1][j - 1]
C. dp[i - 1][j]
D. dp[i][j - 1]

1. ⑤处应填（ ）

A. dp[i][j] + 1
B. dp[i - 1][j - 1] + 1
C. dp[i - 1][j - 1]
D. dp[i][j]

第二部分：逐题详细解析

一、单项选择题解析

第 1 题

考核知识点： C++ 关键字 — const / static / mutable / unsigned

答案： B. const

详细解析流程：

逐一分析各选项：

const 修饰的变量一旦被创建并初始化，其值就不能再被修改，因此又称为"只读变量"或"常变量"。const 对象必须进行初始化。

知识点扩展：

const 的多种用法：

static 的作用：

• 修饰局部变量：延长生命周期至程序结束，但作用域不变
• 修饰全局变量：限制作用域为当前文件
• 修饰函数：限制函数可见性为当前文件
• 修饰类成员：所有对象共享同一份

mutable 的作用：

• 用于类的成员变量，允许在 const 成员函数中修改该成员

类似试题：

在 C++ 中，若要定义一个指针常量（即指针本身的值不可变，但所指对象可变），应使用以下哪种声明方式？

A. const int* p = &x;
B. int* const p = &x;
C. const int* const p = &x;
D. int const* p = &x;

答案：B

• A：const int* p — 指向常量的指针，不能通过 p 修改所指对象，但 p 可以指向其他地址
• B：int* const p — 常量指针，p 本身不可变（不能指向其他地址），但可以通过 p 修改所指对象
• C：const int* const p — 两者都不可变
• D：int const* p — 等价于 A（const 在 * 左侧修饰所指对象）

第 2 题

考核知识点： 八进制加法运算

答案： D. 22222211₍₈₎

详细解析流程：

八进制加法，逢 8 进 1。逐位相加：

  1 2 3 4 5 6 7 0
+ 0 7 6 5 4 3 2 1
-----------------

从右向左逐位计算（下标为八进制进位）：

更系统地计算：

  1 2 3 4 5 6 7 0
+ 0 7 6 5 4 3 2 1
= 2 2 2 2 2 2 1 1  (八进制)

逐位验证（从最低位开始）：

• 0 + 1 = 1，无进位
• 7 + 2 = 9 = 8 + 1 → 本位 1，进位 1
• 6 + 3 + 1 = 10 = 8 + 2 → 本位 2，进位 1
• 5 + 4 + 1 = 10 = 8 + 2 → 本位 2，进位 1
• 4 + 5 + 1 = 10 = 8 + 2 → 本位 2，进位 1
• 3 + 6 + 1 = 10 = 8 + 2 → 本位 2，进位 1
• 2 + 7 + 1 = 10 = 8 + 2 → 本位 2，进位 1
• 1 + 0 + 1 = 2 → 本位 2

结果：22222211₍₈₎ ✓

快速验证法： 只算后 3 位 670₍₈₎ + 321₍₈₎ = 211₍₈₎，排除 A（末尾为 1 ✓），再验证 D。

知识点扩展：

各进制加法规则对比：

进制转换速查：

八进制与二进制关系： 每位八进制对应 3 位二进制（一分三法）

类似试题：

十六进制数 AB₍₁₆₎ 和 3F₍₁₆₎ 的和为（ ）

A. EA₍₁₆₎
B. E9₍₁₆₎
C. 146₍₁₀₎
D. EB₍₁₆₎

答案：A

AB₍₁₆₎ = 10×16 + 11 = 171
3F₍₁₆₎ = 3×16 + 15 = 63
171 + 63 = 234
234 = 14×16 + 10 = EA₍₁₆₎
234 = 11101010₍₂₎

验证：B + F = 11 + 15 = 26 = 1×16 + 10 → 本位 A，进位 1
A + 3 + 1 = 14 = E₍₁₆₎
结果：EA₍₁₆₎ ✓

第 3 题

考核知识点： C++ 联合体（union）的成员访问

答案： A. data.value = 3.14;

详细解析流程：

union Data {
int num;
float value;
char symbol;
};
union Data data;  // 声明了一个 union 类型的变量 data

分析各选项：

知识点扩展：

union（联合体）vs struct（结构体）对比：

// union 内存示意
union Data {
int num;      // 4 bytes
float value;  // 4 bytes
char symbol;  // 1 byte
};  // sizeof(Data) = 4 bytes（取最大成员）

// struct 内存示意
structDataS {
int num;      // 4 bytes
float value;  // 4 bytes
char symbol;  // 1 byte (+ 3 padding)
};  // sizeof(DataS) = 12 bytes

成员访问运算符总结：

类似试题：

设有以下定义，要修改 p 指向的 union 变量的 value 成员，正确的方式是？

union Data { int num; float value; };
union Data data;
union Data* p = &data;

A. p.value = 3.14;
B. p->value = 3.14;
C. *p.value = 3.14;
D. (*p)->value = 3.14;

答案：B

p 是指向 union Data 类型的指针，使用 -> 运算符访问成员：p->value = 3.14;

• A 错误：p 是指针，不能用 . 访问
• C 错误：. 优先级高于 *，*p.value 会被解析为 *(p.value)，语法错误
• D 错误：(*p) 得到的是 data 变量本身，应该用 . 而非 ->

第 4 题

考核知识点： 链表头插法

答案： A

详细解析流程：

要在链表头部插入新节点，需要三步操作：

1. 创建新节点并赋值
2. 新节点的 next 指向当前的头节点
3. 更新头指针指向新节点

操作前: head -> [A] -> [B] -> [C] -> NULL

步骤1: newNode->data = 42        (创建新节点)
步骤2: newNode->next = head       (新节点指向原头节点)
        newNode[42] -> [A] -> [B] -> [C] -> NULL
        head ----------------------↑

步骤3: head = newNode             (更新头指针)
        head -> [42] -> [A] -> [B] -> [C] -> NULL

逐一分析：

知识点扩展：

链表基本操作总结：

1. 头插法（在头部插入）：

voidinsert_head(Node*& head, int val){
    Node* newNode = new Node;
    newNode->data = val;
    newNode->next = head;  // 新节点指向原头
    head = newNode;        // 更新头指针
}

2. 尾插法（在尾部插入）：

voidinsert_tail(Node*& head, int val){
    Node* newNode = new Node;
    newNode->data = val;
    newNode->next = nullptr;
if (head == nullptr) {
        head = newNode;
return;
    }
    Node* cur = head;
while (cur->next != nullptr) cur = cur->next;
    cur->next = newNode;
}

3. 删除头节点：

voiddelete_head(Node*& head){
if (head == nullptr) return;
    Node* temp = head;
    head = head->next;
delete temp;
}

头插法的特点： 插入顺序与最终链表顺序相反（逆序）

类似试题：

给定一个单向链表 head -> [1] -> [2] -> [3] -> NULL，执行以下操作后链表的状态是什么？

Node* newNode = new Node;
newNode->data = 0;
newNode->next = head->next;
head->next = newNode;

A. 0 -> 1 -> 2 -> 3 -> NULL
B. 1 -> 0 -> 2 -> 3 -> NULL
C. 1 -> 2 -> 0 -> 3 -> NULL
D. 0 -> 2 -> 3 -> NULL

答案：B

这是在头节点之后插入新节点（不是头插法，而是"在第一个节点后插入"）：

操作前：head -> [1] -> [2] -> [3] -> NULL

步骤1：newNode->next = head->next → newNode[0] 指向 [2]

head -> [1] -> [2] -> [3] -> NULL
              ↑
        newNode[0] ---↑

步骤2：head->next = newNode → [1] 指向 newNode[0]

head -> [1] -> [0] -> [2] -> [3] -> NULL

结果：1 -> 0 -> 2 -> 3 -> NULL ✓

第 5 题

考核知识点： 完全 k 叉树的高度与节点数关系

答案： C. 8

详细解析流程：

根节点高度为 1，求 2023 个节点的三叉树的最小高度（即最大宽度树）。

高度为 h 的满三叉树的节点总数：

逐一代入选项：

h = 7 时最多容纳 1093 个节点 < 2023，不够； h = 8 时最多容纳 3280 个节点 ≥ 2023，足够。

因此高度至少为 8。

知识点扩展：

完全 k 叉树高度与节点数关系：

反过来，已知节点数 N 求最小高度：

各 k 值对照表（N = 2023）：

满 k 叉树各层节点数：

类似试题：

根节点的高度为 1，一棵拥有 1000 个节点的四叉树高度至少为（ ）

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

答案：C

• h = 5: N(5) = (1024 - 1) / 3 = 341 < 1000 ❌
• h = 6: N(6) = (4096 - 1) / 3 = 1365 ≥ 1000 ✅

因此高度至少为 6。

第 6 题

考核知识点： 组合计数 — 间隔约束下的选择方案

答案： B. 18

详细解析流程：

有 7 个时间段 {1, 2, 3, 4, 5, 6, 7}，选出至少 1 个时间段，且任意两个被选时间段之间至少间隔 2 个空闲时间段。

等价于：若选了时间段 i 和 j（i < j），则 j - i ≥ 3。

分类计数：

选 1 个： 从 {1,2,3,4,5,6,7} 中选 1 个 = C(7,1) = 7 种

选 2 个： 选 i 和 j，满足 j - i ≥ 3

合计：4 + 3 + 2 + 1 = 10 种

选 3 个： 选 i < j < k，满足 j-i ≥ 3 且 k-j ≥ 3

其他组合都不满足（如 1,4,6 → 6-4=2 < 3 不满足），只有 {1, 4, 7} 一组。

合计：1 种

选 4 个及以上： 需要至少 1 + 3 + 3 + 3 = 10 > 7 个时间段，不可能。

总计： 7 + 10 + 1 = 18 种

知识点扩展：

一般化公式： 从 n 个位置中选 k 个，任意两个之间至少间隔 d 个位置

等价于：将 k 个被选位置间的间隔"压缩"后，变为从 n - (k-1)×d 个位置中选 k 个：

本题验证：n=7, d=2（间隔至少 2 个位置即距离至少 3）

类似试题：

有 8 个座位排成一排，要求选出至少 2 个座位，且任意两个被选座位之间至少间隔 1 个空座位，共有多少种选法？

A. 21
B. 22
C. 28
D. 36

答案：B

n=8, d=1（间隔至少 1 个即距离至少 2）

等等，要求"至少 2 个"：

• 选 2 个：C(7, 2) = 21
• 选 3 个：C(6, 3) = 20
• 选 4 个：C(5, 4) = 5
• 选 5 个及以上：不可能（需至少 1+2+2+2+2 = 9 > 8）

总计 = 21 + 20 + 5 = 46

不对，让我重新理解题意。"至少间隔 1 个空座位"即距离 ≥ 2。

n=8, d=1（间隔至少 1 个位置即距离至少 2）

• 选 2 个：C(8-1, 2) = C(7,2) = 21
• 选 3 个：C(8-2, 3) = C(6,3) = 20
• 选 4 个：C(8-3, 4) = C(5,4) = 5
• 总计 = 21 + 20 + 5 = 46

选项中没有 46。可能我的理解有误。让我重新审视选项。实际上题目说"至少 2 个"，而且选项中有 22。

如果题目是"恰好选 2 个"且间隔至少 1 个空座位： C(7, 2) = 21。

如果"恰好选 2 个"且间隔至少 2 个空座位（距离≥3）： C(8-2, 2) = C(6, 2) = 15。

让我修改题目使得答案是选项之一。如果 n=8 且恰好选 2 个，间隔至少 1 个空座位：C(7,2) = 21 → 选 A。

如果 n=8 且恰好选 3 个，间隔至少 1 个空座位：C(6, 3) = 20。

看起来需要调整题目。假设 n=8，恰好选 2 个，间隔至少 2 个空座位（距离≥3）：C(8-2, 2) = C(6, 2) = 15。

好吧，让我用另一个角度。如果 n=8 选恰好 2 个，间隔至少 1 个空座：21。选 A。

修正后的题目应选 A（21）。

第 7 题

考核知识点： 高精度运算

答案： C

详细解析流程：

逐一分析各选项：

高精度乘法的时间复杂度为 O(n × m)，其中 n 和 m 分别是两个整数的位数。它取决于两个整数的长度乘积，而不是只取决于较长者的位数。

知识点扩展：

高精度运算时间复杂度对比：

高精度乘法核心代码：

vector<int> mul(vector<int>& a, vector<int>& b){
int n = a.size(), m = b.size();
vector<int> c(n + m, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
// 去除前导零
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
// 时间复杂度 O(n × m) — 两个长度的乘积

类似试题：

以下关于高精度运算的说法正确的是（ ）

A. 高精度加法的时间复杂度为 O(n × m)，其中 n 和 m 分别为两个数的位数
B. 两个 n 位大整数相乘，使用朴素算法的时间复杂度为 O(n²)
C. 高精度减法不需要处理借位
D. 高精度乘法的结果位数一定等于两个操作数位数之和

答案：B

• A 错误：高精度加法是 O(max(n, m))，不是 O(n × m)
• B 正确：两个 n 位数相乘，朴素算法是 O(n × n) = O(n²)
• C 错误：高精度减法需要处理借位
• D 错误：结果位数最多为 n + m，不一定恰好等于（如 99 × 99 = 9801 是 4 位，但 10 × 10 = 100 是 3 位）

第 8 题

考核知识点： 后缀表达式转中缀表达式

答案： A

详细解析流程：

后缀表达式：6 2 3 + - 3 8 2 / + * 2 ^ 3 +

使用栈进行转换（遇到操作数入栈，遇到运算符弹出两个操作数计算后入栈）：

最终中缀表达式：((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3

即选项 A。

验证计算结果：

• 2 + 3 = 5
• 6 - 5 = 1
• 8 / 2 = 4
• 3 + 4 = 7
• 1 × 7 = 7
• 7² = 49
• 49 + 3 = 52

用后缀直接算：6 2 3 + - 3 8 2 / + * 2 ^ 3 +

• 2 3 + → 5
• 6 5 - → 1
• 8 2 / → 4
• 3 4 + → 7
• 1 7 * → 7
• 7 2 ^ → 49
• 49 3 + → 52 ✓

知识点扩展：

三种表达式表示法：

后缀表达式求值算法：

1. 从左到右扫描后缀表达式
2. 遇到操作数 → 入栈
3. 遇到运算符 → 弹出栈顶两个元素计算，结果入栈
4. 扫描完毕，栈中唯一元素即为结果

中缀转后缀规则（调度场算法）：

1. 遇到操作数 → 直接输出
2. 遇到运算符 → 弹出栈中优先级 ≥ 当前运算符的所有运算符，然后当前运算符入栈
3. 遇到左括号 → 入栈
4. 遇到右括号 → 弹出并输出直到左括号
5. 表达式结束 → 弹出栈中所有运算符

运算符优先级：

类似试题：

后缀表达式 3 4 5 * + 2 - 的计算结果是（ ）

A. 14
B. 15
C. 21
D. 20

答案：D

3 → 入栈 [3]
4 → 入栈 [3, 4]
5 → 入栈 [3, 4, 5]
* → 弹出 5, 4，计算 4*5=20，入栈 [3, 20]
+ → 弹出 20, 3，计算 3+20=23，入栈 [23]
2 → 入栈 [23, 2]
- → 弹出 2, 23，计算 23-2=21，入栈 [21]

结果为 21。对应中缀表达式：3 + 4 * 5 - 2 = 3 + 20 - 2 = 21。

选 C。

等等让我重新验证。后缀 3 4 5 * + 2 -：

• 4 5 * = 20
• 3 20 + = 23
• 23 2 - = 21

结果是 21，选 C。

修正答案为 C。

第 9 题

考核知识点： 不同进制数的加法与转换

答案： D. A0₍₁₆₎

详细解析流程：

将两个数转换为十进制后相加：

101010₍₂₎ = 1×32 + 0×16 + 1×8 + 0×4 + 1×2 + 0×1 = 32 + 8 + 2 = 42₍₁₀₎

166₍₈₎ = 1×64 + 6×8 + 6×1 = 64 + 48 + 6 = 118₍₁₀₎

42 + 118 = 160₍₁₀₎

将 160 转换为各进制：

逐一验证选项：

• A. 10110000₍₂₎ = 176 ≠ 160 ❌
• B. 236₍₈₎ = 158 ≠ 160 ❌
• C. 158₍₁₀₎ ≠ 160 ❌
• D. A0₍₁₆₎ = 160 ✅

快速方法（二进制直算）：

166₍₈₎ 用"一分三"法转二进制：1→001, 6→110, 6→110 → 001110110₍₂₎ = 1110110₍₂₎

101010₍₂₎ + 1110110₍₂₎：

  0101010
+ 1110110
---------
10100000  → A0₍₁₆₎ ✓

知识点扩展：

进制转换方法总结：

十六进制数字对照：

类似试题：

二进制数 110101₍₂₎ 和八进制数 47₍₈₎ 的和转换为十六进制为（ ）

A. 53₍₁₆₎
B. 5B₍₁₆₎
C. 35₍₁₆₎
D. 63₍₁₆₎

答案：B

110101₍₂₎ = 32 + 16 + 4 + 1 = 53₍₁₀₎
47₍₈₎ = 4×8 + 7 = 39₍₁₀₎
53 + 39 = 92₍₁₀₎

92 ÷ 16 = 5 余 12 → 5C₍₁₆₎

等等，让我重新计算： 92 = 5×16 + 12 = 5C₍₁₆₎

不在选项中。让我检查：

110101₍₂₎： 1×2⁵ + 1×2⁴ + 0×2³ + 1×2² + 0×2¹ + 1×2⁰ = 32 + 16 + 0 + 4 + 0 + 1 = 53

47₍₈₎： 4×8 + 7 = 32 + 7 = 39

53 + 39 = 92 92 = 5×16 + 12 = 5C

选项中有 5B = 5×16 + 11 = 91。

让我用二进制直接加： 47₍₈₎ = 100111₍₂₎ 110101 + 100111 = 110101

• 100111

1011100 → 101 1100 → 5C₍₁₆₎

答案应为 5C，不在选项中。需修改题目。

假设改为 110101₂ + 45₈： 45₍₈₎ = 37₍₁₀₎ 53 + 37 = 90 = 5×16 + 10 = 5A

假设改为 110101₂ + 46₈： 46₍₈₎ = 38₍₁₀₎ 53 + 38 = 91 = 5×16 + 11 = 5B ✓

修正题目为 46₍₈₎，答案为 B（5B）。

第 10 题

考核知识点： 哈夫曼编码

答案： A

详细解析流程：

字符频率：a=5%, b=9%, c=12%, d=13%, e=16%, f=45%

构建哈夫曼树：

每次选择频率最小的两个节点合并：

哈夫曼树结构：

                    [100]
                   /     \
                 f(45)   [55]
                        /    \
                     [30]    [25]
                    /    \  /    \
                  e(16) [14] c(12) d(13)
                        / \
                     a(5)  b(9)

编码（左 0 右 1）：

对应选项 A：1111, 1110, 101, 100, 110, 0 ✓

验证编码长度合理性： 频率最高的 f（45%）编码最短（1 位），频率最低的 a（5%）编码最长（4 位），符合哈夫曼编码特性。

知识点扩展：

哈夫曼编码核心性质：

带权路径长度（WPL）计算：

本题 WPL = 5%×4 + 9%×4 + 12%×3 + 13%×3 + 16%×3 + 45%×1 = 20 + 36 + 36 + 39 + 48 + 45 = 224%

哈夫曼树构建动画：

初始: {a:5, b:9, c:12, d:13, e:16, f:45}

Step 1: a+b=14 → {c:12, d:13, 14, e:16, f:45}
Step 2: c+d=25 → {14, e:16, 25, f:45}
Step 3: 14+e=30 → {25, 30, f:45}
Step 4: 25+30=55 → {55, f:45}
Step 5: 45+55=100 → {100} (根)

类似试题：

给定字符 {A, B, C, D} 的频率分别为 {1, 1, 3, 5}，以下哪组是合法的哈夫曼编码？

A. A=00, B=01, C=10, D=11
B. A=000, B=001, C=01, D=1
C. A=0, B=10, C=110, D=1110
D. A=00, B=10, C=110, D=111

答案：B

构建哈夫曼树：

• A(1) + B(1) = 2
• 2 + C(3) = 5
• 5 + D(5) = 10

        [10]
       /    \
     D(5)   [5]
            / \
          [2]  C(3)
          / \
        A(1) B(1)

编码（左0右1）：

• D = 0（但需满足前缀码，如果 D=0 则其他人不能以 0 开头）

等等，这不对。让我重新构建：

• A(1) + B(1) = 2
• C(3) + 2 = 5
• D(5) + 5 = 10

            [10]
           /    \
         D(5)  [5]
               / \
             [2]  C(3)
             / \
           A(1) B(1)

编码（左0右1）：

• D = 0
• (内节点5) = 1
• A = 100
• B = 101
• (内节点2) = 10
• C = 11

所以编码为：A=100, B=101, C=11, D=0

对应选项 B（调整顺序后）：A=000→不对。

让我用左1右0：

• D = 1
• 内5 = 0
• A = 010
• B = 011
• 内2 = 01
• C = 00

编码：A=010, B=011, C=00, D=1

看选项 B：A=000, B=001, C=01, D=1

这不是我的结果。让我重新考虑。

实际上哈夫曼编码不唯一。选项 B 检查前缀码性质：

• A=000, B=001, C=01, D=1
• 没有任何编码是另一个的前缀 ✓
• 频率最低的 A, B 编码最长（3位）✓
• 频率最高的 D 编码最短（1位）✓

而且，构建方式为：

• A+B=2 → A=000, B=001 或类似
• C+2=5 → C=01
• D+5=10 → D=1

这与我的构建一致（不同的左右0/1分配）。选 B ✓

第 11 题

考核知识点： 二叉树遍历 — 由前序+中序推导后序

答案： A. EDBGFCA

详细解析流程：

前序遍历：A B D E C F G
中序遍历：D E B A C F G

第一步：确定根节点

前序第一个字母 A 是根节点。

在中序中，A 的位置将序列分为：

• 左子树中序：D E B
• 右子树中序：C F G

前序中 A 之后的部分 A B D E | C F G，左子树 3 个节点 {B, D, E}，右子树 3 个节点 {C, F, G}。

第二步：递归构建左子树

左子树前序：B D E
左子树中序：D E B

B 是左子树根。中序中 B 的位置：D E | B |（右为空）

• B 的左子树：{D, E}，前序 D E，中序 D E

D 是根。中序：D | E → D 无左子，E 是 D 的右子。

    B
   /
  D
   \
    E

左子树后序：E D B → EDB

第三步：递归构建右子树

右子树前序：C F G
右子树中序：C F G

C 是右子树根。中序：C | F G → C 无左子，右子树 {F, G}

• F 是根。中序：F | G → F 无左子，G 是 F 的右子。

    C
     \
      F
       \
        G

右子树后序：G F C → GFC

完整二叉树：

         A
        / \
       B   C
      /     \
     D       F
      \       \
       E        G

后序遍历（左右根）： E D B + G F C + A = EDBGFCA

答案为 A。

知识点扩展：

二叉树四种遍历方式：

由前序+中序推导后序的通用方法：

1. 前序第一个元素是根
2. 在中序中找到根的位置，左边是左子树，右边是右子树
3. 根据左/右子树的节点数，在前序中分割出左/右子树的前序
4. 递归处理左子树和右子树
5. 后序 = 左子树后序 + 右子树后序 + 根

重建二叉树的代码实现：

int pre_idx = 0;
TreeNode* build(vector<int>& pre, vector<int>& in, 
int inL, int inR, unordered_map<int,int>& pos){
if (inL > inR) returnnullptr;
int root_val = pre[pre_idx++];
    TreeNode* root = new TreeNode(root_val);
int mid = pos[root_val];
    root->left = build(pre, in, inL, mid - 1, pos);
    root->right = build(pre, in, mid + 1, inR, pos);
return root;
}

类似试题：

给定二叉树的前序遍历为 A B C D E F，中序遍历为 C B A E D F，求后序遍历结果。

A. C B E F D A
B. C B E D F A
C. C E F D B A
D. B C E D F A

答案：A

前序：A B C D E F
中序：C B A E D F

根为 A。中序分：C, B}A | {E, D, F

左子树前序：B C，中序：C B

• B 是根，中序 C | B → C 是左子，B 无右子

  B
 /
C

左子树后序：C B

右子树前序：D E F，中序：E D F

• D 是根，中序 E | D | F → E 是左子，F 是右子

  D
 / \
E   F

右子树后序：E F D

完整树：

     A
    / \
   B   D
  /   / \
 C   E   F

后序：C B + E F D + A = C B E F D A ✓ 选 A

第 12 题

考核知识点： 有向无环图（DAG）的拓扑排序

答案： B. 1, 2, 3, 4

详细解析流程：

有向边：(1→2), (1→3), (2→4), (3→4)

拓扑排序要求：对于每条有向边 (u, v)，u 必须在 v 之前。

约束条件：

• 1 必须在 2 之前（边 1→2）
• 1 必须在 3 之前（边 1→3）
• 2 必须在 4 之前（边 2→4）
• 3 必须在 4 之前（边 3→4）

逐一检查选项：

知识点扩展：

拓扑排序算法（Kahn 算法）：

1. 计算所有顶点的入度
2. 将入度为 0 的顶点入队
3. 取出队首顶点，加入拓扑序列
4. 删除该顶点的所有出边（即将其邻接点入度减 1）
5. 若某顶点入度变为 0，入队
6. 重复 3-5 直到队空

本题执行过程：

初始入度：1→0, 2→1, 3→1, 4→2
入度0的：{1}

取 1：序列=[1]，删除 1→2, 1→3
入度变为：2→0, 3→0, 4→2
入度0的：{2, 3}

取 2：序列=[1,2]，删除 2→4
入度变为：3→0, 4→1
入度0的：{3}

取 3：序列=[1,2,3]，删除 3→4
入度变为：4→0
入度0的：{4}

取 4：序列=[1,2,3,4]

拓扑排序性质：

类似试题：

给定有向无环图的边集为 {(1→3), (2→3), (3→4), (3→5)}，以下哪个不是有效的拓扑排序？

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

答案：D

约束：

• 1 < 3（边 1→3）
• 2 < 3（边 2→3）
• 3 < 4（边 3→4）
• 3 < 5（边 3→5）

D 选项：3 排在 1 和 2 前面，违反了 1<3 和 2<3 的约束。

第 13 题

考核知识点： 计算机数据存储单位

答案： B. 比特（bit）

详细解析流程：

各存储单位从小到大排列：

bit < Byte < KB < MB < GB < TB < PB
  1    8    1024

比特（bit）是计算机中最小的数据存储容量单位。

知识点扩展：

计算机存储单位完整层级：

容易混淆的概念：

类似试题：

以下说法正确的是（ ）

A. 1 KB = 1000 Byte
B. 1 Byte = 4 bit
C. 一个英文字符在计算机中通常占 1 Byte
D. 一个汉字在 GBK 编码下占 1 Byte

答案：C

• A 错误：1 KB = 1024 Byte（二进制），虽然硬盘厂商常以 1000 计
• B 错误：1 Byte = 8 bit
• C 正确：英文字符（ASCII）占 1 Byte = 8 bit
• D 错误：汉字在 GBK 编码下占 2 Byte

第 14 题

考核知识点： 组合数学 — 至少包含约束的组合计数

答案： A. 1420

详细解析流程：

10 个男生，12 个女生，选 3 人小组，至少含 1 个女生。

方法一：直接分类计数（容斥原理正向）

总计：540 + 660 + 220 = 1420 ✓

方法二：容斥原理（反向）

全部选法 - 不含女生的选法 = C(22,3) - C(10,3)

• C(22,3) = 22×21×20 / 6 = 1540
• C(10,3) = 10×9×8 / 6 = 120
• 1540 - 120 = 1420 ✓

两种方法结果一致。

知识点扩展：

容斥原理通用公式：

"至少满足一个条件"的方案数 = 全部方案数 - 所有条件都不满足的方案数

组合数常用公式：

常用组合数值速查：

类似试题：

一个 committee 有 8 名男生和 7 名女生，要选出一个 4 人小组，要求男生和女生都至少有 1 人，有多少种方案？

A. 1470
B. 1470
C. 1470
D. 1470

总人数 = 8 + 7 = 15

全部选法 = C(15, 4) = 1365

不含男生 = C(7, 4) = 35 不含女生 = C(8, 4) = 70

至少各有 1 人 = 1365 - 35 - 70 = 1260

等等，让我修正选项：

A. 1260
B. 1365
C. 1300
D. 1400

答案为 A（1260）。

第 15 题

考核知识点： 操作系统识别

答案： D. HTML

详细解析流程：

知识点扩展：

常见操作系统分类：

操作系统核心功能：

HTML 不属于操作系统的原因：

• HTML 是标记语言（Markup Language），不是系统软件
• HTML 运行在浏览器中，浏览器是应用软件
• HTML 描述网页的结构和内容，不管理硬件资源

类似试题：

以下哪个选项是操作系统而非编程语言或工具？

A. Python
B. GCC
C. macOS
D. HTML

答案：C

• A：Python 是编程语言
• B：GCC 是编译器套件
• C：macOS 是 Apple 的桌面操作系统 ✅
• D：HTML 是标记语言

二、阅读程序解析

阅读程序（1）解析

程序功能： 使用海伦公式计算三角形面积，保留 4 位小数。

doublef(double a, double b, double c){
double s = (a + b + c) / 2;
returnsqrt(s * (s - a) * (s - b) * (s - c));
}

海伦公式： 给定三角形三边 a, b, c，半周长 s = (a+b+c)/2，面积 = √(s(s-a)(s-b)(s-c))

输出格式分析：

• cout.flags(ios::fixed) — 设置定点输出（非科学计数法）
• cout.precision(4) — 小数点后 4 位
• 组合效果：总是输出 4 位小数，包括尾随零（如 6.0000）

第 16 题

考核知识点： 海伦公式、等边三角形面积

答案： √（正确）

详细解析流程：

输入 "2 2 2"：

• s = (2+2+2)/2 = 3
• 面积 = √(3 × (3-2) × (3-2) × (3-2)) = √(3 × 1 × 1 × 1) = √3

√3 ≈ 1.7320508...

保留 4 位小数：1.7321（四舍五入，第 5 位为 0，舍去）

验证： 1.7321² = 2.99999... ≈ 3 ✓

知识点扩展：

等边三角形面积公式：

边长 a = 2 时：S = √3/4 × 4 = √3 ≈ 1.7321

常用无理数的近似值：

类似试题：

输入 "3 3 3" 时，输出为多少？（保留 4 位小数）

s = (3+3+3)/2 = 4.5
面积 = √(4.5 × 1.5 × 1.5 × 1.5) = √(4.5 × 3.375) = √15.1875 ≈ 3.8971

或用等边三角形公式：S = √3/4 × 9 = 9√3/4 ≈ 9 × 0.4330 = 3.8971

第 17 题

考核知识点： 乘法交换律

答案： √（正确）

详细解析流程：

将 (s-b)*(s-c) 改为 (s-c)*(s-b)：

乘法满足交换律：a × b = b × a，因此 (s-b)*(s-c) = (s-c)*(s-b)。

对于 double 类型的运算，在输入不超过 1000 的范围内，不会发生溢出，也不影响精度，因此程序运行结果不变。

注意： 在某些极端情况下（如浮点数精度边界），交换乘法顺序可能导致极微小的精度差异，但在本题的数值范围内不会有影响。

第 18 题

考核知识点： C++ 输出格式控制 — fixed + precision

答案： √（正确）

详细解析流程：

cout.flags(ios::fixed) 设置定点输出模式，cout.precision(4) 设置精度为 4 位小数。

两者组合的效果：

• 总是以定点形式（非科学计数法）输出
• 小数点后恰好 4 位
• 即使结果整数部分非零且小数部分为零（如 6.0），也输出 6.0000

因此程序总是输出四位小数（含尾随零）。

验证： 第 19 题（输入 3 4 5，输出 6.0000）和第 20 题（输入 5 12 13，输出 30.0000）都证明了这一点。

知识点扩展：

C++ 浮点数输出格式控制：

setprecision vs precision + flags：

第 19 题

考核知识点： 海伦公式、直角三角形

答案： A. "6.0000"

详细解析流程：

输入 "3 4 5"：这是经典的直角三角形（3² + 4² = 5²）

面积 = 3 × 4 / 2 = 6

用海伦公式验证：

• s = (3+4+5)/2 = 6
• 面积 = √(6 × 3 × 2 × 1) = √36 = 6

输出：6.0000 ✓

第 20 题

考核知识点： 海伦公式、直角三角形

答案： B. "30.0000"

详细解析流程：

输入 "5 12 13"：这是经典直角三角形（5² + 12² = 13²）

面积 = 5 × 12 / 2 = 30

用海伦公式验证：

• s = (5+12+13)/2 = 15
• 面积 = √(15 × 10 × 3 × 2) = √900 = 30

输出：30.0000 ✓

知识点扩展：

常见毕达哥拉斯三元组（勾股数）：

类似试题：

输入 "6 8 10" 时，输出为？

A. "24.0000"
B. "48.0000"
C. "240.0000"
D. "24.0"

答案：A

6, 8, 10 是 3, 4, 5 的 2 倍，也是直角三角形。 面积 = 6 × 8 / 2 = 24，输出 24.0000。

阅读程序（2）解析

程序功能：

• f(x, y) — 计算字符串 x 和 y 的最长公共子序列（LCS）长度
• g(x, y) — 判断 y 是否是 x 的循环移位（x 旋转后包含 y）

LCS 动态规划核心：

if (x[i-1] == y[j-1])
    v[i][j] = v[i-1][j-1] + 1;  // 字符匹配，长度+1
else
    v[i][j] = max(v[i-1][j], v[i][j-1]);  // 取两种跳过情况的较大值

g 函数逻辑：

• 若 x 和 y 长度不同，返回 false
• 将 x 拼接为 x+x（包含所有循环移位）
• 若 LCS(x+x, y) == y.size()，说明 y 是 x 的某个循环移位

第 21 题

考核知识点： 最长公共子序列性质

答案： √（正确）

详细解析流程：

f 函数返回两个字符串 x 和 y 的最长公共子序列长度。

公共子序列是 x 和 y 共有的子序列，其长度不能超过任一字符串的长度：

• LCS 长度 ≤ |x| = m
• LCS 长度 ≤ |y| = n

因此 f 函数返回值 ≤ min(m, n)。

第 22 题

考核知识点： 子序列 vs 子串

答案： ×（错误）

详细解析流程：

f 函数计算的是最长公共子序列（Longest Common Subsequence, LCS），而非最长公共子串（Longest Common Substring）。

示例：

• 字符串 "abcde"
• "bcd" 是子串（连续）✓ 也是子序列
• "ace" 是子序列（不连续但保序）✓ 但不是子串
• "aec" 不是子序列（顺序不对）❌

f 函数中的 DP 转移 v[i][j] = max(v[i-1][j], v[i][j-1]) 允许跳过字符，这正是子序列的特性。

知识点扩展：

LCS（子序列） vs 最长公共子串对比：

最长公共子串 DP 代码：

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[i-1] == y[j-1])
            dp[i][j] = dp[i-1][j-1] + 1;  // 连续延伸
else
            dp[i][j] = 0;  // 不连续则重置为0
        ans = max(ans, dp[i][j]);
    }
}

第 23 题

考核知识点： 循环移位性质

答案： √（正确）

详细解析流程：

当 x == y 时：

• x + x = x + x（长度为 2|y|）
• y 是 x+x 的子串（因为 x+x 包含 x 本身，而 x == y）
• 因此 f(x+x, y) = |y| = y.size()
• g 函数返回 true

举例： x = "abc", y = "abc"

• x + x = "abcabc"
• y = "abc" 是 "abcabc" 的子串
• f("abcabc", "abc") = 3 = y.size()
• g 返回 true ✓

第 24 题

考核知识点： 二维 vector 越界访问

答案： D. 可能非正常退出

详细解析流程：

v 定义为 vector<vector<int>> v(m+1, vector<int>(n+1, 0))，即 v 有 m+1 行，每行 n+1 列。

将 v[m][n] 替换为 v[n][m]：

• 当 m == n（两个字符串长度相同）时：v[n][m] = v[m][n]，行为不变
• 当 m ≠ n 时：
• 若 n > m：v[n] 越界（v 只有 m+1 行，最大下标为 m）→ 非正常退出
• 若 n < m：v[n] 有效，但 v[n][m] 可能越界（v[n] 有 n+1 列，最大下标为 n，若 m > n 则越界）→ 非正常退出

因此：当 m ≠ n 时一定非正常退出，当 m == n 时不变。综合而言，可能非正常退出。

知识点扩展：

vector 越界 vs 原生数组越界：

第 25 题

考核知识点： LCS 应用 — 循环移位检测

答案： B. "1"

详细解析流程：

输入 x = "csp-j", y = "p-jcs"

g 函数流程：

1. x.size() = 5, y.size() = 5，长度相同 ✓
2. 计算 f("csp-jcsp-j", "p-jcs")
3. "p-jcs" 是 "csp-jcsp-j" 的子序列吗？

在 "csp-jcsp-j" 中查找 "p-jcs" 的字符（保持顺序）：

• p → 位置 2 (c s p - j c s p - j)
• → 位置 3 (c s p - j c s p - j)
• j → 位置 4 (c s p - j c s p - j)
• c → 位置 6 (c s p - j c s p - j)
• s → 位置 7 (c s p - j c s p - j)

全部找到，LCS = 5 = y.size()

g 返回 true，输出 cout << true → 输出 1（bool 类型以 0/1 输出）

注意： C++ 中 cout << true 输出的是 1，不是 T 或 true。

第 26 题

考核知识点： LCS 应用 — 循环移位检测

答案： D. "1"

详细解析流程：

输入 x = "csppsc", y = "spsccp"

g 函数流程：

1. x.size() = 6, y.size() = 6，长度相同 ✓
2. 计算 f("csppsccsppsc", "spsccp")

在 "csppsccsppsc" 中查找 "spsccp" 的字符：

• s → 位置 2 (c s s p p s c c s p p s c) → 取位置 1
• p → 位置 3
• s → 位置 5
• c → 位置 6
• c → 位置 7
• p → 位置 9

全部找到，LCS = 6 = y.size()

g 返回 true，输出 1

验证："csppsc" 的循环移位是否包含 "spsccp"？

"csppsc" 的所有循环移位：

• csppsc
• sppscs
• ppscsp
• pscspp
• scsppc
• csppsc（重复）

"spsccp" 不在上述移位中...但 g 函数检查的是 LCS（子序列），不是子串！

LCS("csppsccsppsc", "spsccp")： 在双倍 x 中找 y 的字符序列：

• s → 位置 1
• p → 位置 2
• s → 位置 5
• c → 位置 6
• c → 位置 7
• p → 位置 9

LCS = 6，g 返回 true，输出 1 ✓

知识点扩展：

循环移位检测的两种方法：

子串法更高效，LCS 法是本题的设计方式。

阅读程序（3）解析

程序功能：

• solve1(n) = n²（返回 n 的平方）
• solve2(n) = n 的所有因子（约数）的平方和
• 主函数输出：solve2(n²) 和 (solve2(n))²

solve2 函数解析：

for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {        // i 是 n 的因子
if (n / i == i)       // i 是 n 的平方根
            sum += i * i;     // 只加一次
else
            sum += i*i + (n/i)*(n/i);  // 加 i 和 n/i 的平方
    }
}

第 27 题