第九章单元测试
- 一个有n个顶点和n条边的无向图一定是 ( )。
- 若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是 ( )。
- 以下关于图的存储结构的叙述中，正确的是（ ）。
- 对一个有n个顶点、e条边的图采用邻接表表示时，进行DFS遍历的时间复杂度为（ ）。
- 对一个有n个顶点、e条边的图采用邻接表表示时，进行BFS遍历的空间复杂度为（ ）。
- 一个无向连通图的最小生成树是唯一的。（ ）
- 用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树可能相同，也可能不同。（ ）
使用Dijkstra算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（ ）。
对下图进行拓扑排序，可得不同拓扑序列的个数是（ ）。
一个有向图G的邻接表存储如下图所示，从顶点1出发，对图G调用深度优先遍历所得顶点序列是（ ）。
设图的邻接矩阵A如下所示，各顶点的度依次是 ( )。
A:有环的
B:连通的
C:不连通的
D:无环的
答案:有环的
A:强连通图
B:有回路
C:一棵树
D:连通图
A:一个图的邻接矩阵表示唯一，邻接表表示不唯一
B:一个图的邻接矩阵表示不唯一，邻接表表示唯一
C:一个图的邻接矩阵表示唯一，邻接表表示唯一
D:一个图的邻接矩阵表示不唯一，邻接表表示不唯一
A:O(1)
B:O(n)
C:O(e)
D:O(n+ e)
A:O(e)
B:O(1)
C:O(n)
D:O(n+ e)
A:错 B:对
A:错 B:对
A:5, 2, 3, 6, 4 B:5, 2, 6, 3, 4 C:5, 2, 3, 4, 6 D:5, 2, 4, 3, 6
A:4 B:3 C:2 D:1
A:124563 B:124536 C:125436 D:362514
A:4, 4, 2, 2 B:1, 2, 1, 2 C:2, 2, 1, 1 D:3, 4, 2, 3
温馨提示支付 ￥3.00 元后可查看付费内容,请先翻页预览!
