一、单项选择题（每题2分，共20分）

1、存储带权图的邻接矩阵，无边的位置应当赋值为？（） {{ select(1) }}

• 0
• 极大值（如99）
• 1
• -1

2、N个结点的有向连通图，邻接矩阵表示，至少有多少个非零元素？（） {{ select(2) }}

• N‑1
• N
• N+1
• N*N

3、关于图DFS遍历（访问全部结点），vis标记处理正确的是？（） {{ select(3) }}

• 递归返回时撤销vis标记
• 只标记起点，其他点不标记
• 每次进入函数重新置0
• 全程不撤销vis标记

4、使用DFS统计起点到终点的路径总方案数，回溯时vis操作是？（） {{ select(4) }}

• 不做任何处理
• 直接清空整个vis数组
• 撤销vis标记
• 把vis全部置1

5、BFS实现图的遍历，标记vis的正确时机是？（） {{ select(5) }}

• 入队的时候标记
• 出队的时候标记
• 找到终点才标记
• 输出结点时标记

6、BFS求解无权图起点到终点最短步数，队列元素需要保存？（） {{ select(6) }}

• 只有结点编号
• 整张邻接矩阵
• vis数组副本
• 结点编号+步数step

7、无向图欧拉回路存在的条件（前提图连通）？（） {{ select(7) }}

• 恰好2个奇点
• 全部结点度数为奇数
• 0个奇点
• 奇点数量大于2

8、无向图存在欧拉路径（非回路），下面说法正确的是？（） {{ select(8) }}

• 0个奇点，任意点做起点
• 2个奇点，一个为起点另一个为终点
• 奇点数目可以为3
• 不需要图连通

9、干扰者病毒（二分图判定），相邻未访问结点状态赋值正确的是？（） {{ select(9) }}

• a[i] = a[f]
• a[i] = 1 - a[f]
• a[i] = 0
• a[i] = 1

10、二分图判定BFS过程，若相邻已经访问结点与当前结点状态相同，则？（） {{ select(10) }}

• 继续循环
• 直接跳过这条边
• 该连通子图无解输出Impossible
• 修改状态继续运行

二、判断题（每题2分，共10分）

11、无向图存储到邻接矩阵，一条边需要对矩阵两个位置赋值。（） {{ select(11) }}

• 正确
• 错误

12、图的遍历目标是寻找特定终点；图的搜索目标是访问全部结点。（） {{ select(12) }}

• 正确
• 错误

13、DFS适合统计路径方案，BFS适合求无权图最短步数。（） {{ select(13) }}

• 正确
• 错误

14、七桥问题无法一笔画，原因是图中奇点数量为2。（） {{ select(14) }}

• 正确
• 错误

15、一张图含有多个互不连通子图，二分图判定时每个子图要单独处理。（） {{ select(15) }}

• 正确
• 错误