试卷解析 · 理解每一步

2023 CCF CSP-J 第一轮（入门级 C++）

CSPJ-2023-R1

试卷解析总览，可直接查看每题答案与解析。

一、单项选择题

第 1 题（单选题，2 分）

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

unsigned

const

static

mutable

正确答案B

解析详情

答案 BC++ 常量声明

思路与推导

const 用于限定对象不可通过该变量名被修改，例如 const int x = 1; 之后不能再给 x 赋值。unsigned 只改变整数的取值范围，static 改变存储期或链接属性，均不表示只读。

第 2 题（单选题，2 分）

八进制数 $12345670_8$ 和 $07654321_8$ 的和为（）。

22222221_8

21111111_8

22111111_8

22222211_8

正确答案D

解析详情

答案 D八进制加法

思路与推导

按八进制逐位相加，满 8 向高位进 1： $12345670_8 + 07654321_8 = 22222211_8$ 。因此应选写作 $22222211_8$ 的 D。

第 3 题（单选题，2 分）

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

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

data.value = 3.14;

value.data = 3.14;

data->value = 3.14;

value->data = 3.14;

正确答案A

解析详情

答案 A联合体成员访问

思路与推导

data 是 Data 类型的对象而不是指针，对象成员应使用点运算符访问，所以赋值语句是 data.value = 3.14;。只有指向 Data 的指针才使用 ->。

第 4 题（单选题，2 分）

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

struct Node {
    int data;
    Node* next;
};

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

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

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

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

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

正确答案A

解析详情

答案 A单链表头插法

思路与推导

先令 newNode->data = 42，再让 newNode->next 指向原头节点 head，最后执行 head = newNode。这样新节点既连接了原链表，又成为新的首节点。

第 5 题（单选题，2 分）

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

正确答案C

解析详情

答案 C满三叉树节点数

思路与推导

高度为 h 的三叉树最多有 1+3+⋯+3^(h-1)=(3^h-1)/2 个节点。h=7 时最多 1093 个，不足 2023 个；h=8 时最多 3280 个，因此最小高度为 8。

第 6 题（单选题，2 分）

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

正确答案B

解析详情

答案 B有限制的组合计数

思路与推导

选 1 段有 7 种；选 2 段且编号至少相差 3，有 C(5,2)=10 种；选 3 段只有 {1,4,7} 这 1 种。至少选一段，共 7+10+1=18 种。

第 7 题（单选题，2 分）

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

高精度计算主要是用来处理大整数或需要保留多位小数的运算。

大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。

高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。

高精度加法运算的关键在于逐位相加并处理进位。

正确答案C

解析详情

答案 C高精度运算复杂度

思路与推导

朴素高精度乘法要让一个数的每一位与另一个数的每一位相乘，两个数分别有 m、n 位时，时间量级通常为 O(mn)。它同时取决于两者的位数，而不是只由较长者的位数决定，所以 C 错误。

第 8 题（单选题，2 分）

后缀表达式 “6 2 3 + - 3 8 2 / + * 2 ^ 3 +” 对应的中缀表达式是（）。

(6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3

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

解析详情

答案 A后缀表达式求值栈

思路与推导

依次合并操作数可得 6-(2+3) 和 3+8/2，随后 * 将两部分相乘，2 ^ 对整个乘积平方，最后再 +3。对应式为 ((6-(2+3))*(3+8/2))^2+3，即 A 所表达的结构。

第 9 题（单选题，2 分）

数 $101010_{2}$ 和 $166_{8}$ 的和为（）。

10110000_{2}

236_{8}

158_{10}

A0_{16}

正确答案D

解析详情

答案 D不同进制数转换与加法

思路与推导

101010₂=42，166₈=1×64+6×8+6=118，两数之和为 160。160=10×16+0，因此十六进制表示为 A0₁₆。

第 10 题（单选题，2 分）

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

1111, 1110, 101, 100, 110, 0

1010, 1001, 1000, 011, 010, 00

000, 001, 010, 011, 10, 11

1010, 1011, 110, 111, 00, 01

正确答案A

解析详情

答案 A哈夫曼编码

思路与推导

按频率从小到大合并：5+9=14，12+13=25，14+16=30，25+30=55，最后 45+55=100。因此 f 的码长为 1，a、b 的码长为 4，c、d、e 的码长为 3；A 的码长分布及前缀关系均符合。

第 11 题（单选题，2 分）

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

EDBGFCA

EDBGCFA

DEBGFCA

DBEGFCA

正确答案A

解析详情

答案 A二叉树遍历序列还原

思路与推导

前序首字符 A 是根，中序将其分成左子树 DEB 和右子树 CFG。左子树后序为 EDB，右子树后序为 GFC，最后访问根 A，得到 EDBGFCA。
（注：原卷选项 A 印制为 EDBFGCA，系原题笔误，此处已更正为正确后序 EDBGFCA）

第 12 题（单选题，2 分）

考虑一个有向无环图，该图包含 4 条有向边: $(1,2)$ ， $(1,3)$ ， $(2,4)$ 和 $(3,4)$ 。以下哪个

选项是这个有向无环图的一个有效的拓扑排序？（）

4, 2, 3, 1

1, 2, 3, 4

1, 2, 4, 3

2, 1, 3, 4

正确答案B

解析详情

答案 B有向无环图的拓扑排序

思路与推导

边 (1,2)、(1,3) 要求 1 位于 2、3 之前，边 (2,4)、(3,4) 又要求 4 位于 2、3 之后。序列 1,2,3,4 满足全部先后约束。

第 13 题（单选题，2 分）

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

字节（byte）

比特（bit）

字（word）

千字节（kilobyte）

正确答案B

解析详情

答案 B计算机存储单位

思路与推导

比特 bit 是一个二进制位，只能表示 0 或 1；1 byte=8 bit，word 通常包含若干字节，1 KB 也远大于 1 byte。因此四者中 bit 最小。

第 14 题（单选题，2 分）

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

1420

1770

1540

2200

正确答案A

解析详情

答案 A组合计数与补集

思路与推导

先从 22 人中任选 3 人，共 C(22,3)=1540 种；再减去全是男生的 C(10,3)=120 种。至少有 1 名女生的方案数为 1540-120=1420。

第 15 题（单选题，2 分）

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

Linux

Windows

Android

HTML

正确答案D

解析详情

答案 D操作系统与标记语言

思路与推导

Linux、Windows 和 Android 都是操作系统；HTML 是用于描述网页结构的超文本标记语言，不负责进程、内存和设备等操作系统资源管理。

二、阅读程序（1）

 1 | #include <iostream>
 2 | #include <cmath>
 3 | using namespace std;
 4 |
 5 | double f(double a, double b, double c) {
 6 |     double s = (a + b + c) / 2;
 7 |     return sqrt(s * (s - a) * (s - b) * (s - c));
 8 | }
 9 |
10 | int main() {
11 |     cout.flags(ios::fixed);
12 |     cout.precision(4);
13 |
14 |     int a, b, c;
15 |     cin >> a >> b >> c;
16 |     cout << f(a, b, c) << endl;
17 |     return 0;
18 | }

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

第 16 题（判断题，2 分）

当输入为 “2 2 2” 时，输出为 “1.7321”。（）

正确答案正确

解析详情

答案正确海伦公式与浮点输出

思路与推导

输入 2,2,2 时，变量 s=(2+2+2)/2=3。面积计算公式为 sqrt(3*(3-2)*(3-2)*(3-2)) = sqrt(3) ≈ 1.7320508。代码中通过 cout << fixed << setprecision(4) 会对该浮点数进行四舍五入并保留四位小数，因此输出确为 1.7321，结论正确。

第 17 题（判断题，2 分）

将第 7 行中的 “ $(s - b)$ * $(s - c)$ ” 改为 “ $(s - c)$ * $(s - b)$ ” 不会影响程序运行的结果。（）

正确答案正确

解析详情

答案正确乘法交换律

思路与推导

(s-b) 与 (s-c) 都是 double 表达式，只交换这两个乘法因子的顺序，数学乘积及本程序的计算结果不变。

第 18 题（判断题，2 分）

程序总是输出四位小数。（）

正确答案错误

解析详情

答案错误浮点格式与非法三角形输入

思路与推导

fixed 与 precision(4) 会让正常有限浮点数显示 4 位小数，但题目只保证输入为正整数，并未保证三边能组成三角形。若根号内为负数，sqrt 会产生 nan，输出就不是四位小数形式。

第 19 题（单选题，3 分）

当输入为 “3 4 5” 时，输出为（）。

“6.0000”

“12.0000”

“24.0000”

“30.0000”

正确答案A

解析详情

答案 A海伦公式

思路与推导

输入 3,4,5 时 s=(3+4+5)/2=6，面积为 sqrt(6×3×2×1)=sqrt(36)=6。按 4 位小数输出为 6.0000。

第 20 题（单选题，3 分）

当输入为 “5 12 13” 时，输出为（）。

“24.0000”

“30.0000”

“60.0000”

“120.0000”

正确答案B

解析详情

答案 B海伦公式

思路与推导

输入 5,12,13 时 s=15，面积为 sqrt(15×10×3×2)=sqrt(900)=30。程序最终输出 30.0000。

二、阅读程序（2）

 1 | #include <iostream>
 2 | #include <vector>
 3 | #include <algorithm>
 4 | using namespace std;
 5 |
 6 | int f(string x, string y) {
 7 |     int m = x.size();
 8 |     int n = y.size();
 9 |     vector<vector<int>> v(m+1, vector<int>(n+1, 0));
10 |     for (int i = 1; i <= m; i++) {
11 |         for (int j = 1; j <= n; j++) {
12 |             if (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 |     }
19 |     return v[m][n];
20 | }
21 |
22 | bool g(string x, string y) {
23 |     if (x.size() != y.size()) {
24 |         return false;
25 |     }
26 |     return f(x + x, y) == y.size();
27 | }
28 |
29 | int main() {
30 |     string x, y;
31 |     cin >> x >> y;
32 |     cout << g(x, y) << endl;
33 |     return 0;
34 | }

第 21 题（判断题，1.5 分）

f 函数的返回值小于等于 $\min(n, m)$ 。（）

正确答案正确

解析详情

答案正确最长公共子序列长度上界

思路与推导

函数 f(x, y) 使用二维动态规划 v[i][j] 计算两字符串的最长公共子序列（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])。因 LCS 的长度受限于两字符串长度的最小值，故算法返回值必然 ≤ min(x.size(), y.size())，即 min(n, m)，结论正确。

第 22 题（判断题，1.5 分）

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

正确答案错误

解析详情

答案错误子序列与子串的区别

思路与推导

程序状态转移 v[i][j] = max(v[i-1][j], v[i][j-1]) 表明当字符不匹配时，它允许跳过 x 或 y 中的字符继续匹配。这正是“最长公共子序列”（LCS，元素不要求连续）的典型 DP 转移方程，而“最长公共子串”（要求元素连续）当不匹配时需将状态清零，两者定义与状态转移完全不同。

第 23 题（判断题，1.5 分）

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

正确答案正确

解析详情

答案正确最长公共子序列与字符串判等

思路与推导

当 x==y 时两者长度相等，而且 y 本身就是 x+x 的一个子序列，所以 f(x+x,y)=y.size()。g 的两个判断均通过，返回 true。

第 24 题（单选题，3 分）

将第 19 行中的 “v[m][n]” 替换为 “v[n][m]”，那么该程序（）。

行为不变

只会改变输出

一定非正常退出

可能非正常退出

正确答案D

解析详情

答案 D二维 vector 下标越界

思路与推导

v 有 m+1 行、每行 n+1 列，合法的最终位置是 v[m][n]。改成 v[n][m] 后，m≠n 时至少一个下标可能越界，产生未定义行为并可能非正常退出；m=n 时访问位置不变。

第 25 题（单选题，3 分）

当输入为 “csp-j p-jcs” 时，输出为（）。

“0”

“1”

“T”

“F”

正确答案B

解析详情

答案 B循环移位与布尔输出

思路与推导

p-jcs 是 csp-j 的循环移位，可在 csp-jcsp-j 中连续找到，因此也是其长度为 5 的公共子序列。f 返回 5，g 返回 true；未启用 boolalpha 时 true 输出为 1。

第 26 题（单选题，3 分）

当输入为 “csppsc spsccp” 时，输出为（）。

“T”

“F”

“0”

“1”

正确答案D

解析详情

答案 D最长公共子序列造成的判定偏差

思路与推导

在 csppsccsppsc 中，可依次取下标对应字符 s、p、s、c、c、p，组成完整的 spsccp。因此 f 返回 6，g 返回 true，程序输出 1；这也说明 g 实际可能把非循环移位串判为真。

二、阅读程序（3）

 1 | #include <iostream>
 2 | #include <cmath>
 3 | using namespace std;
 4 |
 5 | int solve1(int n) {
 6 |     return n * n;
 7 | }
 8 |
 9 | int solve2(int n) {
10 |     int sum = 0;
11 |     for (int i = 1; i <= sqrt(n); i++) {
12 |         if (n % i == 0) {
13 |             if (n / i == i)
14 |                 sum += i * i;
15 |             else
16 |                 sum += i * i + (n / i) * (n / i);
17 |         }
18 |     }
19 |     return sum;
20 | }
21 |
22 | int main() {
23 |     int n;
24 |     cin >> n;
25 |     cout << solve2(solve1(n)) << " " << solve1(solve2(n)) << endl;
26 |     return 0;
27 | }

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

第 27 题（判断题，1.5 分）

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

正确答案正确

解析详情

答案正确因数成对枚举及复杂度分析

思路与推导

函数 solve2(n) 求解 n 的所有因数的平方和。通过 for 循环以 i*i <= n 为界（复杂度 O(sqrt(n))）枚举。若 n%i==0，则找到因数 i 及 n/i。`sum += i*i` 累加较小因数的平方；当 i*i != n 即非平方根时，else 分支 `sum += (n/i)*(n/i)` 累加配对大因数的平方。完全平方数的平方根仅在 if 判定后计算一次，完美覆盖所有因数且无遗漏与重复。

第 28 题（判断题，1.5 分）

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

正确答案正确

解析详情

答案正确完全平方数的因数配对

思路与推导

当 n/i==i 时，i 正是 n 的平方根，因数对 (i,n/i) 的两个值相同。此时只执行 sum += i*i，可避免在 else 分支把同一个因数平方加两次。

第 29 题（判断题，1.5 分）

如果输入的 n 为质数， $\text{solve}_2(n)$ 的返回值为 $n^2 + 1$ 。（）

正确答案正确

解析详情

答案正确质数的因数

思路与推导

质数 n 的正因数只有 1 和 n。solve2 将它们的平方相加，返回 1²+n²=n²+1。

第 30 题（单选题，4 分）

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

p^{2}+p+1

n^{2}+n+1

n^{2}+1

p^{4}+2p^{2}+1

正确答案B

解析详情

答案 B质数平方的因数平方和

思路与推导

若 n=p²，则 n 的正因数为 1、p、p²。solve2(n)=1+p²+p⁴；又因 p²=n、p⁴=n²，所以结果为 n²+n+1。

第 31 题（单选题，3 分）

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

大于 0

大于等于 0 且不一定大于 0

小于 0

小于等于 0 且不一定小于 0

正确答案D

解析详情

答案 D因数平方和函数比较

思路与推导

两项之差是 solve2(n²)-solve2(n)²。把 solve2(n)² 展开为所有因数平方的两两乘积后，它覆盖 solve2(n²) 中的各项且可能重复，故差值≤0；n=1 时两项都为 1，差值等于 0。

第 32 题（单选题，3 分）

当输入为 “5” 时，输出为（）。

“651 625”

“650 729”

“651 676”

“652 625”

正确答案C

解析详情

答案 C函数嵌套调用与因数平方和

思路与推导

solve1(5)=25，solve2(25)=1²+5²+25²=651；solve2(5)=1²+5²=26，再算 solve1(26)=26²=676。因此输出 651 676。

三、完善程序（1）寻找被移除的元素

（寻找被移除的元素）问题：原有长度为 $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;
}

第 33 题（单选题，3 分）

①处应填（）

1

nums[0]

right

left

正确答案B

解析详情

答案 B等差数列二分查找边界

思路与推导

数组原应是公差为 1 的等差连续序列。若某位置 mid 前无缺失，应满足 nums[mid] == nums[0] + mid。因此 ① 处需填入 nums[0] 以补齐起点偏移量，用以判断 mid 是否仍处于前缀的连续正常段。若等式成立，说明缺口在 mid 之后。

第 34 题（单选题，3 分）

②处应填（）

left = mid + 1

right = mid - 1

right = mid

left = mid

正确答案A

解析详情

答案 A二分查找区间收缩策略

思路与推导

当 nums[mid] == nums[0] + mid 成立时，意味着从 nums[0] 到 nums[mid] 完全连续无缺口，缺失的元素必定在下标 mid 之后。因此应将二分查找的左边界更新为 mid + 1，即缩小搜索范围至 [mid+1, right]。选项 A 正确。

第 35 题（单选题，3 分）

③处应填（）

left = mid + 1

right = mid - 1

right = mid

left = mid

正确答案C

解析详情

答案 C二分查找下界

思路与推导

当 nums[mid]≠nums[0]+mid 时，缺失元素位于 mid 之前或正好导致 mid 首次错位，因此 mid 仍可能是目标边界，必须保留它并令 right=mid。

第 36 题（单选题，3 分）

④处应填（）

left + nums[0]

right + nums[0]

mid + nums[0]

right + 1

正确答案A

解析详情

答案 A由缺失下标还原数值

思路与推导

二分结束时 left 是第一个不符合 nums[i]=nums[0]+i 的下标。公差为 1，因此该位置原本应有的数就是 nums[0]+left，即 left+nums[0]。

第 37 题（单选题，3 分）

⑤处应填（）

nums[0]+n

nums[0]+n-1

nums[0]+n+1

nums[n-1]

正确答案D

解析详情

答案 D连续数组的边界判定

思路与推导

若现有 nums 完全连续，二分最终令 left=n-1，find_missing 返回 nums[0]+n-1，恰好等于 nums[n-1]。因此用 missing_number==nums[n-1] 判定程序没有发现内部缺口。

三、完善程序（2）编辑距离

(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] = ④;
            else
                dp[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 << "Minimum number of operations: "
         << edit_dist_dp(str1, str2) << endl;
    return 0;
}

第 38 题（单选题，3 分）

①处应填（）

j

i

m

n

正确答案A

解析详情

答案 A编辑距离动态规划状态初始化

思路与推导

dp[i][j] 表示 str1 前 i 个字符转换为 str2 前 j 个字符的最小操作数。当 i=0 时，str1 的前缀为空，要将其变为长度为 j 的 str2 前缀，只能通过执行 j 次插入操作。因此对于 dp[0][j] 这个边界状态，其操作次数即为 j，故 ① 处应填 j。

第 39 题（单选题，3 分）

②处应填（）

j

i

m

n

正确答案B

解析详情

答案 B编辑距离动态规划初始化

思路与推导

当 j=0 时，目标字符串前缀为空，需要删除 str1 前 i 个字符，操作次数为 i。因此 dp[i][0]=i，②应填 i。

第 40 题（单选题，3 分）

③处应填（）

str1[i - 1] == str2[j - 1]

str1[i] == str2[j]

str1[i - 1] != str2[j - 1]

str1[i] != str2[j]

正确答案A

解析详情

答案 A编辑距离状态转移条件

思路与推导

dp[i][j] 表示 str1 前 i 个字符与 str2 前 j 个字符的编辑距离，当前末字符的下标分别是 i-1、j-1。两字符相等时无需新增操作，所以条件是 str1[i-1]==str2[j-1]。

第 41 题（单选题，3 分）

④处应填（）

dp[i - 1][j - 1] + 1

dp[i - 1][j - 1]

dp[i - 1][j]

dp[i][j - 1]

正确答案B

解析详情

答案 B编辑距离相同字符转移

思路与推导

当 str1[i-1]==str2[j-1] 时，两个前缀的末字符可以直接匹配，不产生编辑操作。于是 dp[i][j] 继承去掉这两个末字符后的 dp[i-1][j-1]。

第 42 题（单选题，3 分）

⑤处应填（）

dp[i][j] + 1

dp[i - 1][j - 1] + 1

dp[i - 1][j - 1]

dp[i][j]

正确答案C

解析详情

答案 C编辑距离三种操作的状态转移

思路与推导

当两字符不同时，可通过三种基本操作转移：1) 插入(对应 dp[i][j-1])；2) 删除(对应 dp[i-1][j])；3) 替换(对应 dp[i-1][j-1])。因为最外层已经有 +1(代表本次操作代价)，因此求 min 时，三个候选项必须是转移前状态本身的值。⑤ 处应为替换操作对应的前置状态 dp[i-1][j-1]，选项 C 正确。