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

admin2019-10-08 62

问题对有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～问题4。[算法说明]某旅馆共有N间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。
请将图4-15中各实体之间的联系补充完整。如果将商品信息只存储在中心数据库中，与在各POS机上存储其备份相比，从前台销售效率和更新商品库两方面论述各自的优缺点(不超过300字)。
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
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

随机试题

薪酬对员工、企业及社会的功能。
化脓性关节炎早期诊断中，最有价值的方法是
下列关于K—B纸片扩散法操作的描述，错误的是
腹部泌尿系平片(KUB)影像细节显示指标为
消防安全组织人员基本分为()。
用人单位在满足一定条件下可以延长工作时间，但是每月不得超过()小时。
个体产生新奇独特的、有社会价值的产品能力或特性称之为______。
具有方向性的过电流保护的主要组成元件有()。
定时器的Interval属性的值是一个整数，它表示的是
Thegovernmentmustincreasethe______ofreformstoavoidfurtherbloodshed.

最新回复(0)

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

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

软考中级

阅读以下说明和Java码，将应填入(n)处的字名写在的对应栏内。[说明]编写一个完整的JavaApplet程序使用复数类Complex验证两个复数1+2i和3+4i相加产生一个新的复数4+6i。复数类Complex必须满足如下要求

请将图4-15中各实体之间的联系补充完整。如果将商品信息只存储在中心数据库中，与在各POS机上存储其备份相比，从前台销售效率和更新商品库两方面论述各自的优缺点(不超过300字)。

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

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

薪酬对员工、企业及社会的功能。

化脓性关节炎早期诊断中，最有价值的方法是

下列关于K—B纸片扩散法操作的描述，错误的是

腹部泌尿系平片(KUB)影像细节显示指标为

消防安全组织人员基本分为()。

用人单位在满足一定条件下可以延长工作时间，但是每月不得超过()小时。

个体产生新奇独特的、有社会价值的产品能力或特性称之为______。

具有方向性的过电流保护的主要组成元件有()。

定时器的Interval属性的值是一个整数，它表示的是

Thegovernmentmustincreasethe______ofreformstoavoidfurtherbloodshed.

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

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