选 单项选择题（共 15 题，共 0 分）
在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（ ）。
二进制数 $00101010_2$ 和 $00010110_2$ 的和为（ ）。
在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。
以下排序方法中，（ ）是不稳定的。
以比较为基本运算，对于 $2\times n$ 个数，同时找到最大值和最小值，最坏情况下需要的最小的比较次数为（ ）。
现有一个地址区间为 $0\sim 10$ 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储（到 $10$ 冲突了就从 $0$ 开始往后），现在要依次存储（$0,1, 2,3,4,5,6,7$），哈希函数为 $h(x)=x^2 \mod 11$。请问 $7$ 存储在哈希表哪个地址中（ ）。
$G$ 是一个非连通简单无向图（没有自环和重边），共有 $36$ 条边，则该图至少有（ ）个点。
令根结点的高度为 $1$，则一棵含有 $2021$ 个结点的二叉树的高度至少为（ ）。
前序遍历和中序遍历相同的二叉树为且仅为（ ）。
定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF 最少需要（ ） 次上述操作。
有如下递归代码
solve(t, n):
if t = 1 return 1
else return 5 * solve(t - 1, n) mod n
则 solve(23, 23) 的结果为（ ）。
斐波那契数列的定义为：
$$F_1=1,\F_2=1,\F_n=F_{n-1}+F_{n-2} (n\ge 3)$$
现在用如下程序来计算斐波那契数列的第 $n$ 项，其时间复杂度为（ ）。
F(n):
if n <= 2 return 1
else return F(n - 1) + F(n - 2)
有 $8$ 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ ）种方案。
设一个三位数 $n= \overline {abc}$，$a, b, c$ 均为 $1\sim9$ 之间的整数，若以 $a$、$b$、$c$ 作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 $n$ 有（ ）个。
有如下的有向图，节点为 $A, B, \cdots , J$，其中每条边的长度都标在图中。则节点 $A$ 到节点 $J$ 的最短路径长度为（ ）。
[图片]
阅 阅读程序（共 18 题，共 0 分）
#include <iostream>
#include <cmath>
using namespace std;
const double r = acos(0.5);
int a1, b1, c1, d1;
int a2, b2, c2, d2;
inline int sq(const int x) { return x * x; }
inline int cu(const int x) { return x * x * x; }
int main()
{
cout.flags(ios::fixed);
cout.precision(4);
cin >> a1 >> b1 >> c1 >> d1;
cin >> a2 >> b2 >> c2 >> d2;
int t = sq(a1 - a2) + sq(b1 - b2) + sq(c1 - c2);
if (t <= sq(d2 - d1)) cout << cu(min(d1, d2)) * r * 4;
else if (t >= sq(d2 + d1)) cout << 0;
else {
double x = d1 - (sq(d1) - sq(d2) + t) / sqrt(t) / 2;
double y = d2 - (sq(d2) - sq(d1) + t) / sqrt(t) / 2;
cout << (x * x * (3 * d1 - x) + y * y * (3 * d2 - y)) * r;
}
cout << endl;
return 0;
}
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
将第 $18$ 行中 $t$ 的类型声明从 int 改为double，不会影响程序运行的结果。（ ）
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
将第 $23$、$24$ 行中的 / sqrt(t) / 2 替换为 / 2 / sqrt(t)，不会影响程序运行的结果。（ ）
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
将第 $25$ 行中的 x * x 改成 sq(x)，y * y 改成 sq(y)，不会影响程序运行的结果。（ ）
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
当输入为 0 0 0 1 1 0 0 1 时，输出为 1.3090。
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
当输入为 1 1 1 1 1 1 1 2 时，输出为（ ）。
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
这段代码的含义为（ ）。
#include <algorithm>
#include <iostream>
using namespace std;
int n, a[1005];
struct Node
{
int h, j, m, w;
Node(const int _h, const int _j, const int _m, const int _w) :
h(_h), j(_j), m(_m), w(_w)
{}
Node operator + (const Node &o) const
{
return Node(
max(h, w + o.h),
max(max(j, o.j), m + o.h),
max(m + o.w, o.m),
w + o.w);
}
};
Node solve1(int h, int m)
{
if (h > m)
return Node(-1, -1, -1, -1);
if (h == m)
return Node(max(a[h], 0), max(a[h], 0), max(a[h], 0), a[h]);
int j = (h + m) >> 1;
return solve1(h, j) + solve1(j + 1, m);
}
int solve2(int h, int m)
{
if (h > m)
return -1;
if (h == m)
return max(a[h], 0);
int j = (h + m) >> 1;
int wh = 0, wm = 0;
int wht = 0, wmt = 0;
for (int i = j; i >= h; i--) {
wht += a[i];
wh = max(wh, wht);
}
for (int i = j + 1; i <= m; i++) {
wmt += a[i];
wm = max(wm, wmt);
}
return max(max(solve2(h, j), solve2(j + 1, m)), wh + wm);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << solve1(1, n).j << endl;
cout << solve2(1, n) << endl;
return 0;
}
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
程序总是会正常执行并输出两行两个相等的数。（ ）
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
第 $28$ 行与第 $38$ 行分别有可能执行两次及以上。（ ）
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
当输入为 5 -10 11 -9 5 -7 时，输出的第二行为 7。（ ）
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
solve1(1, n) 的时间复杂度为（ ）。
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
solve2(1, n) 的时间复杂度为（ ）。
假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题：
当输入为 10 -3 2 10 0 -8 9 -4 -5 9 4 时，输出的第一行为（ ）。
#include <iostream>
#include <string>
using namespace std;
char base[64];
char table[256];
void init()
{
for (int i = 0; i < 26; i++) base[i] = 'A' + i;
for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
base[62] = '+', base[63] = '/';
for (int i = 0; i < 256; i++) table[i] = 0xff;
for (int i = 0; i < 64; i++) table[base[i]] = i;
table['='] = 0;
}
string encode(string str)
{
string ret;
int i;
for (i = 0; i + 3 <= str.size(); i += 3) {
ret += base[str[i] >> 2];
ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
ret += base[(str[i + 1] & 0x0f) << 2 | str[i + 2] >> 6];
ret += base[str[i + 2] & 0x3f];
}
if (i < str.size()) {
ret += base[str[i] >> 2];
if (i + 1 == str.size()) {
ret += base[(str[i] & 0x03) << 4];
ret += "==";
}
else {
ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
ret += base[(str[i + 1] & 0x0f) << 2];
ret += "=";
}
}
return ret;
}
string decode(string str)
{
string ret;
int i;
for (i = 0; i < str.size(); i += 4) {
ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
if (str[i + 2] != '=')
ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
if (str[i + 3] != '=')
ret += table[str[i + 2]] << 6 | table[str[i + 3]];
}
return ret;
}
int main()
{
init();
cout << int(table[0]) << endl;
int opt;
string str;
cin >> opt >> str;
cout << (opt ? decode(str) : encode(str)) << endl;
return 0;
}
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
程序总是先输出 一行 一个整数，再输出 一行 一个字符串。（ ）
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
对于任意不含空白字符的字符串 str1，先执行程序输入 0 str1，得到输出的第二行记为 str2；再执行程序输入 1 str2，输出的第二行必为 str1。（ ）
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
当输入为 1 SGVsbG93b3JsZA== 时，输出的第二行为 HelloWorld。（ ）
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
设输入字符串长度为 $n$，encode 函数的时间复杂度为（ ）。
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
输出的第一行为（ ）。
假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：
当输入为 0 CSP2021csp 时，输出的第二行为（ ）。
完 完善程序（共 10 题，共 0 分）
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
const int M = 10000;
bool Vis[M + 1];
int F[M + 1];
void update(int &x, int y) {
if (y < x)
x = y;
}
int main() {
int n;
cin >> n;
for (int i = 0; i <= M; i++)
F[i] = INT_MAX;
①;
int r = 0;
while (②) {
r++;
int x = 0;
for (int i = 1; i <= M; i++)
if (③)
x = i;
Vis[x] = 1;
for (int i = 1; i <= M; i++)
if (④) {
int t = F[i] + F[x];
if (i + x <= M)
update(F[i + x], t);
if (i != x)
update(F[abs(i - x)], t);
if (i % x == 0)
update(F[i / x], t);
if (x % i == 0)
update(F[x / i], t);
}
}
cout << F[n] << endl;
return 0;
}
（魔法数字）小 H 的魔法数字是 $4$。给定 $n$，他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M = 10000$ 的正整数。求至少可能用到多少个 $4$。
例如，当 $n= 2$ 时，有 2 = (4 + 4) / 4，用到了 $3$ 个 $4$，是最优方案。试补全程序。
① 处应填（ ）
（魔法数字）小 H 的魔法数字是 $4$。给定 $n$，他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M = 10000$ 的正整数。求至少可能用到多少个 $4$。
例如，当 $n= 2$ 时，有 2 = (4 + 4) / 4，用到了 $3$ 个 $4$，是最优方案。试补全程序。
②处应填（ ）
描述
（魔法数字）小 H 的魔法数字是 $4$。给定 $n$，他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M = 10000$ 的正整数。求至少可能用到多少个 $4$。
例如，当 $n= 2$ 时，有 2 = (4 + 4) / 4，用到了 $3$ 个 $4$，是最优方案。试补全程序。
③ 处应填（ ）
（魔法数字）小 H 的魔法数字是 $4$。给定 $n$，他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M = 10000$ 的正整数。求至少可能用到多少个 $4$。
例如，当 $n= 2$ 时，有 2 = (4 + 4) / 4，用到了 $3$ 个 $4$，是最优方案。试补全程序。
④ 处应填（ ）
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 100000, MAXT = MAXN << 1;
const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;
struct node {
int val;
int dep, dfn, end;
node *son[2]; // son[0], son[1] 分别表示左右儿子
} T[MAXN];
int n, t, b, c, Log2[MAXC + 1];
int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];
node *root, *A[MAXT], *Min[MAXL][MAXC];
void build() { // 建立 Cartesian 树
static node *S[MAXN + 1];
int top = 0;
for (int i = 0; i < n; i++) {
node *p = &T[i];
while (top && S[top]->val < p->val)
①;
if (top)
②;
S[++top] = p;
}
root = S[1];
}
void DFS(node *p) { // 构建 Euler 序列
A[p->dfn = t++] = p;
for (int i = 0; i < 2; i++)
if (p->son[i]) {
p->son[i]->dep = p->dep + 1;
DFS(p->son[i]);
A[t++] = p;
}
p->end = t - 1;
}
node *min(node *x, node *y) {
return ③ ? x : y;
}
void ST_init() {
b = (int)(ceil(log2(t) / 2));
c = t / b;
Log2[1] = 0;
for (int i = 2; i <= c; i++)
Log2[i] = Log2[i >> 1] + 1;
for (int i = 0; i < c; i++) {
Min[0][i] = A[i * b];
for (int j = 1; j < b; j++)
Min[0][i] = min(Min[0][i], A[i * b + j]);
}
for (int i = 1, l = 2; l <= c; i++, l <<= 1)
for (int j = 0; j + l <= c; j++)
Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);
}
void small_init() { // 块内预处理
for (int i = 0; i <= c; i++)
for (int j = 1; j < b && i * b + j < t; j++)
if (④)
Dif[i] |= 1 << (j - 1);
for (int S = 0; S < (1 << (b - 1)); S++) {
int mx = 0, v = 0;
for (int i = 1; i < b; i++) {
⑤;
if (v < mx) {
mx = v;
Pos[S] = i;
}
}
}
}
node *ST_query(int l, int r) {
int g = Log2[r - l + 1];
return min(Min[g][l], Min[g][r - (1 << g) + 1]);
}
node *small_query(int l, int r) { // 块内查询
int p = l / b;
int S = ⑥;
return A[l + Pos[S]];
}
node *query(int l, int r) {
if (l > r)
return query(r, l);
int pl = l / b, pr = r / b;
if (pl == pr) {
return small_query(l, r);
} else {
node *s = min(small_query(l, pl * b + b - 1),
small_query(pr * b, r));
if (pl + 1 <= pr - 1)
s = min(s, ST_query(pl + 1, pr - 1));
return s;
}
}
int main() {
int m;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> T[i].val;
build();
DFS(root);
ST_init();
small_init();
while (m--) {
int l, r;
cin >> l >> r;
cout << query(T[l].dfn, T[r].dfn)->val << endl;
}
return 0;
}
最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。 试补全程序。
最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。 试补全程序。
最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。 试补全程序。
最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。 试补全程序。
最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。 试补全程序。
最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。 试补全程序。