选择题

1. （2分）在有向图的邻接表表示中，每个顶点的出边链表存储的是？{{ select(1) }}

• 所有指向该顶点的边
• 所有从该顶点出发的边
• 所有与该顶点相关联的边
• 所有权值大于0的边

2. （2分）以下哪种算法可用于求解带权有向图的单源最短路径问题？{{ select(2) }}

• Kruskal算法
• Prim算法
• Dijkstra算法
• Floyd-Warshall算法

3. （2分）一个具有n个顶点的有向完全图有多少条边？{{ select(3) }}

• n(n-1)/2
• n(n-1)
• n^2
• 2n(n-1)

4. （2分）图的广度优先遍历（BFS）通常使用哪种数据结构实现？{{ select(4) }}

• 栈
• 队列
• 哈希表
• 二叉树

5. （2分）以下哪个不是判断有向图是否存在环的方法？{{ select(5) }}

• 深度优先搜索
• 拓扑排序
• 广度优先搜索
• 并查集

6. （2分）在无向图中，若从顶点A到顶点B有路径，则称A和B是？{{ select(6) }}

• 连通的
• 强连通的
• 关联的
• 邻接的

7. （2分）邻接表表示法中，查找一个顶点的所有邻接顶点的时间复杂度是？{{ select(7) }}

• O(1)
• O(n)
• O(n+e)
• O(e)

8. （2分）以下哪种图的遍历算法可以产生最小生成树？{{ select(8) }}

• DFS
• BFS
• Prim算法
• 拓扑排序

9. （2分）在有向图中，如果两个顶点之间可以互相到达，则称这两个顶点是？{{ select(9) }}

• 连通的
• 强连通的
• 关联的
• 邻接的

10. （2分）拓扑排序的结果具有什么特点？{{ select(10) }}

• 每个顶点的所有前驱都出现在该顶点之前
• 每个顶点的所有后继都出现在该顶点之前
• 顶点按度数从小到大排列
• 顶点按度数从大到小排列

11. （2分）Floyd-Warshall算法主要用于解决什么问题？{{ select(11) }}

• 单源最短路径
• 多源最短路径
• 最小生成树
• 拓扑排序

12. （2分）以下哪种图一定是连通图？{{ select(12) }}

• 有向图
• 无向图
• 树
• 有向无环图

13. （2分）在图的邻接矩阵表示中，空间复杂度是？{{ select(13) }}

• O(n)
• O(e)
• O(n+e)
• O(n^2)

14. （2分）以下哪个算法不是基于贪心思想的？{{ select(14) }}

• Kruskal算法
• Prim算法
• Dijkstra算法
• Floyd-Warshall算法

15. （2分）在无向图中，所有顶点的度数之和等于？{{ select(15) }}

• 边数
• 边数的2倍
• 顶点数
• 顶点数的2倍