2021 CSP-S 提高组初赛真题及解析

四季读书网 2026-08-02 16:07:05 3 0

CCF CSP-S 2021 第一轮（提高级）完整真题 + 逐题解析 + 答案速查表 + 考点分析

共 43 题：15 道单项选择 + 3 道阅读程序（18 小题）+ 2 道完善程序（10 小题），满分 100 分。

获取 2021CSP-S提高初赛完整真题及详细解析.pdf

请关注状元编程公众号，回复 2021CSP-S

一、单项选择题（共 15 题，每题 2 分，共 30 分）

第 1 题

在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（）。

A. ls B. cd C. cp D. all

查看答案与解析

答案：A

ls（list）：列出目录内容
cd（change directory）：切换工作目录
cp（copy）：复制文件或目录
all：Linux 中不存在此命令

第 2 题

二进制数 00101010 和 00010110 的和为（）。

A. 00111100 B. 01000000 C. 00111100 D. 01000010

查看答案与解析

答案：B

  00101010  (42)+ 00010110  (22)= 01000000  (64)

二进制加法，逢二进一。

第 3 题

在程序运行过程中，如果递归调用的层数过多，可能会由于（）引发错误。

A. 系统分配的栈空间溢出 B. 系统分配的队列空间溢出 C. 系统分配的链表空间溢出 D. 系统分配的堆空间溢出

查看答案与解析

答案：A

递归函数的参数和局部变量存储在系统栈（Call Stack）中，每个未完成的函数调用对应一个栈帧。如果递归层数过多，系统分配的栈空间会溢出，导致 Stack Overflow。

第 4 题

以下排序方法中，（）是不稳定的。

A. 插入排序 B. 冒泡排序 C. 堆排序 D. 归并排序

查看答案与解析

答案：C

稳定性指：对于值相同的元素，排序后相对次序不变。

插入排序：相邻比较，稳定
冒泡排序：相邻交换，稳定
归并排序：合并时相等取左边，稳定
堆排序：堆的构建过程中，相等元素间原有顺序会丢失，不稳定

第 5 题

以比较为基本运算，对于 2n 个数，同时找到最大值和最小值，最坏情况下需要的最小的比较次数为（）。

A. 4n − 2 B. 3n + 1 C. 3n − 2 D. 2n + 1

查看答案与解析

答案：C

分组比较法：将 2n 个数两两比较（n 次），每对中较大的与当前最大值比较，较小的与当前最小值比较。

第 1 对比较：1 次，直接确定当前最大值和最小值
剩余 n − 1 对，每对比较 3 次（内对比较 + 大的与 max 比 + 小的与 min 比）
总计：1 + (n − 1) × 3 = 3n − 2

第 6 题

现有一个地址区间为 0 ~ 10 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储（到 10 冲突了就从 0 开始往后），现在要依次存储 (0, 1, 2, 3, 4, 5, 6, 7)，哈希函数为 h(x) = x² mod 11。请问 7 存储在哈希表哪个地址中（）。

A. 5 B. 6 C. 7 D. 8

查看答案与解析

答案：C

逐一计算哈希值：

元素	h(x) = x² mod 11	存储位置
0	0	0
1	1	1
2	4	4
3	9	9
4	5	5
5	3	3
6	3 → 冲突 → 4,5已占 → 6	6
7	5 → 冲突 → 6已占 → 7	7

所以 7 存储在地址 7。

第 7 题

G 是一个非连通简单无向图（没有自环和重边），共有 36 条边，则该图至少有（）个点。

A. 8 B. 9 C. 10 D. 11

查看答案与解析

答案：C

9 个顶点的完全无向图有 9 × 8 / 2 = 36 条边。但题目要求非连通，所以需要再加一个孤立点，共 10 个点。

或者：设 n 个点中，n−1 个点构成完全图，1 个点孤立：

(n−1)(n−2)/2 ≥ 36，解得 n ≥ 10。

第 8 题

令根结点的高度为 1，则一棵含有 2021 个结点的二叉树的高度至少为（）。

A. 10 B. 11 C. 12 D. 2021

查看答案与解析

答案：B

高度为 h 的满二叉树有 2^h − 1 个结点。

h = 10：2^10 − 1 = 1023 < 2021
h = 11：2^11 − 1 = 2047 ≥ 2021

所以至少需要高度 11。

第 9 题

前序遍历和中序遍历相同的二叉树为且仅为（）。

A. 只有 1 个点的二叉树 B. 根结点没有左子树的二叉树 C. 非叶子结点只有左子树的二叉树 D. 非叶子结点只有右子树的二叉树

查看答案与解析

答案：D

前序遍历：根 → 左 → 右
中序遍历：左 → 根 → 右

两者相同意味着"根"始终在"左"之前出现，即不存在左子树。等价于：非叶子结点只有右子树。

第 10 题

定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF 最少需要（）次上述操作。

A. 7 B. 8 C. 9 D. 6

查看答案与解析

答案：A

交换相邻字符的最少次数 = 逆序对数。

DACFEB 的逆序对：

D>A(1), D<C(1) → 2
C>A(1) → 1
F>E(1), F>B(1) → 2
E>B(1) → 1

共 7 个逆序对，即最少需要 7 次交换。

第 11 题

有如下递归代码：

solve(t, n):    if t = 1 return 1    else return 5 * solve(t-1, n) mod n

则 solve(23, 23) 的结果为（）。

A. 1 B. 7 C. 12 D. 22

查看答案与解析

答案：A

展开递归：

solve(23, 23) = 5 × solve(22, 23) mod 23             = 5² × solve(21, 23) mod 23             = ...             = 5²² × solve(1, 23) mod 23             = 5²² mod 23

由费马小定理：若 p 为质数，则 a^(p−1) ≡ 1 (mod p)。

23 是质数，所以 5²² ≡ 1 (mod 23)，结果为 1。

第 12 题

斐波那契数列的定义为 F₁ = 1, F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ (n ≥ 3)。现在用如下递归程序来计算斐波那契数列的第 n 项，其时间复杂度为（）。

F(n):    if n <= 2 return 1    else return F(n-1) + F(n-2)

A. O(n) B. O(n²) C. O(2ⁿ) D. O(n log n)

查看答案与解析

答案：C

递归树分析：每层结点数最多翻倍，共 n−1 层，总结点数为 1 + 2 + 4 + … + 2^(n−2) = O(2ⁿ)。

实际上 T(n) = T(n−1) + T(n−2)，这与斐波那契数列本身的增长率相同，复杂度为 O(2ⁿ)。

第 13 题

有 8 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（）种方案。

A. 36 B. 48 C. 54 D. 64

查看答案与解析

答案：C

插空法：选 k 个苹果，不选相邻等价于在 8−k 个未选苹果形成的 8−k+1 个空中插入 k 个苹果：

选的个数 k	方案数
1	C(8,1) = 8
2	C(7,2) = 21
3	C(6,3) = 20
4	C(5,4) = 5
合计	54

第 14 题

设一个三位数 n = abc̄，a, b, c 均为 1~9 之间的整数，若以 a、b、c 作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 n 有（）个。

A. 81 B. 120 C. 165 D. 216

查看答案与解析

答案：C

等边三角形：a = b = c，共 9 个（111, 222, …, 999）。

等腰三角形（a = b ≠ c）：

a=b	c 的范围	c 的个数
1	{1}	1（等边）
2	{1,2,3}	3（含等边）
3	{1,2,3,4,5}	5
4	{1,2,3,4,5,6,7}	7
5~9	{1~9} 中满足	各 9

非等边的等腰（a=b≠c）个数：

a=b	可取 c 的个数
1	0
2	2
3	4
4	6
5~9	各 8 × 5 = 40

合计非等边等腰 = 0 + 2 + 4 + 6 + 40 = 52。

每种等腰 (a=b≠c) 有 3 种排列（aab, aba, baa），所以 52 × 3 = 156。

总计 = 9（等边）+ 156（等腰）= 165。

第 15 题

有如下的有向图，节点为 A, B, …, J，其中每条边的长度都标在图中。则节点 A 到节点 J 的最短路径长度为（）。

A. 16 B. 19 C. 20 D. 22

查看答案与解析

答案：B

使用 Dijkstra 算法模拟，最短路径为 A → C → E → H → J，路径长度为 19。

二、阅读程序（共 3 道大题，18 小题，共 40 分）

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

阅读程序 1：球体相交体积

#include<iostream>#include<cmath>usingnamespace std;constdouble r = acos(0.5);int a1, b1, c1, d1;int a2, b2, c2, d2;inlineintsq(constint x){ return x * x; }inlineintcu(constint x){ return x * x * x; }intmain(){    cout.flags(ios::fixed);    cout.precision(4);    cin >> a1 >> b1 >> c1 >> d1;    cin >> a2 >> b2 >> c2 >> d2;int t = sq(a1 - a2) + sq(b1 - b2) + sq(c1 - c2);if (t <= sq(d2 - d1)) cout << cu(min(d1, d2)) * r * 4;elseif (t >= sq(d1 + d2)) cout << 0;else {double x = d1 - (sq(d1) - sq(d2) + t) / sqrt(t) / 2;double y = d2 - (sq(d2) - sq(d1) + t) / sqrt(t) / 2;        cout << (x * x * (3 * d1 - x) + y * y * (3 * d2 - y)) * r;    }    cout << endl;return0;}

程序分析：r = acos(0.5) = π/3，该程序计算两个球体相交部分的体积。输入为两个球的球心坐标 (a, b, c) 和半径 d。

第 16 题（判断题）将第 21 行中 t 的类型声明从 int 改为 double，不会影响程序运行的结果。（）

第 17 题（判断题）将第 26、27 行中的 / sqrt(t) / 2 替换为 / 2 / sqrt(t)，不会影响程序运行的结果。（）

第 18 题（判断题）将第 28 行中的 x * x 改成 sq(x)、y * y 改成 sq(y)，不会影响程序运行的结果。（）

第 19 题（判断题，2 分）当输入为 0 0 0 1 1 0 0 1 时，输出为 1.3090。（）

第 20 题（单选题）当输入为 1 1 1 1 1 1 1 2 时，输出为（）。

A. 3.1416 B. 6.2832 C. 4.7124 D. 4.1888

第 21 题（单选题，2.5 分）这段代码的含义为（）。

A. 求圆的面积并 B. 求球的体积并 C. 求球的体积交 D. 求椭球的体积并

查看答案与解析

题号	答案	解析
16	√	`sq` 返回 `int`，赋值给 `double` 会自动转换，不影响结果
17	×	先除以 2 会造成整除丢失精度（`t` 是 `int`，`t/2` 为整数除法）
18	×	`sq` 参数为 `int`，而 `x`、`y` 是 `double`，调用时会截断小数部分
19	√	两个半径为 1 的球，球心距离为 1，相交体积 = 5π/12 ≈ 1.3089969…，保留 4 位为 1.3090
20	D	同心球，大球包含小球，输出小球体积 = 1³ × r × 4 = 4 × π/3 ≈ 4.1888
21	C	第 24 行 `t >= sq(d1+d2)` 输出 0（不相交），第 22 行大包含小，故为体积交

阅读程序 2：分治法求最大子段和

#include<algorithm>#include<iostream>usingnamespace std;int n, a[1005];structNode {int h, j, m, w;Node(constint _h, constint _j, constint _m, constint _w)        : h(_h), j(_j), m(_m), w(_w) {}    Node operator+(const Node &o) const {returnNode(max(h, w + o.h),max(max(j, o.j), m + o.h),max(m + o.w, o.m),            w + o.w);    }};Node solve1(int h, int m){if (h > m) returnNode(-1, -1, -1, -1);if (h == m) returnNode(max(a[h], 0), max(a[h], 0), max(a[h], 0), a[h]);int j = (h + m) >> 1;returnsolve1(h, j) + solve1(j + 1, m);}intsolve2(int h, int m){if (h > m) return-1;if (h == m) returnmax(a[h], 0);int j = (h + m) >> 1;int wh = 0, wm = 0;int wht = 0, wmt = 0;for (int i = j; i >= h; i--) {        wht += a[i];        wh = max(wh, wht);    }for (int i = j + 1; i <= m; i++) {        wmt += a[i];        wm = max(wm, wmt);    }returnmax(max(solve2(h, j), solve2(j + 1, m)), wh + wm);}intmain(){    cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];    cout << solve1(1, n).j << endl;    cout << solve2(1, n) << endl;return0;}

程序分析：solve1 使用结构体 + 运算符重载的分治法求最大子段和；solve2 是另一种分治实现。结构体字段：h=最大前缀和，j=最大子段和，m=最大后缀和，w=区间和。

第 22 题（判断题）程序总是会正常执行并输出两行两个相等的数。（）

第 23 题（判断题）第 28 行与第 38 行分别有可能执行两次及以上。（）

第 24 题（判断题）当输入为 5 -10 11 -9 5 -7 时，输出的第二行为 7。（）

第 25 题（单选题）solve1(1, n) 的时间复杂度为（）。

A. O(n²) B. O(n) C. O(n log n) D. O(n log²n)

第 26 题（单选题）solve2(1, n) 的时间复杂度为（）。

A. O(n²) B. O(n) C. O(n log n) D. O(n log²n)

第 27 题（单选题）当输入为 10 -3 2 10 0 -8 9 -4 -5 9 4 时，输出的第一行为（）。

A. 13 B. 17 C. 24 D. 12

查看答案与解析

题号	答案	解析
22	√	`solve1` 和 `solve2` 都是求最大连续子段和，结果相同
23	×	`h > m` 和 `h == m` 是递归终止条件，每个函数调用中只执行一次
24	×	最大子段和为 11（仅取第二个元素），不是 7
25	B	`solve1` 是线性的分治（类似归并），每层总工作量 O(n)，但只有 log n 层。实际上每层每个元素只被访问一次，总复杂度 O(n)
26	C	`solve2` 每层需要 O(n) 遍历，共 log n 层递归，总复杂度 O(n log n)
27	B	最大子段和 = 2+10+0+(−8)+9+(−4)+(−5)+9+4 = 17

阅读程序 3：Base64 编码与解码

#include<iostream>#include<string>usingnamespace std;char base[64];char table[256];voidinit(){for (int i = 0; i < 26; i++) base[i] = 'A' + i;for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;    base[62] = '+', base[63] = '/';for (int i = 0; i < 256; i++) table[i] = 0xff;for (int i = 0; i < 64; i++) table[base[i]] = i;    table['='] = 0;}string encode(string str){    string ret;int i;for (i = 0; i + 3 <= str.size(); i += 3) {        ret += base[str[i] >> 2];        ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];        ret += base[(str[i + 1] & 0x0f) << 2 | str[i + 2] >> 6];        ret += base[str[i + 2] & 0x3f];    }if (i < str.size()) {        ret += base[str[i] >> 2];if (i + 1 == str.size()) {            ret += base[(str[i] & 0x03) << 4];            ret += "==";        } else {            ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];            ret += base[(str[i + 1] & 0x0f) << 2];            ret += "=";        }    }return ret;}string decode(string str){    string ret;int i;for (i = 0; i < str.size(); i += 4) {        ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;if (str[i + 2] != '=')            ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;if (str[i + 3] != '=')            ret += table[str[i + 2]] << 6 | table[str[i + 3]];    }return ret;}intmain(){init();    cout << int(table[0]) << endl;int opt;    string str;    cin >> opt >> str;    cout << (opt ? decode(str) : encode(str)) << endl;return0;}

程序分析：这是标准的 Base64 编解码实现。encode 将 3 字节 → 4 字符，decode 反之。输入 opt=0 编码，opt=1 解码。

第 28 题（判断题）程序总是先输出一行一个整数，再输出一行一个字符串。（）

第 29 题（判断题）对于任意不含空白字符的字符串 str1，先执行程序输入 0 str1，得到输出的第二行记为 str2，再执行程序输入 1 str2，输出的第二行必为 str1。（）

第 30 题（判断题）当输入为 1 SGVsbG93b3JsZA== 时，输出的第二行为 HelloWorld。（）

第 31 题（单选题）设输入字符串长度为 n，encode 函数的时间复杂度为（）。

A. O(n²) B. O(n) C. O(n log n) D. O(1)

第 32 题（单选题）输出的第一行为（）。

A. 0xff B. 255 C. 0xFF D. −1

第 33 题（单选题，4 分）当输入为 0 CSP2021csp 时，输出的第二行为（）。

A. Q1NQMjAyMWNzcAv= B. Q1NQMjAyMGNzcA== C. Q1NQMjAyMGNzcAv= D. Q1NQMjAyMWNzcA==

查看答案与解析

题号	答案	解析
28	×	解码结果可能包含换行符等特殊字符，输出可能不止一行
29	√	Base64 编码与解码互为逆操作
30	×	正确解码结果为 `Helloworld`（小写 w），不是 `HelloWorld`
31	B	每个输入字符最多访问一次，时间复杂度 O(n)
32	D	`table[0] = 0xff` ，`char` 类型转 `int` 时符号扩展，`0xff` → `0xffffffff` = −1
33	D	`CSP2021csp` 共 10 个字符，10 % 3 = 1，末尾补 `==`。逐步编码验证得 `Q1NQMjAyMWNzcA==`

三、完善程序（共 2 道大题，10 小题，每题 3 分，共 30 分）

完善程序 1：最少使用 4 的个数

有 n 个人围成一个圈，依次标号 0 至 n−1。从 0 号开始，依次 0, 1, 0, 1, … 交替报数，报到 1 的人会离开，直至圈中只剩一个人。求最后剩下人的编号。

#include<iostream>#include<cstdlib>#include<climits>usingnamespace std;constint M = 10000;bool Vis[M + 1];int F[M + 1];voidupdate(int &x, int y){if (y < x) x = y;}intmain(){int n;    cin >> n;for (int i = 0; i <= M; i++) F[i] = INT_MAX;    F[4] = 1;  // 【1】int r = 0;while (【2】) {        r++;int x = 0;for (int i = 1; i <= M; i++)if (【3】)                x = i;        Vis[x] = 1;for (int i = 1; i <= M; i++)if (【4】) {int t = F[i] + F[x];if (i + x <= M) update(F[i + x], t);if (i != x) update(F[abs(i - x)], t);if (i % x == 0) update(F[i / x], t);if (x % i == 0) update(F[x / i], t);            }    }    cout << F[n] << endl;return0;}

第 34 题 ① 处应填（）。

A. F[4] = 0 B. F[1] = 4 C. F[1] = 2 D. F[4] = 1

第 35 题 ② 处应填（）。

A. !Vis[n] B. r < n C. F[M] == INT_MAX D. F[n] == INT_MAX

第 36 题 ③ 处应填（）。

A. F[i] == r B. !Vis[i] && F[i] == r C. F[i] < F[x] D. !Vis[i] && F[i] < F[x]

第 37 题 ④ 处应填（）。

A. F[i] < F[x] B. F[i] <= r C. Vis[i] D. i <= x

查看答案与解析

题号	答案	解析
34	D	数字 4 只需要 1 个 4 表示，是递推起点：`F[4] = 1`
35	A	循环终止条件：目标数字 n 的最小值已确定，即 `!Vis[n]` 为假时退出
36	D	在未确定集合中找 F 值最小的：`!Vis[i] && F[i] < F[x]`
37	C	用已确定集合 S（`Vis[i]==1`）中的数与新数 x 组合：`Vis[i]`

算法本质：类似 Dijkstra 最短路。F[i] 表示用最少的 4 通过 +、−、×、÷ 运算得到 i 的个数。每次取出 F 值最小的未确定数，用它与已确定的数组合更新其他数。

完善程序 2：笛卡尔树 + 欧拉序求区间最值（RMQ）

#include<iostream>#include<cmath>usingnamespace std;constint MAXN = 100000, MAXT = MAXN << 1;constint MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;structnode {int val;int dep, dfn, end;    node *son[2];} T[MAXN];int t, n, b, c, Log2[MAXC + 1];int pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];node *root, *A[MAXT], *Min[MAXL][MAXC];voidbuild(){static node *S[MAXN + 1];int top = 0;for (int i = 0; i < n; i++) {        node *p = &T[i];while (top && S[top]->val < p->val)            p->son[0] = S[top--];  // 【1】if (top)            S[top]->son[1] = p;  // 【2】        S[++top] = p;    }    root = S[1];}voidDFS(node *p){    A[p->dfn = t++] = p;for (int i = 0; i < 2; i++)if (p->son[i]) {            p->son[i]->dep = p->dep + 1;DFS(p->son[i]);            A[t++] = p;        }    p->end = t - 1;}node *min(node *x, node *y){return x->dep < y->dep ? x : y;  // 【3】}voidST_init(){    b = (int)(ceil(log2(t) / 2));    c = t / b;    Log2[1] = 0;for (int i = 2; i <= c; i++) Log2[i] = Log2[i >> 1] + 1;for (int i = 0; i < c; i++) {        Min[0][i] = A[i * b];for (int j = 1; j < b; j++)            Min[0][i] = min(Min[0][i], A[i * b + j]);  // 【4】    }for (int i = 1, l = 2; l <= c; i++, l <<= 1)for (int j = 0; j + l <= c; j++)            Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);}voidsmall_init(){for (int i = 0; i <= c; i++)for (int j = 1; j < b && i * b + j < t; j++)if (A[i * b + j]->dep < A[i * b + j - 1]->dep)  // 相关                Dif[i] |= 1 << (j - 1);for (int S = 0; S < (1 << (b - 1)); S++) {int mx = 0, v = 0;for (int i = 1; i < b; i++) {            v += (S >> (i - 1) & 1) ? -1 : 1;  // 【5】if (v < mx) {                mx = v;                pos[S] = i;            }        }    }}node *ST_query(int l, int r){int g = Log2[r - l + 1];returnmin(Min[g][l], Min[g][r - (1 << g) + 1]);}node *small_query(int l, int r){int p = l / b;int S = (Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1);  // 【6】return A[l + pos[S]];}node *query(int l, int r){if (l > r) returnquery(r, l);int pl = l / b, pr = r / b;if (pl == pr) returnsmall_query(l, r);else {        node *s = min(small_query(l, pl * b + b - 1), small_query(pr * b, r));if (pl + 1 <= pr - 1) s = min(s, ST_query(pl + 1, pr - 1));return s;    }}intmain(){int m;    cin >> n >> m;for (int i = 0; i < n; i++) cin >> T[i].val;build();DFS(root);ST_init();small_init();while (m--) {int l, r;        cin >> l >> r;        cout << query(T[l].dfn, T[r].dfn)->val << endl;    }return0;}

第 38 题 ① 处应填（）。

A. p->son[0] = S[top--] B. p->son[1] = S[top--] C. S[top--]->son[0] = p D. S[top--]->son[1] = p

第 39 题 ② 处应填（）。

A. p->son[0] = S[top] B. p->son[1] = S[top] C. S[top]->son[0] = p D. S[top]->son[1] = p

第 40 题 ③ 处应填（）。

A. x->dep < y->dep B. x < y C. x->dep > y->dep D. x->val < y->val

第 41 题 ④ 处应填（）。

A. A[i * b + j - 1] == A[i * b + j]->son[0] B. A[i * b + j]->val < A[i * b + j - 1]->val C. A[i * b + j] == A[i * b + j - 1]->son[1] D. A[i * b + j]->dep < A[i * b + j - 1]->dep

第 42 题 ⑤ 处应填（）。

A. v += (S >> i & 1) ? -1 : 1 B. v += (S >> i & 1) ? 1 : -1 C. v += (S >> (i - 1) & 1) ? 1 : -1 D. v += (S >> (i - 1) & 1) ? -1 : 1

第 43 题 ⑥ 处应填（）。

A. (Dif[p] >> (r - p * b)) & ((1 << (r - l)) - 1) B. Dif[p] C. (Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1) D. (Dif[p] >> ((p + 1) * b - r)) & ((1 << (r - l + 1)) - 1)

查看答案与解析

题号	答案	解析
38	A	笛卡尔树建树，大根堆，维护单调递增栈。当栈顶值小于当前值，栈顶成为 p 的左子树，栈顶弹出
39	D	如果栈非空，当前 p 成为栈顶节点的右子树
40	A	LCA：找深度最浅（dep 最小）的节点
41	D	块内预处理：若当前节点深度比前一个浅，标记 1
42	D	枚举状态 S，若第 i−1 位为 1 表示深度变浅，v 减 1；否则 v 加 1
43	C	从 `Dif[p]` 中提取区间 [l, r] 对应的位：右移 `l - p*b` 位去掉左侧，再与掩码取交集

算法本质：笛卡尔树将 RMQ 转化为 LCA，再用欧拉序 + 分块 + ST 表实现 O(1) 查询。这是经典的 ±1 RMQ 优化。

答案速查表

单项选择题

题号	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
答案	A	B	A	C	C	C	C	B	D	A	A	C	C	C	B

阅读程序

题号	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33
答案	√	×	×	√	D	C	√	×	×	B	C	B	×	√	×	B	D	D

完善程序

题号	34	35	36	37	38	39	40	41	42	43
答案	D	A	D	C	A	D	A	D	D	C

考点分布分析

知识板块	涉及题号	分值	占比
数据结构与算法	4, 5, 8, 9, 12, 22-27, 38-43	36	36%
数学与组合	2, 7, 10, 11, 13, 14	12	12%
图论	6, 7, 15	8	8%
位运算与编码	28-33, 16-21	28	28%
Linux 基础	1	2	2%
递归与复杂度	3, 12, 22-26	14	14%