选择题

1. （2分）在一个无向图中，所有顶点的度数之和等于边数的多少倍？{{ select(1) }}

• 1
• 2
• 3
• 4

2. （2分）以下哪种图的存储结构最适合用于稠密图？{{ select(2) }}

• 邻接表
• 邻接矩阵
• 十字链表
• 邻接多重表

3. （2分）在图的深度优先遍历中，通常使用哪种数据结构来存储访问路径？{{ select(3) }}

• 队列
• 栈
• 链表
• 数组

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

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

5. （2分）一个有n个顶点的无向连通图，至少需要多少条边才能保证其连通性？{{ select(5) }}

• n-1
• n
• n+1
• 2n-1

6. （2分）在拓扑排序中，以下哪种图一定不存在拓扑序列？{{ select(6) }}

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

7. （2分）以下哪种算法用于寻找图的最小生成树？{{ select(7) }}

• Dijkstra算法
• BFS算法
• Kruskal算法
• Floyd算法

8. （2分）在有向图中，每个顶点的入度是指什么？{{ select(8) }}

• 以该顶点为起点的边的数目
• 以该顶点为终点的边的数目
• 与该顶点相关联的边的数目
• 该顶点的度数

9. （2分）使用邻接表存储一个有n个顶点和e条边的无向图，需要多少存储空间？{{ select(9) }}

• O(n)
• O(e)
• O(n+e)
• O(n*e)

10. （2分）以下哪种图遍历算法可以用于检测图中是否存在环？{{ select(10) }}

• BFS
• DFS
• 拓扑排序
• 以上都可以

11. （2分）在一个有向图中，如果从顶点u到顶点v有路径，且从顶点v到顶点u也有路径，则称u和v处于什么关系？{{ select(11) }}

• 连通
• 强连通
• 弱连通
• 不连通

12. （2分）以下哪种数据结构不适用于存储图？{{ select(12) }}

• 数组
• 链表
• 栈
• 哈希表

13. （2分）在无向图中，如果从一个顶点出发进行深度优先遍历，能够访问到所有顶点，则该图是什么图？{{ select(13) }}

• 连通图
• 强连通图
• 有向图
• 完全图

14. （2分）以下哪种算法的时间复杂度为O(n^3)？{{ select(14) }}

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

15. （2分）在图论中，以下哪项不是图的基本要素？{{ select(15) }}

• 顶点
• 边
• 权重
• 深度