GESP 客观题评测系统

【答案】A

【考点】Linux 常用命令

【解析】 `pwd` 会输出当前工作目录的绝对路径；`cd` 用于切换目录，`ls` 用于列出目录内容。

【易错点】 不要把“查看当前路径”与“切换目录”的 `cd` 混淆。

【答案】A

【考点】顺序查找的时间复杂度

【解析】 数组无序时无法排除任何尚未检查的元素，必须扫描全部 n 个元素并维护当前最大值，因此时间复杂度为 O(n)。

【易错点】 O(log n) 需要有序性等可用于缩小搜索范围的条件。

【答案】C

【考点】递归与调用栈

【解析】 `baz()` 没有递归终止条件，每次调用还会在栈上分配 `int a[1000]`；调用帧不断累积，最终耗尽栈空间。

【易错点】 局部数组本身不必然导致栈溢出，无限递归才是持续占用栈空间的关键。

【答案】B

【考点】排列计数

【解析】 金、银、铜牌有次序，依次有 10、9、8 种选择，颁奖方式数为 P(10,3)=10×9×8=720。

【易错点】 奖牌有等级区别，不能按无序组合 C(10,3) 计算。

【答案】B

【考点】队列的基本性质

【解析】 队列从队尾入队、从队首出队，最先进入的元素最先离开，正好实现 FIFO。

【易错点】 栈遵循的是后进先出 LIFO。

【答案】B

【考点】递推计算

【解析】 依次计算：f(2)=f(1)+f(1)=2，f(3)=f(2)+f(1)=3，f(4)=f(3)+f(2)=3+2=5。

【易错点】 [n/2] 表示整数部分，计算 f(3) 时应取 f(1)。

【答案】D

【考点】欧拉图判定

【解析】 无向欧拉图连通、所有顶点度数为偶数，并存在欧拉回路；这些条件不限制边数的奇偶性，因此边数不一定是奇数。

【易错点】 “所有顶点度数为偶数”不能推出边数为奇数，因为度数和等于 2|E|。

【答案】A

【考点】二分查找的适用条件

【解析】 二分查找依据中间元素与目标值的大小关系排除一半区间，数组必须按某种单调次序排列。

【易错点】 数组长度无需是 2 的幂，元素类型也不限于整数。

【答案】B

【考点】模逆元与扩展欧几里得算法

【解析】 扩展欧几里得算法可求出 nx+my=gcd(n,m) 的整数解；当 gcd(n,m)=1 时，x mod m 就是 n 的模逆元。

【易错点】 模逆元并非总存在，必须先满足 gcd(n,m)=1。

【答案】D

【考点】开放地址哈希的最坏复杂度

【解析】 发生严重聚集时，一次查找可能沿探测序列检查表中全部 n 个已占位置，最坏时间复杂度为 O(n)。

【易错点】 平均探测次数的估计不能替代最坏情况上界。

【答案】A

【考点】完全二叉树的结点数

【解析】 第 i 层最多有 2^(i-1) 个结点，h 层全部填满时总结点数为 1+2+…+2^(h-1)=2^h-1。

【易错点】 题目把根结点计为第 1 层，指数不要多加 1。

【答案】C

【考点】完全图中的环计数

【解析】 先从 10 个顶点中选 4 个，再计算这 4 个点构成的无向环：C(10,4)×(4-1)!/2=210×3=630。

【易错点】 同一个无向环的不同起点及正反两个方向不能重复计数。

【答案】B

【考点】数位和

【解析】 对 x=199，有 f(x)=1+9+9=19，继而 f(f(x))=1+9=10。小于 199 的自然数数位和最大不超过 18，二次求和不可能为 10。

【易错点】 条件是对数位和再求一次数位和，不是直接令 f(x)=10。

【答案】C

【考点】相邻交换与逆序对

【解析】 最坏排列为 k 个 1 全在左侧、n-k 个 0 全在右侧；每个 1 都要跨过 n-k 个 0，共需 k(n-k) 次相邻交换。

【易错点】 交换次数取决于 1 与 0 的逆序对数，而不是 1 之间的相对次序。

【答案】D

【考点】最小割与路径阻断

【解析】 最少需删 2 条边。可行最小割共有 4 组：{1→2,4→6}、{2→5,4→6}、{4→6,5→7}、{5→7,6→7}。

【易错点】 必须同时阻断所有从 1 到 7 的路径，不能只检查某一条路径。

【答案】正确

【考点】快速排序的递归深度极限分析

【解析】 代码中的 `recursion` 是一次标准的快速排序划分。每次递归会将原数组根据 `pivot` 划分为左右两部分。当限制递归深度 `d` 大于等于数组大小 `b` 时，考虑到快速排序最坏情况下（例如数组本身已有序，每次划分只能使规模减 1），需要的最大递归深度为 `b`。因此 `d >= b` 足以保证在强制退出前完全完成排序，序列必定是有序的。

【易错点】 容易忽略快速排序最坏情况下的深度可达 $O(N)$，仅仅看到平均深度 $O(\log N)$ 而产生误判。

【答案】错误

【考点】快速排序单层划分的变量状态追踪

【解析】 `generate` 生成的序列依赖 `logic(5, i)`，真值表化简可知其等价于 `5 | i`。对于 `i=0~4`，`5|i` 分别为 5,5,7,7,5，对 6 取模后初始序列为 `c = {5, 5, 1, 1, 5}`。`recursion(1, c, 5)` 时 `depth=1`，`pivot=5`，双指针 `i=0, j=4`。第一步交换 `c[0], c[4]` 得到 `{5,5,1,1,5}`；第二步交换 `c[1], c[3]` 得到 `{5,1,1,5,5}`。之后 `i=3, j=2` 退出循环。由于传入的 `d=1`，下一层递归直接 `depth <= 0` 返回，排序终止。因此最终输出是 `{5, 1, 1, 5, 5}`，并非 `{1, 1, 5, 5, 5}`。

【易错点】 一次划分只是将元素粗略分到枢轴两侧，并不意味着单侧内部已经有序，必须严格跟进首尾双指针的交换过程。

【答案】错误

【考点】递归算法的时间复杂度退化分析

【解析】 程序的两个阶段中，`generate` 循环了 `b` 次，时间复杂度为 $O(b)$。但核心阶段 `recursion` 实现的是快速排序。在最坏情况下（比如输入的序列由于取模已经产生大量重复元素，或者退化为单边递归），每层划分需要 $O(k)$ 的扫描，且只使问题规模减 1。这样递归总工作量可达 $b + (b-1) + \dots + 1 = O(b^2)$。因此该算法整体最坏时间复杂度为 $O(b^2)$，而非 $O(b)$。

【易错点】 数组容量无限制只能说明不会越界，不能改变基于比较的快速排序在极端情况下的时间复杂度退化。

【答案】B

【考点】位运算真值表推导

【解析】 分析 `logic(x, y) = (x & y) ^ ((x ^ y) | (~x & y))`。我们针对一个二进制位进行状态推演： - x=0, y=0: 0 ^ (0 | 0) = 0 - x=0, y=1: 0 ^ (1 | 1) = 1 - x=1, y=0: 0 ^ (1 | 0) = 1 - x=1, y=1: 1 ^ (0 | 0) = 1 该真值表与按位或运算 `x | y` 的真值表完全吻合，因此逻辑上该函数等价于 `x | y`。

【易错点】 面对复杂的位运算表达式，试图通过分配律化简容易出错，直接通过 0/1 枚举真值表是最可靠的做法。

【答案】C

【考点】位运算极值追踪与取模规律

【解析】 输入 "10 100 100"，`d=100` 足够对 100 个数彻底排序。数组由 `c[i] = (10 | i) % 101` 生成，`i` 范围是 0 到 99。10 的二进制是 `1010`，按位或会将 `i` 的第 1、3 位置 1。当 `i` 在此范围内时，`(10 | i)` 的最大可能值发生在 `i = 95` (二进制 `1011111`) 时，此时 `10 | 95 = 95`，对 101 取模仍为 95。排序后第 100 个数即为这 100 个数中的最大值，因此结果是 95。

【易错点】 排序后的第 100 个数即序列最大值，需注意 `i` 的上限是 99，追踪 `10 | i` 在 `i<100` 下的极值是解题关键。

【答案】正确

【考点】状态压缩动态规划的循环嵌套复杂度

【解析】 函数 `solve()` 采用状态压缩 DP。外层循环变量 `i` 遍历 `n` 次（处理每一位），内层循环变量 `j` 遍历 `0` 到 `(1 << (m-1)) - 1`，即 `2^{m-1}` 个状态。循环体内进行常数次判断和状态转移。总的时间复杂度严格为 $O(n \cdot 2^{m-1})$，也就是 $O(n \cdot 2^m)$。即使 `dp` 数组长度无限大，也不会改变循环执行的次数。

【易错点】 时间复杂度由循环控制条件决定，只要不依赖外部变长输入，双层嵌套次数直接决定了渐进复杂度。

【答案】正确

【考点】子序列计数中的前导零与状态转移分析

【解析】 输入为 `s = "10000000001"` (两端为 1，中间 9 个 0)。`solve2` 会统计所有长度不超过 2 的子序列：单独 1 有两个，单独 0 有九个；长度为 2 的组合。计算可知总计数包含大量的带前导 0 的序列。`solve2` 对下标组合无差别计数得到 32。而 `solve` 增加了 `!j && s[i] == '0'` 的特判，避免了以 0 开头（前导零）产生冗余的子序列，过滤后真正计算的本质不同子序列数为 23。

【易错点】 需清楚 `solve` 与 `solve2` 在 DP 转移时的本质区别，即 `solve` 抑制了首位取 '0' 时的转移路径，从而避免重复统计相同数值的二进制串。

【答案】正确

【考点】组合数与子序列总数上界放缩

【解析】 当 $n \leq 10$ 时，字符串的最大长度为 10。长度为 $n$ 的字符串总共能产生 $2^n - 1$ 个非空子序列（包含前导零在内）。每个子序列作为二进制数，其数值必然 $< 2^{10}$。即便是最极端的全 1 字符串，其累加和最多也只有 $2^{10} \times 2^{10} = 4^{10}$。`solve()` 去除了前导零的重复计算，其实际返回值远小于所有子序列直接累加的理论上界。

【易错点】 此处是数学放缩法：子序列最大个数乘以单个子序列可能达到的最大数值，从而轻松论证其严格小于给定上界。

【答案】B

【考点】前导零对子序列计数的影响

【解析】 两函数不同只可能来自“先选 0、后选 1”的前导零子序列。结果相同当且仅当串中不存在 0 在 1 之前，即形如 1^k0^(10-k)，k=0…10，共 11 种。

【易错点】 全 0 串也满足条件，应计入 k=0。

【答案】C

【考点】二进制子序列求和

【解析】 最大值在 n=6、s=`111111` 且允许取满 6 位时取得。长度为 r 的子序列值均为 2^r-1，总和 Σ C(6,r)(2^r-1)=3^6-2^6=665。

【易错点】 同一数值可由不同下标子序列产生，`dp` 会累计其出现次数。

【答案】C

【考点】前导零造成的重复计数

【解析】 差值来自 `solve2` 计入而 `solve` 忽略的前导零选择。枚举 8 位串可知最大值在 `01111111` 取得：solve2=4118、solve=2059，差为 2059。

【易错点】 比较的是两个函数的返回值之差，不是某个函数单独的最大值。

【答案】正确

【考点】筛法与排序复杂度

【解析】 `init` 的筛法约为 O(n log log n)，构造全部 `h[i]` 为 O(n)，对 n 个哈希值排序为 O(n log n)，故总体为 O(n log n)。

【易错点】 总体复杂度由增长更快的排序阶段决定。

【答案】错误

【考点】算法瓶颈分析

【解析】 `init()` 的筛法约为 O(n log log n)，而 `solve()` 中 `sort(h+1,h+n+1)` 为 O(n log n)，排序才是渐进时间瓶颈。

【易错点】 嵌套循环不一定比库排序慢，应先比较其实际渐进复杂度。

【答案】正确

【考点】字符串哈希参数

【解析】 B1 是第一组多项式哈希的底数，K1 会改变每个布尔值的编码；修改它们会改变 `h[i].h1`，也可能改变哈希碰撞情况和最终输出。

【易错点】 双哈希只能降低碰撞概率，并不意味着任意修改一组参数都保证输出不变。

【答案】C

【考点】完全二叉树的遍历与字符串哈希

【解析】 程序用数组下标表示完全二叉树，但 `h[i]=h[2*i]+h[i]+h[2*i+1]` 的拼接顺序是左子树、根、右子树，因此生成的是中序遍历序列，对应选项 C。

【易错点】 数组下标采用层序编号，并不意味着程序输出层序遍历；应以实际拼接顺序判断。

【答案】A

【考点】完全二叉树的中序遍历与二进制计算

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： 当 n=10 时，中序遍历下标依次为 8,4,9,2,10,5,1,6,3,7。按结点编号是否为质数写成 0/1，得到二进制串 `0001010011`，其十进制值为 83，因此选 A。

【易错点】 若误按后序或层序拼接，会得到其他数值；本题应严格按代码中的“左子树+根+右子树”计算。

【答案】C

【考点】子树哈希去重

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： 对 n=16 自底向上计算每个结点子树的二元哈希及长度，再排序去重；共有 10 组不同的 `(l,h1,h2)`，所以第二行输出 10。

【易错点】 `unique` 比较完整的长度和双哈希，不是只比较 `h1`。

【答案】A

【考点】指针区间上的二分查找

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： 搜索区间是半开区间 `[a,an)`，其中元素个数为指针差 `an-a`，所以右边界 r 应初始化为 `an-a`。

【易错点】 半开区间允许 r 等于元素个数，不应再减 1。

【答案】A

【考点】upper_bound 的判定条件

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： `upper_bound` 要找第一个严格大于 ai 的元素；若 `a[mid]>ai`，答案就在 mid 或其左侧，因此令 `r=mid`。

【易错点】 使用 `>=` 找到的是第一个不小于 ai 的位置，即 `lower_bound`。

【答案】A

【考点】数组指针与下标转换

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： 二分结束时 l 是第一个大于 ai 的元素下标，返回对应指针应为 `a+l`；调用处再减 b 即得到不大于阈值的元素个数。

【易错点】 返回值是指针而不是整数下标。

【答案】A

【考点】答案值域二分

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： A、B 均单调不降，所有两数之和的最大值是 `a[n-1]+b[n-1]`，可将其作为二分答案的右边界。

【易错点】 长度为 n 的数组最后一个合法下标是 n-1。

【答案】A

【考点】第 k 小与二分判定

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： `get_rank(mid)` 统计和不大于 mid 的数对个数；若该数小于 k，说明第 k 小的和必定大于 mid，应令 `l=mid+1`。

【易错点】 当计数恰为 k 时，mid 已可能是答案，不能继续排除 mid。

【答案】A

【考点】次短路的双层状态转移

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： 当 d 刷新 b 的最短路时，b 原来的最短路应降为次短路状态 n+b；其长度是 `dis[b]`，前驱仍是原来的 `pre[b]`，故调用该选项。

【易错点】 更新最短路前必须先保存旧最短路，否则会丢失次短路候选。

【答案】A

【考点】优先队列模拟小根堆

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： C++ 的 `priority_queue<pair<int,int>>` 默认取最大值；把距离 d 取负后压入 `make_pair(-d,b)`，即可让距离最小的状态最先弹出。

【易错点】 若直接压入 d，程序会优先处理最长距离。

【答案】B

【考点】memset 初始化整数无穷大

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： `memset(dis,0x1f,...)` 会把每个 int 填成 `0x1f1f1f1f`，十进制正好是 522133279，与常量 `inf` 一致。

【易错点】 `memset` 按字节填充，参数不是直接写入每个 int 的数值。

【答案】A

【考点】次短路松弛

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： 从最短路状态 a 沿边到 b 得到 `dis[a]+c`；若它未成为 b 的新最短路，就应尝试写入 b 的次短路状态 n+b，前驱状态为 a。

【易错点】 候选路径尚未进入第二层前，前驱仍是最短路层的 a，而不是 n+a。

【答案】A

【考点】路径前驱回溯

【解析】 本题考察核心变量与递归/循环状态的精确推导。通过对相关代码的具体追踪： 当状态 a≥n 时，它代表顶点 `a%n` 的次短路状态；该层前驱数组是 `pre2`，因此递归回溯 `pre2[a%n]`。

【易错点】 `pre2` 已指向 `pre+n`，索引必须还原为 0…n-1。