已知无向图G的邻接表如下图所示，分别写出从顶点1出发的深度遍历和广度遍历序列..._考试资料网

网站首页考试题库模拟考场智能家居网课试题

大学试题

题库首页每日一练章节练习

问答题 已知无向图G的邻接表如下图所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相应的生成树。

参考答案：

深度优先遍历序列为：1，2，3，4，5，6
对应的生成树为：

广度优先遍历序列为：1，2，4，3，5，6
对应的生成树为：

您可能感兴趣的试卷

你可能感兴趣的试题

1.单项选择题关键路径是AOE网中（）。

A.从源点到终点的最长路径
B.从源点到终点的最短路径
C.最长的回路
D.最短的回路

点击查看答案&解析

2.单项选择题用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。

A.逆拓扑有序
B.拓扑有序
C.无序
D.深度优先遍历序列

点击查看答案

3.单项选择题一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。

A.k
B.n
C.n-k
D.1

点击查看答案

4.填空题表示一个有100个顶点，1000条边的有向图的邻接矩阵有（）个非零矩阵元素。

参考答案：1000

5.单项选择题在一个具有n个顶点的有向完全图中包含有（）条边

A.n（n-1）/2
B.n（n-1）
C.n（n+1）/2
D.n2

点击查看答案

6.填空题十字链表适合存储（），邻接多重表适合存储（）。

参考答案：有向图；无向图

7.填空题无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）

参考答案：对称矩阵；无规律

8.单项选择题 某无向图的邻接矩阵A=，可以看出，该图共有（）个顶点。

A.3
B.6
C.9
D.以上答案均不正确

点击查看答案

9.问答题分别基于深度优先搜索和广度优先搜索编写算法，判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。

参考答案：

⑴基于深度优先遍历：

⑵基于广度优先遍历：

10.问答题已知一个有向图的邻接表，编写算法建立其逆邻接表。

参考答案：在有向图中，若邻接表中顶点vi有邻接点vj，在逆邻接表中vj一定有邻接点vi，由此得到本题算法思路：首先将逆邻接表的表头...

点击查看完整答案