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

初赛模拟卷 A

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

第 1 题（单选）

在 C++ 中，若向 vector 继续插入元素并触发扩容，原来指向其中元素的迭代器或引用（）。

{{ select(1) }}

• 自动更新
• 一定仍有效
• 变成下标
• 可能失效

第 2 题（单选）

根据常见定义，erase 一个 set 迭代器后，被删除迭代器（）。

{{ select(2) }}

• 自动指向 begin
• 仍可解引用
• 失效
• 变为 end 且可解引用

第 3 题（单选）

在线性扫描一次数组的算法中，时间复杂度通常是（）。

{{ select(3) }}

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

第 4 题（单选）

将函数参数写成 const vector<int>& a，通常是为了（）。

{{ select(4) }}

• 允许修改原 vector
• 只传第一个元素
• 避免复制且禁止修改
• 复制整个 vector

第 5 题（单选）

字符串 s = "ababa" 的前缀函数 pi[4]（下标从 0 开始）为（）。

{{ select(5) }}

• 1
• 2
• 3
• 4

第 6 题（单选）

根据常见定义，长度为 n 的字符串中，不同子串数量可由后缀数组计算为（）。

{{ select(6) }}

• ΣLCP
• n-ΣLCP
• n(n+1)/2-ΣLCP
• n(n-1)/2+ΣLCP

第 7 题（单选）

根据常见定义，倍增思想除了 LCA，还常用于（）。

{{ select(7) }}

• 跳祖先或函数迭代
• 输入换行
• 冒泡排序
• 高精度加法

第 8 题（单选）

在 C++ 中，在 C++ 标准库中，对区间 [first,last) 使用 lower_bound(first,last,x,cmp) 时，标准语义要求该区间至少满足（）。

{{ select(8) }}

• 按同一比较规则对目标值 x 已分区，即所有应排在 x 前的元素在前
• 元素必须按内存地址连续递增
• 区间长度必须为 2 的幂
• 元素必须互不相同

第 9 题（单选）

lambda 捕获 [&] 的表示的是（）。

{{ select(9) }}

• 默认按值捕获
• 默认按引用捕获
• 只捕获 this
• 不允许捕获

第 10 题（单选）

memset(a, 0x3f, sizeof a) 常用于把 int 数组初始化为（）。

{{ select(10) }}

• -1
• 全 0
• 较大的正数
• 随机数

第 11 题（单选）

如果一个算法使用三重循环枚举 i、j、k，且每一层循环规模都约为 n，它的时间复杂度通常是（）。

{{ select(11) }}

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

第 12 题（单选）

对 n 个点、m 条边的非负权图使用堆优化 Dijkstra，时间复杂度通常是（）。

{{ select(12) }}

• O(n^3)
• O((n+m)log n)
• O(2^n)
• O(nm)

第 13 题（单选）

读题时先看数据范围，有助于判断简单做法能否通过。

{{ select(13) }}

• 矩阵乘法
• DFS 深度
• 排序边
• 读入点权

第 14 题（单选）

用邻接表遍历一张 n 点 m 边的图，时间复杂度通常是（）。

{{ select(14) }}

• O(2^n)
• O(n+m)
• O(n^2m)
• O(nm)

第 15 题（单选）

树链剖分将树上路径拆成若干重链段，单次路径操作一般拆成（）段级别。

{{ select(15) }}

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

第 16 题（单选）

当同一批数据要回答很多次查询时，先整理辅助信息通常能减少重复计算。

{{ select(16) }}

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

第 17 题（单选）

根据常见定义，一个有向图的强连通分量缩点后得到的图一定是（）。

{{ select(17) }}

• 二分图
• 完全图
• 树
• DAG

第 18 题（单选）

根据常见定义，Tarjan 求强连通分量时，low[u] 更准确地表示（）。

{{ select(18) }}

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

第 19 题（单选）

根据常见定义，无向图的割点是指删除该点后（）。

{{ select(19) }}

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

第 20 题（单选）

根据常见定义，桥是指无向图中删除后会使（）。

{{ select(20) }}

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

第 21 题（单选）

处理无权图最短步数问题时，BFS 往往比盲目深搜更合适。

{{ select(21) }}

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

第 22 题（单选）

根据常见定义，最小生成树一定满足的性质是（）。

{{ select(22) }}

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

第 23 题（单选）

根据常见定义，若图不连通，则最小生成树（）。

{{ select(23) }}

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

第 24 题（单选）

在二分图最大匹配中，如果增广路算法找到一条增广路，匹配数会（）。

{{ select(24) }}

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

第 25 题（单选）

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

{{ select(25) }}

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

第 26 题（单选）

做课堂小测时，在无权图中按边数一层层扩展，通常会使用广度优先搜索。

{{ select(26) }}

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

第 27 题（单选）

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

{{ select(27) }}

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

第 28 题（单选）

根据常见定义，对有根树做 DFS，tin[u] 是进入 u 时的时间戳，sz[u] 是 u 的子树大小。按进入顺序将节点展平后，u 的子树对应（）。

{{ select(28) }}

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

第 29 题（单选）

在程序阅读题中，写 DP 程序时，循环顺序要和状态转移关系相匹配。

{{ select(29) }}

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

第 30 题（单选）

根据常见定义，有向图包含边 s→a（权 2）、s→b（权 5）、b→a（权 -10）。若直接使用标准 Dijkstra，最主要的问题是（）。

{{ select(30) }}

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

第 31 题（多选）

关于 DAG 与拓扑序，判断正确的有（）。

{{ multiselect(31) }}

• 拓扑排序过程也可用于发现有向环
• 有向图存在覆盖全部顶点的拓扑序当且仅当它是 DAG
• 有环时不存在完整拓扑序
• 任意无向图都有拓扑序

第 32 题（多选）

关于 LCA，判断正确的有（）。

{{ multiselect(32) }}

• 欧拉序 + RMQ 可求 LCA
• LCA 只在二叉树中有定义
• LCA 是最近公共祖先
• 倍增可求 LCA

第 33 题（多选）

关于可撤销并查集，判断正确的有（）。

{{ multiselect(33) }}

• 通常避免普通路径压缩
• 常用于离线分治动态图
• 天然支持任意在线删边且无需额外结构
• 通常记录修改栈

第 34 题（多选）

广度优先搜索会先访问离起点更近的一层节点。

{{ multiselect(34) }}

• 使用双端队列
• 适合任意负权图
• 适合边权为 0 或 1 的最短路
• 一定比 Dijkstra 适用范围更广

第 35 题（多选）

关于 C++ sort 的比较函数，下列说法正确的有（）。

{{ multiselect(35) }}

• 若比较器不合法，排序结果不可依赖
• 应满足严格弱序
• 相等元素时 cmp(a,b) 与 cmp(b,a) 均应为 false
• 可以依赖随机数改变比较结果

第 36 题（多选）

关于整数溢出和取模，判断正确的有（）。

{{ multiselect(36) }}

• 可用 __int128 承接大整数乘法中间结果
• long long 也可能溢出
• 两个余数相乘一定不会溢出
• signed int 溢出是未定义行为

第 37 题（多选）

关于矩阵快速幂，判断正确的有（）。

{{ multiselect(37) }}

• 维度不匹配也能相乘
• 使用二进制快速幂思想
• 矩阵乘法一般满足交换律
• 可优化线性递推

第 38 题（多选）

关于 STL 迭代器失效，判断正确的有（）。

{{ multiselect(38) }}

• set 插入通常不影响已有元素迭代器
• 所有容器插入都会使全部迭代器失效
• erase 被删元素的迭代器失效
• vector 扩容可能使迭代器失效

第 39 题（多选）

关于 Tarjan 求 SCC，判断正确的有（）。

{{ multiselect(39) }}

• 当 low[u]==dfn[u] 时，u 是一个 SCC 的根并弹栈直到 u
• dfn[u] 是 DFS 访问时间戳
• 每个点会属于多个 SCC
• low[u] 反映从 u 可追溯到的最小 dfn

第 40 题（多选）

关于网络流，判断正确的有（）。

{{ multiselect(40) }}

• 残量网络表示仍可调整的容量
• 增广路只能在树上寻找
• 最大流值等于最小割容量
• 反向边用于撤销或调整已有流量

第 41 题（判断）

请判断下列说法是否正确：强连通分量缩点后一定是 DAG。（）

{{ select(41) }}

• 正确
• 错误

第 42 题（判断）

请判断下列说法是否正确：树链剖分可以把树上路径拆成 O(log n) 个重链区间。（）

{{ select(42) }}

• 正确
• 错误

第 43 题（判断）

请判断下列说法是否正确：可撤销并查集通常避免普通路径压缩。（）

{{ select(43) }}

• 正确
• 错误

第 44 题（判断）

请判断下列说法是否正确：残量网络只包含原图中未被使用过的边。（）

{{ select(44) }}

• 正确
• 错误

第 45 题（判断）

请判断下列说法是否正确：二分图最大匹配中的一条增广路会使匹配数减少 1。（）

{{ select(45) }}

• 正确
• 错误

第 46 题（判断）

请判断下列说法是否正确：树上差分常用于批量统计路径贡献。（）

{{ select(46) }}

• 正确
• 错误

第 47 题（判断）

在 C++ 中，std::sort 的比较函数可以不满足严格弱序。（）

{{ select(47) }}

• 正确
• 错误

第 48 题（判断）

在 C++ 中，signed int 溢出在 C++ 标准中是良定义的按模回绕。（）

{{ select(48) }}

• 正确
• 错误

第 49 题（判断）

请判断下列说法是否正确：NTT 可以在合适质数模数下做卷积并避免 FFT 的浮点误差。（）

{{ select(49) }}

• 正确
• 错误

第 50 题（判断）

1LL * x * y 可以避免 x * y 先以 int 计算而溢出。

{{ select(50) }}

• 正确
• 错误