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

admin2019-10-08 51

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

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

答案A

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

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

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

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

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

软考中级

相关试题推荐

阅读下列算法说明和流程图1，回答问题1至问题3。[算法说明]某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(
根据题意，给出联系的属性。实体间的联系有“一对一”、“一对多”和“多对多”，指出各联系分别属于哪一种。若用Student表存储学生信息，Teacher表存储教师信息，Course表存储课程信息，Study表存储学生选修课程情况。教务处想要“查询2006
阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在对应栏内。[预备知识]①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图
阅读以下某旅馆客房管理系统的算法说明和程序流程图，根据要求回答问题1～问题4。[算法说明]某旅馆共有N间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。
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

随机试题

下列哪种调查方法是一种自我管理调查的形式()
下列哪项不属于压力源中的心理社会因素()。
主要用于胃肠道造影的对比剂是
银行信用是以货币形式向企业提供的信用。()
人的日常思维和行动，哪怕是极其微小的，都包含着有意识的主动行为，包含着某种创造性。而计算机的一切行为都是由预先编制的程序控制的，因此计算机永远不能拥有人所具有的主动性和创造性。下面哪一项将对题干中的推理构成严重质疑?()
中学教学工作的基本单位是()。
我国横断山脉是具有国际意义生物多样性的关键地区，横亘（）。
有四个自然数A、B、C、D，它们的和不超过400，并且A除以B商是5余5,A除以C商是6余6,A除以D商是7余7。那么，这四个自然数的和是()。
陈兴夫妇到红星照相馆为儿子陈华拍照留念，摄影师翻拍了陈华的底片，后将其卖给个体户张某做挂历用。张某又将该底片卖给某电器厂作广告之用。在本案中，侵害陈华肖像权的侵权人是()。
Esperantoisanartificiallanguage,designedtoserveinternationallyasan【B1】______meansofcommunicationamongspeakersofd

最新回复(0)

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

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

软考中级

阅读下列算法说明和流程图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

下列哪种调查方法是一种自我管理调查的形式()

下列哪项不属于压力源中的心理社会因素()。

主要用于胃肠道造影的对比剂是

银行信用是以货币形式向企业提供的信用。()

中学教学工作的基本单位是()。

我国横断山脉是具有国际意义生物多样性的关键地区，横亘（）。

有四个自然数A、B、C、D，它们的和不超过400，并且A除以B商是5余5,A除以C商是6余6,A除以D商是7余7。那么，这四个自然数的和是()。

陈兴夫妇到红星照相馆为儿子陈华拍照留念，摄影师翻拍了陈华的底片，后将其卖给个体户张某做挂历用。张某又将该底片卖给某电器厂作广告之用。在本案中，侵害陈华肖像权的侵权人是()。

Esperantoisanartificiallanguage,designedtoserveinternationallyasan【B1】______meansofcommunicationamongspeakersofd

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