GESP 客观题评测系统

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

CSPJ-2023-R1

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

一、单项选择题

第 1 题（单选题，2 分）

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

unsigned

const

static

mutable

正确答案B

解析详情

【答案】B

【考点】C++ 常量声明

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

【易错点】不要把 static 的“长期存在”误解为“值不能改变”。

第 2 题（单选题，2 分）

八进制数123456708和076543218的和为（）。

222222218

211111118

221111118

222222118

正确答案D

解析详情

【答案】D

【考点】八进制加法

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

【易错点】八进制中 7 + 2 = 11₈，需要写 1 并向前进 1。

第 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。这样新节点既连接了原链表，又成为新的首节点。

【易错点】只设置 newNode->next 而不更新 head，新节点不会成为链表头。

第 5 题（单选题，2 分）

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

正确答案C

解析详情

【答案】C

【考点】满三叉树节点数

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

【易错点】题目规定根节点高度为 1，不能把根所在层记为第 0 层。

第 6 题（单选题，2 分）

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

正确答案B

解析详情

【答案】B

【考点】有限制的组合计数

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

【易错点】 “之间至少两个空闲时间段”表示所选编号之差至少为 3。

第 7 题（单选题，2 分）

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

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

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

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

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

正确答案C

解析详情

【答案】C

【考点】高精度运算复杂度

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

【易错点】高精度加法的 O(max(m,n)) 不能直接套用于乘法。

第 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。请问这棵树的正确后序遍历结果是什么？（）

EDBFGCA

EDBGCFA

DEBGFCA

DBEGFCA

正确答案A

解析详情

【答案】A

【考点】二叉树遍历序列还原

【解析】前序首字符 A 是根，中序将其分成左子树 DEB 和右子树 CFG。左子树后序为 EDB，右子树后序为 GFC，最后访问根 A，得到 EDBGFCA。

【易错点】后序遍历顺序是“左—右—根”，根 A 必须放在最后。

第 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 最小。

【易错点】 bit 与 byte 名称相近，但 byte 不是一个二进制位。

第 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。

【易错点】 “至少 1 名女生”包含 1、2、3 名女生，用补集计算更简洁。

第 15 题（单选题，2 分）

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

Linux

Windows

Android

HTML

正确答案D

解析详情

【答案】D

【考点】操作系统与标记语言

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

【易错点】能在计算机或手机上使用的技术名称不一定就是操作系统。

二、阅读程序（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 的正整数，完成下面的判断题和单选题：

第 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，结论正确。

【易错点】注意 fixed 配合 setprecision 才会严格控制小数点后的位数，且会自动进行四舍五入操作。

第 17 题（判断题，2 分）

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

正确答案正确

解析详情

【答案】正确

【考点】乘法交换律

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

【易错点】这里交换的是同一连乘式中的两个因子，并未改变减法内部的操作数顺序。

第 18 题（判断题，2 分）

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

正确答案错误

解析详情

【答案】错误

【考点】浮点格式与非法三角形输入

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

【易错点】输出格式设置不能保证 nan、inf 等特殊浮点值也带 4 位小数。

第 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。

【易错点】海伦公式计算的是面积，不是三角形周长 12。

第 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。

【易错点】 5、12、13 是直角三角形，面积是 5×12÷2=30，而不是两直角边之积 60。

二、阅读程序（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;
}

第 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。

【易错点】 f 的第一个参数虽然变成 x+x，但这不会妨碍完整匹配其中的一份 x。

第 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。

【易错点】 cout 默认把 bool 输出为 0 或 1，而不是字符串 true 或 T。

第 26 题（单选题，3 分）

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

“T”

“F”

“0”

“1”

正确答案D

解析详情

【答案】D

【考点】最长公共子序列造成的判定偏差

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

【易错点】 f 检查的是子序列而非连续子串，字符之间可以被跳过。

二、阅读程序（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 的整数，完成下面的判断题和单选题：

第 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 判定后计算一次，完美覆盖所有因数且无遗漏与重复。

【易错点】循环边界条件 i*i <= n 配合内部的 n/i 判定，实现了因数的成对获取。

第 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。

【易错点】题目求的是因数的平方和，不是因数和 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。

【易错点】 p 是 n 的平方根，代换后 p⁴=n²，而不是 n⁴。

第 31 题（单选题，3 分）

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

大于 0

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

小于 0

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

正确答案D

解析详情

【答案】D

【考点】因数平方和函数比较

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

【易错点】存在 n=1 使差值为 0，所以不能选择“一定小于 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。

【易错点】第二项是先求 solve2(5)=26，再对 26 平方，不是再次求因数平方和。

三、完善程序（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 之后。

【易错点】极易遗忘原数组并非从 0 开始，必须加上起始值 nums[0] 作基准。

第 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 正确。

【易错点】若填入 left = mid，在 left+1 == right 时会导致死循环；必须跨过确定正常的 mid。

第 35 题（单选题，3 分）

③处应填（）

left = mid + 1

right = mid - 1

right = mid

left = mid

正确答案C

解析详情

【答案】C

【考点】二分查找下界

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

【易错点】写 right=mid-1 会跳过“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]。

【易错点】 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] 判定程序没有发现内部缺口。

【易错点】这里的“连续”判断利用末元素作哨兵，不是比较 nums[0]+n 这个数组外的下一项。

三、完善程序（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。

【易错点】易将空串到目标串的编辑距离误认为是 0，忽略了逐个插入的代价。

第 39 题（单选题，3 分）

②处应填（）

j

i

m

n

正确答案B

解析详情

【答案】B

【考点】编辑距离动态规划初始化

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

【易错点】注意此处分支固定的是列下标 j=0，对应的代价随行下标 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]。

【易错点】 i、j 表示前缀长度，直接访问 str1[i] 或 str2[j] 会错一位。

第 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]。

【易错点】字符相等时不需要加 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 正确。

【易错点】易错选带有 +1 的选项。注意外层已加上操作代价 1，内部不能重复相加。