首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
admin
2021-01-13
23
问题
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
选项
A、O(n
2
)
B、O(e
2
)
C、O(n*e)
D、O(n+e)
答案
D
解析
本题考查数据结构基础知识。深度优先和广度优先遍历图的过程实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n
2
)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为 O(n+e)。
转载请注明原文地址:https://kaotiyun.com/show/l3CZ777K
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明，回答【问题1】至【问题3】，将解答填入答题纸的对应栏内。【说明】某集团公司在全国不同城市拥有多个大型超市，为了有效管理各个超市的业务工作，需要构建一个超市信息管理系统。【需求分析结果】(1)超市信息包括
阅读下列说明和图，回答问题1～问题3，将解答填入答题纸的对应栏内。【说明】某城市的各国家公园周边建造了许多供游客租用的小木屋和营地，为此该城市设置了一个中心售票处和若干个区域售票处。游客若想租用小木屋或营地，必须前往中心售票处进行预定并用现金支付全额费
阅读下列说明和Java代码，将应填入(1)～(5)处的字句写在答题纸的对应栏内。【说明】生成器(Builder)模式的意图是将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。下图为其类图。【Java代码】
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足
在UML提供的图中，(31)用于描述系统与外部系统及用户之间的交互；(32)用于按时间顺序描述对象间的交互。
某一确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|19，则以下字符串中，不能被该DFA接受的是(28)，与该DFA等价的正规式是(29)。(其中，ε表示空字符)①3857 ②1.2E+5 ③-123． ④.576
在过程式程序设计(①)、数据抽象程序设计(②)、面向对象程序设计(③)、泛型(通用)程序设计(④)中，C++语言支持(16)，C语言支持(17)。
XML is a(71)language for documents containing(72)information. Structured information contains both content(words, pictures, e
The most accurate and most boring way to(66)Java is that it is a new computer programming language developed by Sun Microsystems
随机试题
你安排下属去完成任务，而他完成后直接越级上报，请问你怎么处理？
X线摄影条件选择的基本因素的叙述，错误的是
对生产环境气象条件的正确描述是
冬期砂浆拌合水温、砂加热温度不宜超过()℃和()℃。
求助者觉得咨询师和自己情投意合，因此每次要求咨询师延长咨询时间，咨询师也愿意这样做。咨询师的行为（）。
国民收入再分配的主要途径是()。
婚姻关系因法院的离婚判决而终止，导致这一具体法律关系消灭的事实称为()。
Venus(金星)isknownastheearth’s"twin"becausethetwoplanetsaresolikeeachotherinsize.ThediameterofVenusisabout
我国中央军事委员会实行()。
BusinessCollege,UHRealEstateMath6*4-hourslessonsBi-weekly
最新回复
(
0
)
