第 1 题

按给定邻接顺序，写出 dfs(1) 的输出，数字用一个空格分隔。

vector<int> g[5]={{},{2,3},{1,4},{1},{2}}; bool vis[5];
void dfs(int u){vis[u]=true;cout<<u<<' ';for(int v:g[u])if(!vis[v])dfs(v);} 
dfs(1);

{{ input(1) }}

第 2 题

DFS 的核心搜索方式是（ ）。

{{ select(2) }}

• 一层一层
• 一条路走到底再返回
• 每次取最小权值
• 区间减半

第 3 题

递归 DFS 最自然地对应（ ）。

{{ select(3) }}

• 队列
• 调用栈
• 邻接矩阵专用
• 二分

第 4 题

图有环而 DFS 不使用 visited，可能（ ）。

{{ select(4) }}

• 无限递归或重复访问
• 自动得到最短路
• 自动删除环
• 复杂度变为O(1)

第 5 题

以下程序中 cnt 最终表示什么？填写“可达顶点数”。

void dfs(int u){vis[u]=true;cnt++;for(int v:g[u])if(!vis[v])dfs(v);}

{{ input(5) }}

第 6 题

以下外层循环统计的 ans 是什么？填写“连通块数量”。

for(int i=1;i<=n;i++) if(!vis[i]){ans++;dfs(i);}

{{ input(6) }}

第 7 题

邻接表 DFS 的常见复杂度是（ ）。

{{ select(7) }}

• $O(n+m)$
• $O(n^2)$ 固定
• $O(\log n)$
• $O(1)$

第 8 题

DFS 访问顺序是否可能随邻接表邻居顺序改变？

{{ select(8) }}

• 可能
• 不可能