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

admin2019-01-30 57

问题假设有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

学硕统考专业

相关试题推荐

试论春秋战国时期思想文化获得发展的主要原因。
北约和华约两个组织对峙近半个世纪，其影响是()。
简述路德“唯信称义”与加尔文“预定论”的关系与区别。
根据下列史料，说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆，久为两国人民通商之地。从今日起，改革从前惯例及岁遣船等事，以此次新订条款为标准，办理贸易事务，朝鲜政府开放第五款所载两口岸，准日本人民往来通商，随意在该两地租借地
下列能体现《独立宣言》是“一个伟大的历史文件”的表述是()
把中国第一次工人运动的高潮推向顶点的是（）。
下列叙述正确的个数是()。　1)向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
有二个处理机P1和P2，它们各自有一个cache和主存，分别为C1、C2和M1、M2，其性能见下表：若两个处理机的指令系统相同，指令的执行时间与存储器的平均存取周期成正比，当执行某程序时，cache的命中率为70％，则P1处理机的速度比
假定变量i、f和d的数据类型分别为int、float和double(int用补码表示，float和double分别用IEEE754单精度和双精度浮点数格式表示)，已知i=785，f=1．5678e3，d=1．5e100。若在32位机器中执行下列关系表达式，

随机试题

诊断骨质软化最可靠的征象是
设inta；floatb；charc；longd；doublee；，则表达式a/c-b+d-e值的类型是______。
免疫放射分析与放射免疫的相同点是
急性胰腺炎最常见的临床表现是
罗某从外地采购一批玉米存放在一粮食仓库销售。甲市乙区市场监督管理局接到这批玉米已发生霉变举报后，即派员前往现场检查核实。该局人员对这批玉米全部进行查封，并从这批玉米中抽出四袋样品送检，制作了现场笔录。罗某对此不服，向法院提起行政诉讼。据此，回答下列问题。
房地产置业投资的投资者从长期投资的角度出发希望获得的利益有()。[2005年考题]
甲公司为增值税一般纳税人，适用的增值税税率为17%。(1)2006年11月15日，以银行存款购入一台需要安装的设备，买价100万元，增值税17万元，支付的运杂费、包装费共3万元。(2)在安装上述设备过程中，领用生产用库存原材料10万元，增
刑事案件一般由（）管辖。
AhasremainedapuzzleBlackssufficientevidenceCisauniversityprofessorDwasgeneratedbytheexplosionEwillkillman
PatentsandInventionsWhenaninventionismade,theinventorhasthreepossiblecoursesofactionopentohim:first,hecang

最新回复(0)

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

计算机408

学硕统考专业

试论春秋战国时期思想文化获得发展的主要原因。

北约和华约两个组织对峙近半个世纪，其影响是()。

简述路德“唯信称义”与加尔文“预定论”的关系与区别。

下列能体现《独立宣言》是“一个伟大的历史文件”的表述是()

把中国第一次工人运动的高潮推向顶点的是（）。

假定变量i、f和d的数据类型分别为int、float和double(int用补码表示，float和double分别用IEEE754单精度和双精度浮点数格式表示)，已知i=785，f=1．5678e3，d=1．5e100。若在32位机器中执行下列关系表达式，

诊断骨质软化最可靠的征象是

设inta；floatb；charc；longd；doublee；，则表达式a/c-b+d-e值的类型是______。

免疫放射分析与放射免疫的相同点是

急性胰腺炎最常见的临床表现是

房地产置业投资的投资者从长期投资的角度出发希望获得的利益有()。[2005年考题]

刑事案件一般由（）管辖。

AhasremainedapuzzleBlackssufficientevidenceCisauniversityprofessorDwasgeneratedbytheexplosionEwillkillman

PatentsandInventionsWhenaninventionismade,theinventorhasthreepossiblecoursesofactionopentohim:first,hecang