2025.06 东城提高班月测 - 题目详情 - 信创计划

ID: 1816

客观题

难度: 7

上传者:

管理员 (admin)

并查集的 路径压缩 优化主要作用是：
{{ select(1) }}

加快查找时的路径长度，降低后续查找时间
加快合并时的树高调整
减少存储的父节点数量
允许树结构循环

用并查集判断无向图是否有环，核心逻辑是：
{{ select(2) }}

遍历边时，若两顶点已连通则存在环
遍历边时，若两顶点未连通则合并
上述A和B结合
统计连通分量数量

并查集的 路径压缩 优化是在哪个操作中实现的？ {{ select(3) }}

仅Find操作
仅Union操作
Find和Union都可能
初始化时

Dijkstra算法不能正确处理含负权边的图，原因是：
{{ select(4) }}

贪心策略下，已确定的最短路径可能被后续负权边更新
优先队列无法存储负权值
负权边会导致队列溢出
无法初始化距离数组

用优先队列（堆）优化Dijkstra时，时间复杂度通常是： {{ select(5) }}

O(n²)
O(m log n)（m是边数，n是顶点数）
O(n log m)
O(mn)

Bellman-Ford算法检测负权环的条件是：
{{ select(6) }}

对某条边松弛次数≥n（n为顶点数）
距离数组无法再更新
优先队列为空
所有边都被处理n次

关于BF和Dijkstra的对比，正确的是：
{{ select(7) }}

BF只能处理有向图，Dijkstra可处理无向图
BF能处理负权边，Dijkstra默认不能
BF的时间复杂度一定比Dijkstra低
BF不需要初始化距离数组

SPFA是对Bellman-Ford的哪类优化？
{{ select(8) }}

空间优化，用队列存储待松弛顶点
时间优化，仅松弛可能更新的顶点
减少初始化次数
改用优先队列

SPFA判断负权环的常用方法是：
{{ select(9) }}

某个顶点的入队次数≥n
队列长度超过n
距离数组出现负数
松弛次数超过m

SPFA中，初始时队列通常放入：
{{ select(10) }}

所有顶点
起点
所有边的终点
随机顶点

在下列比赛中:

东城提高班 2025.06 月测