1.txt - 43.txt，其中判断题的答案为单个大写字母 T 或 F，选择题的答案为正确选项对应的单个大写字母。下列关于图灵机的说法一定不正确的是（）。
A. 有无穷多个
B. 包含无穷多个状态
C. 接受无穷多种输入
D. 能运行无穷多步而不停机
摩尔定律对（）的性能迭代速度做出了预测。
A. CPU
B. GPU
C. RAM
D. ROM
在 NOI Linux 2.0 上安装 GNU G++ 9.3.0 编译器的方式是（）。
A. 系统预装
B. 通过 apt 包管理器获取
C. 通过 Git 拉取 Github 仓库得到二进制文件
D. 在 GNU 官网获取源代码自行构建
在 /home 目录下执行下列命令，执行结果与其他三个差异最大的是（）。
A. cd .
B. cd ..
C. cd /
D. cd //
在某个时间限制为 秒的题目下，某测试点的自测结果如下，则（）。
real 0m1.931s
user 0m0.945s
sys 0m0.985s
A. 超过时间限制，以此申诉会被接受
B. 超过时间限制，以此申诉不会被接受
C. 没有超过时间限制，以此申诉会被接受
D. 没有超过时间限制，以此申诉不会被接受
下列指令中会让待编译的 C++ 程序无法通过编译的是（）。
A. echo "int main(){}" > A.cpp && g++ A.cpp -O2 -lm -fsanitize=undefined
B. echo "int main(){}" > B.cpp && g++ B.cpp -static -fsanitize=undefined
C. echo "int main(){}" > C.cpp && g++ C.cpp -O2 -lm -fsanitize=address
D. echo "int main(){}" > D.cpp && g++ D.cpp -static -fsanitize=address
下列头文件中被 bits/stdc++.h 包含的是（）。
A. glad
B. locale
C. opencv2
D. sys
下面两个数组占用的空间分别为（）。
struct E { void greet() { puts("Hello!"); } } e[1024];
union U { int x; char y; } u[1024];
A. 0，4 KiB
B. 0，5 KiB
C. 1 KiB，4 KiB
D. 1 KiB，5 KiB
在 -O0 开关下，以下代码的时间复杂度是（）。
int f(int n)
{
if (n <= 1) return n;
int s = 0;
for (int i = 1; i <= n - 1; i++)
s += f(n - i);
return s;
}
A.
B.
C.
D.
存储 位二进制数至少需要（）个三进制位。
A.
B.
C.
D.
同时接受 ABCDEF、ABCFED、ACEFDB 三个序列作为 DFS 序的有根树有（）棵。
A.
B.
C.
D.
Sleeping Lion 带着 匹速度互不相同的马穿越到了战国时期，重新组织了一次「田忌赛马」，并安排对局让田忌以 险胜齐威王，则开赛前可能的马匹分配方式有（）种。
A.
B.
C.
D.
给定序列 ，请完成下面三个问题。
在相邻两项间填入 中的一个，所组成的算式可能出现的最大运算结果是（）。
A.
B.
C.
D.
从中选出两个数，能够得到的最大异或和为（）。
A.
B.
C.
D.
下面四个上述序列的子序列中，对应集合不存在所含元素异或和为 的非空子集的是（）。
A.
B.
C.
D.
#include <cstdio>
#include <cstring>
using namespace std;
char s[50];
int main()
{
int P = scanf("%s", s + 1);
int Q = printf("%c%u%c\n", s[1], strlen(s + 1) - 2, s[strlen(s + 1)]);
return 0;
} // Line 10
输入格式：
不超过 个（但不少于 个）大小写拉丁字母字符。
。
。
输入 a，输出 a-1a。
在 NOI Linux 2.0 下，从控制台读入时，（）可以代替回车让程序结束读入。
A. Ctrl + A
B. Ctrl + B
C. Ctrl + C
D. Ctrl + D
忽略输入格式要求，输入 Sleeping Lion，输出（）。
A. S6g
B. S8g
C. S11n
D. S13n
忽略输入格式要求，下列输入中不会使得程序行为未定义的最长输入是（）。
A. 输入 个 a
B. 输入 个 a
C. 输入 个 a
D. 输入 个 a
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
pair <int, int> c[100012];
bool cmp(pair <int, int> first, pair <int, int> second)
{
return first.first < second.first;
}
int main()
{
int n, k, x = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> c[i].first >> c[i].second;
sort(c + 1, c + n + 1, cmp); // Line 16
for (int i = 1; i <= n; i++)
{
if (c[i].first - x >= 2)
cout << x + 1 << ' ' << c[i].first - 1 << endl;
x = max(x, c[i].second);
}
if (x < k) cout << x + 1 << ' ' << k;
return 0;
} // Line 25
输入格式：
第一行两个正整数，分别为 。
下面 行，第 行两个正整数 。
该程序的时间复杂度为 。
输出数据中每行的第一个整数总是不大于第二个整数。
将第 行的 c + 1 改为 c，程序对所有输入的运行结果不变。
输入以下数据：
5 25
2 8
3 7
11 15
16 20
<1> 23
输出结果为：
1 1
9 10
21 22
<2> 25
填写 <1> 处和 <2> 处缺失的内容：（）
A. ，
B. ，
C. ，
D. ，
输入以下数据：
5 20
1 3
6 10
11 13
16 20
<3> <4>
输出结果为空，则填写 <3> 处和 <4> 处缺失的内容的方案数为：（）
A.
B.
C.
D.
输出数据至多有（）行。
A.
B.
C.
D.
#include <algorithm> // Line 1
#include <iostream>
#include <vector>
using namespace std;
int size1[100012], size2[100012], layer[100012], above[100012];
vector <int> e[22][100012], d[100012];
bool label[22][100012];
void dfs0(int x, int up, int round)
{
size1[x] = 0; // Line 10
size2[x] = 0; // Line 11
label[round + 1][x] = true;
for (auto y: e[round][x])
{
if (y == up) continue; // Line 15
dfs0(y, x, round);
}
}
int dfs1(int x, int up, int round)
{
size1[x] = 1;
for (auto y: e[round][x])
{
if (y == up) continue;
size1[x] += dfs1(y, x, round);
}
return size1[x];
}
void dfs2(int n, int x, int up, int round)
{
size2[x] = n - size1[x];
for (auto y: e[round][x])
{
if (y == up) continue;
size2[x] = max(size2[x], size1[y]);
dfs2(n, y, x, round);
}
}
void dfs3(int x, int up, int top, int round)
{
above[x] = top;
if (x != top && up != top)
{
e[round + 1][x].push_back(up);
e[round + 1][up].push_back(x);
}
for (auto y: e[round][x])
{
if (y == up) continue;
dfs3(y, x, top, round);
}
}
int center(int n, int start, int round) // Line 53
{
int total = dfs1(start, 0, round);
dfs2(total, start, 0, round);
for (int i = 1; i <= n; i++)
if (size1[i] && 2 * size2[i] <= total)
{
dfs0(start, 0, round); // Line 60
return i;
}
return -1;
}
void build(int n)
{
for (int i = 1; i <= 20; i++)
for (int j = 1; j <= n; j++)
if (!layer[j] && !label[i][j])
{
int root = center(n, j, i - 1);
layer[root] = i;
if (i >= 2)
{
d[root].push_back(above[root]);
d[above[root]].push_back(root);
}
dfs3(root, 0, root, i - 1);
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n - 1; i++)
{
int x, y;
cin >> x >> y;
e[0][x].push_back(y);
e[0][y].push_back(x);
}
build(n);
for (int i = 1; i <= n; i++)
{
sort(d[i].begin(), d[i].end());
for (auto y: d[i])
if (y > i) cout << i << ' ' << y << endl;
}
return 0;
} // Line 100
输入格式：
第一行一个正整数 ，表示无向图 的结点个数。
约定 中 个结点的标号分别为 。
下面 行，第 行两个正整数 ，表示 中的一条无向边 。
中有且仅有输入数据中描述的无向边。
保证 是一棵无根树。
约定无向图 中 个结点的标号分别为 。
输出数据中第 行的两个正整数 表示 中的一条无向边 。
中有且仅有输出数据中描述的无向边。
第 行的 center 函数不可能返回 。
删去第 行，则程序可能会出现运行超时、运行错误等问题。
删去第 行和第 行，在第 行后加入 #include <cstring>，在第 行后加入 memset(size1, 0, sizeof size1); 和 memset(size2, 0, sizeof size2);，则新程序在最坏情况下的时间复杂度比原程序更劣。
输入以下数据：
8
1 2
3 4
5 6
7 8
2 4
4 6
6 8
则输出数据中所有正整数的和为（）。
A.
B.
C.
D.
程序运行过程中，layer 数组中元素的最大可能值是（）。
A.
B.
C.
D.
以下输入数据中均有 ，其中会导致 与 不同构的是（）。
A.
B. ，
C. ，
D. ，，
现有一个 的排列 ，设 为 中前 项的最大值，给定序列 ，试构造一个合法的排列 ，如果无解则输出 。
，。
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int a[10000012], b[10000012];
queue <int> c;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
if (a[i] /* (34) _____ */ max(a[i - 1], i))
{
puts("-1");
return 0;
}
for (int i = 1; i <= n; i++)
if (a[i] /* (35) _____ */ a[i - 1])
{
b[i] = a[i];
for (int j = /* (36) _____ */; j <= /* (37) _____ */; j++)
c.push(j);
}
for (int i = 1; i <= n; i++)
{
if (b[i]) continue;
int d = c.front();
c.pop();
b[i] = d;
}
for (int i = 1; i <= /* (38) _____ */; i++)
printf("%d ", b[i]);
printf("%d\n", b[n]);
return 0;
}
A. >
B. >=
C. <
D. <=
A. >
B. >=
C. <
D. <=
A. 1
B. a[i - 1] - 1
C. a[i - 1]
D. a[i - 1] + 1
A. 1
B. a[i] - 1
C. a[i]
D. a[i] + 1
A. 1
B. n - 1
C. n
D. n + 1
定义一个「安全的样例」为满足以下条件的数字：
求「安全的样例」的数量对 取模后的结果。
，， 中只含数字字符。
#include <algorithm>
#include <iostream>
#include <string>
#define B39 /* (39) _____ */
#define B40 /* (40) _____ */
#define B41 /* (41) _____ */
#define B42 /* (42) _____ */
#define B43 /* (43) _____ */
using namespace std;
const int P = 1e9 + 7;
int f[1012][1012][2], p[1012];
void accumulate(int& x, int y)
{
x += y;
if (x >= P) x -= P;
}
int main()
{
string n, S;
cin >> n >> S;
reverse(n.begin(), n.end());
int m = (int) S.size(), l = (int) n.size() - 1;
S = ' ' + S;
for (int i = 2; i <= m; i++)
{
int h = p[i - 1];
while (h)
{
if (B39) break;
B40;
}
if (B39) h++;
p[i] = h;
}
for (int j = 1; j <= n[l] - '0'; j++)
f[l][B41][j == n[l] - '0'] = 1;
for (int i = l - 1; i >= 0; i--)
for (int j = 1; j <= 9; j++)
f[i][B41][0]++;
for (int i = l - 1; i >= 0; i--)
for (int j = 0; j <= B42; j++)
for (int k = 0; k <= 9; k++)
{
int h = j;
while (B43 && h) B40;
if (!(B43)) h++;
accumulate(f[i][h][0], f[i + 1][j][0]);
if (k <= n[i] - '0') accumulate(f[i][h][k == n[i] - '0'], f[i + 1][j][1]);
}
int a = 0;
for (int i = 0; i <= B42; i++)
{
accumulate(a, f[0][i][0]);
accumulate(a, f[0][i][1]);
}
cout << a << endl;
return 0;
}
A. S[h] == S[i]
B. S[h] == S[i + 1]
C. S[h + 1] == S[i]
D. S[h + 1] == S[i + 1]
A. h = p[h]
B. h = p[h] + 1
C. h = p[h + 1]
D. h = p[h + 1] + 1
A. j == S[0] - '0'
B. j != S[0] - '0'
C. j == S[1] - '0'
D. j != S[1] - '0'
A. 1
B. m - 1
C. m
D. m + 1
A. k == S[h] - '0'
B. k != S[h] - '0'
C. k == S[h + 1] - '0'
D. k != S[h + 1] - '0'