GESP 客观题评测系统

2022 CCF CSP-S 第一轮（提高级 C++）

CSPS-2022-R1

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

一、单项选择题

第 1 题（单选题，2 分）

在 Linux 系统终端中，用于切换工作目录的命令为（）。

all

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

第 2 题（单选题，2 分）

你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下:

real 0m30.721s

user 0m24.579s

sys 0m6.123s

以下最接近秒表计时的时长为（）。

30s

24s

18s

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 3 题（单选题，2 分）

若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（）。

dcebfa

cbdaef

bcaefd

afedcb

正确答案D

解析详情

【答案】{'kind': 'single_choice', 'value': 'D'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'D'} 成立。

【易错点】边界条件判断错误。

第 4 题（单选题，2 分）

考虑对 n 个数进行排序，以下最坏时间复杂度低于 $O(n^{2})$ 的排序方法是（）。

插入排序

冒泡排序

归并排序

快速排序

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 5 题（单选题，2 分）

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（）。

移除受影响的数据后，最终序列是有序序列

移除受影响的数据后，最终序列是前后两个有序的子序列

移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列

移除受影响的数据后，最终序列基本无序

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 6 题（单选题，2 分）

计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（）

unsigned x = 0xDEADBEEF;

unsigned char *p = (unsigned char *)&x;

printf("%X", *p);

EF、EF

EF、DE

DE、EF

DE、DE

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

第 7 题（单选题，2 分）

一个深度为5（根结点深度为1）的完全3叉树，按前序遍历的顺序给结点从1开始编号，

则第 100 号结点的父结点是第（）号。

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 8 题（单选题，2 分）

强连通图的性质不包括（):

每个顶点的度数至少为 1

任意两个顶点之间都有边相连

任意两个顶点之间都有路径相连

每个顶点至少都连有一条边

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

第 9 题（单选题，2 分）

每个顶点度数均为2的无向图称为“2正规图”。由编号为从1到n的顶点构成的所有2正规图，其中包含欧拉回路的不同2正规图的数量为（）。

(n-1)!

n! / 2

(n-1)!

正确答案D

解析详情

【答案】{'kind': 'single_choice', 'value': 'D'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'D'} 成立。

【易错点】边界条件判断错误。

第 10 题（单选题，2 分）

共有 8 人选修了程序设计课程，期末大作业要求由 2 人组成的团队完成。假设不区分每个团队内 2 人的角色和作用，请问共有多少种可能的组队方案。（）

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 11 题（单选题，2 分）

小明希望选到形如“省 A·LLDDD”的车牌号。车牌号在“·”之前的内容固定不变；后面的 5 位号码中，前 2 位必须是大写英文字母，后 3 位必须是阿拉伯数字（ℱ代表 A 至 Z，ℱ表示 0 至 9，两个ℱ和三个ℱ之间可能相同也可能不同）。请问总共有多少个可供选择的车牌

号。（）

20280

52000

676000

1757600

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 12 题（单选题，2 分）

给定地址区间为 0~9 的哈希表，哈希函数为 $h(x) = x \% 10$ ，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 9 冲突了则从地址 0 重新开始探查）。哈希表初始为空表，依次存储(71, 23, 73, 99, 44, 79, 89)后，请问 89 存储在哈希表哪个地址中。（）

正确答案D

解析详情

【答案】{'kind': 'single_choice', 'value': 'D'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'D'} 成立。

【易错点】边界条件判断错误。

第 13 题（单选题，2 分）

对于给定的 n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。

13. 对于给定的 n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。

int i, j, k = 0;

for (i = 0; i < n; i++) {

    for (j = 0; j < n; j != 2) {

        k = k + n / 2;

    }

}

O(n)

O(n \log n)

O(n\sqrt{n})

O(n^{2})

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

第 14 题（单选题，2 分）

以比较为基本运算，在 n 个数的数组中找最大的数，在最坏情况下至少要做（）次运算。

n/2

n-1

n+1

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

第 15 题（单选题，2 分）

ack 函数在输入参数“ $(2,2)$ ”时的返回值为（）。

unsigned ack(unsigned m, unsigned n) {
    if (m == 0) return n + 1;
    if (n == 0) return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

二、阅读程序（1）

#include <iostream>
#include <string>
#include <vector>
04
using namespace std;
06
int f(const string &s, const string &t)
{
    int n = s.length(), m = t.length();
    10
vector<int> shift(128, m + 1);
    12
int i, j;
    14
for (j = 0; j < m; j++)
    {
        shift[t[j]] = m - j;
    }
}

for (i = 0; i <= n - m; i += shift[s[i + m]]) {
    j = 0;
    while (j < m && s[i + j] == t[j]) j++;
    if (j == m) return i;
}
return -1;

int main()
{
    string a, b;
    cin >> a >> b;
    cout << f(a, b) << endl;
    return 0;
}

假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：

第 16 题（判断题，1 分）

当输入为“abcde fg”时，输出为-1。

正确答案正确

解析详情

【答案】{'kind': 'true_false', 'value': True}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': True} 成立。

【易错点】边界条件判断错误。

第 17 题（判断题，1.5 分）

当输入为 “abbababbbab abab” 时，输出为 4。（）

正确答案错误

解析详情

【答案】{'kind': 'true_false', 'value': False}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': False} 成立。

【易错点】边界条件判断错误。

第 18 题（判断题，1.5 分）

当输入为 “GoodLuckCsp2022 22” 时，第 20 行的 “j++” 语句执行次数为 2。

正确答案正确

解析详情

【答案】{'kind': 'true_false', 'value': True}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': True} 成立。

【易错点】边界条件判断错误。

第 19 题（单选题，3 分）

该算法最坏情况下的时间复杂度为（）。

O(n+m)

O(n\log m)

O(m\log n)

O(nm)

正确答案D

解析详情

【答案】{'kind': 'single_choice', 'value': 'D'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'D'} 成立。

【易错点】边界条件判断错误。

第 20 题（单选题，3 分）

f(a, b)与下列（）语句的功能最类似。

a.find(b)

a.rfind(b)

a.substr(b)

a.compare(b)

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 21 题（单选题，3 分）

当输入为“baaabaaabaaabaaaa aaaa”，第20行的“j++”语句执行次数为（）。

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

二、阅读程序（2）

#include <iostream>
02
using namespace std;
04
const int MAXN = 105;

06
int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];
09
void init()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> val[i];
int maximum = val[0];
for (int i = 1; i < n; i++)
if (val[i] > maximum) maximum = val[i];
m = 1;
while (maximum >= k) {
maximum / = k;
m++;
}
}
23
void solve()
{
int base = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < k; j++) cnt[j] = 0;
for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
for (int j = n - 1; j >= 0; j--) {
temp[cnt[val[j] / base % k] - 1] = val[j];
cnt[val[j] / base % k] --;
}
for (int j = 0; j < n; j++) val[j] = temp[j];
base *= k;
}
}
39
int main()
{
init();
solve();
for (int i = 0; i < n; i++) cout << val[i] << '';
cout << endl;
return 0;
}

假设输入的 n 为不大于 100 的正整数，k 为不小于 2 且不大于 100 的正整数，val[i] 在 int 表示范围内，完成下面的判断题和单选题：

第 22 题（判断题，1.5 分）

这是一个不稳定的排序算法。（）

正确答案错误

解析详情

【答案】{'kind': 'true_false', 'value': False}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': False} 成立。

【易错点】边界条件判断错误。

第 23 题（判断题，1.5 分）

该算法的空间复杂度仅与 n 有关。（）

正确答案错误

解析详情

【答案】{'kind': 'true_false', 'value': False}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': False} 成立。

【易错点】边界条件判断错误。

第 24 题（判断题，1.5 分）

该算法的时间复杂度为 $O(m(n + k))$ 。（）

正确答案正确

解析详情

【答案】{'kind': 'true_false', 'value': True}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': True} 成立。

【易错点】边界条件判断错误。

第 25 题（单选题，3 分）

当输入为 “5 3 98 26 91 37 46” 时，程序第一次执行到第 36 行，val[] 数组的内容依次为（）。

91 26 46 37 98

91 46 37 26 98

98 26 46 91 37

91 37 46 98 26

正确答案D

解析详情

【答案】{'kind': 'single_choice', 'value': 'D'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'D'} 成立。

【易错点】边界条件判断错误。

第 26 题（单选题，3 分）

若 val[i] 的最大值为 100，k 取（）时算法运算次数最少。

不确定

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 27 题（单选题，3 分）

当输入的 k 比 val[i] 的最大值还大时，该算法退化为（）算法。

选择排序

冒泡排序

计数排序

桶排序

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

二、阅读程序（3）

#include <iostream>
#include <algorithm>
03
using namespace std;
05
const int MAXL = 1000;
07
int n, k, ans[MAXL];
09
int main(void)
{
cin >> n >> k;
if (!n) cout << 0 << endl;
else
{
int m = 0;
while (n)
{
ans[m++] = (n % (-k) + k) % k;
n = (ans[m - 1] - n) / k;
}
for (int i = m - 1; i >= 0; i--)

cout << char(ans[i] >= 10 ?
ans[i] + 'A' - 10 :
ans[i] + '0';
cout << endl;
}
return 0;
}

假设输入的 n 在 int 范围内，k 为不小于 2 且不大于 36 的正整数，完成下面的判断题和单选题：

第 28 题（判断题，1.5 分）

该算法的时间复杂度为 $O(\log_k n)$ 。（）

正确答案正确

解析详情

【答案】{'kind': 'true_false', 'value': True}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': True} 成立。

【易错点】边界条件判断错误。

第 29 题（判断题，1.5 分）

删除第 23 行的强制类型转换，程序的行为不变。（）

正确答案错误

解析详情

【答案】{'kind': 'true_false', 'value': False}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': False} 成立。

【易错点】边界条件判断错误。

第 30 题（判断题，1.5 分）

除非输入的 n 为 0，否则程序输出的字符数为 $O(|\log_k |n| + 1)$ 。（）

正确答案正确

解析详情

【答案】{'kind': 'true_false', 'value': True}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'true_false', 'value': True} 成立。

【易错点】边界条件判断错误。

第 31 题（单选题，3 分）

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

202

1515

244

1754

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 32 题（单选题，3 分）

当输入为 “-255 8” 时，输出为 “( )”。

1400

1401

417

400

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

第 33 题（单选题，3 分）

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

BG939

87GIB

1CD428

7CF1B

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

三、完善程序（1）

(1)（归并第 k 小）已知两个长度均为 n 的有序数组 a1 和 a2（均为递增序，但不保证严格单调递增），并且给定正整数 k（ $1 \leqslant k \leqslant 2n$ ），求数组 a1 和 a2 归并排序后的数组里第 k 小的数值。

试补全程序。

#include <bits/stdc++.h>
using namespace std;
03
int solve(int *a1, int *a2, int n, int k) {
int left1 = 0, right1 = n - 1;
int left2 = 0, right2 = n - 1;
while (left1 <= right1 && left2 <= right2) {

int m1 = (left1 + right1) >> 1;
int m2 = (left2 + right2) >> 1;
int cnt = ①;
if (②) {
    if (cnt < k) left1 = m1 + 1;
    else right2 = m2 - 1;
} else {
    if (cnt < k) left2 = m2 + 1;
    else right1 = m1 - 1;
}

if (③) {
    if (left1 == 0) {
        return a2[k - 1];
    } else {
        int x = a1[left1 - 1], ④;
        return std::max(x, y);
    }
} else {
    if (left2 == 0) {
        return a1[k - 1];
    } else {
        int x = a2[left2 - 1], ⑤;
        return std::max(x, y);
    }
}

第 34 题（单选题，3 分）

①处应填（）

(m1 + m2) * 2

(m1 - 1) + (m2 - 1)

m1 + m2

(m1 + 1) + (m2 + 1)

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 35 题（单选题，3 分）

②处应填（）

a1[m1] == a2[m2]

a1[m1] <= a2[m2]

a1[m1] >= a2[m2]

a1[m1] != a2[m2]

正确答案B

解析详情

【答案】{'kind': 'single_choice', 'value': 'B'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'B'} 成立。

【易错点】边界条件判断错误。

第 36 题（单选题，3 分）

③处应填（）

left1 == right1

left1 < right1

left1 > right1

left1 != right1

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 37 题（单选题，3 分）

④处应填（）

y = a1[k - left2 - 1]

y = a1[k - left2]

y = a2[k - left1 - 1]

y = a2[k - left1]

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 38 题（单选题，3 分）

⑤处应填（）

y = a1[k - left2 - 1]

y = a1[k - left2]

y = a2[k - left1 - 1]

y = a2[k - left1]

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

三、完善程序（2）

(2)（容器分水）有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：

1）FILL(i)：用水龙头将容器 i（i∈{1,2}）灌满水；

2）DROP(i)：将容器 i 的水倒进下水道；

3）POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。

求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 $c \leq \max\{a, b\}$ 。

试补全程序。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
04
int f[N][N];
int ans;
int a, b, c;
int init;
09
int dfs(int x, int y) {
if (f[x][y] != init)
return f[x][y];
if (x == c || y == c)
return f[x][y] = 0;
f[x][y] = init - 1;
f[x][y] = min(f[x][y], dfs(a, y) + 1);
f[x][y] = min(f[x][y], dfs(x, b) + 1);
f[x][y] = min(f[x][y], dfs(0, y) + 1);
f[x][y] = min(f[x][y], dfs(x, 0) + 1);
int t = min(a - x, y);
f[x][y] = min(f[x][y], ①);
t = min(x, b - y);
f[x][y] = min(f[x][y], ②);
return f[x][y];
}
26
void go(int x, int y) {
if (③)
return;
30

if (f[x][y] == df(s(a, y) + 1) {
cout << "FILL(1)" << endl;
go(a, y);
} else if (f[x][y] == dfs(x, b) + 1) {
cout << "FILL(2)" << endl;
go(x, b);
} else if (f[x][y] == dfs(0, y) + 1) {
cout << "DROP(1)" << endl;
go(0, y);
} else if (f[x][y] == dfs(x, 0) + 1) {
cout << "DROP(2)" << endl;
go(x, 0);
} else {
int t = min(a - x, y);
if (f[x][y] == ④) {
cout << "POUR(2,1)" << endl;
go(x + t, y - t);
} else {
t = min(x, b - y);
if (f[x][y] == ⑤) {
cout << "POUR(1,2)" << endl;
go(x - t, y + t);
} else
assert(0);
}
}
}
57
int main() {
cin >> a >> b >> c;
ans = 1 << 30;
memset(f, 127, sizeof f);
init = **f;
if ((ans = dfs(0, 0)) == init - 1)
cout << "impossible";
else {
cout << ans << endl;
go(0, 0);
}
}

第 39 题（单选题，3 分）

①处应填（）

dfs(x + t, y - t) + 1

dfs(x + t, y - t) - 1

dfs(x - t, y + t) + 1

dfs(x - t, y + t) - 1

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 40 题（单选题，3 分）

②处应填（）

dfs(x + t, y - t) + 1

dfs(x + t, y - t) - 1

dfs(x - t, y + t) + 1

dfs(x - t, y + t) - 1

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。

第 41 题（单选题，3 分）

③处应填（）

x == c || y == c

x == c && y == c

x >= c || y >= c

x >= c && y >= c

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 42 题（单选题，3 分）

④处应填（）

dfs(x + t, y - t) + 1

dfs(x + t, y - t) - 1

dfs(x - t, y + t) + 1

dfs(x - t, y + t) - 1

正确答案A

解析详情

【答案】{'kind': 'single_choice', 'value': 'A'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'A'} 成立。

【易错点】边界条件判断错误。

第 43 题（单选题，3 分）

⑤处应填（）

dfs(x + t, y - t) + 1

dfs(x + t, y - t) - 1

dfs(x - t, y + t) + 1

dfs(x - t, y + t) - 1

正确答案C

解析详情

【答案】{'kind': 'single_choice', 'value': 'C'}

【考点】核心算法

【解析】此题考察了相关算法的实际应用。通过追踪关键变量状态，我们可以推导得到正确结果，选项 {'kind': 'single_choice', 'value': 'C'} 成立。

【易错点】边界条件判断错误。