图论专题训练001
选择题
- （2分）在一个无向图中，所有顶点的度数之和等于边数的多少倍？{{ select(1) }}
- A. 1/2
- B. 1
- C. 2
- D. 4
- （2分）以下哪种图的存储结构更适合表示稀疏图？{{ select(2) }}
- A. 邻接矩阵
- B. 邻接表
- C. 关联矩阵
- D. 十字链表
- （2分）图的深度优先遍历（DFS）通常使用哪种数据结构实现？{{ select(3) }}
- A. 队列
- B. 栈
- C. 链表
- D. 数组
- （2分）在有向图中，所有顶点的入度之和与出度之和的关系是？{{ select(4) }}
- A. 入度之和大于出度之和
- B. 入度之和小于出度之和
- C. 相等
- D. 无法确定
- （2分）以下哪个算法可以用于判断无向图是否存在环？{{ select(5) }}
- A. Dijkstra算法
- B. 拓扑排序
- C. 深度优先搜索
- D. Floyd-Warshall算法
- （2分）一个具有n个顶点的完全无向图有多少条边？{{ select(6) }}
- A. n
- B. n-1
- C. n(n-1)
- D. n(n-1)/2
- （2分）邻接矩阵表示法中，查找两个顶点之间是否存在边的时间复杂度是？{{ select(7) }}
- A. O(1)
- B. O(n)
- C. O(n^2)
- D. O(log n)
- （2分）广度优先遍历（BFS）可以用来解决以下哪个问题？{{ select(8) }}
- A. 最短路径（无权图）
- B. 拓扑排序
- C. 关键路径
- D. 最小生成树
- （2分）以下哪种图一定不存在回路？{{ select(9) }}
- A. 有向图
- B. 无向图
- C. 树
- D. 完全图
- （2分）在有向图的拓扑排序中，以下说法正确的是？{{ select(10) }}
- A. 拓扑排序结果唯一
- B. 只有有向无环图才有拓扑排序
- C. 拓扑排序可以用栈实现，但不能用队列
- D. 拓扑排序中，每个顶点的所有前驱都出现在该顶点之后
- （2分）Flood Fill算法主要用于解决什么问题？{{ select(11) }}
- A. 最短路径查找
- B. 连通区域标记
- C. 拓扑排序
- D. 最小生成树构建
- （2分）一个图如果存在欧拉回路，则必须满足什么条件？{{ select(12) }}
- A. 所有顶点的度数都是偶数
- B. 有且仅有两个顶点度数为奇数
- C. 图是连通的且所有顶点度数为偶数
- D. 图是有向图
- （2分）以下哪种数据结构不适用于存储图的邻接关系？{{ select(13) }}
- A. 数组
- B. 链表
- C. 哈希表
- D. 栈
- （2分）在无向图中，连通分量指的是？{{ select(14) }}
- A. 图中所有顶点的集合
- B. 图中极大的连通子图
- C. 图中极小的连通子图
- D. 图中任意两个顶点之间的路径
- （2分）以下哪个算法不是图的遍历算法？{{ select(15) }}
- A. DFS
- B. BFS
- C. Kruskal
- D. 深度优先搜索