选 单项选择题（共 15 题，共 0 分）
在 Linux 系统终端中，用于切换工作目录的命令为（ ）。
你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：
real 0m30.721s
user 0m24.579s
sys 0m6.123s
以下最接近秒表计时的时长为（ ）。
若元素 $a$、$b$、$c$、$d$、$e$、$f$ 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（ ）。
考虑对 $n$ 个数进行排序，以下最坏时间复杂度低于 $\mathcal{O}(n^{2})$的排序方法是（ ）
假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ）。
计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（ ）
unsigned x = 0xDEADNEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);
一个深度为 $5$（根结点深度为 $1$）的完全 3 叉树，按前序遍历的顺序给结点从 $1$ 开始编号，则第 100 号结点的父结点是第（ ）号
强连通图的性质不包括（ ）：
每个顶点度数均为 $2$ 的无向图称为“$2$-正规图”。由编号为从 $1$ 到 $n$ 的顶点构成的所有 $2$-正规图，其中包含欧拉回路的不同 $2$-正规图的数量为（ ）。
共有 $8$ 人选修了程序设计课程，期末大作业要求由 $2$ 人组成的团队完成。假设不区分每个团队内 $2$ 人的角色和作用，请问共有多少种可能的组队方案。（ ）
小明希望选到形如“省 A ·$\mathscr{LL}\mathcal{DDD}$”的车牌号。车牌号在“ ·”之前的内容固定不变； 后面 的 $5$ 位号码中， 前 $2$ 位必须是大写英文字母， 后 $3$ 位必须是阿拉伯数字($\mathscr{L}$代表 A 至 Z，$\mathcal{D}$ 表示 0 至 9，两个$\mathscr{L}$和三个$\mathcal{D}$之间可能相同也可能不同)。请问总共有多少个可供选择的车牌号。（ ）
给定地址区间为 $0$~$9$ 的哈希表，哈希函数为 $h(x) = x$ % $10$，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 $9$ 冲突了则从地址 $0$ 重新开始探查）。哈希表初始为空表，依次存储（$71, 23, 73, 99, 44, 79, 89$）后，请问 $89$ 存储在哈希表哪个地址中。（ ）
对于给定的 n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。
int i, j, k = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j*=2) {
k = k + n / 2;
}
}
以比较为基本运算，在 $n$ 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。
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));
}
阅 阅读程序（共 18 题，共 0 分）
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int f(const string &s, const string &t) {
int n = s.length(), m = t.length();
vector<int> shift(128, m + 1);
int i, j;
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 可见字符组成，当输入为“abcde fg”时，输出为 -1。( )
当输入为“GoodLuckCsp2022 22”时，第 20 行的“j++”语句执行次数为 $2$。（ ）
该算法最坏情况下的时间复杂度为( )。
f(a, b) 与下列（ ）语句的功能最类似。
当输入为“baaabaaabaaabaaaa aaaa”，第 20 行的“j++”语句执行次数为 ( )。
#include <iostream>
using namespace std;
const int MAXN = 105;
int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];
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++;
}
}
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;
}
}
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 表示范围内， 这是一个不稳定的排序算法。( )
假设输入的 $n$ 为不大于 $100$ 的正整数，$k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内， 该算法的空间复杂度仅与 $n$ 有关。( )
假设输入的 $n$ 为不大于 $100$ 的正整数，$k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，该算法的时间复杂度为 $\mathcal{O}(m (n + k))$。( )
假设输入的 $n$ 为不大于 $100$ 的正整数，$k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 36 行， val[] 数组的内容依次为( )。
假设输入的 $n$ 为不大于 $100$ 的正整数，$k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，若 val[i] 的最大值为 $100$，$k$ 取（ ）时算法运算次数最少。
假设输入的 $n$ 为不大于 $100$ 的正整数，$k$ 为不小于 $2$ 且不大于 $100$ 的正整数， val[i] 在 int 表示范围内，当输入的 $k$ 比 val[i] 的最大值还大时，该算法退化为（ ）算法。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXL = 1000;
int n, k, ans[MAXL];
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$ 的正整数，该算法的时间复杂度为 $\mathcal{O}(\log_{k}{n})$。( )
假设输入的 $n$ 在 int 范围内，$k$ 为不小于 $2$ 且不大于 $36$ 的正整数，删除第 23 行的强制类型转换，程序的行为不变。( )
假设输入的 $n$ 在 int 范围内，$k$ 为不小于 $2$ 且不大于 $36$ 的正整数，除非输入的 $n$ 为 $0$，否则程序输出的字符数为 $\Theta(\lfloor\log_{k}{|n|}\rfloor + 1)$。( )
假设输入的 $n$ 在 int 范围内，$k$ 为不小于 $2$ 且不大于 $36$ 的正整数，当输入为“100 7”时，输出为( )
假设输入的 $n$ 在 int 范围内，$k$ 为不小于 $2$ 且不大于 $36$ 的正整数，当输入为“-255 8”时，输出为“( )”。
假设输入的 $n$ 在 int 范围内，$k$ 为不小于 $2$ 且不大于 $36$ 的正整数，当输入为“1000000 19”时，输出为“（ ）”。
完 完善程序（共 10 题，共 0 分）
#include <bits/stdc++.h>
using namespace std;
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);
}
}
}
(归并第 $k$ 小) 已知两个长度均为 $n$ 的有序数组 a1 和 a2 (均为递增序，但不保证严格单调递增)，并且给定正整数 $k$ ($1\leq k\leq 2n$)，求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。
试补全程序。
①处应填（ ）
(归并第 $k$ 小) 已知两个长度均为 $n$ 的有序数组 a1 和 a2 (均为递增序，但不保证严格单调递增)，并且给定正整数 $k$ ($1\leq k\leq 2n$)，求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。
试补全程序。
②处应填( )
(归并第 $k$ 小) 已知两个长度均为 $n$ 的有序数组 a1 和 a2 (均为递增序，但不保证严格单调递增)，并且给定正整数 $k$ ($1\leq k\leq 2n$)，求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。
试补全程序。
③处应填( )
(归并第 $k$ 小) 已知两个长度均为 $n$ 的有序数组 a1 和 a2 (均为递增序，但不保证严格单调递增)，并且给定正整数 $k$ ($1\leq k\leq 2n$)，求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。
试补全程序。
④处应填( )
(归并第 $k$ 小) 已知两个长度均为 $n$ 的有序数组 a1 和 a2 (均为递增序，但不保证严格单调递增)，并且给定正整数 $k$ ($1\leq k\leq 2n$)，求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。
试补全程序。
⑤处应填( )
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int ans;
int a, b, c;
int init;
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];
}
void go(int x, int y) {
if (③)
return;
if (f[x][y] == dfs(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);
}
}
}
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);
}
}
$POUR(i,j)$：将容器 $i$ 的水倒进容器 $j$ (完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空)。
$POUR(i,j)$：将容器 $i$ 的水倒进容器 $j$ (完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空)。
$POUR(i,j)$：将容器 $i$ 的水倒进容器 $j$ (完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空)。
$POUR(i,j)$：将容器 $i$ 的水倒进容器 $j$ (完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空)。
$POUR(i,j)$：将容器 $i$ 的水倒进容器 $j$ (完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空)。