首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
admin
2021-01-13
43
问题
具有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和E—R图，回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】图2．1是某医院组织的结构图。该医院分为多个病区，每个病区有一个唯一的编号，一个病区包括多个病房，多名医生；每位医生有一个唯一的编号，负责管辖其主治病人的所有病房；病人住院
阅读下列说明和图，回答问题l至问题4，将解答填入答题纸的对应栏内。【说明】某公司欲开发招聘系统以提高招聘效率，其主要功能如下：(1)接受申请验证应聘者所提供的自身信息是否完整，是否说明了应聘职位，受理验证合格的申请，给应聘者发送致谢信息。(2)评
阅读下列说明C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一
阅读以下说明和C代码，根据要求回答问题1～问题3。【说明】某工程计算中要完成多个矩阵相乘(链乘)的计算任务。两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算Am×n*Bn×p，需要m
(2012年上半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在
(50)反映了类间的一种层次关系，而(51)反映了一种整体与部分的关系。
常见的软件开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型等。其中(15)模型适用于需求明确或很少变更的项目，(16)模型主要用来描述面向对象的软件开发过程。
对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行(61)遍历可以得到一个
在软件开发中，(29)不能用来描述项目开发的进度安排。在其他三种图中，可用(30)动态地反映项目开发进展情况。
以下序列不是堆的是(40)。
随机试题
RUP是一种以用况为驱动、以__________为中心的迭代、增量式开发。
试述国际铁路货物联运进出口程序。
肾虚腰痛，日久不愈，无明显阴阳偏虚，宜选用
在教学的“循序渐进原则”中，“序”一是指学科的逻辑顺序，二是指______。
在我国，课程具体表现为课程计划、_________和_________。
景德元年(1004年)闰九月，辽圣宗和萧太后亲率大军大举南犯，转战定、瀛诸州，在十一月攻占德清军，直指北宋重镇澶州。辽军来势凶猛，北宋朝野震惊，宰相寇准要求皇帝御驾亲征，鼓舞军民。辽国害怕腹背受敌，决计与北宋议和。经过反复磋商，在同年十二月达成协议，规定北
(2012年国家.58)1798年，英国航空科学家乔治.凯利设计出最早的直升飞行器并实践了飞行计划，其创意来自童年玩耍过的中国玩具“竹蜻蜓”。一百年后，“竹蜻蜓”加上达.芬奇直升飞行器的设计草图，又变幻成了俄国伊戈尔.西科斯基童年梦中的趣味飞行；当他的公司
某分页存储管理系统中，设页面尺寸为4KB，某进程的页表数据(块号)为：8、9、10、15、18、20、21、22、23，则该进程的逻辑地址0x05AF8H对应的物理地址是()。
【B1】【B4】
A、Itwasmorerespected.B、Itwasusedbymorepeople.C、Itwasvandalizedbytourists.D、ItquicklydeterioratedagainafterLi
最新回复
(
0
)
