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

1. 在P进制下（9≤p≤16）有如下等式成立：78=44，则该进制下5274=（ ）。 {{ select(1) }}

• 2b88
• 6365
• 3848
• 28b5

2. 在8位二进制补码中，10101101表示的数是十进制下的（ ）。 {{ select(2) }}

• 45
• -45
• -83
• 173

3. 后缀表达式9 3 1-3*+10 2/+的计算结果为（ ）。 {{ select(3) }}

• 20
• 1030
• 2
• 15

4. 7个同学坐在一排，由于现在要考试，为了避免同学们在自己的桌子上留下小抄作弊，老师打算打乱所有人的位置，以保证每个人都不坐在自己原来的位置，那么一共有（ ）种打乱方式。 {{ select(4) }}

• 265
• 1854
• 720
• 1440

5. 若某算法的计算时间表示为递推关系$T(n) = 2T(n/2) + n \log_2 n$，则该算法的时间复杂度为（ ）。 {{ select(5) }}

• $O\left(n \log_2^3 n\right)$
• $O\left(n \log_2^2 n\right)$
• $O\left(n \log_2 n\right)$
• $O(n)$

6. 若让元素1,2,3,4,5依次进栈，则出栈次序不可能出现（ ）的情况。 {{ select(6) }}

• 5,4,3,2,1
• 2,1,5,4,3
• 4,3,1,2,5
• 1,2,5,4,3

7. NOI Linux2是CCF NOI系列赛事的标准竞赛环境之一。以下终端命令中，能够显示当前目录名称的是（ ）。 {{ select(7) }}

• cat
• ls
• man
• pwd

8. 以下程序段的作用是求出1至n的所有（ ）。

for (i=1; i<=n; i++) a[i] = i;
for (i=2; i<=n; i++)
    if (i == a[i]) {
        for (j=1; j*i <=n; j++)
            a[j*i] = a[j*i] / i * (i-1);
    }

{{ select(8) }}

• 素数个数
• 整数的最大因数
• 整数的因数个数
• 整数的$\phi(i)$

9. 给定地址区间为0-12的哈希表，哈希函数为$h(x) = x^2 \% 13$，采用线性探查的冲突解决策略（若出现冲突情况，会往后探查第一个空的地址存储；若地址12冲突了，则从地址0重新开始探查）。哈希表初始为空表，依次存储(3,4,5,6,7,8,9,10)后，10存储在哈希表的哪个地址中？（ ） {{ select(9) }}

• 0
• 1
• 9
• 10

10. 令根结点的高度为1，则一棵含有2023个结点的二叉树和一棵含有2023个结点的三叉树的高度分别至少为（ ）。 {{ select(10) }}

• 11,8
• 11,7
• 10,7
• 10,8

11. 以下选项中哪一个的期望时间复杂度与其他三个不同？（ ） {{ select(11) }}

• 包含n个元素的set容器使用lower_bound查询返回第一个大于某个数的迭代器
• 包含n个元素的vector使用erase删除n/2位置的值
• 从包含n个元素的数组中构建一个小顶堆
• 求包含n个结点的树的直径

12. 该无向图的最小生成树的权值为（ ）。

{{ select(12) }}

• 39
• 38
• 47
• 42

13. 以下说法中不正确的是（ ）。 {{ select(13) }}

• 无向图具有欧拉回路的充分必要条件是每个点的度数均为奇数
• 在稠密图上，相较于堆优化的Dijkstra算法，SPFA表现更优
• 无向图是二分图，当且仅当图上不存在奇数长度的环
• 树的重心不一定唯一

14. 掷7次质地均匀的正方体骰子，出现和为1的概率可表示为$\frac{x}{6^7}$，则x的值为（ ）。 {{ select(14) }}

• 84
• 210
• 121
• 240

15. 设循环队列中数组的下标范围是1~m，其头尾指针分别为front和rear，front指向队列的第一个元素，rear指向最后一个元素位置的下一个位置，则其元素个数为（ ）。 {{ select(15) }}

• rear - front
• rear - front + 1
• (rear - front + 1) MOD m
• (rear - front + m) MOD m

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

(1)

01 #include <iostream>
02 #include <algorithm>
03 #define Type double
04 using namespace std;
05 
06 const int maxn = 100005;
07 struct point {
08     Type x, y;
09     point() {}
10     point(Type x, Type y) : x(x), y(y) {}
11     point operator-(const point b) const {
12         return point(x - b.x, y - b.y);
13     }
14     void input() {
15         cin >> x >> y;
16     }
17 };
18 point pnt[maxn], res[maxn];
19 
20 Type cross(point a, point b) {
21     return a.x * b.y - a.y * b.x;
22 }
23 
24 int solve(int n) {
25     sort(pnt, pnt + n, [](point a, point b) {
26         return a.x == b.x ? a.y < b.y : a.x < b.x;
27     });
28     int m = 0;
29     for (int i = 0; i < n; ++i) {
30         while (m > 1 && cross(res[m - 1] - res[m - 2], pnt[i] - res[m - 1]) <= 0)
31             --m;
32         res[m++] = pnt[i];
33     }
34     int k = m;
35     for (int i = n - 2; i >= 0; --i) {
36         while (m > k && cross(res[m - 1] - res[m - 2], pnt[i] - res[m - 1]) <= 0)
37             --m;
38         res[m++] = pnt[i];
39     }
40     if (n > 1) --m;
41     return m;
42 }
43 
44 int main() {
45     int n;
46     cin >> n;
47     for (int i = 0; i < n; ++i) pnt[i].input();
48     cout << solve(n) << endl;
49 }

假设输入的所有数均为整数，且绝对值都不超过10000，以下是3个输入样例。

输入样例1：	输入样例2：	输入样例3：
5	11	6
0 0	0 4	0 0
0 2	2 8	4 4
2 2	4 4	0 4
2 1	4 1	2 2
2 0	8 2	2 0
	8 8	4 0
	9 6
	14 0
	12 4
	13 8
	12 10

■ 判断题 16. 在输入样例1的情况下，结果为5。（ ） {{ select(16) }}

• 正确
• 错误

17. 将第30行和第36行中的<=均修改为<，所有合法输入的结果均不会发生变化。（ ） {{ select(17) }}

• 正确
• 错误

18. 将第30行和第36行中的<=均修改为<，输入样例1的输出结果不会发生变化。（ ） {{ select(18) }}

• 正确
• 错误

19. 该算法的时间复杂度为$O(n \log n)$。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题 20. 在输入样例2的情况下，结果为（ ）。 {{ select(20) }}

• 4
• 5
• 6
• 7

21. （4分）在输入样例3的情况下，第30行和第37行的运行次数加起来一共为（ ）。 {{ select(21) }}

• 5
• 6
• 7
• 8

(2)

01 #include <iostream>
02 #include <algorithm>
03 using namespace std;
04 
05 const int maxn = 2e5 + 7;
06 
07 int func1(const char str[], int n) {
08     int k = 0, i = 0, j = 1;
09     for (; j < n; j++) {
10         while (k < n && str[i + k] == str[j + k])
11             k++;
12         if (str[i + k] > str[j + k])
13             i = j;
14         k = 0;
15     }
16     return i;
17 }
18 
19 int func2(const char str[], int n) {
20     int i = 0, j = 1, k = 0;
21     while (i < n && j < n && k < n) {
22         if (str[i + k] == str[j + k])
23             k++;
24         else {
25             if (str[i + k] > str[j + k])
26                 i += k + 1;
27             else
28                 j += k + 1;
29             if (i == j)
30                 i++;
31             k = 0;
32         }
33     }
34     return min(i, j);
35 }
36 
37 char str[maxn];
38 
39 int main() {
40     int n;
41     cin >> n >> str;
42     for (int i = 0; i < n; ++i)
43         str[i + n] = str[i];
44     cout << func1(str, n) << ' ' << func2(str, n) << endl;
45 }

假设输入均为整数加一个字符串，其中整数表示字符串的长度，整数不超过10000。

■ 判断题 22. 若输入5 12312，则输出的第一个整数为4。（ ） {{ select(22) }}

• 正确
• 错误

23. 将第10行中的while (k < n && str[i + k] == str[j + k])修改为while (str[i + k] == str[j + k])，则程序有可能会陷入死循环或出现数组越界。（ ） {{ select(23) }}

• 正确
• 错误

24. 将第30行中的i++修改为j++，结果不会发生变化。（ ） {{ select(24) }}

• 正确
• 错误

25. 在合法输入下，输出的两个整数一定是一样的。（ ） {{ select(25) }}

• 正确
• 错误

■ 选择题 26. （4分）输入9 321321323时，第25行一共运行了（ ）次。 {{ select(26) }}

• 8
• 7
• 6
• 5

27. （4分）假设字符串s是一个长度为3且只包含数字0到9的字符串，其中s的每个位置为0到9的可能性相同，则对该程序输入3和字符串s时，输出的第二个整数是0的概率为（ ）。 {{ select(27) }}

• $\frac{1}{3}$
• $\frac{37}{100}$
• $\frac{17}{50}$
• $\frac{2}{5}$

(3)

01 #include <iostream>
02 #include <vector>
03 using namespace std;
04 const int maxn = 1e6 + 5;
05 
06 vector<int> pri;
07 bool not_prime[maxn];
08 int value[maxn], num[maxn];
09 
10 int init(int n) {
11     value[1] = 1;
12     for (int i = 2; i <= n; ++i) {
13         if (!not_prime[i]) {
14             pri.push_back(i);
15             value[i] = 2;
16             num[i] = 1;
17         }
18         for (int j : pri) {
19             if (i * j > n) break;
20             not_prime[i * j] = true;
21             if (i % j == 0) {
22                 num[i * j] = num[i] + 1;
23                 value[i * j] = value[i] / num[i] * (num[i] + 1);
24                 break;
25             }
26             num[i * j] = 1;
27             value[i * j] = value[i] * 2;
28         }
29     }
30     return value[n];
31 }
32 
33 int main() {
34     int n;
35     cin >> n;
36     cout << init(n) << endl;
37 }

假设输入为一个不超过1000000的整数。

■ 判断题 28. 输入180时，输出结果为18。（ ） {{ select(28) }}

• 正确
• 错误

29. 分别输入180和300时，在main函数退出前，数组num在下标1到100上的值是不同的。（ ） {{ select(29) }}

• 正确
• 错误

30. 输入100时，在main函数退出前，vector容器pri内的元素个数在22和28之间。（ ） {{ select(30) }}

• 正确
• 错误

31. 将第23行修改为value[i * j] = value[i] * (num[i] + 1) / num[i]，结果不变。（ ） {{ select(31) }} -正确

• 错误

■ 选择题 32. 该算法的时间复杂度为（ ）。 {{ select(32) }}

• $O(n)$
• $O(n \log n)$
• $O(n \log \log n)$
• $O(\sqrt{n})$

33. （4分）数组value在下标i处的含义为（ ）。 {{ select(33) }}

• i的质因子个数
• i的欧拉函数值
• i的所有因子和
• i的因子个数

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

(1) 有N种物品和一个容量为V的背包。 物品一共有3类：

• 第一类物品只能用1次（0-1背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用$s_i$次（多重背包）。

每种物品的体积是$v_i$，价值是$w_i$。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

输入格式： 第1行有两个整数N；V，用空格隔开，分别表示物品种数和背包容量。接下来有N行，每行3个整数$v_i$，$w_i$，$s_i$，用空格隔开，分别表示第i种物品的体积、价值和数量。

• $s_i = -1$表示第i种物品只能用1次；
• $s_i = 0$表示第i种物品可以用无限次；
• $s_i > 0$表示第i种物品可以用$s_i$次。

输出格式： 输出一个整数，表示最大价值。

数据范围： [0 < N, V \leq 1000] [0 < v_i, w_i \leq 1000] [-1 < s_i \leq 1000]

输入样例：

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

8

提示：解决思路是将多重背包使用二进制拆分转换为0-1背包，使得只包含0-1背包和完全背包。

01 #include <iostream>
02 #include <algorithm>
03 #include <vector>
04 using namespace std;
05 const int maxn = 2023;
06 
07 int N, V;
08 int dp[maxn];
09 struct Item {
10     int w, v;
11     int s;
12 };
13 void upd(int j, Item item) {
14     dp[j] = max(dp[j], ①);
15 }
16 int main() {
17     vector<Item> items;
18     cin >> N >> V;
19     
20     for (int i = 1; i <= N; i++) {
21         int w, v, s;
22         cin >> w >> v >> s;
23         if (②) {
24             for (int k = 1; k <= s; k <<= 1) {
25                 s -= k;
26                 items.push_back(③);
27             }
28             if (s > 0)
29                 items.push_back({s * w, s * v, -1});
30         } else
31             items.push_back({w, v, s});
32     }
33     for (auto item : items) {
34         if (item.s == ④)
35             for (int j = V; j >= item.w; j--)
36                 upd(j, item);
37         else
38             for (⑤)
39                 upd(j, item);
40     }
41     cout << dp[V] << endl;
42     return 0;
43 }

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

• dp[j - item.v] + item.w
• dp[j - item.w] + item.v
• dp[j + item.v] + item.w
• dp[j + item.w] + item.v

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

• s > 0
• s == 0
• s == -1
• s != 0

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

• {w * k, v * k, -1}
• {w * k, v, -1}
• {w, v, -1}
• {w * k, v, 0}

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

• 1
• N
• 0
• -1

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

• int j = item.w; j <= V; j++
• int j = item.v; j <= V; j++
• int j = V; j >= item.w; j--
• int j = V; j >= item.v; j--

(2) 给定n个正整数$a_1, a_2, \cdots, a_n$，m次询问，每次询问一个给定的区间$[l, r]$，输出$a_l, a_{l+1}, \cdots, a_r$的最大公因数。

输入格式： 第1行两个整数n，m。第2行n个整数表示$a_1, a_2, \cdots, a_n$。以下m行，每行两个整数l，r，表示询问区间的左右端点。

输出格式： 共m行，每行表示一个询问的答案。

数据范围： [1 \leq l \leq r \leq n \leq 100000] [1 \leq m \leq 10^6] [1 \leq a_i \leq 10^9]

输入样例：

5 3
4 12 36 7
1 3
2 3
5 5

输出样例：

1
3
7

01 #include <iostream>
02 #include <algorithm>
03 using namespace std;
04 const int maxn = 2e5 + 7;
05 const int maxp = 20;
06 
07 int a[maxn], dp[maxn][maxp];
08 int gcd(int a, int b) {
09     if (b == 0)
10         return a;
11     ①;
12 }
13 void init(int n) {
14     for (int i = 1; i <= n; i++)
15         dp[i][②] = a[i];
16     for (int j = 1; (1 << j) <= n; j++)
17         for (int i = 1; i + (1 << j) - 1 <= n; i++)
18             dp[i][j] = gcd(dp[i][j - 1], dp[③][j - 1]);
19 }
20 int rmq(int l, int r) {
21     int k = 0;
22     while (④)
23         k++;
24     return gcd(dp[l][k], dp[⑤][k]);
25 }
26 int main() {
27     int n, m;
28     cin >> n >> m;
29     for (int i = 1; i <= n; i++)
30         cin >> a[i];
31     init(n);
32     for (int i = 1; i <= m; i++) {
33         int l, r;
34         cin >> l >> r;
35         cout << rmq(l, r) << endl;
36     }
37 }

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

• gcd(b, a % b)
• gcd(b, a * b)
• gcd(a, a % b)
• gcd(a, a / b)

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

• 1
• 0
• -1
• i

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

• i + (1 << (j - 1)) - 1
• i + (1 << j) - 1
• i + (1 << j)
• i + (1 << (j - 1))

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

• (1 << k) <= r - l + 1
• (1 << (k + 1)) <= r - l + 1
• (k << 1) <= r - l + 1
• ((k + 1) << 1) <= r - l + 1

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

• r - (1 << k) + 1
• r - (1 << k)
• l + (1 << k) - 1
• l + (1 << k)

---