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

admin2019-10-08 65

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

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

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

软考中级

相关试题推荐

阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。[说明]以下是某图像二元树存储与还原算法的主要思想描述。设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示
阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：#include＜iostream．h＞#include＜assert．h＞templ
图7-13是对该IC卡加油机应用系统的基本流路径和备选流路径的描述，请用试题描述中的相应字母(见表7-15和表7-16)将图中(1)～(6)空缺处的内容填写完整。场景中的每一个场景都需要确定测试用例，一般采用矩阵或决策表来确定和管理测试用例。表7-1
Networks　can　be　interconnected　by　different　devices.　In　the　physical　layer,　networks　can　be　connected　by(66)or　hubs,　which　just　
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
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、肾衰竭E、呼气有尿臭味慢性肾衰竭特征性的表现是（）
合成和分泌雄激素的是
与胁瘸无关的是
《民法通则》规定普通诉讼时效的期间为()年。
2009年中央1号文件指出，要鼓励和支持金融机构创新农村金融产品和金融服务，大力发展()。
给定材料【材料1】十八大以来，习近平总书记就改革创新发表了一系列重要讲座，强调创新始终是推动一个国家，一个民族向前发展的重要力量。实施创新驱动发展战略，最根本的是要增强自主创新能力，最紧迫的是要破除体制机制障碍。最大限度解放和激发科技作
《中立法》
(2008上项管)(2009下项管)在项目每个阶段结束时进行项目绩效评审是很重要的，评审的目标是______。
A—thechiefcoachB—thechiefrefereeC—thedefenderD—centreforwardE—thesecon

最新回复(0)

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

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

软考中级

阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：#include＜iostream．h＞#include＜assert．h＞templ

Networks can be interconnected by different devices. In the physical layer, networks can be connected by(66)or hubs, which just

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

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、肾衰竭E、呼气有尿臭味慢性肾衰竭特征性的表现是（）

合成和分泌雄激素的是

与胁瘸无关的是

《民法通则》规定普通诉讼时效的期间为()年。

2009年中央1号文件指出，要鼓励和支持金融机构创新农村金融产品和金融服务，大力发展()。

《中立法》

(2008上项管)(2009下项管)在项目每个阶段结束时进行项目绩效评审是很重要的，评审的目标是______。

A—thechiefcoachB—thechiefrefereeC—thedefenderD—centreforwardE—thesecon

Networks　can　be　interconnected　by　different　devices.　In　the　physical　layer,　networks　can　be　connected　by(66)or　hubs,　which　just　

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

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