图论·单选训练4

第 1 题（单选）

树的直径可以通过两次 DFS/BFS 求出，适用于（）。

{{ select(1) }}

• 字符串集合
• 含负环图
• 任意有向图
• 无权树或带非负边权树的相应距离遍历

第 2 题（单选）

一棵有 11 个节点的树中，删除节点 u 后各连通块大小为 5、3、2。关于 u 的判断正确的是（）。

{{ select(2) }}

• u 一定不是重心，因为仍有大小为 5 的连通块
• u 是重心，因为删除它后最大连通块大小不超过 11/2
• u 是叶节点，因为连通块数量为 3
• 无法判断，因为树的重心只能有一个

第 3 题（单选）

对有根树做 DFS，tin[u] 是进入 u 时的时间戳，sz[u] 是 u 的子树大小。按进入顺序将节点展平后，u 的子树对应（）。

{{ select(3) }}

• 任意一组不连续下标
• 只包含 tin[u] 一个位置
• 区间 [1,tin[u])
• 连续区间 [tin[u],tin[u]+sz[u]-1]

第 4 题（单选）

拓扑 DP 中，如果存在环，直接按拓扑序转移的问题是（）。

{{ select(4) }}

• 所有点入度为 0
• 复杂度变成 O(1)
• 答案一定为 0
• 没有合法拓扑序

第 5 题（单选）

有向图包含边 s→a（权 2）、s→b（权 5）、b→a（权 -10）。若直接使用标准 Dijkstra，最主要的问题是（）。

{{ select(5) }}

• 图中顶点数太少
• 负权边破坏了已弹出最短距离不可再改进的贪心前提
• 必须先求最小生成树
• 邻接表不能存负权边