第6章+图习题解答(严蔚敏版)1
需积分: 0 201 浏览量
2022-08-03
21:09:49
上传
评论
收藏 520KB PDF 举报
第 6 章 图
1．选择题
（1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。
A．1/2 B．1 C．2 D．4
答案：C
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
A．1/2 B．1 C．2 D．4
答案：B
解释：有向图所有顶点入度之和等于所有顶点出度之和。
（3）具有 n 个顶点的有向图最多有（ ）条边。
A．n B．n(n-1) C．n(n+1) D．n
2
答案：B
解释：有向图的边有方向之分，即为从 n 个顶点中选取 2 个顶点有序排列，结果为 n(n-1)。
（4）
n 个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。
A．n B．2(n-1) C．n/2 D．n
2
答案：B
（5）G 是一个非连通无向图，共有 28 条边，则该图至少有（ ）个顶点。
A．7 B．8 C．9 D．10
答案：C
解释：8 个顶点的无向图最多有 8*7/2=28 条边，再添加一个点即构成非连通无向图，故至
少有 9 个顶点。
（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则
该图一定是（ ）图。
A．非连通 B．连通 C．强连通 D．有向
答案：B
解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。
（7）下面（ ）算法适合构造一个稠密图 G 的最小生成树。
A． Prim 算法 B．Kruskal 算法 C．Floyd 算法 D．Dijkstra 算法
答案：A
解释：Prim 算法适合构造一个稠密图 G 的最小生成树，Kruskal 算法适合构造一个稀疏图 G
的最小生成树。
（8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。
A．栈 B. 队列 C. 树 D．图
答案：B
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
（9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。
A．栈 B. 队列 C. 树 D．图
答案：A
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
（10）深度优先遍历类似于二叉树的（ ）。
评论0