该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

初赛模拟卷 B

考试时长：60 分钟。满分 100 分。

第 1 题（单选）

Tarjan 算法求强连通分量时，low[u] 通常表示（）。

{{ select(1) }}

• 以 u 为根的 DFS 子树的节点数
• 从 u 的 DFS 子树沿树边，并至多再沿一条指向当前栈内节点的边，能够到达的最小 dfn
• u 所在强连通分量的节点数
• u 到 DFS 树根的距离

第 2 题（单选）

在无向图中，割点指删除该点及相关边后会导致（）。

{{ select(2) }}

• 度数变成 0
• 所有路径变短
• 图边权变小
• 连通块数增加

第 3 题（单选）

无向图中的桥，是指删除这条边后会使（）。

{{ select(3) }}

• 最短路必变短的边
• 入度为 0 的边
• 连通块数增加的边
• 权值最大的边

第 4 题（单选）

0-1 BFS 适合处理边权只可能为哪些值的最短路问题（）。

{{ select(4) }}

• 任意实数
• 任意非负整数
• 全部负数
• 0 和 1

第 5 题（单选）

最小生成树必须满足的基本性质是（）。

{{ select(5) }}

• 连接所有点且无环
• 包含图中所有边
• 边权必须不同
• 只适用于有向图

第 6 题（单选）

若原图本身不连通，则最小生成树（）。

{{ select(6) }}

• 仍一定存在
• 边数为 m
• 不存在覆盖所有点的生成树
• 等于最短路树

第 7 题（单选）

根据常见定义，二分图最大匹配的增广路算法中，找到一条增广路会使匹配数（）。

{{ select(7) }}

• 不变
• 减少 1
• 增加 1
• 变为 0

第 8 题（单选）

某 DAG 只有边 1 -> 3 和 2 -> 3，关于它的拓扑序，下列说法正确的是（）。

{{ select(8) }}

• 只有 1,2,3
• 只有 2,1,3
• 1,2,3 和 2,1,3 都是合法拓扑序
• 1,3,2 和 3,1,2 都是合法拓扑序

第 9 题（单选）

树上距离问题中，哪类场景可以通过一次 DFS/BFS 等遍历求出从起点到各点的距离（）。

{{ select(9) }}

• 字符串集合
• 含负环图
• 任意有向图
• 无权树或带非负边权树的相应距离遍历

第 10 题（单选）

判断树的重心时，若一棵 11 个节点的树删除节点 u 后各连通块大小为 5、3、2，关于 u 的说法正确的是（）。

{{ select(10) }}

• u 一定不是重心，因为仍有大小为 5 的连通块
• u 是重心，因为删除它后最大连通块大小不超过 11/2
• u 是叶节点，因为连通块数量为 3
• 无法判断，因为树的重心只能有一个

第 11 题（单选）

树上 DFS 序中，若 tin[u] 是进入 u 的时间戳、sz[u] 是子树大小，则 u 的子树对应（）。

{{ select(11) }}

• 任意一组不连续下标
• 只包含 tin[u] 一个位置
• 区间 [1,tin[u])
• 连续区间 [tin[u],tin[u]+sz[u]-1]

第 12 题（单选）

有向图存在环时，拓扑排序最直接的结果是（）。

{{ select(12) }}

• 所有点入度为 0
• 复杂度变成 O(1)
• 答案一定为 0
• 没有合法拓扑序

第 13 题（单选）

有向图含边 s -> a（权 2）、s -> b（权 5）、b -> a（权 -10）。直接使用标准 Dijkstra 的主要问题是（）。

{{ select(13) }}

• 图中顶点数太少
• 负权边破坏了已弹出最短距离不可再改进的贪心前提
• 必须先求最小生成树
• 邻接表不能存负权边

第 14 题（单选）

根据常见定义，DAG 中有边 1→3、2→3、3→4。Kahn 拓扑排序开始时可进入队列的顶点数为（）。

{{ select(14) }}

• 1
• 2
• 3
• 4

第 15 题（单选）

根据常见定义，无权树中，设 w=LCA(u,v)，depth 表示深度，则 u、v 间距离为（）。

{{ select(15) }}

• depth[w]
• depth[u]+depth[v]
• depth[u]-depth[v]
• depth[u]+depth[v]-2*depth[w]

第 16 题（单选）

可撤销并查集一般不使用普通路径压缩，主要原因是（）。

{{ select(16) }}

• 路径压缩会使 find 变成 O(n)
• 路径压缩只适用于有向图
• 路径压缩会改变集合数量
• 一次 find 可能改写多个父指针，使历史状态难以按栈精确撤销

第 17 题（单选）

根据常见定义，并查集带权值时，额外维护的是（）。

{{ select(17) }}

• 线段树懒标记
• 拓扑序
• 字符串哈希
• 节点到父亲或根的关系量

第 18 题（单选）

可撤销并查集通常不能使用普通路径压缩，主要原因是（）。

{{ select(18) }}

• 不能合并
• 必须递归
• 路径压缩修改太多信息不易回滚
• find 会变慢到 O(0)

第 19 题（单选）

在 C++ 中，若比较函数 cmp(a,b) 在 sort 中同时可能使 cmp(a,b) 和 cmp(b,a) 为 true，最可能导致（）。

{{ select(19) }}

• 自动去重
• 稳定排序
• 排序更快
• 违反严格弱序，结果未定义或异常

第 20 题（单选）

根据常见定义，stable_sort 相比 sort，额外保证（）。

{{ select(20) }}

• 相等元素相对顺序不变
• 自动去重
• 线性复杂度
• 只能升序

第 21 题（单选）

二分查找在有序数组中查找一个元素，时间复杂度通常是（）。

{{ select(21) }}

• O(1)
• O(log n)
• O(n)
• O(n log n)

第 22 题（单选）

在 C++ 程序中，signed int 溢出的行为是（）。

{{ select(22) }}

• 未定义行为
• 按模回绕且标准保证
• 自动变 long long
• 抛出异常

第 23 题（单选）

根据常见定义，若 int x=1e9, y=1e9，则 x*y 的计算在赋给 long long 前（）。

{{ select(23) }}

• 可能已经 int 溢出
• 自动取模
• 编译失败
• 一定按 long long 算

第 24 题（单选）

若需要计算 a*b%mod 且 a,b 可接近 1e18，最稳妥的典型方法是（）。

{{ select(24) }}

• 使用 __int128 或快速乘
• 转成 int
• 先除以 mod
• 直接 long long 相乘

第 25 题（单选）

根据常见定义，埃氏筛中，当 i 已知为质数时，从 i*i 开始标记其倍数的主要原因是（）。

{{ select(25) }}

• i*i 以前的倍数一定也是质数
• 更小的合数倍数已被更小质因子标记
• 只有平方数才是合数
• 可以把空间复杂度降为 O(1)

第 26 题（单选）

每轮都把搜索范围缩小约一半的算法，时间复杂度通常是（）。

{{ select(26) }}

• O(log n)
• O(n)
• O(n log n)
• O(2^n)

第 27 题（单选）

根据常见定义，next_permutation 返回 false 表示（）。

{{ select(27) }}

• 当前是字典序最后一个排列
• 数组为空
• 已自动排序为降序并停止
• 发生编译错误

第 28 题（单选）

C++ 中，std::endl 与字符 \n 的重要区别是（）。

{{ select(28) }}

• std::endl 会结束程序
• 字符 '\n' 不能用于 cout
• std::endl 输出换行后还会刷新输出缓冲区
• 字符 '\n' 会强制刷新输出缓冲区

第 29 题（单选）

根据常见定义，设 T(1)=Θ(1)，且对 n 为 2 的幂有 T(n)=2T(n/2)+Θ(n)，则 T(n)=（）。

{{ select(29) }}

• Θ(n)
• Θ(n log n)
• Θ(n^2)
• Θ(log n)

第 30 题（单选）

根据常见定义，设 T(1)=Θ(1)，且对 n 为 2 的幂有 T(n)=T(n/2)+Θ(1)，则 T(n)=（）。

{{ select(30) }}

• Θ(n)
• Θ(1)
• Θ(log n)
• Θ(n log n)

第 31 题（多选）

关于 CDQ 分治，下列说法正确的有（）。

{{ multiselect(31) }}

• 常与 BIT 结合处理偏序
• 只能用于在线逐个加入数据
• 不允许递归
• 常处理离线贡献

第 32 题（多选）

关于莫队算法，判断正确的有（）。

{{ multiselect(32) }}

• 适用于所有最短路问题
• 通过移动左右端点维护答案
• 通常离线重排询问
• 是在线算法不能排序询问

第 33 题（多选）

关于 FFT/NTT，判断正确的有（）。

{{ multiselect(33) }}

• 可加速多项式卷积
• NTT 在合适模数下避免浮点误差
• FFT 是单源最短路算法
• NTT 不需要模数条件

第 34 题（多选）

关于主席树求静态区间第 k 小，判断正确的有（）。

{{ multiselect(34) }}

• 每次查询必须重建整棵树
• 不能处理离散化后的值域
• 通常建立前缀版本
• 查询 [l,r] 可用 version[r] 与 version[l-1] 相减

第 35 题（多选）

关于后缀数组，判断正确的有（）。

{{ multiselect(35) }}

• sa 表示后缀字典序排名对应的起点
• height/LCP 常记录相邻排名后缀的最长公共前缀
• 只能处理回文串
• 不能与 RMQ 结合

第 36 题（多选）

关于常见算法特点，下列说法正确的有（）。

{{ multiselect(36) }}

• 并查集可维护集合合并与查询
• 线段树可维护区间信息
• Dijkstra 适合非负边权最短路
• 贪心只要看起来合理就一定正确

第 37 题（多选）

关于算法题中的常见结论，下列说法正确的有（）。

{{ multiselect(37) }}

• Dijkstra 适合非负边权最短路
• 贪心只要看起来合理就一定正确
• 并查集可维护集合合并与查询
• 线段树可维护区间信息

第 38 题（多选）

阅读题目条件时，关于搜索、排序和动态规划等常见算法，下列说法正确的有（）。

{{ multiselect(38) }}

• 贪心只要看起来合理就一定正确
• Dijkstra 适合非负边权最短路
• 线段树可维护区间信息
• 并查集可维护集合合并与查询

第 39 题（多选）

下列算法判断中，合理的有（）。

{{ multiselect(39) }}

• 线段树可维护区间信息
• 贪心只要看起来合理就一定正确
• 并查集可维护集合合并与查询
• Dijkstra 适合非负边权最短路

第 40 题（多选）

关于二分适用场景，下列说法合理的有（）。

{{ multiselect(40) }}

• 答案越大越容易满足限制
• 有序数组中查找元素
• 最小化满足条件的最大值
• 完全没有可比较规则的随机过程

第 41 题（判断）

请判断下列说法是否正确：容斥原理通过加减交集修正重复计数。（）

{{ select(41) }}

• 正确
• 错误

第 42 题（判断）

请判断下列说法是否正确：三集合容斥中三重交集项的符号为负。（）

{{ select(42) }}

• 正确
• 错误

第 43 题（判断）

请判断下列说法是否正确：莫队算法是典型离线区间询问算法。（）

{{ select(43) }}

• 正确
• 错误

第 44 题（判断）

请判断下列说法是否正确：Knuth 优化不需要任何额外条件。（）

{{ select(44) }}

• 正确
• 错误

第 45 题（判断）

请判断下列说法是否正确：DP 不是只写公式，还要保证状态来源和更新顺序一致。

{{ select(45) }}

• 正确
• 错误

第 46 题（判断）

下面这句话是否正确：同一种问题在不同数据规模下，适合的算法可能并不一样。

{{ select(46) }}

• 正确
• 错误

第 47 题（判断）

数据范围往往能提示我们应该选择多快的算法。

{{ select(47) }}

• 正确
• 错误

第 48 题（判断）

判断这一说法是否成立：使用 vector 时，可以根据需要继续加入元素，不必一开始固定全部大小。

{{ select(48) }}

• 正确
• 错误

第 49 题（判断）

请判断下列说法是否正确：Tarjan 求 SCC 时，low[u]!=dfn[u] 表示 u 一定是某个 SCC 的弹栈根。（）

{{ select(49) }}

• 正确
• 错误

第 50 题（判断）

可持久化线段树做一次单点修改时，必须把整棵树的所有节点都复制一遍。（）

{{ select(50) }}

• 正确
• 错误