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

admin2019-10-08 50

问题对有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，回答问题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，可构造如图
阅读下列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
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　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control

随机试题

银基钎料主要是()的合金。
建国以来我们在社会主义建设中所经历的曲折和失误，归根结底，就在于没有完全搞清楚()
水泥按其物化性质属于()．
A公司为支付货款，向B公司签发了一张金额为200万元的银行承兑汇票，某商业银行作为承兑人在票面上签章。B公司收到汇票后将其背书转让给C公司，以偿还所欠C公司的租金，但未在被背书人栏内记载C公司的名称。C公司欠D公司一笔应付账款，遂直接将D公司记载为B公司的
若该企业2015年第二季度产量同比增长降低至8％，环比增长速度为20％，则2015年第一季度的产量为()万吨。
下列关于缓刑的表述，正确的有()。
求微分方程y"+y＇－2y=xex+sin2x的通解．
设个体域为整数集，下列公式中其值为1的是(61)。
Thehotelprovidesfreeshuttle______tothetrainstationandtheairport.
Inthisageofthekeyboard,somepeopleseemtothinkhandwritinglessonsare______.

最新回复(0)

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

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

软考中级

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

阅读下列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

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 program memory serves basically as a place(66)instructions, the coded pieces of data(67)direct the activities of the control

银基钎料主要是()的合金。

建国以来我们在社会主义建设中所经历的曲折和失误，归根结底，就在于没有完全搞清楚()

水泥按其物化性质属于()．

若该企业2015年第二季度产量同比增长降低至8％，环比增长速度为20％，则2015年第一季度的产量为()万吨。

下列关于缓刑的表述，正确的有()。

求微分方程y"+y＇－2y=xex+sin2x的通解．

设个体域为整数集，下列公式中其值为1的是(61)。

Thehotelprovidesfreeshuttle______tothetrainstationandtheairport.

Inthisageofthekeyboard,somepeopleseemtothinkhandwritinglessonsare______.

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

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

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