首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-08-15
125
问题
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
选项
A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)
答案
C
解析
删除与某顶点v相关的所有边的过程如下:先删除下标为v的顶点表结点的单链表,出边数最多为n一1,对应时间复杂度为O(n),再扫描所有边表结点,删除所有的入边,对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。
转载请注明原文地址:https://www.kaotiyun.com/show/EOCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于一战后构筑的凡尔赛体系,说法不正确的是()。
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:对于二里头文化的发现的意义,下列选项表述最准确的是()
(1)所有事件的最早发生时间如下:Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3,ve(3)+6}=12Ve(5)=max{ve(3)+3,ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
下面元件存取速度最快的是()。
给定页面请求序列RS=cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
简单无向图的邻接矩阵是对称的,可以对其进行压缩存储。若无向图G有n个结点,其邻接矩阵为A[1..n,1..n],且压缩存储在B[1..k],则k的值至少为()。
计算机操作系统中,若WAIT、SIGNAL操作的信号量S初值为3,当前值为一2,则表示当前有()个等待信号量S的进程。
随机试题
A.利多卡因B.地高辛C.辛伐他汀D.硝苯地平E.地西泮治疗室性心律失常的首选药是
伤寒病人不适合灌肠。()
某项目团队全职人员所占比例为20%,且有专职的项目经理,则该项目的组织模式是()。
定期定额纳税户“同富居酒店"的老板李某,2012年1月,将酒店承包给张某经营,张某每月向李某交承包费5000元,有关承包经营的事项,李某未向税务机关报告。自2012年1月起该酒店一直未向税务机关申报纳税,税务机关多次催缴无效,2012年5月20日,税务所找
提高权益净利率的基本动力是()。
教学从本质上说是一种()。
警卫工作的对象包括()。
从1953年起,国家对民族资本主义企业的利润采取“四马分肥”的分配形式,“四马”指
选择教育研究课题时应大处着眼,小处着手。
Ithasbeenprovedthatit______toinvestmoreineducationandscienceresearchprojects.
最新回复
(
0
)