一、单项选择题（共15题）
每题只有一个正确选项，绿色为正确答案，并附简要解析。
1. 在 NOI Linux 系统终端中，以下哪个命令可以用来创建一个新的空白文档？（ ）
A. mkdir
B. cp -a
C. mv
D. touch
答案：D。touch 可以新建空文件；mkdir 是建目录，cp -a 是复制，mv 是移动或重命名。
2. 以下关于数据结构的表述中不恰当的一项是（ ）。
A. 栈是一种后进先出的数据结构
B. 非连通有向图的边数一定小于顶点数
C. 队列是一种先进先出的数据结构
D. 哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构
答案：B。A、C、D 都是标准定义。B 不成立，不连通并不意味着边数一定少，某些连通块内部仍然可以有很多边。
3. 对于 4 个结点的简单有向图，最少（ ）条边可以形成一个覆盖所有结点的环。
答案：C。覆盖 4 个点的有向环长度至少为 4，例如 1→2→3→4→1，所以至少需要 4 条边。
4. 对于给定的正整数 a 和 n（n 为 2 的正整数次幂），下面求幂函数的最准确描述是（ ）。
long long fun(int a, int n) {
long long ret = 1;
if (n <= 1)
return pow(a, n);
else {
ret = fun(a, n / 2);
return ret * ret;
}
}
答案：A。它先递归求出 a^(n/2)，再平方得到 a^n，本质是快速幂思想。在这组选项里最贴近的是“倍增”。
5. 约定杨辉三角形第 0 行第 1 个元素是 1，第 1 行有 2 个元素是 1，则第 5 行的所有元素之和是（ ）。
答案：C。杨辉三角第 n 行所有元素之和为 2^n，因此第 5 行之和为 2^5 = 32。
6. 下列哪个问题不能用贪心法精确求解？（ ）
A. 哈夫曼编码
B. 多重背包
C. 打水问题
D. 最小生成树
答案：B。多重背包通常需要动态规划，单靠局部最优不能保证全局最优；其余三项都有经典贪心解法。
7. 对于具有 n 个元素的二叉排序树，进行后序遍历的时间复杂度是（ ）。
A. O(log n)
B. O(n)
C. O(n²)
D. O(n log n)
答案：B。无论树形如何，后序遍历都会访问每个结点一次，所以复杂度是 O(n)。
8. 考虑对 n 个数进行排序，以下方法中最坏时间复杂度最优的排序方法是（ ）。
A. 选择排序
B. 快速排序
C. 堆排序
D. 插入排序
答案：C。选择、插入最坏都是 O(n^2)，快速排序最坏也会退化成 O(n^2)；堆排序最坏仍为 O(n log n)。
9. 下面有向图中的数字表示顶点序号，则从 1 号顶点出发的 BFS 遍历输出的顶点序列可能是（ ）。图关系为：1→2, 1→3, 2→4, 3→4
A. 1 4 3 2
B. 1 4 2 3
C. 1 3 2 4
D. 1 2 4 3
答案：C。BFS 按层访问，4 不可能先于 2、3 被访问，所以 A、B 错。若 1 的邻接点先访问 3 后访问 2，则序列可以是 1 3 2 4。
10. 给定地址区间为 0~10 的哈希表，哈希函数为 h(x)=x%11，采用线性探查。依次存储 (60, 34, 62, 88, 22, 57, 78) 后，78 存储在哈希表的哪个地址中？（ ）
答案：D。依次插入后：60→5，34→1，62→7，88→0，22 冲突后到 2，57 冲突后到 3，78 从 1 开始探查，1、2、3 已占用，最终落在 4。
11. STL 中的容器可以分为顺序容器和关联容器。以下哪个不属于顺序容器？（ ）
A. multiset
B. vector
C. list
D. deque
答案：A。vector、list、deque 都是顺序容器，而 multiset 属于关联容器。
12. 二分图是指能将顶点划分成两个部分，且每一部分内的顶点间没有边相连的简单无向图。对于 24 个顶点的二分图（两部分的顶点数之差不超过 6），最多有（ ）条边。
A. 144
B. 128
C. 135
D. 140
答案：A。二分图边数最大时两部分尽量平均，分成 12 和 12，最大边数为 12×12=144。
13. 令二叉树根结点的高度为 0，则一棵含有 2024 个结点的二叉树的高度可能是（ ）。
A. 2024
B. 2023
C. 9
D. 8
答案：B。若退化成一条链，2024 个结点的最大高度就是 2023。A 比结点数还大，不可能；C、D 容纳不了这么多结点。
14. 设集合 I = {1, 2, 3, 4, 5}，选择集合 I 的两个非空子集 A 和 B，要使 B 中最小的数大于 A 中最大的数，则不同的选择方法有（ ）种。
答案：B。用列表法更直观：先确定
A 中最大的数，然后
B 只能从它后面的数里选。
max(A)=1：A 只能是 {1}，共 1 种；B 可从 {2,3,4,5} 中任取非空子集，共 15 种。max(A)=2：A 可为 {2}、{1,2}，共 2 种；B 可从 {3,4,5} 中任取非空子集，共 7 种。max(A)=3：A 共 4 种；B 可从 {4,5} 中任取非空子集，共 3 种。max(A)=4：A 共 8 种；B 只能是 {5}，共 1 种。max(A)=5：后面没有数了，B 无法选，不计入。
所以总数为
1×15+2×7+4×3+8×1=49。
15. 设全集 I = {1, 2, 3, 4, 5, 6, 7, 8}，B ∪ A = {1, 2, 3, 4, 5, 6}，∁A = {7, 8}，∁B ∩ A = {1, 4}，那么集合 ∁(B ∪ A) 为（ ）。
A. {7, 8}
B. {6, 7, 8}
C. {3, 4, 5}
D. {4, 6}
答案：A。关键看并集：A ∪ B = {1,2,3,4,5,6}，而全集是 {1,2,3,4,5,6,7,8}，所以它的补集就是全集里没有出现在并集中的元素，也就是 {7,8}。这里给出的 ∁A 和 ∁B ∩ A 只是附加条件，不影响最后这一步求补集。
二、阅读程序题（共10题）
阅读代码后作答，绿色为正确答案，并附简要解析。
（一）阅读程序，回答 16~20 题
这段代码在解决什么问题？
- 本题目是在统计一个
n × m 网格中有多少个水坑连通块。
- 网格里字符为
w 的位置表示水。
- 如果两个
w 在 8 个方向之一相邻，就算连在一起。
- 程序用
BFS 把每一整块连通的水都搜掉，最后输出水坑块数。
- 这就是经典的 8 连通块计数问题，也常叫“池塘计数 / Lake Counting”。
代码里的关键点：
- 外层双重循环依次检查每个格子。
- 遇到一个还没有访问过的
w，就从这里开始做一次 bfs。
- 这次
bfs 会把这一整块连通的水全部标记为已访问。
- 每启动一次新的
bfs，说明发现了一个新的水坑块，所以答案 ans 加 1。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1007;
int n, m, ans;
char g[N][N];
bool st[N][N];
void bfs(int x, int y) {
queue<PII> q;
q.push({x, y});
st[x][y] = true;
while (q.size()) {
PII t = q.front();
q.pop();
for (int i = t.first - 1; i <= t.first + 1; ++i)
for (int j = t.second - 1; j <= t.second + 1; ++j) {
if (i == t.first && j == t.second) continue;
if (i < 1 || i > n || j < 1 || j > m) continue;
if (g[i][j] != 'w' || st[i][j]) continue;
q.push({i, j});
st[i][j] = true;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
scanf("%s", g[i] + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (g[i][j] == 'w' && !st[i][j]) {
bfs(i, j);
++ans;
}
printf("%d\n", ans);
return 0;
}
16. 若将第 cin >> n >> m; 改为 cin >> m >> n;，程序的输出不变。（ ）
答案：B。n 是行数、m 是列数。交换后，读图范围和边界判断都会错位，输出一般会变化。
17. 该问题也可以用 DFS 解决。（ ）
答案：A。这里是在统计连通块个数，BFS 和 DFS 都能完成连通块搜索。
18. 从程序中可以看出题目允许的拓展方向有 4 个。（ ）
答案：B。双重循环会检查中心周围 8 个方向，只排除了自己，所以是 8 连通，不是 4 连通。
19. 对于输入 4 5 / WSWWS / WWWSS / SSWSW / SSSSW，程序的输出是（ ）。
答案：B。按题意统计水块连通块，左上形成一大块，右下形成一小块，共 2 块。这里样例用大写 W，本质是在考连通块统计。
20. 本程序的时间复杂度是（ ）。
A. O(n)
B. O(n²m)
C. O(nm²)
D. O(nm)
答案：D。每个格子最多被主循环扫描一次，每个水格在 BFS 中也只会入队一次，且只检查常数个邻居，所以总复杂度是 O(nm)。
（二）阅读程序，回答 21~25 题
这段代码在解决什么问题？
- 这段程序是在根据多边形顶点坐标，计算多边形的面积。
- 输入按顺序给出一个多边形的各个顶点，程序会输出它的面积，保留 1 位小数。
- 它用到的是叉积求面积的方法，也就是常说的“鞋带公式”。
- 无论是凸多边形还是凹多边形，只要顶点顺序是按顺时针或逆时针依次给出的，都可以直接计算。
代码里的关键点：
cross(a, b) 计算的是两个向量的叉积。polygonArea 把相邻顶点的叉积依次累加，得到的是带符号面积的 2 倍。- 最后在
solve 里除以 2，再取绝对值 fabs(area)，就得到真正的多边形面积。
- 主函数支持多组数据输入，直到读到
n = 0 为止。
#include <bits/stdc++.h>
using namespace std;
typedef struct {
double x;
double y;
} Point;
Point point_init(double x, double y) {
Point p;
p.x = x;
p.y = y;
return p;
}
Point point_sub(Point a, Point b) {
Point p;
p.x = a.x - b.x;
p.y = a.y - b.y;
return p;
}
double cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
double polygonArea(const vector<Point>& v) {
double area = cross(v.back(), v.front());
for (size_t i = 0; i < v.size() - 1; ++i) {
area += cross(v[i], v[i + 1]);
}
return area;
}
void solve(int n) {
vector<Point> pts(n);
for (int i = 0; i < n; ++i) {
double a, b;
cin >> a >> b;
pts[i] = point_init(a, b);
}
double area = polygonArea(pts) / 2;
cout << fixed << setprecision(1) << fabs(area) << "\n";
}
int main() {
while (true) {
int n;
cin >> n;
if (n == 0) break;
solve(n);
}
return 0;
}
21. 将第 42 行改为 double area = polygonArea(pts) >> 1;，程序正常运行。（ ）
答案：B。polygonArea(pts) 返回的是 double，而位移运算 >> 只能用于整数类型，这样写无法正常编译。
22. 程序可以处理凹多边形而不需要任何修改。（ ）
答案：A。这里使用的是叉积求和，也就是鞋带公式。只要顶点按顺时针或逆时针顺序给出，凹多边形也能直接算面积。
23. polygonArea 的返回值始终为正。（ ）
答案：B。该函数返回的是带符号面积的两倍。点按不同方向给出时，结果可能为正也可能为负，因此最后才要取 fabs。
24. cross 函数的计算结果用于表示（ ）。
A. 两个点的欧几里得距离
B. 连接两点的直线的斜率
C. 两个向量的点积
D. 两个向量的叉积
答案：D。a.x * b.y - a.y * b.x 正是二维向量叉积的计算式。
25. 对于输入 3 / 1 1 / 0 0 / 1 0，程序输出（ ）。
A. 1.0
B. 0.5
C. 0.0
D. 0.6
答案：B。三个点构成一个底和高都为 1 的直角三角形，面积为 1×1÷2=0.5。
三、完善程序题（共5题）
根据题意和代码补全空格，绿色为正确答案。
定义“魔法数字”：没有前导 0，且数字 d 恰好出现在这个数的所有偶数位置。现给定 m, d，询问区间 [a, b] 中是 m 倍数的魔法数字个数。
这段代码在解决什么问题？
- 这段程序是在统计区间
[a,b] 中有多少个“魔法数字”。
- 这里的“魔法数字”要同时满足两个条件：一是某些位置上的数字必须等于
d，二是整个数还必须是 m 的倍数。
- 由于区间很大，不能把
a 到 b 每个数都枚举出来检查，所以程序使用了数位 DP。
- 它先求“不超过上界的合法数字个数”，再用前缀思想算出区间
[a,b] 的答案。
举个具体例子：
- 假设
m = 3，d = 7，并且题意要求“偶数位必须是 7，奇数位不能是 7”。
273 是合法的，因为第 2 位是 7，第 1 位和第 3 位都不是 7，并且 2+7+3=12，是 3 的倍数。474 也是合法的，因为第 2 位是 7，其他位置不是 7，并且 4+7+4=15，是 3 的倍数。
代码里的关键点：
dfs(i, sum, small_taken, s) 表示当前处理到第 i 位，当前余数是 sum，并记录前面是否已经严格小于上界。- 如果前面已经比上界小了，后面的数字就可以自由选；否则当前位不能超过上界对应位置。
- 通过
(sum * 10 + j) % m 维护当前前缀对 m 的余数。
- 先分别求出不超过
a 和不超过 b 的合法个数，再根据 a 自身是否合法，得到闭区间 [a,b] 的答案。
#include <bits/stdc++.h>
using namespace std;
const int M = 2005;
const int mod = 1e9 + 7;
int dp[M][M][2];
int m, d;
int dfs(int i, int sum, int small_taken, string &s) {
if ( ① ) return sum == 0;
int &ans = dp[i][sum][small_taken];
if (ans != -1) return ans;
ans = 0;
int digit = s[i] - '0';
int low = 0, high = digit;
if (small_taken) high = 9;
for (int j = low; j <= high; ++j) {
if (i % 2 == 1 && j != d) continue;
if (i % 2 == 0 && j == d) continue;
int new_small = ② ;
int new_sum = ③ ;
ans += dfs(i + 1, new_sum, new_small, s);
ans %= mod;
}
return dp[i][sum][small_taken] = ans;
}
int main() {
string a, b;
cin >> m >> d >> a >> b;
int is_a_magic = 1;
int res = 0;
for (int i = 0; i < a.size(); ++i) {
int dig = a[i] - '0';
if ( ④ ) is_a_magic = 0;
res = (res * 10 + dig) % m;
}
if (res) is_a_magic = 0;
memset(dp, -1, sizeof dp);
int sum_a = dfs(0, 0, 0, a);
memset(dp, -1, sizeof dp);
int sum_b = dfs(0, 0, 0, b);
cout << ⑤ << endl;
return 0;
}
26. ① 处应填（ ）。
A. i >= s.size()
B. i > s.size()
C. i >= sum
D. i > sum
答案：A。i 表示当前处理到第几位，下标范围是 0 到 s.size()-1。当 i == s.size() 时，说明所有数位都已经处理完了，这正是递归终点，所以应写成 i >= s.size()。这时只需要判断当前构造出的整个数字对 m 取模后的余数是否为 0。如果写成 i > s.size()，那么在 i == s.size() 时还不会结束，后面继续访问 s[i] 就会越界。
27. ② 处应填（ ）。
A. j != d || j < high
B. j == d && j < high
C. j == d || j < high
D. small_taken || j < high
答案：D。如果前面已经比上界小，后面一直自由；否则只有当前位取到严格更小的值，后续才进入自由状态。
28. ③ 处应填（ ）。
A. (sum + digit) % m
B. (sum * 10 + j) % m
C. (sum + high) % m
D. (sum * 10 + high) % m
答案：B。前缀后面拼上当前选择的数字 j，新的余数应为“原余数乘 10 再加 j”后对 m 取模。
29. ④ 处应填（ ）。
A. i % 2 == 1 && dig != d
B. i % 2 == 1 && dig == d
C. i % 2 == 0 || dig != d
D. dig != d && !is_a_magic
答案：A。
代码下标从 0 开始，因此下标为 1、3、5 的位置对应题目里的偶数位；这些位置若不是 d，就不满足“魔法数字”的要求。
30. ⑤ 处应填（ ）。
A. (sum_b - sum_a + is_a_magic + mod) % mod
B. (sum_b - sum_a + is_a_magic) % mod
C. (sum_b - sum_a + !is_a_magic + mod) % mod
D. (sum_b - sum_a + !is_a_magic) % mod
答案：A。
sum_b 是不超过 b 的个数，sum_a 是不超过 a 的个数；要算闭区间 [a,b]，若 a 本身合法，还要把它补回来。
说明：第 20 题这里按题面代码保留为 D. O(nm)。此前只列答案字母的速查版用了旧答案稿，这里已按代码逻辑修正。