首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
admin
2021-01-13
30
问题
具有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，将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域道路交通网的信息。道路交通网由若干个路段(RoadSegment)构成，每个路段由
阅读下列说明C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一
阅读下列说明和图，回答问题1～问题3，将解答填入答题纸的对应栏内。【说明】某城市的各国家公园周边建造了许多供游客租用的小木屋和营地，为此该城市设置了一个中心售票处和若干个区域售票处。游客若想租用小木屋或营地，必须前往中心售票处进行预定并用现金支付全额费
某公司的主要业务是出租图书和唱碟。由于业务需求，该公司委托希赛公司开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。希赛公司决定采用面向对象的分析和设计方法开发此系统。图14-3所示为某类图书或唱碟被借阅时应记录的信息，
阅读下列说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】某软件系统中，已设计并实现了用于显示地址信息的类Address(如图5—1所示)，现要求提供基于。Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某软件公司欲设计实现一个虚拟世界仿真系统。系统中的虚拟世界用于模拟现实世界中的不同环境(由用户设置并创建)，用户通过操作仿真系统中的l～2个机器人来探索虚拟世界。机器人维护着两个
如图3-1所示为一确定有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是(1)，图中的(2)是可以合并的状态。
(35)从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。
在系统验收测试中，(23)是在一个模拟的环境下使用模拟数据运行系统；(24)是在一个实际环境中使用真实数据运行系统。
在常用的描述二叉排序树的存储结构中，关键字值最大的结点(48)。
随机试题
江泽民指出：“坚持公有制主体地位，是社会主义的一条根本原则，也是我国社会主义市场经济的基本标志。”要坚持公有制的主体地位，必须做到()。
男性，56岁。在医院诊断为稳定性心绞痛，经一个时期的治疗，效果欠佳，拟采用联合用药，较为合理的是
甲公司被法院宣告破产，清算组在清理该公司财产时，发现的下列哪些财产应列入该公司的破产财产?（）
银行金融理财业务如雨后春笋，发展迅猛。目前全国银行类理财产品多达2000多种，金额超过10000亿元。对于银行来说，下列表述正确的是()。
企业采取以投资促进发展的战略时，适合采用()的薪酬结构类型。
关于中国共产党历史上的重大战斗，下列说法不正确的是()。
运输公司从5名男司机、4名女司机中选派出3名男司机、2名女司机，到A、B、C、D、E五个不同地区执行任务，要求A地只能派男司机，E地只能派女司机。问有多少种不同的方案?()
Anysufficientlyadvancedtechnology,notedArthurC.Clarke,aBritishscience-fictionwriter,isindistinguishablefrommagic.
ReadthefollowingreviewsofabookcalledTheBossesSpeak.Foreachquestion23-28,choosethecorrectanswer.Markl
Thereareplacesintheworldwherepeoplearealleged(被认为)tolivemuchlongerandremainmorevigorousinoldagethaninmos
最新回复
(
0
)
