遍历图的基本方法有深度优先搜索和广度优先搜索，其中（）是一个递归过程。

题目

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

图的()优先搜索遍历算法是一种递归算法,图的()优先搜索遍历算法需要使用队列。

参考答案：深度;广度

第2题：

具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

A．O(n2)

B．O(n)

C．O(n-1)

D．O(n+1)

正确答案：A

第3题：

●具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为 (48) ；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为 (49) ；深度优先或广度优先搜索遍历的空间复杂度为 (50) 。

(48) ,(50) A．O(n2)

B．O(n)

C．O(n-1)

D．O(n+1)

(49) A．O(e)

B．O(e-1)

C．O(e2)

D．O(e+10)

正确答案：A,A,B
【解析】不论是深度优先还是广度优先搜索遍历，图中n个顶点都必须被访问一次。从某个顶点出发，要搜索到其他顶点，必须沿着图中的边去找。用邻接矩阵做图的存储结构时，这些边是分布在一个n阶方阵中，要检测出这些边，必须对矩阵中n²个元素进行检测，因此，其时间复杂度为O(n²)。若用邻接表作为存储结构，只需对代表e条无向边的2e个边表结点进行检测，其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号，每个顶点都要进栈一次，故 n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号，每个顶点都要进队一次，故队列长度为n，所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。

第4题：

图的深度优先搜索和广度优先搜索序列不一定是唯一的。

A对

B错

对
略

第5题：

下面关于图的遍历说法不正确的是()。

A.遍历图的过程实质上是对每个顶点查找其邻接点的过程
B.深度优先搜索和广度优先搜索对无向图和有向图都适用
C.深度优先搜索和广度优先搜索对顶点访问的顺序不同，它们的时间复杂度也不相同
D.深度优先搜索是一个递归的过程，广度优先搜索的过程中需附设队列

答案：C

解析：

深度优先搜索和广度优先搜索的时间算杂度相同，均为O(n+e)。

第6题：

图的遍历算法有深度优先搜索算法和广度优先搜索算法。()

此题为判断题(对，错)。

正确答案：√

第7题：

下列说法中不正确的是（）。

A.图的遍历过程中每一顶点仅被访问一次
B.遍历图的基本方法有深度优先搜索和广度优先搜索两种
C.图的深度优先搜索的方法不适用于有向图
D.图的深度优先搜索是一个递归过程

答案：C

解析：

图的深度优先搜索的方法对于有向图和无向图都适用。

第8题：

图的遍历有()。

A、广度优先搜索遍历

B、深度优先搜索遍历

C、前序遍历

D、后序遍历

正确答案:A,B

第9题：

执行（）操作时，需要使用队列作为辅助空间。

A.前序遍历二叉树
B.深度优先搜索图
C.广度优先搜索图
D.查找哈希表

答案：C

解析：

广度优先搜索图类似于对二叉树进行层次遍历，需要借助队列实现。

第10题：

图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是（）的。（回答正确或不正确）
正确
略

遍历图的基本方法有深度优先搜索和广度优先搜索，其中（）是一个递归

题目

相似问题和答案

更多相关问题

相关内容