假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

admin2019-01-30 69

问题假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

选项 A、O(n)
B、O(e)
C、O(n+e)
D、O(ne)

答案C

解析删除与某项点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n—1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

转载请注明原文地址:https://kaotiyun.com/show/5ZRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

简述中、苏分歧和中、苏同盟关系破裂的原因及其影响。
第一个五年计划的具体时间段是()。
隋统一全国时，与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩
对西欧封建社会的说法不正确的是()。
分析希腊大殖民运动发生的背景和影响。
宋代至清代我国书籍印刷的主要方式是()
下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。
在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。
某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1
有二个处理机P1和P2，它们各自有一个cache和主存，分别为C1、C2和M1、M2，其性能见下表：若两个处理机的指令系统相同，指令的执行时间与存储器的平均存取周期成正比，当执行某程序时，cache的命中率为70％，则P1处理机的速度比

随机试题

虎斑心(tigroidheart)
P公司为评估公司，2020年发生的具体业务如下：　(1)P公司受托对甲企业的持有至到期投资进行评估，该持有至到期投资账面余额为66万元(购买债券6600张、面值100元／张)，年利率10％，期限5年，已上市交易。　在评估前，该债券未计提减值准备。根据市
女，25岁。发现心悸、盗汗、易怒1年，伴有饮食量增加、消瘦。查体：BP110／80mmHg，重度突眼，甲状腺弥漫性肿大，深入胸骨后上纵隔内，心率116次／分。测血T3、T4值高于参考值上限一倍。该患者诊断是
水泥混凝土抗压强度试验的标准试件是边长为()mm的正立方体。
我国甲公司欲与比利时乙公司签订销售合同出口服装到比利时，拟采取海陆联运方式，甲公司将货物运至目的地的运费并支付保险，根据《INCOTERMS2000》，应采用的贸易术语是()
在中国，乐山大佛与云冈、龙门、敦煌共称为中国四大佛教石刻。()
某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：请回答下列问题：页和页框的大小各为多少字节?进程的虚拟地址空间大小为多少页?
设随机变量X和Y均服从B(1，)，且D(X+Y)=1，则X与Y的相关系数ρ=_________。
ManyAmericansregardthejurysystemasaconcreteexpressionofcrucialdemocraticvalues,includingtheprinciplesthatallc
结构化程序设计主要强调的是(　　)。

最新回复(0)

假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

计算机408

学硕统考专业

简述中、苏分歧和中、苏同盟关系破裂的原因及其影响。

第一个五年计划的具体时间段是()。

隋统一全国时，与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩

对西欧封建社会的说法不正确的是()。

分析希腊大殖民运动发生的背景和影响。

宋代至清代我国书籍印刷的主要方式是()

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。

某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1

虎斑心(tigroidheart)

女，25岁。发现心悸、盗汗、易怒1年，伴有饮食量增加、消瘦。查体：BP110／80mmHg，重度突眼，甲状腺弥漫性肿大，深入胸骨后上纵隔内，心率116次／分。测血T3、T4值高于参考值上限一倍。该患者诊断是

水泥混凝土抗压强度试验的标准试件是边长为()mm的正立方体。

我国甲公司欲与比利时乙公司签订销售合同出口服装到比利时，拟采取海陆联运方式，甲公司将货物运至目的地的运费并支付保险，根据《INCOTERMS2000》，应采用的贸易术语是()

在中国，乐山大佛与云冈、龙门、敦煌共称为中国四大佛教石刻。()

某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：请回答下列问题：页和页框的大小各为多少字节?进程的虚拟地址空间大小为多少页?

设随机变量X和Y均服从B(1，)，且D(X+Y)=1，则X与Y的相关系数ρ=_________。

ManyAmericansregardthejurysystemasaconcreteexpressionofcrucialdemocraticvalues,includingtheprinciplesthatallc

结构化程序设计主要强调的是( )。

结构化程序设计主要强调的是(　　)。