GESP 客观题评测系统

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

CSPJ-2022-R1

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

一、单项选择题

第 1 题（单选题，2 分）

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

C++中调用 printf 函数

C++中调用用户定义的类成员函数

C++中构造一个 class 或 struct

C++中构造来源于同一基类的多个派生类

正确答案A

解析详情

【答案】A

【考点】面向对象特性

【解析】 printf 是 C 风格的普通库函数，调用它不涉及类、对象、继承或多态。类成员函数、class/struct 以及基类与派生类都属于 C++ 对面向对象特性的支持。

【易错点】不要把“在 C++ 程序中可调用”误认为“体现了 C++ 的面向对象特性”。

第 2 题（单选题，2 分）

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

5 4 3 6 1 2

4 5 3 1 2 6

3 4 6 5 2 1

2 3 4 1 5 6

正确答案C

解析详情

【答案】C

【考点】栈的出栈序列

【解析】要先输出 3，栈中从底到顶为 6、5、4、3；输出 3、4 后，5 仍压在 6 上方，因此不可能接着输出 6。故序列 3 4 6 5 2 1 非法。

【易错点】判断出栈序列时要保留尚未弹出的栈内元素，不能任意跳过栈顶。

第 3 题（单选题，2 分）

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

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

将 x 的值赋为 201

将 y 的值赋为 101

将 q 指向 x 的地址

将 p 指向 y 的地址

正确答案D

解析详情

【答案】D

【考点】指针赋值

【解析】 q 保存 y 的地址，执行 p = q 后，p 复制了这个地址，因此 p 也指向 y。该语句没有解引用指针，所以 x、y 的值都不改变。

【易错点】指针之间赋值改变的是指针所存的地址，不等同于给所指对象赋值。

第 4 题（单选题，2 分）

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

数组不能排序，链表可以

链表比数组能存储更多的信息

数组大小固定，链表大小可动态调整

以上均正确

正确答案C

解析详情

【答案】C

【考点】数组与链表

【解析】普通数组在创建时长度确定，连续存储；链表可通过申请或释放结点动态改变长度。两者都能排序，能存多少信息主要受可用内存限制。

【易错点】链表的优势是动态增删结点，不代表它天然更能存储数据或才可以排序。

第 5 题（单选题，2 分）

对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（）个数据。

正确答案B

解析详情

【答案】B

【考点】栈与队列的操作序列

【解析】为先弹出 e2，可依次压入 e1、e2 后弹出 e2；再压入 e3、e4 时栈深达到 3，随后弹出 e4、e3。类似地压入 e5、e6 后可弹出 e6、e5、e1，最大栈深为 3，且保留 e1 时压入 e3、e4 说明容量 2 不够。

【易错点】队列的出队次序也限定了入队次序，不能只按栈的压入顺序估算容量。

第 6 题（单选题，2 分）

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

*+a-bcd

+a*-bcd

abc-d*+

abc-+d

正确答案B

解析详情

【答案】B

【考点】前缀表达式

【解析】原式的运算树为 +(a, *((-(b,c)), d))。按“运算符在前、随后依次写左右操作数”得到 +a*-bcd。

【易错点】转换前缀式时要保留括号确定的运算层次，不能只按字符顺序移动运算符。

第 7 题（单选题，2 分）

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

2 或 3

正确答案B

解析详情

【答案】B

【考点】哈夫曼编码

【解析】依次合并最小权值：10+15=25，16+25=41，29+30=59，最后合并 41 与 59。权值为 16 的 d 从根到叶经过 2 条边，所以编码长度为 2 位。

【易错点】哈夫曼编码长度由叶结点深度决定，不按频率大小直接编号。

第 8 题（单选题，2 分）

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

8, 18

10, 18

8, 19

10, 19

正确答案C

解析详情

【答案】C

【考点】完全二叉树的顺序存储

【解析】下标 9 是父结点 4 的右孩子，因此兄弟结点是下标 8。下标 i 的左右孩子分别在 2i 和 2i+1，所以它的右孩子在 19。

【易错点】根结点从下标 1 开始时，右孩子公式是 2i+1，不是 2i。

第 9 题（单选题，2 分）

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

（）个非零元素。

N-1

N+1

N^{2}

正确答案A

解析详情

【答案】A

【考点】连通图的最少边数

【解析】要使 N 个顶点连通，至少需要形成一棵包含全部顶点的生成树，边数为 N-1；邻接矩阵中每条有向边对应一个非零元素。因此至少有 N-1 个非零元素。

【易错点】题目问的是保证连通所需的最少边数，不是邻接矩阵共有多少个位置。

第 10 题（单选题，2 分）

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

图的深度优先遍历算法常使用的数据结构为栈。

栈的访问原则为后进先出，队列的访问原则是先进先出。

队列常常被用于广度优先搜索算法。

栈与队列存在本质不同，无法用栈实现队列。

正确答案D

解析详情

【答案】D

【考点】栈与队列的应用

【解析】栈和队列的访问次序不同，但可以用两个栈实现队列：一个栈负责入队，另一个栈通过倒序负责出队。因此“无法用栈实现队列”不恰当。

【易错点】抽象数据类型的访问规则不同，不代表它们不能相互模拟。

第 11 题（单选题，2 分）

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

p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;

p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

正确答案D

解析详情

【答案】D

【考点】双向链表插入

【解析】插入前必须先用 s->next=p->next 保存 p 的原后继，再令原后继的 prev 指向 s；随后设置 s->prev=p，最后令 p->next=s。这样四条相邻指针关系均正确且不会丢失原后继。

【易错点】若过早执行 p->next=s，再通过 p->next 访问原后继，就会丢失原链关系。

第 12 题（单选题，2 分）

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

冒泡排序算法是稳定的

简单选择排序是稳定的

简单插入排序是稳定的

归并排序算法是稳定的

正确答案B

解析详情

【答案】B

【考点】排序算法的稳定性

【解析】简单选择排序每轮把最小元素与当前位置交换，远距离交换可能让两个相等元素的相对次序颠倒，因此通常是不稳定排序。冒泡、直接插入和归并排序的常见实现均可保持稳定。

【易错点】 “每次选最小值”不保证稳定，关键要看交换是否会跨过相等元素。

第 13 题（单选题，2 分）

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

24.125

24.250

26.125

26.250

正确答案C

解析详情

【答案】C

【考点】八进制转十进制

【解析】 (32.1)₈=3×8¹+2×8⁰+1×8⁻¹=24+2+0.125=26.125。

【易错点】八进制小数点后的第一位权值是 8⁻¹，而不是 10⁻¹。

第 14 题（单选题，2 分）

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

正确答案A

解析详情

【答案】A

【考点】不同子串计数

【解析】按长度统计不同子串：长度 1、2、3 分别有 3 个，长度 4 有 2 个，长度 5 有 1 个，共 3+3+3+2+1=12 个。

【易错点】题目统计内容不同的子串，重复出现的 a、b、ab 只能各计一次。

第 15 题（单选题，2 分）

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

递归是允许使用多组参数调用函数的编程技术

递归是通过调用自身来求解问题的编程技术

递归是面向对象和数据而不是功能和逻辑的编程语言模型

递归是将用某种高级语言转换为机器代码的编程技术

正确答案B

解析详情

【答案】B

【考点】递归定义

【解析】递归是函数直接或间接调用自身，并把问题缩小到同类子问题，直到到达终止条件。多组参数、面向对象和编译过程都不是递归的定义。

【易错点】递归必须同时关注“调用自身”和“终止条件”，不能只看函数参数形式。

二、阅读程序（1）

#include <iostream>

using namespace std;

int main()
{
    unsigned short x, y;
    cin >> x >> y;
    x = (x | x << 2) & 0x33;
    x = (x | x << 1) & 0x55;
    y = (y | y << 2) & 0x33;
    y = (y | y << 1) & 0x55;
    unsigned short z = x | y << 1;
    cout << z << endl;
    return 0;
}

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

第 16 题（判断题，1.5 分）

删去第7行与第13行的unsigned，程序行为不变。（）

正确答案正确

解析详情

【答案】正确

【考点】整数类型范围与整型提升

【解析】输入均不超过 15，移位和按位运算会先提升为 int，计算结果最大不超过 255；有符号 short 足以表示这些值。删去 unsigned 后，各步结果和最终输出不变。

【易错点】判断符号类型是否影响行为，要核对实际中间结果是否越过有符号类型范围。

第 17 题（判断题，1.5 分）

将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（）

正确答案错误

解析详情

【答案】错误

【考点】字符类型的流输入输出

【解析】把 short 改为 char 后，x、y、z 都成为 unsigned char；cin >> x 会读取字符而非十进制整数，cout << z 也按字符输出。程序的输入解释和输出形式都会改变。

【易错点】 char 不只是更窄的整数类型，流运算符会把它作为字符处理。

第 18 题（判断题，1.5 分）

程序总是输出一个整数“0”。（）

正确答案错误

解析详情

【答案】错误

【考点】位分离与交错

【解析】程序把 x 的各位放到 z 的偶数位，把 y 的各位放到奇数位；只要 x 或 y 非零，z 就可能非零。例如输入 1 0 时输出 1。

【易错点】掩码 0x33 和 0x55 是在移动并分散二进制位，不是把数值清零。

第 19 题（判断题，1.5 分）

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

正确答案错误

解析详情

【答案】错误

【考点】二进制位交错

【解析】 2 的二进制为 10：x 的这一位被放到 z 的第 2 位，贡献 4；y 的这一位被放到第 3 位，贡献 8。最终 z=4+8=12，并非 10。

【易错点】交错的是二进制位的位置，不是把两个十进制数直接拼接。

第 20 题（判断题，1.5 分）

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

正确答案错误

解析详情

【答案】错误

【考点】二进制位交错

【解析】输入 2 2 时，x 经掩码处理为 4，y 经处理后左移一位为 8，所以 z=4|8=12，不是 59。

【易错点】按位或只合并已经错开的位，本题不能用普通加法前的原始输入估算结果。

第 21 题（单选题，3 分）

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

“0”

“209”

“197”

“226”

正确答案B

解析详情

【答案】B

【考点】二进制位交错编码

【解析】 13=(1101)₂，放到偶数位后得到 1+16+64=81；8=(1000)₂，放到奇数位后贡献 128。两部分按位或得到 81+128=209。

【易错点】最低位编号从 0 开始，x 放偶数位、y 放奇数位。

二、阅读程序（2）

#include <algorithm>

#include <iostream>

#include <limits>

using namespace std;

const int MAXN = 105;

const int MAXK = 105;

int h[MAXN][MAXK];

int f(int n, int m)
{
{
if (m == 1) return n;
if (n == 0) return 0;

int ret = numeric_limits<int>::max();
for (int i = 1; i <= n; i++)
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
return ret;
}

int g(int n, int m)
{
{
for (int i = 1; i <= n; i++)
h[i][1] = i;
for (int j = 1; j <= m; j++)
h[0][j] = 0;

for (int i = 1; i <= n; i++)
for (int j = 2; j <= m; j++)
h[i][j] = numeric_limits<int>::max();
for (int k = 1; k <= i; k++)
h[i][j] = min(
h[i][j],
max(h[i - k][j], h[k - 1][j - 1]) + 1);
}
}

return h[n][m];
}

int main()
{
{
int n, m;
cin >> n >> m;
cout << f(n, m) << endl << g(n, m) << endl;
return 0;
}

假设输入的 n、m 均是不超过 100 的正整数，完成下面的判断题和单选题：

第 22 题（判断题，1.5 分）

当输入为 “7 3” 时，第 19 行用来取最小值的 min 函数执行了 449 次。（）

正确答案错误

解析详情

【答案】错误

【考点】递归调用次数

【解析】令 T(n,m) 为第 19 行 min 的执行次数，边界 T(0,m)=T(n,1)=0；其余状态在 n 次循环中递归展开。按该递推计算 T(7,3)=448，不是 449。

【易错点】统计的是 min 的实际执行次数，边界调用不会进入循环。

第 23 题（判断题，1.5 分）

输出的两行整数总是相同的。（）

正确答案正确

解析详情

【答案】正确

【考点】递归与动态规划等价性

【解析】 f 和 g 使用相同的边界条件及状态转移：枚举决策位置 k，取两种结果的较大值再加 1，并在所有 k 中取最小值。g 只是把 f 的重复递归改为填表，所以两行结果相同。

【易错点】实现方式不同不代表计算目标不同，应比较边界条件和状态转移。

第 24 题（判断题，1.5 分）

当 m 为 1 时，输出的第一行总为 n。（）

正确答案正确

解析详情

【答案】正确

【考点】动态规划边界条件

【解析】当 m=1 时，f 直接返回 n；g 初始化 h[i][1]=i，且不会进入 j≥2 的转移，最终 h[n][1]=n。因此第一行恒为 n。

【易错点】边界状态由初始化直接确定，不需要套用一般转移式。

第 25 题（单选题，3 分）

算法 $g(n, m)$ 最为准确的时间复杂度分析结果为（）。

O(n^{3/2}m)

O(nm)

O(n^{2}m)

O(nm^{2})

正确答案C

解析详情

【答案】C

【考点】动态规划时间复杂度

【解析】 g 的外层 i 遍历 1…n，j 遍历 2…m；每个状态 h[i][j] 又枚举 k=1…i。总操作数为 m·Σi=1..n i，数量级是 O(n²m)。

【易错点】第三层循环上界是当前 i，累加后仍是 n² 量级，不能漏掉这层枚举。

第 26 题（单选题，3 分）

当输入为 “20 2” 时，输出的第一行为（）。

“4”

“5”

“6”

“20”

正确答案C

解析详情

【答案】C

【考点】双资源最坏情况动态规划

【解析】当 m=2 时，若允许 t 次尝试，最多可处理 1+2+…+t=t(t+1)/2 个状态。t=5 只能覆盖 15<20，t=6 可覆盖 21≥20，所以结果为 6。

【易错点】两份资源时不能直接二分，因为一次失败后只剩一份资源。

第 27 题（单选题，4 分）

当输入为 “100 100” 时，输出的第一行为（）。

“6”

“7”

“8”

“9”

正确答案B

解析详情

【答案】B

【考点】最优决策次数

【解析】资源数足够时，t 次尝试最多区分 2^t-1 个状态。6 次只能覆盖 63<100，7 次可覆盖 127≥100，因此 f(100,100)=7。

【易错点】需要的是保证最坏情况下成功的次数，应取满足覆盖范围的最小整数 t。

二、阅读程序（3）

#include <iostream>

using namespace std;

int n, k;

int solve1()
{
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (mid * mid <= n) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}

double solve2(double x)
{
if (x == 0) return x;
for (int i = 0; i < k; i++)
x = (x + n / x) / 2;
return x;
}

int main()

{
    cin >> n >> k;
    double ans = solve2(solve1());
    cout << ans << ' ' << (ans * ans == n) << endl;
    return 0;
}

假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

第 28 题（判断题，1.5 分）

该算法最准确的时间复杂度分析结果为 $O(\log n + k)$ 。（）

正确答案正确

解析详情

【答案】正确

【考点】二分查找与牛顿迭代复杂度

【解析】 solve1 在区间 [0,n] 上二分，耗时 O(log n)；solve2 固定迭代 k 次，耗时 O(k)。两部分顺序执行，总时间为 O(log n+k)。

【易错点】顺序执行的复杂度相加，不应把两段误写成相乘。

第 29 题（判断题，1.5 分）

当输入为 “9801 1” 时，输出的第一个数为 “99”。（）

正确答案正确

解析详情

【答案】正确

【考点】整数平方根与牛顿迭代

【解析】 9801=99²，solve1 返回 99。solve2 以 99 为初值，迭代式 (x+9801/x)/2 仍得到 99，所以输出的第一个数为 99。

【易错点】初值已经是精确平方根时，牛顿迭代不会改变它。

第 30 题（判断题，1.5 分）

对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成 “1”。（）

正确答案错误

解析详情

【答案】错误

【考点】浮点数精度与相等比较

【解析】第二个数判断的是 ans*ans==n。对非完全平方数，如 n=2，牛顿迭代只能得到浮点近似值，增大 k 也不保证乘积与整数 2 精确相等，因此不一定变成 1。

【易错点】浮点近似收敛不等于能够通过精确相等比较。

第 31 题（判断题，1.5 分）

该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（）

正确答案错误

解析详情

【答案】错误

【考点】整数溢出边界

【解析】 n>4 时第一次 mid≤n/2≤23500，且 mid²>n 后右边界只会继续减小；因此本题 mid² 最大不超过 23500²=552250000，未超出 32 位 int。题设范围内无须强制转换为 64 位。

【易错点】不能直接用 n² 判断溢出，mid 在二分过程中的实际最大值更小。

第 32 题（单选题，3 分）

当输入为 “2 1” 时，输出的第一个数最接近（）。

1.414

1.5

正确答案C

解析详情

【答案】C

【考点】牛顿迭代求平方根

【解析】 solve1(2) 得到 1；k=1 时只迭代一次，x=(1+2/1)/2=1.5。因此第一个输出数最接近 1.5。

【易错点】 k 表示迭代次数，不能把一次迭代的结果当成已经完全收敛。

第 33 题（单选题，3 分）

当输入为 “3 10” 时，输出的第一个数最接近（）。

1.7

1.732

1.75

正确答案B

解析详情

【答案】B

【考点】牛顿迭代收敛

【解析】 solve1(3)=1，迭代式为 x←(x+3/x)/2；前几次得到 2、1.75、约 1.73214，继续到 10 次后已非常接近 √3≈1.73205。

【易错点】迭代次数较多时应判断收敛值，不要停留在前一两次的中间结果。

第 34 题（单选题，3 分）

当输入为 “256 11” 时，输出的第一个数（）。

等于 16

接近但小于 16

接近但大于 16

前三种情况都有可能

正确答案A

解析详情

【答案】A

【考点】牛顿迭代的不动点

【解析】 solve1(256)=16，且 256/16=16；代入迭代式得到 (16+16)/2=16。之后 11 次迭代都保持 16，所以输出值等于 16。

【易错点】初值为精确平方根时，它是迭代公式的不动点，不会产生近似误差。

三、完善程序（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 << ⑤ << " ";
}
}

第 35 题（单选题，3 分）

①处应填（）

n % i == 0

n % i == 1

n % (i-1) == 0

n % (i-1) == 1

正确答案A

解析详情

【答案】A

【考点】因数判定

【解析】枚举 i 时，只有 n 能被 i 整除，i 才是 n 的正因数并应加入 fac，因此条件是 n % i == 0。

【易错点】整除的余数必须为 0，与 i 在循环中的位置无关。

第 36 题（单选题，3 分）

②处应填（）

n / fac[k]

fac[k]

fac[k]-1

n / (fac[k]-1)

正确答案B

解析详情

【答案】B

【考点】成对因数的有序输出

【解析】 fac 按 i 从小到大的顺序保存所有小于 √n 的小因数，第一段输出应直接打印 fac[k]，才能先得到递增的小因数部分。

【易错点】若此处输出 n/fac[k]，会先打印大因数且顺序不符合要求。

第 37 题（单选题，3 分）

③处应填（）

(i-1)\times(i-1)=n

(i-1)\times i=n

i\times i=n

i\times(i-1)=n

正确答案C

解析详情

【答案】C

【考点】完全平方数判定

【解析】循环结束时 i 是第一个满足 i²≥n 的整数。只有 i²=n 时，√n 本身是一个不能由前后两段重复输出的中间因数，因此条件应为 i*i == n。

【易错点】完全平方数的平方根只能输出一次，不能同时放入成对因数两侧。

第 38 题（单选题，3 分）

④处应填（）

n-i

n-i+1

i-1

I

正确答案D

解析详情

【答案】D

【考点】完全平方数的因数输出

【解析】当 i*i==n 时，i 就是 n 的平方根，也是成对因数序列正中间的因数，所以此处应输出变量 i。

【易错点】这里输出的是平方根 i，不是 n-i 或相邻的 i-1。

第 39 题（单选题，3 分）

⑤处应填（）

n / fac[k]

fac[k]

fac[k]-1

n / (fac[k]-1)

正确答案A

解析详情

【答案】A

【考点】成对因数枚举

【解析】若 fac[k] 是 n 的小因数，与它配对的大因数就是 n/fac[k]。逆序遍历 fac 可使这些大因数从小到大输出，因此应填 n / fac[k]。

【易错点】大因数必须由 n 除以对应小因数得到，不能再次输出 fac[k]。

三、完善程序（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;
    }
    return 0;
}

第 40 题（单选题，3 分）

①处应填（）

image[r][c] == prev_color

image[r][c] != prev_color

image[r][c] == new_color

image[r][c] != new_color

正确答案A

解析详情

【答案】A

【考点】洪水填充的可达条件

【解析】洪水填充只能扩展到与起点原颜色 prev_color 相同的像素；同时排除已染成 new_color 的像素可避免重复访问。因此核心条件是 image[r][c] == prev_color。

【易错点】相邻且未越界并不够，像素颜色还必须与起点原颜色一致。

第 41 题（单选题，3 分）

②处应填（）

image[cur.r+1][cur.c] = new_color

image[cur.r][cur.c] = new_color

image[cur.r][cur.c+1] = new_color

image[cur.r][cur.c] = prev_color

正确答案B

解析详情

【答案】B

【考点】广度优先洪水填充

【解析】起点 cur 入队后应立即染成 new_color，即 image[cur.r][cur.c] = new_color。这样既完成起点填色，也把它标记为已访问，防止之后被邻点重复加入队列。

【易错点】若不先标记起点，搜索相邻像素时可能再次把起点当作未访问点。

第 42 题（单选题，3 分）

③处应填（）

Point(pt.r, pt.c)

Point(pt.r, pt.c+1)

Point(pt.r+1, pt.c)

Point(pt.r+1, pt.c+1)

正确答案C

解析详情

【答案】C

【考点】网格四方向移动

【解析】数组中已有上方 (r-1,c)、右方 (r,c+1) 和左方 (r,c-1)，缺少的是下方 (r+1,c)。因此应构造 Point(pt.r+1, pt.c)。

【易错点】四连通只包含上下左右，不包含对角线位置。

第 43 题（单选题，3 分）

④处应填（）

prev_color = image[p.r][p.c]

new_color = image[p.r][p.c]

image[p.r][p.c] = prev_color

image[p.r][p.c] = new_color

正确答案D

解析详情

【答案】D

【考点】搜索中的访问标记

【解析】 p 通过合法性检查后，应立即执行 image[p.r][p.c] = new_color，把它染色并标记为已发现。这样同一像素不会在正式出队前被其他邻点重复加入队列。

【易错点】访问标记应在入队时设置，而不是等到出队后再设置。

第 44 题（单选题，3 分）

⑤处应填（）

queue.push(p)

queue.push(pt)

queue.push(cur)

queue.push(Point(ROWS,COLS))

正确答案A

解析详情

【答案】A

【考点】广度优先搜索队列

【解析】 p 是当前找到的合法相邻像素，染色后要用 queue.push(p) 将它加入待扩展队列，之后才能继续检查从 p 可达的像素。

【易错点】应入队新发现的邻点 p，而不是已经处理过的 pt 或 cur。