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

admin2019-10-08 69

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

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

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

软考中级

相关试题推荐

根据题意，给出联系的属性。实体间的联系有“一对一”、“一对多”和“多对多”，指出各联系分别属于哪一种。若用Student表存储学生信息，Teacher表存储教师信息，Course表存储课程信息，Study表存储学生选修课程情况。教务处想要“查询2006
阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在对应栏内。[预备知识]①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图
阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句填写完整。[说明](1)对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a,b,c,d)及其权值2、7、4、5，可构造如
图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
The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control

随机试题

盐酸除了能溶解碳酸盐矿物和堵塞地层的铁锈外，还可溶解长石。()
58．材料1：自古以来农不如工，工不如商，农业劳动生产率低，比较效益差，难以获得社会平均利润率，农业是弱质产业。但农业给人类提供比较稳定的食品，人们对农业的生存依赖是100％的，农业又是永恒的必不可少的产业。材料2：在计划经济体制下，城市公共产品供给由国家
患儿，男，5岁，因高度水肿诊断为肾病综合征以泼尼松治疗4个月，此时该患儿会出现
某机电设备安装公司经邀请招标投标，获得某厂生产线的机电设备安装工程，并与业主签订了施工合同。合同规定工程范围、工期、质量标准、安全环境要求。其中质量标准和要求按部颁标准执行，主要材料如钢材、电缆、∮50以上的管道阀门等由业主提供，安装现场的协调由安装公司负
玻璃砖隔墙施工中，玻璃砖墙宜以()mm高为一个施工段。
作为财务管理目标，企业价值最大化与股东财富最大化相比，其优点是()。
①它们没有超过一千年的家谱②金鱼是世界上养殖最普遍的宠物鱼类③不过有一件事是可以确定的④却没有多少证据证实它们是什么时候被驯养的⑤只有少数几个国家还没有引进⑥尽管我们知道金鱼原产于中国将以上6个句子重新排列，语序正确的是（）。
王某，十六岁。一天，她到工艺美术公司以800元购买了项链和宝石戒指。她父母认为她尚未成年，没有征得家长同意，不能进行大数额的买卖行为，要求公司退款。而王某提出她是靠做临时工、自食其力的待业青年，她表示不愿退货。问：王某的买卖行为是否有效?其父母要求公司
古人云：“不谋全局者，不足以谋一域；不谋万世者，不足以谋一时。”这就告诉我们()。
汉代察举注重考察德行的科目是()。(2010年)

最新回复(0)

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

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

软考中级

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

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

盐酸除了能溶解碳酸盐矿物和堵塞地层的铁锈外，还可溶解长石。()

患儿，男，5岁，因高度水肿诊断为肾病综合征以泼尼松治疗4个月，此时该患儿会出现

玻璃砖隔墙施工中，玻璃砖墙宜以()mm高为一个施工段。

作为财务管理目标，企业价值最大化与股东财富最大化相比，其优点是()。

古人云：“不谋全局者，不足以谋一域；不谋万世者，不足以谋一时。”这就告诉我们()。

汉代察举注重考察德行的科目是()。(2010年)

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

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