工学
填空题若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的（）遍历。
题目
参考答案和解析
相似问题和答案
第1题：
●具有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)
【解析】不论是深度优先还是广度优先搜索遍历，图中n个顶点都必须被访问一次。从某个顶点出发，要搜索到其他顶点，必须沿着图中的边去找。用邻接矩阵做图的存储结构时，这些边是分布在一个n阶方阵中，要检测出这些边，必须对矩阵中n2个元素进行检测，因此，其时间复杂度为O(n2)。若用邻接表作为存储结构，只需对代表e条无向边的2e个边表结点进行检测，其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号，每个顶点都要进栈一次，故 n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号，每个顶点都要进队一次，故队列长度为n，所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。
第2题：
采用邻接表存储的图的深度优先遍历算法类似于二叉树的()。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
第3题：
●采用邻接表存储的图的深度优先遍历算法类似于二叉树的 (57) 。
(57) A．中序遍历
B．前序遍历
C．后序遍历
D．按层遍历
【解析】图的深度优先遍历即纵向优先遍历，类似于二叉树的前序遍历。
第4题：
A.先序遍历
B.中序遍历
C.后序遍历
D.层序遍历
第5题：
邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的(38)。
A．先序遍历
B．中序遍历
C．后序遍历
D．按层遍历
解析：图的深度优先遍历是从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通道顶点都被访问到；如果此时还有顶点没有被访问，则另选图中一个未访问道顶点作起始点，重复以上过程，直到图中所有顶点都被访问。
第6题：
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
第7题：
采用邻接表存储的图的广度优先遍历算法类似于二叉树的()。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
第8题：
●采用邻接表存储的图的广度优先遍历算法类似于二叉树的 (58) 。
(58) A．中序遍历
B．前序遍历
C．后序遍历
D．按层遍历
【解析】图的广度优先遍历即横向优先遍历，类似于二叉树的按层遍历。
第9题：
采用邻接表存储的图的深度优先遍历算法类似于树的(22)，用邻接表存储的图的广度优先遍历算法类似于树的(23)，判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用(24)。
A．中序遍历
B．先序遍历
C．后序遍历
D．按层次遍历
解析：采用邻接表存储的图的深度优先遍历算法类似于树的先序遍历。
第10题：
● 具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为 （63） 。
