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

admin2019-10-08 57

问题对有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

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

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

软考中级

相关试题推荐

阅读以下说明，回答问题1～5，将解答填入对应的解答栏内。[说明]编写一个函数根据用户输入的偶对(以输入。表示结束)建立其有向图的邻接表。一个图的邻接表存储结构定义如下：#include＜stdio.h＞#defineMAX
阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。[说明]以下是某图像二元树存储与还原算法的主要思想描述。设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示
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
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　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

随机试题

外资企业所得税税率实行30%的比例税率，另按应纳税所得额征收3%的()。
某建筑企业与某房地产开发公司签订了一项合同税前造价为6000万元的施工合同，合同约定工期为3年。第1年实际发生合同成本1500万元，年末预计为完成合同尚需发生成本3500万元；第2年实际发生合同成本2100万元，年末预计为完成合同尚需发生成本1400万元。
某采用工程量清单招标的工程，公布的招标控制价为6000万元，中标人的投标报价为5200万元，经调整后的中标价为5100万元，所有合格投标人的平均报价为5450万元，则中标人报价浮动率为()。
被审计单位资产负债表上的银行存款数额，应以编制或取得银行存款余额调节表日银行存款账户数额为准。　　　　(　　)
2011年1月1日，甲公司将公允价值为2950万元的全新办公设备—套，按照3000万元的价格出售给乙公司，并立即签订了—份租赁合同，从乙公司租回该办公没备，租期为4年。办公设备原账面价值为2900万元，预计使用年限为25年。租赁合同规定，在租期的每年年未支
影响政策执行有效性的因素有（）。
目前在中国，国家行政机关工作人员的薪酬与企业同等级别的人相比要低一些，请以“我这样看待薪酬差异”为题，发表一篇时间约为3分钟的演讲，说明你对这一问题的看法。
下列关于TCP／IP参考模型的说法中，不正确的是()。
Thebeautifuldress,whichwasboughtyesterday,______(send)toMaryasagifttomorrow.
Don’t______thisnewstothepublicuntilwegiveyouthego-ahead.

最新回复(0)

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

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

软考中级

阅读以下说明，回答问题1～5，将解答填入对应的解答栏内。[说明]编写一个函数根据用户输入的偶对(以输入。表示结束)建立其有向图的邻接表。一个图的邻接表存储结构定义如下：#include＜stdio.h＞#defineMAX

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

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 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

外资企业所得税税率实行30%的比例税率，另按应纳税所得额征收3%的()。

某采用工程量清单招标的工程，公布的招标控制价为6000万元，中标人的投标报价为5200万元，经调整后的中标价为5100万元，所有合格投标人的平均报价为5450万元，则中标人报价浮动率为()。

被审计单位资产负债表上的银行存款数额，应以编制或取得银行存款余额调节表日银行存款账户数额为准。 ( )

影响政策执行有效性的因素有（）。

目前在中国，国家行政机关工作人员的薪酬与企业同等级别的人相比要低一些，请以“我这样看待薪酬差异”为题，发表一篇时间约为3分钟的演讲，说明你对这一问题的看法。

下列关于TCP／IP参考模型的说法中，不正确的是()。

Thebeautifuldress,whichwasboughtyesterday,______(send)toMaryasagifttomorrow.

Don’t______thisnewstothepublicuntilwegiveyouthego-ahead.

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

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　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

被审计单位资产负债表上的银行存款数额，应以编制或取得银行存款余额调节表日银行存款账户数额为准。　　　　(　　)