对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历，时间复杂度为______。

admin2019-10-08 46

问题对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历，时间复杂度为______。

选项 A、O(n²)
B、O(e²)
C、O(n+e)
D、O(n^*e)

答案A

解析图的邻接矩阵是指用一个矩阵来表示图中顶点之间的关系。对有n个结点的图，其邻接矩阵是一个n阶方阵。对于无向图来说，其邻接矩阵如下图所示：

当采用深度优先进行遍历的时候，查找所有邻接点所需要的时间是O(n²)。

转载请注明原文地址:https://kaotiyun.com/show/hUCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

阅读以下说明和Java码，将应填入(n)处的字名写在的对应栏内。[说明]编写一个完整的JavaApplet程序使用复数类Complex验证两个复数1+2i和3+4i相加产生一个新的复数4+6i。复数类Complex必须满足如下要求
阅读下列算法说明和流程图1，回答问题1至问题3。[算法说明]某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(
阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。[说明]以下是某图像二元树存储与还原算法的主要思想描述。设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示
阅读以下某旅馆客房管理系统的算法说明和程序流程图，根据要求回答问题1～问题4。[算法说明]某旅馆共有N间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。
图7-13是对该IC卡加油机应用系统的基本流路径和备选流路径的描述，请用试题描述中的相应字母(见表7-15和表7-16)将图中(1)～(6)空缺处的内容填写完整。场景中的每一个场景都需要确定测试用例，一般采用矩阵或决策表来确定和管理测试用例。表7-1
The　purpose　of　the　requirements　definition　phase　is　to　produce　a　clear,　complete,　consistent,　and　testable(71　)of　the　technical　
In　the　open　systems　interconnection(OSI)reference　model,　"layer"　means　one　of　seven　conceptually　complete,(71)arranged　groups
The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a
The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control

随机试题

常见的PCI总线属于
A．Ⅻ因子B．X因子C．Ⅷ因子D．Ⅲ因子E．Ⅳ因子内外源凝血系统共同激活因子
A．责令停产、停业整顿，并处5千元以上2万元以下的罚款B．处2万元以上10万元以下的罚款C．处1万元以上3万元以下的罚款D．处违法生产的药品货值金额2倍以上5倍以下的罚款E．处违法生产的药品货值金额1倍以上3倍以下的罚款未取得《药品生产
“进口口岸”栏应填()。“境内目的地”栏应填()。
以下说法正确的是(　　)。
审计机关审理机构的工作职责有()。
依据我国宪法规定，下列()由全国人民代表大会选举产生。
计算二重积分｜x2+y2一1｜dσ，其中D={(x，y)｜0≤x≤1，0≤y≤1}。
设f(x)是连续函数，F(x)是f(x)的原函数，则
在下列有关Windows98安装与启动的叙述中，错误的是

最新回复(0)

对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历，时间复杂度为______。

软件设计师上午基础知识考试

软考中级

阅读以下说明和Java码，将应填入(n)处的字名写在的对应栏内。[说明]编写一个完整的JavaApplet程序使用复数类Complex验证两个复数1+2i和3+4i相加产生一个新的复数4+6i。复数类Complex必须满足如下要求

阅读下列算法说明和流程图1，回答问题1至问题3。[算法说明]某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(

The purpose of the requirements definition phase is to produce a clear, complete, consistent, and testable(71 )of the technical

In the open systems interconnection(OSI)reference model, "layer" means one of seven conceptually complete,(71)arranged groups

The notion of NP-completeness has provided a(66)mathematical definition for(67)intractability of NP problems. But this measure a

The program memory serves basically as a place(66)instructions, the coded pieces of data(67)direct the activities of the control

常见的PCI总线属于

A．Ⅻ因子B．X因子C．Ⅷ因子D．Ⅲ因子E．Ⅳ因子内外源凝血系统共同激活因子

“进口口岸”栏应填()。“境内目的地”栏应填()。

以下说法正确的是( )。

审计机关审理机构的工作职责有()。

依据我国宪法规定，下列()由全国人民代表大会选举产生。

计算二重积分｜x2+y2一1｜dσ，其中D={(x，y)｜0≤x≤1，0≤y≤1}。

设f(x)是连续函数，F(x)是f(x)的原函数，则

在下列有关Windows98安装与启动的叙述中，错误的是

The　purpose　of　the　requirements　definition　phase　is　to　produce　a　clear,　complete,　consistent,　and　testable(71　)of　the　technical　

In　the　open　systems　interconnection(OSI)reference　model,　"layer"　means　one　of　seven　conceptually　complete,(71)arranged　groups

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a

The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control

以下说法正确的是(　　)。