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

admin2019-10-08 35

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

随机试题

—个群体的基本产出——生产率和成员满意度受两组主要因素或变量的影响，它们是
A．暴发B．散发C．流行D．大流行E．世界大流行某单位突然在24小时内发生了数百例食物中毒患者
吴茱萸的功效是
定作合同对于支付报酬的期限没有约定或者约定不明，又不能达成补充协议，按照合同有关条款或者交易习惯也不能确定的，定作人应当在()支付报酬。
()是田径运动中决定跑速的主要因素。
在计算机系统中，对计算机各类资源进行统一管理和调度的软件是()。
以下哪一个图形是由左边的四个图形不经旋转、翻转直接拼接而成的?
Softmoneyisthehuge,unlimitedcontributionsfromcorporations,laborunionandwealthyindividualsthatpoliticalpartiesra
Whoisthewomanlookingfor?
ThereisnothingnewaboutTVandfashionmagazinesgivinggirlsunhealthyideasabouthowthintheyneedtobeinordertobec

最新回复(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(

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

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

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

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

—个群体的基本产出——生产率和成员满意度受两组主要因素或变量的影响，它们是

A．暴发B．散发C．流行D．大流行E．世界大流行某单位突然在24小时内发生了数百例食物中毒患者

吴茱萸的功效是

定作合同对于支付报酬的期限没有约定或者约定不明，又不能达成补充协议，按照合同有关条款或者交易习惯也不能确定的，定作人应当在()支付报酬。

()是田径运动中决定跑速的主要因素。

在计算机系统中，对计算机各类资源进行统一管理和调度的软件是()。

以下哪一个图形是由左边的四个图形不经旋转、翻转直接拼接而成的?

Softmoneyisthehuge,unlimitedcontributionsfromcorporations,laborunionandwealthyindividualsthatpoliticalpartiesra

Whoisthewomanlookingfor?

ThereisnothingnewaboutTVandfashionmagazinesgivinggirlsunhealthyideasabouthowthintheyneedtobeinordertobec

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

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

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