CSP-J1入门级初赛试卷[2022]

第1题

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

第2题

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

第3题

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

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

第4题

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

第5题

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

第6题

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

第7题

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

第8题

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

第9题

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

第10题

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

第11题

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

第12题

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

第13题

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

第14题

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

第15题

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

第16题

#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 的自然数，删去第 7 行与第 13 行的 unsigned，程序行为不变。

第17题

#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 的自然数，将第 7 行与第 13 行的 short 均改为 char，程序行为不变。

第18题

#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 的自然数，程序总是输出一个整数“0”。

第19题

#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 的自然数，当输入为“2 2”时，输出为“10”。

第20题

#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 的自然数，当输入为“2 2”时，输出为“59”。

第21题

#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 的自然数，当输入为“13 8”时，输出为（ ）。

第22题

#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::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::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 的正整数，当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。

第23题

#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::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::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 的正整数，输出的两行整数总是相同的。

第24题

#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::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::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 的正整数，当 m 为 1 时，输出的第一行总为 n。

第25题

#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::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::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 的正整数，算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。

第26题

#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::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::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 的正整数，当输入为“20 2”时，输出的第一行为（ ）。

第27题

#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::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::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 的正整数，当输入为“100 100”时，输出的第一行为（ ）。

第28题

#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 表示范围的自然数，该算法最准确的时间复杂度分析结果为?(log? + ?)。

第29题

#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 表示范围的自然数，当输入为“9801 1”时，输出的第一个数为“99”。

第30题

#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 表示范围的自然数，对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。

第31题

#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 表示范围的自然数，该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。

第32题

#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 表示范围的自然数，当输入为“2 1”时，输出的第一个数最接近（ ）。

第33题

#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 表示范围的自然数，当输入为“3 10”时，输出的第一个数最接近（ ）。

第34题

#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 表示范围的自然数，当输入为“256 11”时，输出的第一个数（ ）。

第35题

（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vectorfac;
    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 << ⑤ << " ";
    }
}

①处应填（ ）。

第36题

（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vectorfac;
    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 << ⑤ << " ";
    }
}

②处应填（ ）。

第37题

（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vectorfac;
    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 << ⑤ << " ";
    }
}

③处应填（ ）。

第38题

（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vectorfac;
    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 << ⑤ << " ";
    }
}

④处应填（ ）。

第39题

（枚举因数）从小到大打印正整数 n 的所有正因数，试补全枚举程序。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vectorfac;
    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 << ⑤ << " ";
    }
}

⑤处应填（ ）。

第40题

（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

#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) {
    queuequeue;
    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;
    }
    // 输出：
    // 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 y y y y r g r
    // g g g y y r g r
    // g g g y y y y r
    // g g g g g y g g
    // g g g g g y y g
    return 0;
}

①处应填（ ）。

第41题

（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

#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) {
    queuequeue;
    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;
    }
    // 输出：
    // 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 y y y y r g r
    // g g g y y r g r
    // g g g y y y y r
    // g g g g g y g g
    // g g g g g y y g
    return 0;
}

②处应填（ ）。

第42题

（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

#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) {
    queuequeue;
    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;
    }
    // 输出：
    // 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 y y y y r g r
    // g g g y y r g r
    // g g g y y y y r
    // g g g g g y g g
    // g g g g g y y g
    return 0;
}

③处应填（ ）。

第43题

（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

#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) {
    queuequeue;
    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;
    }
    // 输出：
    // 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 y y y y r g r
    // g g g y y r g r
    // g g g y y y y r
    // g g g g g y g g
    // g g g g g y y g
    return 0;
}

④处应填（ ）。

第44题

（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

#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) {
    queuequeue;
    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;
    }
    // 输出：
    // 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 y y y y r g r
    // g g g y y r g r
    // g g g y y y y r
    // g g g g g y g g
    // g g g g g y y g
    return 0;
}

⑤处应填（ ）。