单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 已知小写字母a的ASCII码为97，下列C++代码的输出结果是（ ）。

#include <iostream>
using namespace std;
int main() {
    char a = 'a';
    a++;
    cout << a;
    return 0;
}

{{ select(1) }}

• a
• b
• 97
• 98

2. 以下代码段的时间复杂度是（ ）。

void Merge(int a[], int left, int mid, int right) {
    int temp[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (a[i] < a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int m = left, n = 0; m <= right; m++, n++) a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right) {
    if (left == right) return;
    int mid = (left + right) / 2;
    Merge_Sort(a, left, mid);
    Merge_Sort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

{{ select(2) }}

• $O(n \log n)$
• $O(n)$
• $O(\log n)$
• $O\left(n^2\right)$

3. 以下哪个方案可以合理解决或缓解哈希表冲突？（ ） {{ select(3) }}

• 弃用发生冲突的新元素
• 用新元素覆盖发生冲突的元素
• 用新元素覆盖冲突位置的下一个位置
• 将新元素放置在冲突位置之后的第一个空位

4. 在数组$H[x]$中，若存在$(i < j) \&\& (H[i] > H[j])$，则称$(H[i], H[j])$为数组$H[x]$的一个逆序对。对于序列17, 14, 11, 29, 3, 16, 18, 15，其中有（ ）个逆序对。 {{ select(4) }}

• 13
• 11
• 12
• 14

5. 以下（ ）操作不属于STL模板优先队列的操作函数。 {{ select(5) }}

• push
• pop
• erase
• size

6. 以下选项中，（ ）没有涉及C++语言的面向对象特性。 {{ select(6) }}

• 在C++中构造一个类或结构体
• 在C++的排序应用中调用sort函数
• 在C++中调用用户定义的类成员
• 在C++中构造来源于同一基类的多个派生子类

7. $(2023)_{10} + (2025)_{16}$和以下哪个选项相等？（ ） {{ select(7) }}

• $(10252)_{10}$
• $(280A)_{16}$
• $(24012)_{8}$
• $(24016)_{8}$

8. 三个互不相等的正整数的最大公约数为20，最小公倍数为20000，那么这样的不同的正整数组的个数为（ ）。 {{ select(8) }}

• 42
• 48
• 50
• 52

9. 关于排序算法，下面的说法中哪个是错误的？（ ） {{ select(9) }}

• 堆排序和桶排序不一样，堆排序是基于比较的
• 堆排序不是一个稳定的排序算法
• 堆排序和快速排序在最坏情况下的时间复杂度都是$O(n^2)$
• 删除堆顶元素，需要交换堆顶元素和最后一个元素，并重新调整

10. 假设用$V = (d_1, d_2, d_3, d_4, d_5, d_6, d_7)$来表示某无向图的7个顶点的度数，下面给出的哪组V值是非法的？（ ） {{ select(10) }}

• $\{5, 3, 3, 3, 3, 2, 2\}$
• $\{3, 2, 3, 2, 3, 6, 3\}$
• $\{2, 3, 2, 3, 2, 3, 3\}$
• $\{1, 1, 3, 4, 3, 3, 3\}$

11. 与图论有关的典型算法中不能处理负权值的是（ ）。 {{ select(11) }}

• 弗洛伊德算法
• Tarjan算法
• SPFA算法
• 迪杰斯特拉算法

12. 有如下代码：

#include <iostream>
using namespace std;
const int MAXN = 10;
int dp[MAXN][MAXN];
int main() {
    for (int i = 1; i < MAXN; ++i) dp[i][0] = i;
    for (int j = 1; j < MAXN; ++j) dp[0][j] = j;
    for (int i = 1; i < MAXN; ++i)
        for (int j = 1; j < MAXN; ++j) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    cout << 2 * dp[8][4] + 1 << endl;
    return 0;
}

则程序输出的结果为（ ）。 {{ select(12) }}

• 2021
• 2023
• 2025
• 2027

13. 下列选项中，哪个可能是下图的广度优先遍历序列？（ ）

{{ select(13) }}

• 1, 3, 5, 7, 4, 2, 6, 8, 9
• 9, 4, 2, 1, 3, 7, 5, 6, 8
• 1, 3, 5, 7, 6, 8, 9, 4, 2
• 9, 4, 7, 2, 1, 3, 5, 6, 8

14. 从1到20中任取两个数a和b，$a + b$不是3的倍数的不同取法有（ ）种。 {{ select(14) }}

• 180
• 126
• 150
• 175

15. 某班级有n位同学，编号从1到n，联欢晚会抽奖时从1到n号中抽出两位同学获得特等奖，现在抽出的两位同学的编号之和为5的概率为$1/14$，则n为（ ）。 {{ select(15) }}

• 10
• 9
• 8
• 7

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int N = 3e5 + 5, mod = 1e9 + 7;
05 int n, m, a[N], sum[N], lsh[N], f[N];
06 inline int mod_add(int x, int y) {
07     x += y;
08     return x >= mod ? x - mod : x;
09 }
10 struct BIT {
11     int c[N];
12     inline void modify(int x, int k) {
13         while (x <= m) {
14             c[x] = mod_add(c[x], k);
15             x += (x & -x);
16         }
17     }
18     inline int query(int x) {
19         int res = 0;
20         while (x) {
21             res = mod_add(res, c[x]);
22             x -= (x & -x);
23         }
24         return res;
25     }
26 } odd, even;
27 
28 signed main() {
29     cin >> n;
30     for (int i = 1; i <= n; i++)
31         cin >> a[i];
32     for (int i = 1; i <= n; i++)
33         sum[i] = mod_add(sum[i - 1], a[i]);
34     for (int i = 1; i <= n; i++)
35         lsh[++m] = sum[i];
36     lsh[++m] = 0;
37     sort(lsh + 1, lsh + m + 1);
38     m = unique(lsh + 1, lsh + m + 1) - lsh - 1;
39     even.modify(1, 1);
40     for (int i = 1; i <= n; i++) {
41         int pos = lower_bound(lsh + 1, lsh + m + 1, sum[i]) - lsh;
42         if (sum[i] & 1) {
43             f[i] = mod_add(odd.query(pos), mod_add(even.query(m), mod_add(-even.query(pos - 1), mod)));
44             odd.modify(pos, f[i]);
45         } else {
46             f[i] = mod_add(mod_add(odd.query(m), mod_add(-odd.query(pos - 1), mod)), even.query(pos));
47             even.modify(pos, f[i]);
48         }
49     }
50     cout << f[n] << endl;
51     return 0;
52 }

对于所有数据，保证$1 ≤ n ≤ 3e5$，$0 ≤ a_i < 1e9 + 7$。

■ 判断题

16. 这段代码的空间复杂度为$O(N)$。（ ） {{ select(16) }}

• 正确
• 错误

17. 如果a数组从0开始存的话，这段代码也能输出正确结果。（ ） {{ select(17) }}

• 正确
• 错误

18. 如果不进行取模，$f[n]$可能会大于int的最大值。（ ） {{ select(18) }}

• 正确
• 错误

■ 选择题

19. 如果程序输入

4
1000000006 1 5 1000000004

则程序输出（ ）。 {{ select(19) }}

• 1
• 2
• 3
• 4

20. 对于以下哪种输入，程序输出为0？（ ） {{ select(20) }}

• 1 1
• 1 2
• 2 1 1
• 2 2 2

21. 如果程序输入

7
1 2 3 4 5 6 7

则程序输出（ ）。 {{ select(21) }}

• 1
• 2
• 3
• 4

(2)

01 #include <iostream>
02 #include <algorithm>
03 #include <vector>
04 #include <map>
05 #include <set>
06 #include <numeric>
07 using namespace std;
08 typedef long long ll;
09 typedef vector<int> vi;
10 const int _ = 5e5 * 4 + 1;
11 map<int, vector<int>> mp;
12 ll n, a[_], b[_], last;
13 int o[_];
14 set<int> si;
15 typedef set<int>::iterator sit;
16 sit prei(sit sx) { return --sx; }
17 sit sufi(sit sx) { return ++sx; }
18 class SOL {
19 public:
20     map<int, ll> mtr;
21     void radd(int l, int r, ll val) {
22         mtr[l] += val, mtr[r + 1] -= val;
23     }
24     void rans() {
25         ll ans0 = accumulate(a + 1, a + n + 1, 0LL), add = 0;
26         for (int i = 1; i <= n; i++) {
27             add += mtr[i];
28             cout << (ans0 + add) << endl;
29         }
30     }
31 } TR;
32 int pre[_], suf[_];
33 bool cmp(int i1, int i2) {
34     if (a[i1] == a[i2]) return i1 < i2;
35     else return a[i1] < a[i2];
36 }
37 int main() {
38     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
39     cin >> n;
40     for (int i = 1; i <= n; i++) {
41         cin >> a[i];
42         a[i + n] = a[i];
43         if (last == 0 || a[i] < a[last])
44             last = i + n;
45     }
46     for (int i = 1; i <= n; i++)
47         a[i] = a[last - n + i];
48     iota(o + 1, o + n + 1, 1);
49     sort(o + 1, o + n + 1, cmp);
50     si = set<int>(o + 1, o + n + 1);
51     for (int i = 1; i <= n; i++) {
52         pre[o[i]] = *prei(si.find(o[i]));
53         suf[o[i]] = *sufi(si.find(o[i]));
54     }
55     for (int i = 1; i <= n; i++) {
56         ++pre[i];
57         if (a[i] < a[pre[i]])
58             TR.radd(1, pre[i], -a[i]);
59         if (a[i] > a[suf[i]])
60             TR.radd(suf[i] - i, suf[i] - pre[i], -a[i]);
61     }
62     TR.rans();
63 }

假设$1 ≤ n ≤ 5e5$，$1 ≤ a[i] ≤ 1e9$，回答下列问题。

■ 判断题

22. 不考虑空间问题，本段代码只需要$_ >= 5e5 * 2 + 1$，就不会发生数组越界。（ ） {{ select(22) }}

• 正确
• 错误

23. 本段代码使用了二阶前缀和。（ ） {{ select(23) }}

• 正确
• 错误

24. 在本段代码第58行与第60行中，实际上是向TR加上或者减去一个等比数列。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题

25. 该算法的时间复杂度为（ ）。 {{ select(25) }}

• $O\left(n^2\right)$
• $O\left(\log^2 n\right)$
• $O(n)$
• $O(n \log n)$

26. 如果输入如下：

6
17 18 14 23 13 6676 196 897

则程序输出的第一个数为（ ）。 {{ select(26) }}

• 3862
• 3861
• 3860
• 3859

27. 如果输入如下：

10
99 10 10 682 1000000000 100000000 1000000000

则程序输出的第一个数为（ ）。 {{ select(27) }}

• 1000000054
• 2000000053
• 3000000054
• 3000000053

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e5 + 5, base = 20;
04 int f[1 << base], state[1 << base], cnt[1 << base], a[N];
05 int n, ans;
06 void dfs(int u, int now, int state) {
07     f[state] = min(f[state], u - 1);
08     if (u > 5) return;
09     for (int i = now; i <= base; i++)
10         dfs(u + 1, i, (state | (state << i)) & ((1 << base) - 1));
11 }
12 int main() {
13     memset(f, 0x7f, sizeof(f));
14     dfs(1, 1, 1);
15     for (int mid = 1; mid < (1 << base); mid <<= 1)
16         for (int i = 0; i < (1 << base); i += (mid << 1))
17             for (int j = 0; j < mid; j++)
18                 f[i + j] = min(f[i + j], f[i + j + mid]);
19     for (int i = 1; i < (1 << base); i++)
20         if (!(i & 1)) f[i] = min(f[i], f[i >> 1]);
21     scanf("%d", &n);
22     for (int i = 1; i <= n; i++) {
23         scanf("%d", &a[i]);
24         for (int j = 2; j * j <= a[i]; j++) {
25             if (a[i] % j == 0) {
26                 int c = 0;
27                 while (a[i] % j == 0) c++, a[i] /= j;
28                 state[j] |= (1 << c);
29                 ++cnt[j];
30             }
31         }
32         if (a[i] > 1) ++cnt[a[i]], state[a[i]] |= 2;
33     }
34     for (int i = 2; i <= 1000000; i++) {
35         if (cnt[i] != n) state[i] |= 1;
36         ans += f[state[i]];
37     }
38     printf("%d", ans);
39     return 0;
40 }

对于100%的数据，有$1 ≤ n ≤ 10^5$，$1 < a_i ≤ 10^6$。

■ 判断题

28. 代码第12行运行后，f的所有值都变成-1。（ ） {{ select(28) }}

• 正确
• 错误

29. 设x的二进制表示为1000010，第18行完成之后f[x]为6。（ ） {{ select(29) }}

• 正确
• 错误

■ 选择题

30. 关于第14~18行代码，以下说法中正确的是（ ）。 {{ select(30) }}

• 对于集合i，如果i的所有非自身子集si能被组合出来，那么$f[i] = \min(f[s[i]])$。
• 对于集合i，如果i的所有非自身子集si能被组合出来，那么$f[i] = \max(f[s[i]])$。
• 对于集合i，如果$i < k$能被组合出来（$1 < k = 20$），那么$f[i] = \min(f[i < k])$。
• 对于集合i，如果$i > k$能被组合出来，且二进制下1的个数相同（$1 ≤ k ≤ 20$），那么$f[i] = \min(f[i >> k]) - 1$。

31. 下列关于第6~10行dfs的描述，正确的是（ ）。 {{ select(31) }}

• 删去这段代码，程序复杂度不变。
• 如果改成u>6才return，其他条件不变，则程序输出不变。
• 如果改成u>4就return，则当$base = 15$时，原程序与新程序执行完dfs后，f数组相同。
• dfs执行完后，$f[0] = -1$，但因为后面根本不会访问f[0]，所以程序依然输出正确结果。

32. 关于本段代码，下列说法中正确的是（ ）。 {{ select(32) }}

• 程序执行完毕后，对于state[i]，假设当前值为x，并且有一个a[]恰好能被i^k整除，那么$x \& (1 << k - 1)$必然非零。
• f[]表示在背包下状态为i所需要的物品最小值，例如$f[1000111010] = 4$，因为{1,2,3,4}是一个符合条件的情况。
• 本段代码的时间复杂度为$O(3^{base})$，因为main里面出现了枚举子集的子集。
• 假如$a[1] = 30$，当读入a[1]并执行代码后，cnt[2] = cnt[4] = cnt[8] = 0。

完善程序（单选题，每小题3分，共计30分）

(1) 题目描述： 农场是一块$N \times N$的方格田地（$2 ≤ N ≤ 100$），某些相邻的田地之间有道路分隔，外围有高围栏防止牛离开。牛可以在任意相邻田地间自由移动（北、东、南、西），但不喜欢过马路。

农场上有K头牛（$1 ≤ K ≤ 100$，$K ≤ N^2$），每头牛位于不同的田地中。如果两头牛之间要相互访问必须至少穿越一条路，这对牛就被认为是"遥远的"。请计算有多少对牛是"遥远的"。

分析：直接记录牛的方位，用dfs染色，记录每个连通块上牛的个数，并且把它们两两相乘即可。

01 #include <cstdio>
02 #include <iostream>
03 #include <algorithm>
04 #include <cstring>
05 #include <vector>
06 using namespace std;
07 int n, k;
08 int road;
09 int a[105][105][4];
10 int color[105][105];
11 int b[105][105];
12 int x, y, x1, y1;
13 int num;
14 int all;
15 long long ans;
16 vector<int> area;
17 int dx[4] = {-1, 0, 1, 0};
18 int dy[4] = {0, 1, 0, -1};
19 void dfs(int x, int y) {
20     if (①) {
21         return;
22     }
23     if (color[x][y] != -1) {
24         return;
25     }
26     color[x][y] = num;
27     if (b[x][y] == 1) {
28         all++;
29     }
30     for (int i = 0; i < 4; i++) {
31         if (a[x][y][i] == 1) {
32             continue;
33         }
34         int xx = x + dx[i];
35         int yy = y + dy[i];
36         dfs(xx, yy);
37     }
38 }
39 int main() {
40     cin >> n >> k >> road;
41     for (int i = 1; i <= road; i++) {
42         cin >> x >> y >> x1 >> y1;
43         if (x == x1) {
44             a[x][min(y, y1)][1] = 1;
45             ②;
46         } else {
47             a[min(x, x1)][y][2] = 1;
48             ③;
49         }
50     }
51     for (int i = 1; i <= k; i++) {
52         cin >> x >> y;
53         b[x][y] = 1;
54     }
55     area.push_back(0);
56     memset(color, -1, sizeof(color));
57     for (int i = 1; i <= n; i++) {
58         for (int i1 = 1; i1 <= n; i1++) {
59             if (④) {
60                 all = 0;
61                 num++;
62                 dfs(i, i1);
63                 area.push_back(all);
64             }
65         }
66     }
67     for (int i = 1; i < num; i++) {
68         for (int i1 = i + 1; i1 <= num; i1++) {
69             ⑤;
70         }
71     }
72     cout << ans;
73     return 0;
74 }

33. ①处应填（ ）。 {{ select(33) }}

• x < 1 || y < 1 || x > n || y > n
• x > 1 || y > 1 || x < n || y < n
• x >= 1 && y >= 1 && x <= n && y <= n
• x == 1 && y == 1 && x == n && y == n

34. ②处应填（ ）。 {{ select(34) }}

• a[x][max(y, y1)][0] = 1;
• a[x][max(y, y1)][1] = 1;
• a[x][max(y, y1)][2] = 1;
• a[x][max(y, y1)][3] = 1;

35. ③处应填（ ）。 {{ select(35) }}

• a[max(x, x1)][y][0] = 1;
• a[max(x, x1)][y][1] = 1;
• a[max(x, x1)][y][2] = 1;
• a[max(x, x1)][y][3] = 1;

36. ④处应填（ ）。 {{ select(36) }}

• color[i][i1] != -1
• color[i][i1] == -1
• b[i][i1] == 1
• b[i][i1] != 1

37. ⑤处应填（ ）。 {{ select(37) }}

• ans += area[i] + area[i1];
• ans += area[i] - area[i1];
• ans += area[i] * area[i1];
• ans += area[i] / area[i1];

(2) 题目描述： 对n个单词进行加密。加密过程如下。 (i) 选择一个英文字母表的排列作为密钥。 (ii) 将单词中的a替换为密钥中的第一个字母，b替换为密钥中的第二个字母，以此类推。

例如，以qwertyuiopasdfghjklzxcvbnm作为密钥对cezar加密后，将得到etmqk。请你给出一种构造方式，最初的第$a_i$个单词位于第i位。请你判断这能否实现。如果能，请给出任意一种可行的密钥。考虑使用拓扑排序完成，代码如下。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e2 + 50;
04 int n, ord[N], in[N];
05 char ans[N], wrd[N][N];
06 vector<int> e[N], s;
07 void add(int x, int y) {
08     for (int i = 1; i <= ①; i++) {
09         if (wrd[x][i] != wrd[y][i]) {
10             e[wrd[x][i]].push_back(wrd[y][i]);
11             if (②) in[wrd[x][i]] = 0;
12             if (③) in[wrd[y][i]] = 1;
13             else in[wrd[y][i]]++;
14             return;
15         }
16     }
17     if (strlen(wrd[x] + 1) > strlen(wrd[y] + 1)) puts("NE"), exit(0);
18 }
19 void topo() {
20     queue<int> q;
21     for (int i = 'a'; i <= 'z'; i++) if (!in[i]) q.push(i);
22     while (!q.empty()) {
23         int u = q.front();
24         q.pop();
25         s.push_back(u);
26         for (auto v : e[u])
27             if (!(--in[v])) q.push(v);
28     }
29 }
30 signed main() {
31     scanf("%d", &n);
32     for (int i = 'a'; i <= 'z'; i++) in[i] = -1;
33     for (int i = 1; i <= n; i++) scanf("%s", wrd[i] + 1);
34     for (int i = 1; i <= n; i++) scanf("%d", ord[i]);
35     for (int i = 1; i < n; i++)
36         for (④)
37             add(ord[i], ord[i]);
38     topo();
39     for (int i = 'a'; i <= 'z'; i++) if (in[i] > 0) return puts("NE"), 0;
40     puts("DA");
41     int cnt = 0;
42     for (auto i : s) ans[i] = 'a' + cnt++;
43     for (int i = 'a'; i <= 'z'; i++) {
44         if (!ans[i]) printf("%c", ⑤);
45         else printf("%c", (char)ans[i]);
46     }
47     return 0;
48 }

38. ①处应填（ ）。 {{ select(38) }}

• min(strlen(wrd[x] + 1), strlen(wrd[y] + 1))
• max(strlen(wrd[x] + 1), strlen(wrd[y] + 1))
• strlen(wrd[x] + 1)
• strlen(wrd[y] + 1)

39. ②处应填（ ）。 {{ select(39) }}

• in[wrd[x][i]] != -1
• in[wrd[x][i]] == -1
• in[wrd[x][i]] == 0
• in[wrd[x][i]] != 0

40. ③处应填（ ）。 {{ select(40) }}

• in[wrd[y][i]] != -1
• in[wrd[y][i]] == -1
• in[wrd[y][i]] == 0
• in[wrd[y][i]] != 0

41. ④处应填（ ）。 {{ select(41) }}

• int o = i; o < n; o++
• int o = i; o <= n; o++
• int o = i + 1;o < n; o++
• int o = i + 1; o <= n; o++

42. ⑤处应填（ ）。 {{ select(42) }}

• (char)('z' - cnt--)
• (char)('z' - --cnt)
• (char)('a' + cnt++)
• (char)('a' + ++cnt)

---