图论·单选训练3（2）

第 1 题（单选）

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

{{ select(1) }}

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

第 2 题（单选）

多组测试中重复使用全局邻接表 g 和 visited 数组。为避免上一组数据影响当前结果，每组开始时应（）。

{{ select(2) }}

• 只清空输出缓冲区
• 只重置边数 m，保留所有邻接表
• 按本组使用范围清空 g 并重置 visited 等状态
• 将所有边权加 1

第 3 题（单选）

若一个算法需要 O(n+m) 扫描图，n 通常表示点数，m 表示（）。

{{ select(3) }}

• 权值上限
• 边数
• 答案
• 递归深度

第 4 题（单选）

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

{{ select(4) }}

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

第 5 题（单选）

路径压缩和按秩合并常用于优化（）。

{{ select(5) }}

• 并查集
• 冒泡排序
• 深度优先搜索
• 二分查找