初赛模拟卷 A（2）

第 1 题（单选）

若 vector v={1,2,3,4}; 执行 v.erase(v.begin()+1); 后，v 中元素依次为（）。

{{ select(1) }}

• 2,3,4
• 1,3,4
• 1,2,4
• 1,2,3

第 2 题（单选）

计算 (a*b)%mod，a,b 可达 10^9，mod 可达 10^9+7。为避免 int 乘法先溢出，常写成（）。

{{ select(2) }}

• 1LLab%mod
• a/mod*b
• a*b%mod
• (a%mod)*(b%mod)%mod 且使用 int

第 3 题（单选）

若二分答案的判定 check(x) 满足 x 越大越容易可行，寻找最小可行 x 时，check(mid) 为真通常应（）。

{{ select(3) }}

• 记录 mid 并尝试更小答案
• 交换数组元素
• 舍弃左半边并增大左端点
• 立即输出 mid

第 4 题（单选）

完全背包一维优化时，同一物品可重复选择，容量通常（）。

{{ select(4) }}

• 不能使用一维数组
• 从大到小枚举
• 只能随机枚举
• 从小到大枚举

第 5 题（单选）

用邻接表存储含 n 个点、m 条边的稀疏图，空间通常为（）。

{{ select(5) }}

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

第 6 题（单选）

DFS 枚举图中从 s 到 t 的所有简单路径时，若进入 v 前执行 vis[v]=true，递归返回后却没有恢复 vis[v]=false，则（）。

{{ select(6) }}

• 只会导致路径顺序改变，不影响结果
• 可能把其他分支中本应可用的节点仍视为已访问，从而漏解
• 会自动把 DFS 变成 BFS
• 只要图无环就一定没有影响

第 7 题（单选）

现代 C++ 标准库 std::sort 对 n 个元素排序时，比较次数复杂度保证为（）。

{{ select(7) }}

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

第 8 题（单选）

对 n=2×10^5、m=4×10^5 的非负权稀疏图求单源最短路，采用邻接表和二叉堆 Dijkstra，时间复杂度通常是（）。

{{ select(8) }}

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

第 9 题（单选）

归并排序的典型时间复杂度是（）。

{{ select(9) }}

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

第 10 题（单选）

枚举 n 个不同元素的所有排列，数量是（）。

{{ select(10) }}

• n!
• log n
• 2^n
• n^2

第 11 题（单选）

栈 stack 的出入规则是（）。

{{ select(11) }}

• 先进先出
• 随机访问
• 按值排序
• 后进先出

第 12 题（单选）

树状数组最常见的用途是（）。

{{ select(12) }}

• 求所有排列
• 实现递归
• 维护前缀和并支持单点修改
• 存储字符串

第 13 题（单选）

multiset 与 set 的主要区别是（）。

{{ select(13) }}

• set 允许重复元素
• multiset 允许重复元素
• set 只能存 int
• multiset 无法排序

第 14 题（单选）

邻接矩阵查询两点是否有边的时间复杂度是（）。

{{ select(14) }}

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

第 15 题（单选）

bitset 可以较方便地表示（）。

{{ select(15) }}

• 8 个字符串
• 8 个函数
• 8 条边的权值
• 8 位二进制状态

第 16 题（单选）

BFS 在无权图中从源点出发，第一次到达某点时得到的是（）。

{{ select(16) }}

• 随机路径
• 最长路径
• 最小生成树权值
• 最短边数距离

第 17 题（单选）

若拓扑排序后得到的点数少于 n，说明图中（）。

{{ select(17) }}

• 没有边
• 一定不连通
• 所有边权为负
• 存在有向环

第 18 题（单选）

树上任意两个点之间简单路径的条数是（）。

{{ select(18) }}

• 2
• 不确定
• 0
• 1

第 19 题（单选）

在矩阵中四方向移动，BFS 中每个格子最多入队一次时复杂度为（）。

{{ select(19) }}

• O(2^格子数)
• O(行数+列数)
• O(格子数^2)
• O(格子数)

第 20 题（单选）

若图用邻接表存储，遍历所有点和边的复杂度通常是（）。

{{ select(20) }}

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

第 21 题（单选）

动态规划适合的问题通常具有（）。

{{ select(21) }}

• 只能用浮点数
• 不能分解
• 完全随机性
• 最优子结构和重叠子问题

第 22 题（单选）

最长上升子序列通常简称（）。

{{ select(22) }}

• BFS
• LIS
• LCS
• MST

第 23 题（单选）

从左向右扫描并选择尽可能多的两两不相交闭区间，经典贪心策略是（）。

{{ select(23) }}

• 每次选结束最早的可选区间
• 随机选择
• 每次选最长区间
• 每次选起点最晚的可选区间

第 24 题（单选）

若字符串长度为 n，朴素枚举所有子串数量级是（）。

{{ select(24) }}

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

第 25 题（单选）

快速排序平均复杂度是（）。

{{ select(25) }}

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

第 26 题（单选）

若 a 能被 b 整除，则 a % b 的值是（）。

{{ select(26) }}

• a
• b
• 1
• 0

第 27 题（单选）

在模 mod 运算下，(x+y)%mod 等价于（）。

{{ select(27) }}

• x*y%mod
• x-y
• x+y+mod
• ((x%mod)+(y%mod))%mod

第 28 题（单选）

判断一个数是否为质数，试除到（）即可。

{{ select(28) }}

• n
• log n
• n/2
• sqrt(n)

第 29 题（单选）

在二进制状态压缩中，第 k 位为 1 常表示（）。

{{ select(29) }}

• 答案为 k
• 数组长度为 k
• 第 k 个元素被选中
• 循环结束

第 30 题（单选）

若一个图有 n 个点，则简单无向图最多有（）条边。

{{ select(30) }}

• n^2
• n
• n-1
• n(n-1)/2

第 31 题（多选）

关于 BFS，正确的有（）。

{{ multiselect(31) }}

• 常用队列实现
• 按层扩展
• 无权图中可求最少边数距离
• 可直接处理任意负权最短路

第 32 题（多选）

关于 set/map，正确的有（）。

{{ multiselect(32) }}

• operator[] 可能插入新键
• map 按键查找值
• set 的键唯一
• set 支持下标随机访问

第 33 题（多选）

关于树，正确的有（）。

{{ multiselect(33) }}

• n 个点的树有 n-1 条边
• 树连通且无环
• 任意两点简单路径唯一
• 树一定有 n 条边

第 34 题（多选）

关于 0/1 背包，正确的有（）。

{{ multiselect(34) }}

• 每件物品最多选一次
• 状态可表示容量限制下最优价值
• 一维优化通常倒序枚举容量
• 容量必须随机枚举

第 35 题（多选）

关于取模运算，正确的有（）。

{{ multiselect(35) }}

• 负数取模常需要规范到非负
• 乘法取模仍需注意中间溢出
• 加法可先取模再相加取模
• 模意义下除法总能直接用 /

第 36 题（多选）

关于邻接表，正确的有（）。

{{ multiselect(36) }}

• 遍历所有边方便
• 适合稀疏图
• 任意两点查边一定 O(1)
• 空间通常 O(n^2)

第 37 题（多选）

关于 lower_bound，正确的有（）。

{{ multiselect(37) }}

• 要求元素不能重复
• 返回第一个不小于目标的位置
• 能在无序区间保证语义
• 要求区间按比较规则分区/有序

第 38 题（多选）

关于质数，正确的有（）。

{{ multiselect(38) }}

• 2 是质数
• 合数没有小于等于平方根的因子
• 所有奇数都是质数
• 1 不是质数

第 39 题（多选）

关于空间复杂度，正确的有（）。

{{ multiselect(39) }}

• 递归调用栈要计入空间
• 数组大小会影响空间
• 只看输出文件大小
• 与算法无关

第 40 题（多选）

关于线段树，正确的有（）。

{{ multiselect(40) }}

• 不能处理动态修改
• 懒标记可优化区间修改
• 只能求前缀和
• 可维护可合并的区间信息

第 41 题（判断）

gcd(a,b)=1 表示 a 和 b 一定都是质数。（）

{{ select(41) }}

• 正确
• 错误

第 42 题（判断）

邻接矩阵的空间复杂度通常为 O(n+m)。（）

{{ select(42) }}

• 正确
• 错误

第 43 题（判断）

有向图存在覆盖全部顶点的拓扑序，当且仅当它是 DAG。（）

{{ select(43) }}

• 正确
• 错误

第 44 题（判断）

高精度整数问题只能用浮点数近似，不能用数组或字符串精确模拟。（）

{{ select(44) }}

• 正确
• 错误

第 45 题（判断）

邻接表适合稀疏图。（）

{{ select(45) }}

• 正确
• 错误

第 46 题（判断）

动态规划的状态定义会影响解法正确性。（）

{{ select(46) }}

• 正确
• 错误

第 47 题（判断）

DFS 和 BFS 都可以用于遍历图。（）

{{ select(47) }}

• 正确
• 错误

第 48 题（判断）

浮点数比较时要注意精度误差。（）

{{ select(48) }}

• 正确
• 错误

第 49 题（判断）

所有树都是二分图。（）

{{ select(49) }}

• 正确
• 错误

第 50 题（判断）

二分查找可以直接在任意无序数组上使用并保证正确。（）

{{ select(50) }}

• 正确
• 错误