初赛模拟卷 B（2）

第 1 题（单选）

map mp; 执行 mp["x"]++; 后，下列说法正确的是（）。

{{ select(1) }}

• mp["x"] 的值未定义
• mp["x"] 的值为 1
• mp 中仍没有键 x
• 程序必然编译失败

第 2 题（单选）

对无权图从源点求最少边数距离，最适合的算法是（）。

{{ select(2) }}

• 快速排序
• Kruskal
• BFS
• DFS 枚举所有路径

第 3 题（单选）

差分数组 d 中，对原数组区间 [l,r] 加 x，通常修改（）。

{{ select(3) }}

• d[l]-=x, d[r]-=x
• d[l]+=x, d[r+1]-=x
• 只修改 d[r]
• 修改所有 d[i]

第 4 题（单选）

Kruskal 求最小生成树时，通常按照（）处理边。

{{ select(4) }}

• 点编号从大到小
• 边权从小到大
• 随机顺序
• 输入顺序

第 5 题（单选）

stable_sort 相比 sort 额外保证（）。

{{ select(5) }}

• 复杂度一定 O(n)
• 相等关键字相对顺序不变
• 自动去重
• 只能降序

第 6 题（单选）

0/1 背包使用一维 dp，若对每件物品都把容量从小到大更新，则该物品的本轮新状态可能被再次使用，效果更接近（）。

{{ select(6) }}

• 多重源最短路
• 完全背包
• 区间动态规划
• 最小生成树

第 7 题（单选）

树上最大权独立集 DP 中，f[u][1] 表示选 u 时 u 子树的最优值。对 u 的子节点 v，f[u][1] 应累加（）。

{{ select(7) }}

• max(f[v][0],f[v][1])
• f[v][0]
• f[v][1]
• f[u][0]

第 8 题（单选）

稳定排序的含义是（）。

{{ select(8) }}

• 不能处理重复元素
• 不会超时
• 相等元素相对顺序不变
• 一定是 O(n)

第 9 题（单选）

贪心算法能正确的关键通常是能够证明（）。

{{ select(9) }}

• 局部最优一定可扩展为全局最优
• 所有状态都枚举
• 一定使用递归
• 代码最短

第 10 题（单选）

某算法最坏约进行 10^8 次包含整数除法和取模的操作。关于 1 秒内能否通过，最合理的判断是（）。

{{ select(10) }}

• 只取决于文件名
• 有较大风险，应结合机器、常数和编译优化判断
• 一定能通过
• 一定不能运行

第 11 题（单选）

并查集主要用于维护（）。

{{ select(11) }}

• 最短路径长度
• 动态连通块合并与查询
• 字符串字典序
• 数组区间最大值

第 12 题（单选）

哈希表 unordered_map 平均查找复杂度通常为（）。

{{ select(12) }}

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

第 13 题（单选）

若要维护一组数的当前最大值并频繁取出，常用（）。

{{ select(13) }}

• bitset
• string
• pair
• priority_queue

第 14 题（单选）

堆排序利用的数据结构主要是（）。

{{ select(14) }}

• 队列
• 堆
• 栈
• 并查集

第 15 题（单选）

若需要快速判断一个元素是否出现过，常用的数据结构不包括（）。

{{ select(15) }}

• bool 数组
• stack
• set
• unordered_set

第 16 题（单选）

有向无环图通常简称为（）。

{{ select(16) }}

• LCA
• BST
• DAG
• DSU

第 17 题（单选）

Kruskal 算法用于求（）。

{{ select(17) }}

• 最小生成树
• 拓扑序
• 强连通分量
• 最短路

第 18 题（单选）

若无向图有 n 个点、n-1 条边且连通，则它是（）。

{{ select(18) }}

• 树
• 二分图
• 有向图
• 完全图

第 19 题（单选）

有向图中入度为 0 的点在拓扑排序中通常（）。

{{ select(19) }}

• 不能处理
• 一定是终点
• 可以作为初始入队点
• 一定有自环

第 20 题（单选）

有根树中，根节点的父节点通常设为（）。

{{ select(20) }}

• 最大编号节点
• 自身或 0
• 随机点
• 最小叶子

第 21 题（单选）

一维优化 0/1 背包时，容量循环通常应（）。

{{ select(21) }}

• 只循环一次
• 从小到大
• 随机
• 从大到小

第 22 题（单选）

区间 DP 的状态常常写成 f[l][r]，表示（）。

{{ select(22) }}

• 后缀 [r,n]
• 点 l 到点 r 是否有边
• 前缀 [1,l]
• 区间 [l,r] 的答案

第 23 题（单选）

KMP 算法主要用于（）。

{{ select(23) }}

• 最小生成树
• 背包计数
• 字符串匹配
• 图染色

第 24 题（单选）

滑动窗维护区间和时，右端点右移表示（）。

{{ select(24) }}

• 加入新元素
• 删除左端元素
• 排序窗
• 清空窗

第 25 题（单选）

计数排序适合（）。

{{ select(25) }}

• 值域较小的整数排序
• 字符串最长公共前缀
• 图最短路
• 任意实数排序

第 26 题（单选）

若 gcd(a,b)=1，则 a 和 b 称为（）。

{{ select(26) }}

• 同余
• 同奇偶
• 互质
• 相等

第 27 题（单选）

表达式 x & -x 常用于取得（）。

{{ select(27) }}

• x 的最高位 1
• x 的相反数
• x 的最低位 1 所代表的值
• x 的位数

第 28 题（单选）

如果 a≡b (mod m)，则说明（）。

{{ select(28) }}

• a-b 能被 m 整除
• a*b= m
• a+b 能被 m 整除
• a 和 b 相等

第 29 题（单选）

把状态 s 的第 k 位设为 1，常用表达式是（）。

{{ select(29) }}

• s | (1 << k)
• s & (1 << k)
• s ^ (1 << k)
• ~(1 << k)

第 30 题（单选）

浮点数比较时通常不直接用 ==，主要因为（）。

{{ select(30) }}

• 浮点数不能输出
• == 不能编译
• 浮点运算有精度误差
• 浮点数不能加法

第 31 题（多选）

关于二分查找，正确的有（）。

{{ multiselect(31) }}

• 边界更新要避免死循环
• 可在完全无序数组保证正确
• 要求有序或判定单调
• 时间复杂度通常 O(log n)

第 32 题（多选）

关于前缀和与差分，正确的有（）。

{{ multiselect(32) }}

• 差分还原通常需要前缀累加
• 前缀和可直接支持任意动态图最短路
• 前缀和适合静态区间求和
• 差分适合批量区间加

第 33 题（多选）

关于拓扑序，正确的有（）。

{{ multiselect(33) }}

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

第 34 题（多选）

关于字符串算法，正确的有（）。

{{ multiselect(34) }}

• 朴素匹配最坏可能较慢
• 字符串不能用数组处理
• KMP 可用于模式匹配
• Trie 可维护前缀关系

第 35 题（多选）

关于动态规划，正确的有（）。

{{ multiselect(35) }}

• 状态定义影响正确性
• 一定不能优化空间
• 转移需覆盖所有情况
• 常利用重叠子问题

第 36 题（多选）

关于单调栈，正确的有（）。

{{ multiselect(36) }}

• 可求最近更大/更小元素
• 可直接求任意负权最短路
• 必须递归实现
• 每个元素常入栈出栈各一次

第 37 题（多选）

关于 long long，正确的有（）。

{{ multiselect(37) }}

• 也有固定范围，仍可能溢出
• 通常范围大于 int
• 一定比 int 更省内存
• 能表示任意大整数

第 38 题（多选）

关于图的度数，正确的有（）。

{{ multiselect(38) }}

• 无向图度数和为 m
• 有向图入度和等于出度和
• 树的度数和为 n-1
• 无向图度数和为 2m

第 39 题（多选）

关于 LCA，正确的有（）。

{{ multiselect(39) }}

• 表示最近公共祖先
• 等于两点路径最大边权
• 只在二叉树上存在
• 可用倍增预处理

第 40 题（多选）

关于二进制状态压缩，正确的有（）。

{{ multiselect(40) }}

• 1LL<<k 比 1<<k 更能避免 int 左移溢出
• 可用第 k 位表示第 k 个对象是否被选
• k 任意大都安全
• 位运算不能用于集合 DP

第 41 题（判断）

map 的键默认按顺序维护。（）

{{ select(41) }}

• 正确
• 错误

第 42 题（判断）

0/1 背包一维优化时容量通常从小到大枚举。（）

{{ select(42) }}

• 正确
• 错误

第 43 题（判断）

set 中不会出现两个相等的键。（）

{{ select(43) }}

• 正确
• 错误

第 44 题（判断）

std::sort 默认按降序排序。（）

{{ select(44) }}

• 正确
• 错误

第 45 题（判断）

无权图最短路可以用 BFS 求解。（）

{{ select(45) }}

• 正确
• 错误

第 46 题（判断）

BFS 通常用栈实现。（）

{{ select(46) }}

• 正确
• 错误

第 47 题（判断）

稳定排序会打乱相等关键字的相对顺序。（）

{{ select(47) }}

• 正确
• 错误

第 48 题（判断）

递归函数没有终止条件也一定能正常结束。（）

{{ select(48) }}

• 正确
• 错误

第 49 题（判断）

Dijkstra 标准算法可以直接处理任意负权边。（）

{{ select(49) }}

• 正确
• 错误

第 50 题（判断）

vector 的下标访问通常是 O(1)。（）

{{ select(50) }}

• 正确
• 错误