GESP 客观题评测系统

2020 CCF CSP-S 第一轮（提高级 C++）

CSPS-2020-R1

试卷解析总览，可直接查看每题答案与解析。

一、单项选择题

第 1 题（单选题，2 分）

请选出以下最大的数（）

(550)_{10}

(777)_{8}

2^{10}

(22F)_{16}

正确答案C

解析详情

【答案】C

【考点】进制转换与数值比较

【解析】分别换算为十进制： $(550)_{10}=550$ ， $(777)_8=511$ ， $2^{10}=1024$ ， $(22F)_{16}=559$ 。最大值是 $1024$ 。

【易错点】比较不同进制的数时，应先统一进制，不能直接比较各数的表面位数。

第 2 题（单选题，2 分）

操作系统的功能是（）。

负责外设与主机之间的信息交换

控制和管理计算机系统的各种硬件和软件资源的使用

负责诊断机器的故障

将源程序编译成目标程序

正确答案B

解析详情

【答案】B

【考点】操作系统的基本功能

【解析】操作系统负责统一控制和管理处理器、内存、外设等硬件资源以及文件、程序等软件资源，并为应用程序提供运行环境。

【易错点】不要把设备驱动、故障诊断或编译器的局部功能当成操作系统的总体功能。

第 3 题（单选题，2 分）

现有一段8分钟的视频文件，它的播放速度是每秒24帧图像，每帧图像是一幅分辨率为 $2048\times1024$ 像素的32位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？()。

30G

90G

150G

450G

正确答案B

解析详情

【答案】B

【考点】多媒体数据存储量计算

【解析】每帧占 $2048\times1024\times32/8=8$ MiB，共有 $8\times60\times24=11520$ 帧。总容量为 $8\times11520=92160$ MiB，即 $90$ GiB。

【易错点】 32 位表示每像素 32 bit，换算成字节时还要除以 8。

第 4 题（单选题，2 分）

今有一空栈 S，对下列待进栈的数据元素序列 a, b, c, d, e, f 依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（）。

正确答案B

解析详情

【答案】B

【考点】栈的后进先出特性

【解析】依次执行后，栈的变化为： $[a]\to[a,b]\to[a]\to[a,c]\to[a,c,d]\to[a,c]$ 。因此操作结束时栈底仍为 $a$ 。

【易错点】出栈删除的是栈顶元素，不能按数据的输入顺序从栈底删除。

第 5 题（单选题，2 分）

将（2，7，10，18）分别存储到某个地址区间为 $\theta \sim 10$ 的哈希表中，如果哈希函数 $h(x) = (\quad)$ ，将不会产生冲突，其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

x^2 \mod 11

2x \mod 11

x \mod 11

[x/2] \mod 11

，其中

[x/2]

表示

x/2

下取整

正确答案D

解析详情

【答案】D

【考点】哈希函数与冲突

【解析】取 $h(x)=\lfloor x/2\rfloor\bmod 11$ ，四个关键字的地址依次为 $1,3,5,9$ ，互不相同。例如 $x\bmod11$ 会使 $7$ 和 $18$ 都映射到 $7$ ，会发生冲突。

【易错点】判断冲突要把所有关键字逐一代入，而不能只检查相邻的两个关键字。

第 6 题（单选题，2 分）

下列哪些问题不能用贪心法精确求解？（）

霍夫曼编码问题

\theta

-1背包问题

最小生成树问题

单源最短路径问题

正确答案B

解析详情

【答案】B

【考点】贪心算法的适用范围

【解析】 $0$ -1 背包中的物品只能整件取或不取，按单位价值贪心可能错过全局最优解，通常需要动态规划。霍夫曼编码、最小生成树和非负权图的单源最短路均有正确的贪心算法。

【易错点】不要把可切分的分数背包与不可切分的 $0$ -1 背包混为一谈。

第 7 题（单选题，2 分）

具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（）。

\Theta(n+e)

\Theta(n^{2})

\Theta(e^{2})

\Theta(n)

正确答案A

解析详情

【答案】A

【考点】邻接表上的深度优先遍历

【解析】 DFS 会访问每个顶点一次，并沿邻接表检查每条边常数次，因此总时间为顶点扫描的 $\Theta(n)$ 加边扫描的 $\Theta(e)$ ，即 $\Theta(n+e)$ 。

【易错点】邻接表遍历不是邻接矩阵的 $\Theta(n^2)$ 。

第 8 题（单选题，2 分）

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24个顶点的二分图至多有（）条边。

144

100

122

正确答案A

解析详情

【答案】A

【考点】完全二分图的最大边数

【解析】若两部分分别有 $x$ 和 $24-x$ 个顶点，边数至多为 $x(24-x)$ 。乘积在两部分尽量均分时最大，即 $12\times12=144$ 。

【易错点】二分图同一部分内不能连边，最大边数不是完全图的 $\binom{24}{2}$ 。

第 9 题（单选题，2 分）

广度优先搜索时，一定需要用到的数据结构是（）。

栈

二叉树

队列

哈希表

正确答案C

解析详情

【答案】C

【考点】广度优先搜索

【解析】 BFS 按“先发现、先扩展”的顺序逐层搜索，需要用队列保存已发现但尚未扩展的顶点。

【易错点】栈对应的是深度优先搜索，会优先沿一条路径继续深入。

第 10 题（单选题，2 分）

一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 n 在以下哪个区间？已知 n < 60。( )。

30 < n < 40

40 < n < 50

50 < n < 60

20 < n < 30

正确答案C

解析详情

【答案】C

【考点】同余方程

【解析】条件为 $n\bmod3=2$ 、 $n\bmod5=3$ 、 $n\bmod7=4$ 。在 $n<60$ 的整数中逐步检验可得 $n=53$ ，它位于 $50<n<60$ 。

【易错点】 “每组若干人多几人”表示余数条件，不是用组数加上余数。

第 11 题（单选题，2 分）

小明想通过走楼梯来锻炼身体，假设从第 1 层走到第 2 层消耗 10 卡热量，接着从第 2 层走到第 3 层消耗 20 卡热量，再从第 3 层走到第 4 层消耗 30 卡热量，依此类推，从第 k 层走到第 $k+1$ 层消耗 10k 卡热量 $(k>1)$ 。如果小明想从 1 层开始，通过连续向上爬楼梯消耗 1000 卡热量，至少要爬到第几层楼？( )。

正确答案C

解析详情

【答案】C

【考点】等差数列求和

【解析】爬到第 $k+1$ 层的总消耗为 $10(1+2+\cdots+k)=5k(k+1)$ 。 $k=13$ 时为 $910$ ， $k=14$ 时为 $1050$ ，首次达到至少 $1000$ 卡时到达第 $15$ 层。

【易错点】 $k$ 表示跨越的楼层间隔，爬完第 $k$ 段后到达的是第 $k+1$ 层。

第 12 题（单选题，2 分）

表达式 $a^{*}(b+c)-d$ 的后缀表达形式为（）。

abc^{*}+d-

\dash*abcd

abcd^{*}+

abc+*d-

正确答案D

解析详情

【答案】D

【考点】中缀表达式转后缀表达式

【解析】先把括号内 $b+c$ 写成后缀式 $bc+$ ，再与 $a$ 相乘得到 $abc+*$ ，最后减去 $d$ ，结果为 $abc+*d-$ 。

【易错点】后缀表达式中运算符要放在其两个操作数之后，同时仍须遵守原表达式的优先级。

第 13 题（单选题，2 分）

从一个 $4 \times 4$ 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（）种方法。

正确答案B

解析详情

【答案】B

【考点】组合计数

【解析】先选第一个方格有 $16$ 种，第二个方格不能同行同列，只剩 $3\times3=9$ 种。两个方格没有次序，因此方法数为 $16\times9/2=72$ 。

【易错点】按先后选择会把同一对方格计算两次，最后必须除以 2。

第 14 题（单选题，2 分）

对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（）。

\theta((m + n^2) \log n)

\theta(mn + n^3)

\theta((m + n) \log n)

\theta(n^2)

正确答案D

解析详情

【答案】D

【考点】Dijkstra 算法复杂度

【解析】不用堆时，每轮要在线性范围内寻找当前距离最小的未确定顶点，共进行 $n$ 轮，耗时 $\Theta(n^2)$ 。简单图的松弛工作不超过同一量级。

【易错点】只有使用合适的优先队列后，复杂度中才会出现 $\log n$ 因子。

第 15 题（单选题，2 分）

1948 年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

欧拉（Leonhard Euler）

冯·诺伊曼（John von Neumann）

克劳德·香农（Claude Shannon）

图灵（Alan Turing）

正确答案C

解析详情

【答案】C

【考点】信息论发展史

【解析】克劳德·香农于 1948 年发表《通信的数学理论》，用熵刻画信息的不确定性，奠定了现代信息论的基础。

【易错点】图灵和冯·诺伊曼对计算机科学贡献重大，但信息论的奠基者是香农。

二、阅读程序（1）

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    int ans = -1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]);
                cout << ans;
                return 0;
}

假设输入的 n 和 d[i]都是不超过 10000 的正整数，完成下面的判断题和单选题：

第 16 题（判断题，1.5 分）

n 必须小于 1000，否则程序可能会发生运行错误。（）

正确答案错误

解析详情

【答案】错误

【考点】数组边界

【解析】数组 d 的有效下标为 $0\sim999$ ，循环访问 $0\sim n-1$ ，所以 $n=1000$ 时仍不会越界；要求应为 $n\le1000$ ，而不是必须小于 $1000$ 。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】长度为 1000 的数组最大下标是 999，但它恰好可以存放 1000 个元素。

第 17 题（判断题，1.5 分）

输出一定大于等于 $\theta_{0}$ 。（）

正确答案错误

解析详情

【答案】错误

【考点】循环条件与初值

【解析】 ans 初值为 $-1$ 。若所有 d[i] 都相等，就不存在满足 d[i] < d[j] 的一对元素，ans 不会更新，最终输出 $-1$ ，并非一定不小于 $0$ 。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】分析输出范围时要考虑 if 条件一次也不成立的情况。

第 18 题（判断题，1.5 分）

若将第 13 行的“j = 0”改为“j = i + 1”，程序输出可能会改变。

正确答案正确

解析详情

【答案】正确

【考点】双重循环的枚举范围

【解析】原程序枚举所有有序下标对；改成 j = i + 1 后只枚举 i < j 的对。若较小值出现在较大值之后，例如序列 2,1，原程序能取到这对数，修改后会漏掉，输出可能改变。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】表达式对两个数虽是对称的，但条件 d[i] < d[j] 与下标枚举方向共同决定该数对能否被检查。

第 19 题（判断题，1.5 分）

将第 14 行的“d[i] < d[j]”改为“d[i] != d[j]”，程序输出不会改变。（）

正确答案正确

解析详情

【答案】正确

【考点】位运算恒等式与对称性

【解析】 $d[i]+d[j]-(d[i]\&d[j])$ 等于 $d[i]\mid d[j]$ ，对交换 i、j 对称。把“小于”改成“不等于”只会把每对不同值反向再枚举一次，不会产生新的结果值，故最大值不变。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】循环执行次数会增加，但重复计算同一数对不会改变最终最大值。

第 20 题（单选题，3 分）

若输入 n 为 100，且输出为 127，则输入的 d[i] 中不可能有（）。

127

126

128

125

正确答案C

解析详情

【答案】C

【考点】按位或的数值性质

【解析】程序对不同的两个值计算按位或并取最大值。若输入中有 128，同时输出又能由其他不同值组成，则 128 与任一不同正整数按位或的结果都至少为 128，不可能最终最大值仅为 127。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】数值 128 新增了第 7 位的 1，这一位在按位或中不会被其他位抵消。

第 21 题（单选题，3 分）

若输出的数大于 $\theta$ ，则下面说法正确的是（）。

若输出为偶数，则输入的 d[i] 中最多有两个偶数

若输出为奇数，则输入的 d[i] 中至少有两个奇数

若输出为偶数，则输入的 d[i] 中至少有两个偶数

若输出为奇数，则输入的 d[i] 中最多有两个奇数

正确答案C

解析详情

【答案】C

【考点】按位或与奇偶性

【解析】输出值是某两个不同输入值的按位或。按位或结果为偶数，当且仅当两个操作数的最低位都为 0，也就是这两个输入值均为偶数，因此输入中至少有两个偶数。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】判断按位运算结果的奇偶性，只需检查二进制最低位。

二、阅读程序（2）

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假设输入的 n，k 和 d[i] 都是不超过 10000 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

第 22 题（判断题，1.5 分）

第9行的“x”的数值范围是 $L+1$ 到R，即 $[L+1, R]$ 。（）

正确答案错误

解析详情

【答案】错误

【考点】随机整数区间

【解析】 rand() % (R - L + 1) 的取值为 $0\sim R-L$ ，再加 L 后，x 的范围是 $[L,R]$ ，包含 L，并不是 $[L+1,R]$ 。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】取模数为区间长度 $R-L+1$ ，所以左右端点都能取到。

第 23 题（判断题，1.5 分）

将第 19 行的 “d[a]” 改为 “d[b]”，程序不会发生运行错误。（）

正确答案正确

解析详情

【答案】正确

【考点】分区过程的下标范围

【解析】 while 循环中 a、b 始终处在当前区间 $[L,R]$ 内；把该处读取的 d[a] 改为 d[b] 仍是合法数组访问。修改可能影响分区结果，但不会仅因此发生越界运行错误。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】 “不会发生运行错误”不等于“算法仍能返回正确的第 k 小元素”。

第 24 题（单选题，2.5 分）

当输入的d[i]是严格单调递增序列时，第17行的“swap”平均执行次数是（）。

\theta(n\log n)

\theta(n)

\theta(\log n)

\theta(n^{2})

正确答案A（另接受：B、C、D）

解析详情

【答案】A

【考点】随机化划分的交换次数

【解析】按本题给定答案的计数口径，随机枢轴使递归区间平均按比例缩小，期望有 $\Theta(\log n)$ 层；每层划分累计按线性规模计交换，总量为 $\Theta(n\log n)$ 。该题的源程序行号与“swap”计数口径存在歧义，JSON 也将其余三个选项列为可接受答案。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】要先确认统计的是某一条 swap 语句，还是整个划分过程的交换总量。

第 25 题（单选题，2.5 分）

当输入的d[i]是严格单调递减序列时，第17行的“swap”平均执行次数是（）。

\theta(n^{2})

\theta(n)

\theta(n\log n)

\theta(\log n)

正确答案B

解析详情

【答案】B

【考点】随机化快速选择

【解析】严格递减时，一次分区的交换次数与当前区间长度同阶；随机枢轴使后续递归规模期望按比例缩小。各层规模构成收敛的几何级数，累计为 $\Theta(n)$ 。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】快速选择只递归进入一侧，不应套用快速排序两侧递归的 $\Theta(n\log n)$ 。

第 26 题（单选题，2.5 分）

若输入的d[i]为i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是（）。

\theta(n)

\theta(n^{2})

\theta(n)

\theta(n\log n)

\theta(n\log n)

\theta(n^{2})

\theta(n\log n)

\theta(n\log n)

正确答案A

解析详情

【答案】A

【考点】随机化快速选择的复杂度

【解析】随机选择枢轴时，递归子区间期望持续缩小，扫描代价之和为 $\Theta(n)$ 。最坏情况下每次枢轴都在端点，区间只减少 1，代价为 $n+(n-1)+\cdots+1=\Theta(n^2)$ 。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】随机化保证的是期望复杂度，不排除连续选到极端枢轴的最坏情况。

第 27 题（单选题，2.5 分）

若输入的d[i]都为同一个数，此程序平均的时间复杂度是（）。

\theta(n)

\theta(\log n)

\theta(n\log n)

\theta(n^{2})

正确答案D

解析详情

【答案】D

【考点】快速选择的退化情况

【解析】所有 d[i] 相等时，分区不能把相等元素均匀分到枢轴两侧，递归区间每次至多缩小常数量。各次线性扫描相加为 $n+(n-1)+\cdots+1=\Theta(n^2)$ 。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】随机选枢轴无法改善所有关键字完全相等时的分区失衡。

二、阅读程序（3）

#include <iostream>
#include <queue>

using namespace std;

const int maxl = 2000000000;

class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
    public:
    int find(string x) {
        for (int i = 0; i < cnt; ++i)
            if (d[i].key == x)
                return d[i].value;
        }
        return -1;
    }
}

}
static int end() { return -1; }
void insert(string k, int v) {
d[cnt].key = k; d[cnt++].value = v;
}
} s[2];
24
class Queue {
string q[maxl];
int head, tail;
public:
void pop() { ++head; }
string front() { return q[head + 1]; }
bool empty() { return head == tail; }
void push(string x) { q[++tail] = x; }
} q[2];
34
string st0, st1;
int m;
37
string ltoR(string s, int L, int R) {
string t = s;
char tmp = t[L];
for (int i = L; i < R; ++i)
t[i] = t[i + 1];
t[R] = tmp;
return t;
}
46
string RtoL(string s, int L, int R) {
string t = s;
char tmp = t[R];
for (int i = R; i > L; --i)
t[i] = t[i - 1];
t[L] = tmp;
return t;
}
55
bool check(string st, int p, int step) {
if (s[p].find(st) != s[p].end())
return false;
++step;
if (s[p ^ 1].find(st) == s[p].end()) {

s[p].insert(st, step);
q[p].push(st);
return false;
}
cout << s[p ^ 1].find(st) + step << endl;
return true;
}
68
int main() {
cin >> st0 >> st1;
int len = st0.length();
if (len != st1.length()) {
cout << -1 << endl;
return 0;
}
if (st0 == st1) {
cout << 0 << endl;
return 0;
}
cin >> m;
s[0].insert(st0, 0); s[1].insert(st1, 0);
q[0].push(st0); q[1].push(st1);
for (int p = 0;
    ! (q[0].empty() && q[1].empty());
p ^ = 1) {
string st = q[p].front(); q[p].pop();
int step = s[p].find(st);
if ((p == 0 &&
    (check(LtoR(st, m, len - 1), p, step) ||
    check(RtoL(st, 0, m), p, step))) ||
    ||
    (p == 1 &&
    (check(LtoR(st, 0, m), p, step) ||
    check(RtoL(st, m, len - 1), p, step))))
    return 0;
}
cout << -1 << endl;
return 0;
}

第 28 题（判断题，1.5 分）

输出可能为 $\theta_{0}$ 。（）

正确答案正确

解析详情

【答案】正确

【考点】程序的提前返回条件

【解析】当 st0 == st1 时，程序在开始搜索前直接输出 0 并返回，因此输出确实可能为 0。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】不要只分析后面的双向搜索循环而漏掉主函数中的特殊情况。

第 29 题（判断题，1.5 分）

若输入的两个字符串长度均为 101 时，则 m=0 时的输出与 m=100 时的输出是一样的。（）

正确答案错误

解析详情

【答案】错误

【考点】字符串循环移位

【解析】长度为 101 时，m=0 的有效操作是对整个串左循环移位，m=100 的有效操作则是对整个串右循环移位。两者方向相反，到同一目标串的最少步数可能分别为 k 和 $101-k$ ，不一定相同。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】左右循环移位互为逆操作，但从同一起点到目标的有向步数不一定相等。

第 30 题（判断题，1.5 分）

若两个字符串的长度均为 n，则最坏情况下，此程序的时间复杂度为 $\theta(n!)$ 。（）

正确答案错误

解析详情

【答案】错误

【考点】状态搜索复杂度

【解析】不同字符的排列状态最多可达 $n!$ 个，但程序的 Map::find 还会对已存状态做线性扫描，并逐字符比较字符串。因此总运行时间不能直接写成 $\Theta(n!)$ ，最坏时会比单纯的状态数更高。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】状态数量只是复杂度的一部分，还要计入查重和字符串操作的成本。

第 31 题（单选题，2.5 分）

若输入的第一个字符串长度由100个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的m为0，则输出为（）。

100

-1

正确答案D

解析详情

【答案】D

【考点】可达状态与循环移位

【解析】 m=0 时，从起点一侧只能通过整串循环移位产生状态。含 100 个不同字符的字符串，其倒序不是原串的任何循环移位，因此两侧搜索不会相遇，最终输出 $-1$ 。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】循环移位保持字符的环形相对次序，不能实现任意排列或倒序。

第 32 题（单选题，4 分）

已知当输入为“0123\n3210\n1”时输出为4，当输入为“012345\n543210\n1”时输出为14，当输入为“01234567\n76543210\n1”时输出为28，则当输入为“0123456789ab\nba9876543210\n1”输出为（）。其中“\n”为换行符。

102

正确答案D

解析详情

【答案】D

【考点】双向搜索与逆序变换

【解析】由给出的偶数长度样例可归纳并验证，该逆序变换的最少步数为 $n^2/2-4$ 。目标字符串长度为 12，因此结果为 $12^2/2-4=68$ 。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】输入中的 `\n` 表示换行；第二个字符串是 `ba9876543210`，长度同样为 12。

第 33 题（单选题，4 分）

若两个字符串的长度均为n，且 $\theta<m<n-1$ ，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不一样。

若 n、m 均为奇数，则输出可能小于

\theta

。

若 n、m 均为偶数，则输出可能小于

\theta

。

若 n 为奇数、m 为偶数，则输出可能小于

\theta

。

若 n 为偶数、m 为奇数，则输出可能小于

\theta

。

正确答案C

解析详情

【答案】C

【考点】置换奇偶性与状态可达性

【解析】两种操作分别是长度为 $m+1$ 和 $n-m$ 的循环置换。n 为奇数、m 为偶数时，这两个长度都为奇数，所以每步都是偶置换；与起点相差奇置换的目标无法到达，程序可能输出 $-1<0$ 。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】循环长度为奇数时对应偶置换，判断的是“循环长度减 1”的奇偶性。

三、完善程序（1）

1. （分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 $w_i$ ，体积是 $v_i$ 。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。

他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $\alpha$ （ $\theta < \alpha < 1$ ），并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 $\alpha \cdot w$ ，体积是 $\alpha \cdot v$ ，另一块的价值是 $(1 - \alpha) \cdot w$ ，体积是 $(1 - \alpha) \cdot v$ 。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。那么最优的方案就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.6，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。

输入的数据范围为： $1 \leqslant n \leqslant 1000$ ， $1 \leqslant B \leqslant 10^5$ ； $1 \leqslant w_i, v_i \leqslant 100$ 。提示：将所有的蛋糕按照性价比 $w_i/v_i$ 从大到小排序后进行贪心选择。试补全程序。

#include <cstdio>
using namespace std;
03
const int maxn = 1005;
05
int n, B, w[maxn], v[maxn];
07
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v, u % v);
}
13
void print(int w, int v) {
int d = gcd(w, v);
w = w / d;
v = v / d;
if(v == 1)
printf("%d\n", w);
else
printf("%d/%d\n", w, v);
}
23
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
27
int main() {
scanf("%d %d", &n, &B);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
if(①) {
swap(w[j], w[j + 1]);
swap(v[j], v[j + 1]);
}
int curV, curW;

if(②) {
    ③
} else {
    print(B * w[1], v[1]);
    return 0;
}

for(int i = 2; i <= n; i++)
    if(curV + v[i] <= B) {
        curV += v[i];
        curW += w[i];
    } else {
        print(④);
        return 0;
    }
    print(⑤);
    return 0;
}

第 34 题（单选题，3 分）

①处应填（）

w[j] / v[j] < w[j + 1] / v[j + 1]

w[j] / v[j] > w[j + 1] / v[j + 1]

v[j] * w[j + 1] < v[j + 1] * w[j]

w[j] * v[j + 1] < w[j + 1] * v[j]

正确答案D

解析详情

【答案】D

【考点】分数背包的性价比排序

【解析】蛋糕应按 $w_i/v_i$ 从大到小排列；当 $w_j/v_j<w_{j+1}/v_{j+1}$ 时需要交换。为避免整数除法误差，交叉相乘写成 $w_jv_{j+1}<w_{j+1}v_j$ 。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】直接用整数除法比较比值会截断小数，可能得到错误的排序结果。

第 35 题（单选题，3 分）

②处应填（）

w[1] <= B

v[1] <= B

w[1] >= B

v[1] >= B

正确答案B

解析详情

【答案】B

【考点】分数背包的边界判断

【解析】排序后先处理性价比最高的第 1 块蛋糕。只有当其体积 v[1] <= B 时才能整块装入并继续循环，否则应直接装入它的 B/v[1] 部分。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】盒子容量约束比较的是体积 v[1]，不是价值 w[1]。

第 36 题（单选题，3 分）

③处应填（）

$\text{print}(v[1], w[1])$; return $\theta$;

$\text{curV} = \theta$; $\text{curW} = \theta$;

$\text{print}(w[1], v[1])$; return $\theta$;

$\text{curV} = v[1]$; $\text{curW} = w[1]$;

正确答案D

解析详情

【答案】D

【考点】贪心状态初始化

【解析】当第 1 块蛋糕能完整装入时，当前已用体积和当前总价值应分别初始化为 curV = v[1]、curW = w[1]，随后再从第 2 块开始选择。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】若初始化为 0，就会遗漏已经选定的第 1 块蛋糕。

第 37 题（单选题，3 分）

④处应填（）

curW * v[i] + curV * w[i], v[i]

(curW - w[i]) * v[i] + (B - curV) * w[i], v[i]

curW + v[i], w[i]

curW * v[i] + (B - curV) * w[i], v[i]

正确答案D

解析详情

【答案】D

【考点】分数背包的分数价值

【解析】剩余容量为 B-curV，只能装入第 i 块的这一部分，新增价值为 $(B-curV)w[i]/v[i]$ 。总价值通分后为 $[curW\cdot v[i]+(B-curV)w[i]]/v[i]$ 。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】分子中 curW 也要乘以分母 v[i] 后才能与分数部分相加。

第 38 题（单选题，3 分）

⑤处应填（）

curw, curv

curw, 1

curv, curw

curv, 1

正确答案B

解析详情

【答案】B

【考点】分数的整数输出

【解析】若循环结束仍未装满，说明所有蛋糕都已完整选入，总价值就是整数 curW。调用 print(curW, 1) 可按分母为 1 的形式正确输出。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】 curV 是总体积而不是目标价值，不能作为输出分子。

三、完善程序（2）

2. （最优子序列）取 m = 16，给出长度为 n 的整数序列 $a_1, a_2, \cdots, a_n (0 \leq a_i < 2^m)$ 。对于一个二进制数 x，定义其分值 $w(x)$ 为 $x + \text{popcnt}(x)$ ，其中 $\text{popcnt}(x)$ 表示 x 二进制表示中 1 的个数。对于一个子序列 $b_1, b_2, \cdots, b_k$ ，定义其子序列分值 $S$ 为 $w(b_1 \oplus b_2) + w(b_2 \oplus b_3) + w(b_3 \oplus b_4) + \cdots + w(b_{k-1} \oplus b_k)$ 。其中 $\oplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $\theta$ 。求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 $n (1 \leq n \leq 40000)$ 。接下来一行包含 n 个整数 $a_1, a_2, \cdots, a_n$ 。

提示：考虑优化朴素的动态规划算法，将前 $\frac{m}{2}$ 位和后 $\frac{m}{2}$ 位分开计算。

Max[x][y] 表示当前的子序列下一个位置的高 8 位是 x、最后一个位置的低 8 位是 y 时的最大价值。

试补全程序。

#include <iostream>
02
using namespace std;
04
typedef long long LL;
06
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 10000000000000000LL;
LL Max[MS + 4][MS + 4];
10
int w(int x)
{
int s = x;
while (x)
    {
①;
s++;
}
return s;
}
20
21
void to_max(LL &x, LL y)
{
}

if (x < y)
x = y;
}
27
int main()
{
int n;
LL ans = 0;
cin >> n;
for (int x = 0; x <= MS; x++)
for (int y = 0; y <= MS; y++)
Max[x][y] = -INF;
for (int i = 1; i <= n; i++)
{
LL a;
cin >> a;
int x = ②, y = a & MS;
LL v = ③;
for (int z = 0; z <= MS; z++)
to_max(v, ④);
for (int z = 0; z <= MS; z++)
⑤;
to_max(ans, v);
}
cout << ans << endl;
return 0;
}

第 39 题（单选题，3 分）

①处应填（）

x \gg = 1

x \wedge = x \& (x \wedge (x + 1))

x - = x \mid -x

x \wedge = x \& (x \wedge (x - 1))

正确答案D

解析详情

【答案】D

【考点】统计二进制中 1 的个数

【解析】 x & (x-1) 会清除 x 最低位的一个 1。循环每执行一次就令 s++，同时用 x &= x-1 减少一个 1，最终 s 等于原 x 加 popcnt(x)。复杂度分析：循环结构中包含嵌套迭代，关键变量的变化满足线性或对数级别递推，最终计算结果与选项吻合。

【易错点】若只右移一位，循环次数取决于最高位位置，而不是二进制中 1 的个数。

第 40 题（单选题，3 分）

②处应填（）

(\mathrm{a} \& \mathrm{MS}) \ll \mathrm{B}

a \gg B

a & (1 << B)

a & (MS << B)

正确答案B

解析详情

【答案】B

【考点】位运算拆分高低位

【解析】 B=8，MS=255；代码已用 y = a & MS 取得低 8 位，因此高 8 位应通过右移得到，即 x = a >> B。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】 a & (1 << B) 只能检测单独一位，不能取得完整的高 8 位。

第 41 题（单选题，3 分）

③处应填（）

-INF

Max[y][x]

0

Max[x][y]

正确答案C

解析详情

【答案】C

【考点】动态规划初值

【解析】当前元素可以单独构成长度为 1 的子序列，而该子序列没有相邻元素对，分值为 0。因此每次处理 a 时，当前最优值 v 应先初始化为 0。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】空子序列和单元素子序列的分值都是 0，不能初始化为负无穷后又不保留这一选择。

第 42 题（单选题，3 分）

④处应填（）

\max[x][z] + w(y \wedge z)

\max[x][z] + w(a \wedge z)

\max[x][z] + w(x \wedge (z << B))

\max[x][z] + w(x \wedge z)

正确答案A

解析详情

【答案】A

【考点】拆位动态规划的状态转移

【解析】当前数的高、低 8 位分别为 x、y。枚举上一元素的低 8 位 z 时，Max[x][z] 已匹配当前高位部分，只需补上低位异或的贡献 w(y ^ z)，得到候选值 Max[x][z] + w(y ^ z)。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】高低 8 位的异或贡献要分别匹配，不能把完整的 a 再与低位 z 直接运算。

第 43 题（单选题，3 分）

⑤处应填（）

to_max(Max[y][z], v + w(a ^ (z << B)))

to_max(Max[z][y], v + w((x ^ z) << B))

to_max(Max[z][y], v + w(a ^ (z << B)))

to_max(Max[x][z], v + w(y ^ z))

正确答案B

解析详情

【答案】B

【考点】拆位动态规划的状态更新

【解析】选入当前数后，它的低 8 位 y 成为子序列末项的低位。为未来高位 z 预处理时，应更新 Max[z][y]，并加入当前高位 x 与 z 的贡献 w((x ^ z) << B)，故选 B。关键变量追踪：在执行过程中，变量的状态根据条件分支发生转移，最终输出值可通过状态推演得出。

【易错点】状态的两个下标含义不同：第一个是下一元素的候选高位，第二个是当前末项的低位。