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

1. 已知开放集合S规定，如果正整数x属于该集合，则2x和3x同样属于该集合。若集合包含1，则集合一定包含（ ）。 {{ select(1) }}

• 2024
• 1536
• 2025
• 2026

2. 在C++语言中，容器vector类型不包含函数（ ）。 {{ select(2) }}

• top()
• front()
• back()
• pop_back()

3. 在NOI Linux系统中，列出文件夹内所有文件的命令是（ ）。 {{ select(3) }}

• dir
• display
• ls
• show

4. 在C++语言中，(-5) % (-6)的值为（ ）。 {{ select(4) }}

• -1
• -3
• 1
• 3

5. 已知由x个点组成的森林中有y棵树，则此森林中有（ ）条边。 {{ select(5) }}

• x - y + 1
• x - y - 1
• x - 1
• x - y

6. 某大学计算机系排课，某些课程需要先学才能学习后续的课程，这个排课过程中常用的算法是（ ）。 {{ select(6) }}

• 堆排序
• 拓扑排序
• 插入排序
• 归并排序

7. 迪杰斯特拉算法在最坏情况下的时间复杂度为（ ）。 {{ select(7) }}

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

8. 我们通常称之为FIFO的数据结构为（ ）。 {{ select(8) }}

• 队列
• 链表
• 栈
• 向量

9. 关于C++语言中类的说法中错误的是（ ）。 {{ select(9) }}

• 以struct声明的类中的成员默认为public形式
• 以class声明的类中的成员默认为private形式
• 以private关键字修饰的类对象，可以直接访问，但不能修改其成员数据
• 类可被认为是包含其成员的名字空间

10. 若根结点在第一层，则有2025个结点的二叉树的最大深度为（ ）。 {{ select(10) }}

• 2024
• 2025
• 11
• 12

11. 下面的编码组合中，（ ）不是合法的哈夫曼编码。 {{ select(11) }}

• (0, 1, 00, 11)
• (00, 01, 10, 11)
• (0, 10, 110, 111)
• (1, 01, 000, 001)

12. 在程序运行过程中，如果函数A调用函数B，函数B又调用函数A，这种间接调用操作的循环次数过多可能会引发（ ）空间溢出。 {{ select(12) }}

• 队列
• 栈
• 链表
• 堆

13. 若事件A和事件B相互独立，二者发生的概率相同，即$P(A) = P(B)$，且$P(A \cup B) = 0.64$，则事件A发生的概率$P(A) =（ ）$。 {{ select(13) }}

• 0.3
• 0.4
• 0.6
• 0.8

14. 将8本不同的书分给5个人，其中3个人各拿一本，1个人拿两本，1个人拿三本，共有（ ）种分配法。 {{ select(14) }}

• 33600
• 36000
• 72000
• 67200

15. 随机生成n个各不相同的正整数数组元素，快速排序算法的第一轮执行一遍以后，已经被排到正确位置的元素至少有（ ）个。 {{ select(15) }}

• $n / 2$
• $n / 3$
• 1
• 0

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 #define ll long long
05 
06 int read() {
07     int x = 0, f = 1; char ch = '';
08     while (!isdigit(ch)) { ch = getchar(); if (ch == '-') f = -1; }
09     while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
10     return x * f;
11 }
12 
13 int a[50], Len, f[50][65], vis[50][65];
14 
15 int dfs(bool Limit, bool lead, int pos, int cha) {
16     if (pos == 0) return cha >= 30;
17     if (!Limit && !lead && vis[pos][cha]) return f[pos][cha];
18     int res = 0;
19     int up = Limit ? a[pos] : 1;
20     for (int i = 0; i <= up; ++i) {
21         res += dfs(Limit && (i == a[pos]), lead && (i == 0), pos - 1,
22                   cha + (i == 0 ? (lead ? 0 : 1) : -1));
23     }
24     if (!Limit && !lead) vis[pos][cha] = 1, f[pos][cha] = res;
25     return res;
26 }
27 
28 int solve(int x) {
29     Len = 0;
30     while (x) {
31         a[++Len] = x % 2;
32         x /= 2;
33     }
34     return dfs(1, 1, Len, 30);
35 }
36 
37 int main() {
38     int L = read(), r = read();
39     cout << solve(r) - solve(L - 1);
40 }

假设输入的数据不会超过$10^9$，回答下列问题。

■ 判断题

16. 该程序能够计算$[l, r]$区间内所有二进制下有且仅有一个0的数字的数量（例如$2=10, 5=101, 13=1101$）。（ ） {{ select(16) }}

• 正确
• 错误

17. 如果输入0 0，则该程序获得结果12。（ ） {{ select(17) }}

• 正确
• 错误

18. 如果输入2 12，则该程序获得结果6。（ ） {{ select(18) }}

• 正确
• 错误

19. 第31行代码的执行次数不会超过60次。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题

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

• 该程序的时间复杂度为$O(M \log N)$。
• 该程序能将double类型的数无误差地用a表示。
• 输入15 15时，程序输出为0。
• 如果把除main函数前的int全改为ll，程序能够正确处理long long范围内的输入数据。

21. 对于以下哪组输入，程序会输出最大值？（ ） {{ select(21) }}

• 1 11
• 2 12
• 3 13
• 4 14

(2)

01 #include <algorithm>
02 #include <iostream>
03 #include <fstream>
04 #include <vector>
05 using namespace std;
06 
07 const int INF = 1000000000;
08 template <class T> inline int Size(const T &c) { return c.size(); }
09 
10 struct Impossible {};
11 
12 vector<int> breeds;
13 vector<int> volumes;
14 
15 void ReadInput() {
16     int n, b; cin >> n >> b;
17     for (int i = 0; i < b; ++i) {
18         int v; cin >> v; breeds.push_back(v);
19     }
20     for (int i = 0; i < n; ++i) {
21         int v; cin >> v; volumes.push_back(v);
22     }
23 }
24 
25 vector<int> knapsack;
26 
27 void ExtendKnapsack() {
28     int t = Size(knapsack);
29     int v = INF;
30     for (int i = 0; i < Size(breeds); ++i) {
31         int t2 = t - breeds[i];
32         if (t2 >= 0) v = min(v, 1 + knapsack[t2]);
33     }
34     knapsack.push_back(v);
35 }
36 
37 int Knapsack(int total) {
38     if (total < 0) throw Impossible();
39     while (total >= Size(knapsack)) ExtendKnapsack();
40     if (knapsack[total] == INF) throw Impossible();
41     return knapsack[total];
42 }
43 
44 int Solve() {
45     knapsack.assign(1, 0);
46     int carry = 0;
47     int res = 0;
48     for (int i = 0; i < Size(volumes); ++i) {
49         carry = max(carry - 1, 0);
50         int v = volumes[i] - carry;
51         res += Knapsack(v);
52         carry = volumes[i];
53     }
54     return res;
55 }
56 
57 int main() {
58     ReadInput();
59     try {
60         cout << Solve() << "\n";
61     } catch (Impossible) {
62         cout << "-1\n";
63     }
64 }

假设输入总是满足$1 ≤ n, b ≤ 500$。

■ 判断题（每题2分）

22. knapsack的初始容量是1。（ ） {{ select(22) }}

• 正确
• 错误

23. 如果total小于0，Knapsack函数会抛出Impossible异常。（ ） {{ select(23) }}

• 正确
• 错误

24. 如果breeds不全为0，那么输出一定不为0。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题

25. 若程序输入

4 3
4 2 1
0 4 5 7

则输出是（ ）。 {{ select(25) }}

• 0
• -1
• 3
• 4

26. 下列说法中正确的是（ ）。 {{ select(26) }}

• ExtendKnapsack函数本质上实现了一个背包功能，并且在复杂度上比普通背包更优秀。
• knapsack[i]表示和为i时最少使用breeds中的数的个数（可重复使用，使用几次计几个）。
• 这段代码的时间复杂度是$O(K*N)$（K指的是a数组的值域，N指的是a数组的大小）。
• 若volume[]都为一个值的话，程序要么输出0，要么输出-1。

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 #define N 2000005
04 int n, a[N];
05 pair<int, int> dp[N][10], ans;
06 string s, b = "bessie";
07 pair<int, int> add(pair<int, int> x, pair<int, int> y) {
08     return {x.first + y.first, x.second + y.second};
09 }
10 pair<int, int> Max(pair<int, int> x, pair<int, int> y) {
11     if (x.first == y.first) {
12         if (x.second < y.second)
13             return x;
14         return y;
15     }
16     if (x.first > y.first)
17         return x;
18     return y;
19 }
20 int main() {
21     cin >> s;
22     n = s.size();
23     s = " " + s;
24     for (int i = 1; i <= n; i++) {
25         scanf("%d", &a[i]);
26     }
27     for (int i = 0; i <= n; i++) {
28         for (int j = 0; j <= 6; j++) {
29             dp[i][j] = {-100, 100};
30         }
31     }
32     dp[0][0] = {0, 0};
33     for (int i = 1; i <= n; i++) {
34         dp[i][0] = dp[i - 1][0];
35         if (s[i] == b[5])
36             dp[i][0] = Max(dp[i][0], add(dp[i - 1][5], {1, 0}));
37         for (int j = 1; j <= 5; j++) {
38             dp[i][j] = add(dp[i - 1][j], {0, a[i]});
39             if (s[i] == b[j - 1])
40                 dp[i][j] = Max(dp[i][j], dp[i - 1][j - 1]);
41         }
42     }
43     for (int i = 0; i <= 5; i++) {
44         ans = Max(ans, dp[n][i]);
45     }
46     printf("%d %d\n", ans.first, ans.second);
47 }

■ 判断题（每题2分）

27. 本题中ans.second表示的是满足字符串bessie出现次数最少的条件时最大的删除代价和。（ ） {{ select(27) }}

• 正确
• 错误

28. 如果将第6行代码修改为string s, b = "beef";，程序将变成求s删去若干字符后最多能出现多少个beef以及求满足bessie出现次数最多的前提下最小的删除代价和。（ ） {{ select(28) }}

• 正确
• 错误

■ 选择题

29. dp[i][j].first的含义是（ ）。 {{ select(29) }}

• 通过删除一些字符，字符串前i位匹配到bessie的第j位的，之前匹配了dp[i][j].first个bessie。
• 通过删除一些字符，字符串前i位匹配到bessie的第j位的，之前匹配了dp[i][j].second个bessie。
• 通过删除一些字符，字符串前i位有j个bessie，并且最后匹配到字符串b的dp[i][j].first-1位。
• 通过删除一些字符，字符串前i位有j个bessie，并且最后匹配到字符串b的dp[i][j].first位。

30. 如果本题中输入：

Besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

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

• 1 18
• 2 13
• 1 0
• 3 7

31. 对于以下哪种情况，程序可能会发生运行错误或者输出错误答案？（ ） {{ select(31) }}

• 输入了一个长度为1的字符串。
• 输入了一个长度为200000+2的字符串，并且数组a的平均值不超过10000。
• 输入了一个长度为200000的字符串，并且数组a的平均值超过100000。
• 输入了一个长度为20000010的字符串，并且a都是1。

32. 下列说法中正确的是（ ）。 {{ select(32) }}

• 在本段程序中Max({1, 4}, {2, 3})返回{1, 4}。
• 将第29行代码dp[i][j] = {-100, 100};改成dp[i][j] = {-1, 1};，程序仍能运行并且输出正确答案。
• 在一些情况下，dp[n][6]也可能是正确答案。
• 这段代码的时间复杂度是$O(N \log N)$，其中N代表字符串的长度。

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

(1) 题目描述： 你在一条笔直的公路上驾驶汽车，初始位置在数轴上的0处，给定汽车油箱容量、初始油量、N个加油站在数轴上的位置、单位油量价格、到终点的距离，询问驾驶到终点的最小花费。（注意，我们认为汽车刚驶入加油站就没油也算能到达该加油站并能够继续加油，一个单位油量可以行驶一个单位距离。）

01 #include <bits/stdc++.h>
02 #define NMAX 50010
03 
04 using namespace std;
05 
06 struct station {
07     int pos, cost;
08     bool operator<(station const &o) const {
09         return pos < o.pos;
10     }
11 };
12 station stations[NMAX];
13 
14 int s[NMAX];
15 int nextSmall[NMAX];
16 
17 int main() {
18     int n, maxGas, curGas, dist;
19     scanf("%d%d%d%d", &n, &maxGas, &curGas, &dist);
20     for (int i = 1; i <= n; i++) {
21         scanf("%d", &stations[i].pos);
22         scanf("%d", &stations[i].cost);
23     }
24     sort(①);
25 
26     int stacklen = 0;
27     for (int i = n; i; i--) {
28         while (stacklen > 0 && ②) {
29             stacklen--;
30         }
31         nextSmall[i] = (stacklen == 0 ? -1 : s[stacklen - 1]);
32         s[stacklen] = i;
33         stacklen++;
34     }
35 
36     curGas -= stations[1].pos;
37     long long cost = 0;
38     for (int i = 1; i <= n; i++) {
39         if (③) {
40             printf("-1\n");
41             return 0;
42         }
43         int gasNeeded = min(maxGas, (nextSmall[i] == -1 ? dist : ④) - stations[i].pos);
44         if (gasNeeded > curGas) {
45             cost += ⑤;
46             curGas = gasNeeded;
47         }
48         curGas -= (i == n ? dist : stations[i + 1].pos) - stations[i].pos;
49     }
50 
51     if (curGas < 0) {
52         printf("-1\n");
53     } else {
54         printf("%lld\n", cost);
55     }
56 }

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

• stations + 1, stations + n
• stations + 1, stations + n + 1
• stations, stations + n + 1
• stations, stations + n

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

• stations[s[stacklen - 1]].cost >= stations[i].cost
• stations[s[stacklen]].cost >= stations[i].cost
• stations[stacklen - 1].cost >= stations[i].cost
• stations[stacklen].cost >= stations[i].cost

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

• curGas <= 0
• curGas == 0
• curGas < 0
• curGas > 0

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

• stations[nextSmall[i]].pos
• stations[nextSmall[i - 1]].pos
• nextSmall[i]
• nextSmall[i - 1]

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

• (long long)(gasNeeded) * (long long)stations[i].cost
• (long long)(gasNeeded - curGas) * (long long)stations[i].cost
• (long long)(nowneed) * (long long)stations[i].cost
• (long long)(gasNeeded - curGas) * (long long)stations[i + 1].cost

(2) 题目描述： 在一台计算机中，1号文件为根文件，每个文件夹有零个、一个或多个子文件或子文件夹。你需要找到一个文件夹，从这个文件夹出发，访问所有文件的路径长度之和最小。

例如，现在存在三个文件夹A,B,C以及五个文件a,b,c,d,e。A为根文件夹，有两个文件a,b以及一个文件夹B，文件夹B中有文件c和文件夹C，文件夹C中有d,e两个文件。从文件夹B出发，它访问到的文件为（..\表示上级目录）：

..\a
..\b
c
C\d
C\e

一个文件访问其上级文件和下级文件的长度均视为1。

01 #include <cstdio>
02 #include <cassert>
03 #include <cstring>
04 #include <vector>
05 using namespace std;
06 
07 #define NMAX 100000
08 
09 struct Node {
10     bool isFile;
11     vector<Node*> children;
12     int namelen;
13 
14     int numLeaves;
15     long long totalSubtreeLen;
16 
17     long long total;
18 };
19 
20 Node nodes[NMAX];
21 
22 int n;
23 int nleaves;
24 
25 void dfs1(Node *node) {
26     node->numLeaves = (node->isFile ? 1 : 0);
27     node->totalSubtreeLen = 0;
28     for (Node *child : node->children) {
29         dfs1(child);
30         node->numLeaves += child->numLeaves;
31         node->totalSubtreeLen += child->totalSubtreeLen + ①;
32     }
33 }
34 
35 void dfs2(Node *node, long long parentlen) {
36     node->total = ②;
37 
38     long long pLenadd = 0;
39     for (Node *child : node->children) {
40         pLenadd += child->totalSubtreeLen + child->numLeaves * (child->namelen + (child->isFile ? 0 : 1));
41     }
42     for (Node *child : node->children) {
43         dfs2(child, parentlen + pLenadd - 
44              (child->totalSubtreeLen + child->numLeaves * 
45               (child->namelen + (child->isFile ? 0 : 1))) + ③);
46     }
47 }
48 
49 int main() {
50     scanf("%d", &n);
51     char name[40];
52     nleaves = 0;
53     for (int i = 0; i < n; i++) {
54         scanf("%s", name);
55         nodes[i].namelen = strlen(name);
56         int numChildren;
57         scanf("%d", &numChildren);
58         // 如果为④，说明它是一个文件而不是文件夹
59         nodes[i].isFile = ④;
60         if (nodes[i].isFile) {
61             nleaves++;
62         }
63         for (int j = 0; j < numChildren; j++) {
64             int id;
65             scanf("%d", &id);
66             nodes[i].children.push_back(&nodes[id - 1]);
67         }
68     }
69 
70     assert(!nodes[0].isFile);
71 
72     dfs1(&nodes[0]);
73     dfs2(&nodes[0], 0);
74     long long ans = nodes[0].total;
75     for (int i = 0; i < n; i++) {
76         if (!nodes[i].isFile) {
77             ⑤;
78         }
79     }
80     printf("%lld\n", ans);
81 }

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

• child->numLeaves
• child->numLeaves * (child->namelen)
• child->numLeaves * (child->namelen + (child->isFile ? 0 : 1))
• child->numLeaves * (child->namelen + (child->isFile ? 0 : 1) + child->children.size())

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

• parentlen + (node->isFile ? 0 : node->totalSubtreeLen)
• parentlen + (node->isFile ? node->totalSubtreeLen : 0)
• parentlen
• parentlen + node->totalSubtreeLen

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

• 1 * (nleaves - child->numLeaves)
• 3 * (nleaves - child->numLeaves)
• 1 * nleaves
• 3 * nleaves

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

• numChildren > 0
• numChildren == 1
• numChildren = 0
• numChildren == 0

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

• ans = nodes[i].total;
• ans = min(ans, nodes[i].total);
• ans = max(ans, nodes[i].total);
• ans = -1;

---