1. 在 Linux 系统中，如果想要删除指定文件，应该使用哪个指令？
A. mv
B. rm
C. delete
D. del
2. 某微型机地址总线位长 位，其最大寻址空间为？
A. KB
B. KB
C. KB
D. KB
3. 已知 , 且对于 有 ，则 的值为？
A.
B.
C.
D.
4. 个人每人投一次硬币（每次投出正面或反面的概率均等），投出正面的人各得 元，所有投出反面的人平分 元，有几种情况使得 人总收益不超过 元？
A.
B.
C.
D.
5. 现有一棵树，其部分结点权值如图所示，问空白结点处权值为几时这棵树既可以是二叉堆又可以是哈夫曼树？
A.
B.
C.
D.
6. 表达式 a*(b-c)+d 的前缀表达形式为？
A. +*a-bcd
B. *a+-bcd
C. +a*b-cd
D. *+a-bcd
7. 以下加权图的最小生成树权值之和是？
A.
B.
C.
D.
8. 下列对排序算法的表述不恰当的一项是？
A. 堆排序是利用二叉堆这种数据结构而设计的一种排序算法
B. 堆排序本质是建立在堆上的选择排序
C. 桶排序适用于待排序数据值域较大但分布比较均匀的情况
D. 桶排序的最坏时间复杂度为
9. 以下 取值中哪项符合 等式？
A.
B.
C.
D.
10. 若 ，定义 ，其中 。对于给定的自然数 ，存在序列 ，其中对于 都有 且 ，称 为 的数根，记作 。
给定地址区间为 的哈希表，哈希函数为 。采用地址探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 冲突了则从地址 重新探查）。哈希表初始为空表，依次存储 后，请问 存储在哈希表哪个地址中？
A.
B.
C.
D.
11. 一棵有 个结点的树，其直径长度最短可能是几，最长可能是几？
A. 和
B. 和
C. 和
D. 和
12. 从 中选出 个数围成一圈，至少选出 个偶数围成圈有多少种方案？（若两个圈旋转后相同则视为同一种方案，如 和 为同一种方案）
A.
B.
C.
D.
13. 以下程序中，若在主函数中调用 binary_search(0, 100)，问运行过程中会调用几次 f() 函数？
int f(int x) {
return 3 * x * x - 100;
}
int binary_search(int l, int r) {
if (l >= r) return r;
int mid = (l + r) >> 1;
if (f(mid) > 0) return binary_search(l, mid);
else return binary_search(mid, r);
}
A.
B.
C.
D. 不断调用 f() 函数，直至栈溢出
14. 有三个栈，第一个栈自底向上存放着 这 个元素（），其余两个栈初始为空，每次操作可以把某个栈的栈顶元素取出并放入另一个栈中。问：将第一个栈里的元素倒置成 在最佳的策略下渐进时间复杂度为？
A.
B.
C.
D.
15. 以下有向图有几个合法的拓扑序列？
A. 个
B. 个
C. 个
D. 该图不存在合法的拓扑序列
01 #include <iostream>
02 using namespace std;
03
04 unsigned short f(unsigned short x, unsigned short y) {
05 unsigned short com = x & y;
06 unsigned short bit = 1;
07 while(bit <= 8){
08 com |= com >> bit;
09 bit <<= 1;
10 }
11 com += 1;
12 com >>= 1;
13 return x ^ y ^ com;
14 }
15
16 int main() {
17 unsigned short a, b;
18 cin >> a >> b;
19 unsigned short r1 = f(a, b);
20 unsigned short r2 = (a | b) & ~(a & b);
21 cout << r1 << " " << r2 << endl;
22 return 0;
23 }
设输入的 都是不超过 的自然数，完成下面的判断题和单选题:
f 函数中的变量 com 类型修改为 unsigned int，程序的输出不变。（ ）a 是 b 的 倍时，r1 一定等于 r2。（ ）（4 分）以下选项中，对于 r1 和 r2 的表述正确的是（ ）。
A. r1 一定大于等于 r2
B. r1 一定小于等于 r2
C. r1 一定等于 r2
D. 以上表述都不对
当输入为 时，程序的输出为（ ）。
A.
B.
C.
D.
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int maxn = 10010;
04
05 int rad[maxn];
06 void init(const string &s) {
07 int n = s.size();
08 for (int i = 0, l = 0, r = -1; i < n; i++) {
09 int k = (i > r) ? 0 : min(rad[l + r - i + 1], r - i + 1);
10 while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) k++;
11 rad[i] = k--;
12 if (i + k > r) l = i - k - 1, r = i + k;
13 }
14 }
15
16 vector<int> event[maxn];
17 int len[maxn];
18 int main() {
19 string s;
20 cin >> s;
21 int n = s.size();
22 init(s);
23 for (int i = 1; i < n; ++i) {
24 event[i].push_back(-i * 2);
25 event[i + rad[i]].push_back(i * 2);
26 }
27 multiset<int> ms;
28 for (int i = 1; i < n; ++i) {
29 for (int as : event[i]) {
30 if (as > 0)
31 ms.erase(ms.find(-as));
32 else
33 ms.insert(as);
34 }
35 if (!ms.empty()) len[i] = *ms.begin() + (i + 1) * 2;
36 }
37
38 for (int i = 0; i < n; ++i) {
39 cout << len[i] << " ";
40 }
41 return 0;
42 }
输入字符串 s 满足 ，且字符类型为小写字符，完成下面的判断题和单选题。
将程序第 23、28 行中的 i = 1 均修改为 i = 0，输出不变。（ ）
（2分）若输入为 abbabc，则程序输出为 1 1 2 3 1 1。（ ）
（2分）在字符串长度为 9 的所有合法输入中，字符串 xyzxyzxyz 是使得程序输出和最小的字符串之一，字符串 xyzzyxxyz 是使得程序输出和最大的字符串之一。（ ）
若输入abcbaaa，则执行完 22 行的 init(s) 后，以下说法正确的是（ ）。
A. rad[2] = 0
B. rad[2] = 3
C. rad[6] = 2
D. rad[6] = 3
设输入字符串的长度为 ，程序的时间复杂度为（ ）。
A.
B.
C.
D.
若输入的字符串中字符全部相同，且字符串长度 为偶数，则程序输出结果的和为（ ）。
A.
B.
C.
D.
01 #include <iostream>
02 #include <vector>
03 #include <cstdlib>
04 using namespace std;
05
06 struct Dsu {
07 vector<int> f, siz;
08 Dsu(int n) : f(n), siz(n, 1) {
09 for (int i = 0; i < n; i++) f[i] = i;
10 }
11
12 int getRoot(int u) {
13 if (f[u] == u) return u;
14 return f[u] = getRoot(f[u]);
15 }
16
17 void merge(int u, int v) {
18 u = getRoot(u), v = getRoot(v);
19 if (u == v) return ;
20 if (siz[u] < siz[v]) swap(u, v);
21 siz[u] += siz[v];
22 f[v] = u;
23 }
24
25 int size(int u) {
26 return siz[getRoot(u)];
27 }
28 };
29
30 struct FenwickTree {
31 vector<int> data;
32 FenwickTree(int n) : data(n + 1) {}
33
34 void add(int p, int x) {
35 while (p < data.size()) {
36 data[p] += x;
37 p += p & -p;
38 }
39 }
40
41 int sum(int r) {
42 int s = 0;
43 while (r > 0) {
44 s += data[r];
45 r -= r & -r;
46 }
47 return s;
48 }
49 };
50
51 const int N = 100010;
52 int a[N];
53 vector<int> where[N];
54
55 int main() {
56 int n;
57 cin >> n;
58 for (int i = 0; i < n; i++) cin >> a[i];
59 for (int i = 0; i < n - 1; i++) {
60 int d = abs(a[i] - a[i + 1]);
61 where[d].push_back(i);
62 }
63 Dsu dsu(n);
64 FenwickTree ft1(n), ft2(n);
65 ft1.add(1, n), ft2.add(1, n);
66 long long ans = 0;
67 for (int d = 0; d <= n; d++) {
68 for (const int &i : where[d]) {
69 int s1 = dsu.size(i), s2 = dsu.size(i + 1), s3 = s1 + s2;
70 ft1.add(s1, -s1), ft2.add(s1, -1);
71 ft1.add(s2, -s2), ft2.add(s2, -1);
72 ft1.add(s3, s3), ft2.add(s3, 1);
73 dsu.merge(i, i + 1);
74 }
75 if (d == 0) continue;
76 int sum = ft1.sum(n) - ft1.sum(d - 1), cnt = ft2.sum(n) - ft2.sum(d - 1);
77 ans += sum - cnt * (d - 1);
78 }
79 cout << ans << '\n';
80 return 0;
81 }
假设输入总是合法的且 ，完成下面的判断题和单选题。
此代码所实现的算法时间复杂度是 。（ ）
删除第 行代码，并将第 行的 f[u] == u 改为 f[u] == 0，不影响程序运行结果。（ ）
第 行的 sum - cnt * (d - 1) 可用于计算 a 数组中长度为 d，且相邻元素最大差值也恰好为 d 的子数组个数。（ ）
将第 行的 d <= n 替换为 d < n ，那么原输出与现输出的大小关系为（ ）。
A. 一定大于
B. 一定等于
C. 大于或等于都有可能
D. 以上三种情况都不对
若 ，在程序运行过程中，第 行 sum 变量赋值后可能的最小值和最大值分别是（ ）。
A.
B.
C.
D.
当输入为 ，输出为（ ）。
A.
B.
C.
D.
有一个长度为 的序列 ，序列每个元素都是不超过 的正整数。在 中任选两个数进行异或运算，可以得到 个异或和（ 和 视为两个异或和， 不属于有效的异或和），求其中第 小的异或和。上述参数满足 和 。
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e5 + 5, up = 30;
04 long long k;
05 int a[N], n, tot;
06 int tr[N * 32][2], sz[N * 32];
07
08 void insert(int x) {
09 int u = 0;
10 for (int i = up; i >= 0; i--) {
11 int p = (x >> i) & 1;
12 if (!tr[u][p]) tr[u][p] = ++tot;
13 u = tr[u][p];
14 sz[u]++;
15 }
16 }
17
18 int query(int x, int ai) {
19 int u = 0, cnt = 0;
20 for (int i = up; i >= 0; i--) {
21 int p = (x >> i) & 1, q = (ai >> i) & 1;
22 int to;
23 if (p) {
24 to = tr[u][!q];
25 /*____1____*/;
26 }
27 else /*____2____*/;
28 if (!to) return cnt;
29 u = to;
30 }
31 /*____3____*/;
32 return cnt;
33 }
34
35 bool check(int x) {
36 long long sum = 0;
37 for (int i = 1; i <= n; i++) {
38 sum += query(x, a[i]);
39 }
40 return /*____4____*/;
41 }
42
43 int main() {
44 cin >> n >> k;
45 for (int i = 1; i <= n; i++) {
46 cin >> a[i];
47 insert(a[i]);
48 }
49 int l = 0, r = 1e9;
50 while (l <= r) {
51 int mid = (l + r) / 2;
52 if (check(mid)) {
53 r = mid - 1;
54 }
55 else {
56 l = mid + 1;
57 }
58 }
59 cout << /*____5____*/ << endl;
60 return 0;
61 }
/*____1____*/ 处应填（ ）
A. cnt++
B. cnt += sz[tr[u][to]]
C. cnt += sz[tr[u][p]]
D. cnt += sz[tr[u][q]]
/*____2____*/ 处应填（ ）
A. to = tr[u][p]
B. to = tr[u][q]
C. to = tr[u][x]
D. to = tr[u][ai]
/*____3____*/ 处应填（ ）
A. cnt++
B. cnt += sz[u]
C. cnt += sz[ai]
D. cnt += sz[x]
/*____4____*/ 处应填（ ）
A. sum - n > k
B. sum - n < k
C. sum - n >= k
D. sum - n <= k
/*____5____*/ 处应填（ ）
A. l
B. r
C. l + 1
D. r - 1
给定长度为 的数组 ，以及 次询问，每次询问给定区间范围 和 ，以及正整数 ，问区间中数值第 小的数是多少。
上述参数满足 ，，，。
解决该问题有许多算法，以下程序使用分治算法，时间复杂度 。
试补全程序。
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int maxn = 2e5 + 5;
05
06 int n, m;
07 int a[maxn];
08 int s[maxn], t[maxn], k[maxn];
09 vector<int> vec;
10 vector<vector<int>> pos;
11 int ret[maxn];
12
13 int c[maxn];
14
15 void update(int i, int d) {
16 for (; i <= /*____1____*/; i += i & -i) c[i] += d;
17 }
18
19 int query(int i) {
20 int ret = 0;
21 for (; i; i -= i & -i) ret += c[i];
22 return ret;
23 }
24
25 void dfs(int l, int r, const vector<int> &q) {
26 int mid = (l + r) / 2;
27 for (int x = l; x <= mid; x++) {
28 for (int i: pos[x]) update(i, 1);
29 }
30 if (l == r) {
31 for (int i: q) ret[i] = l;
32 return;
33 }
34 vector<int> q1, q2;
35 for (int i: q) {
36 int cnt = query(t[i]) - query(s[i] - 1);
37 if (k[i] <= cnt) q1.push_back(i);
38 else q2.push_back(i);
39 }
40 for (int x = l; x <= mid; x++) {
41 for (int i: pos[x]) /*____2____*/;
42 }
43 dfs(l, mid, q1);
44 dfs(mid + 1, r, q2);
45 }
46
47 int main() {
48 ios::sync_with_stdio(false);
49 cin.tie(nullptr);
50
51 cin >> n >> m;
52 for (int i = 1; i <= n; i++) cin >> a[i];
53 for (int i = 1; i <= m; i++) cin >> s[i] >> t[i] >> k[i];
54
55 for (int i = 1; i <= n; i++) vec.push_back(a[i]);
56 sort(vec.begin(), vec.end());
57 vec.erase(unique(vec.begin(), vec.end()), vec.end());
58 pos.resize(vec.size() + 1);
59 for (int i = 1; i <= n; i++) {
60 a[i] = /*____3____*/(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
61 pos[a[i]].push_back(i);
62 }
63
64 vector<int> q;
65 for (int i = 1; i <= m; i++) q.push_back(i);
66 dfs(1, /*____4____*/, q);
67 for (int i = 1; i <= m; i++) cout << /*____5____*/ << '\n';
68
69 return 0;
70 }
/*____1____*/ 处应填（ ）
A. n
B. m
C. vec.size()
D. vec.back()
/*____2____*/ 处应填（ ）
A. update(i, 1)
B. update(i, -1)
C. update(a[i], 1)
D. update(a[i], -1)
/*____3____*/ 处应填（ ）
A. find
B. binary_search
C. lower_bound
D. upper_bound
/*____4____*/ 处应填（ ）
A. n
B. m
C. vec.size()
D. vec.back()
/*____5____*/ 处应填（ ）
A. ret[i]
B. a[ret[i]]
C. vec[ret[i]]
D. vec[ret[i]-1]