图论·多选训练10

第 1 题（多选）

关于 LCA，正确的有（）。

{{ multiselect(1) }}

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

第 2 题（多选）

关于最小生成树，正确的有（）。

{{ multiselect(2) }}

• 只能处理有向图
• MST 是最短路树
• 连通无向图的生成树有 n-1 条边
• Kruskal 常用并查集判环

第 3 题（多选）

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

{{ multiselect(3) }}

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

第 4 题（多选）

关于 lower_bound，正确的有（）。

{{ multiselect(4) }}

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

第 5 题（多选）

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

{{ multiselect(5) }}

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