工学

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

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

逆拓扑有序

B

拓扑有序

C

无序

D

深度优先遍历序列

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

下列说法正确的是【】

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次

B．遍历的基本算法有两种：深度遍历和广度遍历

C．图的深度遍历不适用于有向图

D．图的深度遍历是一个递归过程


正确答案：ABD
[解析]图的深度遍历既适用于有向图也适用于无向图．

第2题：

采用邻接表存储的图的深度优先遍历算法类似于树的(22)，用邻接表存储的图的广度优先遍历算法类似于树的(23)，判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用(24)。

A．中序遍历

B．先序遍历

C．后序遍历

D．按层次遍历


正确答案：B
解析：采用邻接表存储的图的深度优先遍历算法类似于树的先序遍历。

第3题：

若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点,则 该图一定是连通图。()

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


正确答案：对

第4题：

下列说法不正确的是()。

A.图的遍历是从给定的源点出发每一个顶点仅被访问一次

B.图的深度遍历不适用于有向图

C.遍历的基本算法有两种：深度遍历和广度遍历

D.图的深度遍历是一个递归过程


正确答案：C

第5题：

对于无向图来说,若深度优先遍历过程中遇到回边(即指向已访问过的顶点的边),则必定存在环。()

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


正确答案：√

第6题：

一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。


参考答案：
　　[算法描述]
　　Void DFSn(Graph G,int v)
　　{ //从第v个顶点出发非递归实现深度优先遍历图G
　　Stack s;
　　SetEmpty(s);
　　Push(s,v);
　　While(!StackEmpty(s))
　　{ //栈空时第v个顶点所在的连通分量已遍历完
　　Pop(s,k);
　　If(!visited[k])
　　{ visited[k]=TRUE;
　　VisitFunc(k); //访问第k个顶点
　　//将第k个顶点的所有邻接点进栈
　　for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w))
　　{
　　if(!visited[w]&&w!=GetTop(s)) Push(s,w); //图中有环时w==GetTop(s)
　　}
　　}
　　}

第7题：

对图分别进行深度优先遍历和广度优先遍历,得到的顶点访问序列________。

A、一定相同

B、一定不同

C、不一定相同

D、可能相同


参考答案：CD

第8题：

对于有向图,其邻接矩阵表示相比邻接表表示更易于进行的操作为( )。

A. 求一个顶点的邻接点

B. 求一个顶点的度

C. 深度优先遍历

D. 广度优先遍历


参考答案：B

第9题：

若从无向图的一个顶点出发进行深度优先遍历可访问到图中所有顶点,则该图一定是连通图。()

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


参考答案：正确

第10题：

● 对连通图进行遍历前设置所有顶点的访问标志为 false（未被访问） ，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true（已访问） ，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。 （40） 是下图的深度优先遍历序列。

（40）

A. 1 2 3 4 6 5

B. 1 2 6 3 4 5

C. 1 6 2 5 4 3

D. 1 2 3 4 5 6


正确答案：A

更多相关问题
相关内容