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

admin2019-08-15 80

问题假设有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://kaotiyun.com/show/EOCi777K

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

计算机408

学硕统考专业

相关试题推荐

鸦片战争失败后，西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点，对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:中国与外国签订的第一个同盟条约是()
鸦片战争失败后，西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点，对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:规定外国人在中国可以不受中国法律管束的不平等条约是()
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。
设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。
一个客户机利用FTP协议从服务器上下载文件，如下图所示为整个过程中协议交换的过程，请回答如下问题：(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表，该列表采用什么端口传输?
设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。
下图是三个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61．60．21．80的互联网地址)。LANA和LANB公用一个C类IP地址
若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

随机试题

解放战争时期，中国共产党直接领导大区人民政府的机构是()
26岁，G1P1，31周妊娠，规律性腹痛3h入院。查体：宫底高度30cm，LOA，胎心120次／分，宫缩20s／5～7min。肛门检查：宫颈管消退70％，宫口尚未扩张。不宜选用的处理措施是()
雌、孕激素在哪些器官生理作用中相互拮抗()
A．＞750m1B．＜400mlC．＜100mlD．＜50mlE．＞2500ml无尿指每日尿量
袋中共有5个球，其中3个新球，2个旧球，每次取1个，无放回的取2次，则第二次取到新球的概率是()。
生产安全事故调查处理的原则是()。
暴力慈善是一种慈善的暴力行为，以牺牲受赠人的尊严来获得自己的满足。暴力慈善是对高调行善行事方式的一种概括。根据上述定义，下列哪项中的现象不属于暴力慈善?
关于计算机网络分类的描述中，错误的是()。
下列有关类继承的表述中，错误的是
TheSkillsRequiredtoGetaJobI.Academicskills:【T1】______【T1】______1.Communicationskills—Understandandspeakthelang

最新回复(0)

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

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

解放战争时期，中国共产党直接领导大区人民政府的机构是()

26岁，G1P1，31周妊娠，规律性腹痛3h入院。查体：宫底高度30cm，LOA，胎心120次／分，宫缩20s／5～7min。肛门检查：宫颈管消退70％，宫口尚未扩张。不宜选用的处理措施是()

雌、孕激素在哪些器官生理作用中相互拮抗()

A．＞750m1B．＜400mlC．＜100mlD．＜50mlE．＞2500ml无尿指每日尿量

袋中共有5个球，其中3个新球，2个旧球，每次取1个，无放回的取2次，则第二次取到新球的概率是()。

生产安全事故调查处理的原则是()。

暴力慈善是一种慈善的暴力行为，以牺牲受赠人的尊严来获得自己的满足。暴力慈善是对高调行善行事方式的一种概括。根据上述定义，下列哪项中的现象不属于暴力慈善?

关于计算机网络分类的描述中，错误的是()。

下列有关类继承的表述中，错误的是

TheSkillsRequiredtoGetaJobI.Academicskills:【T1】______【T1】______1.Communicationskills—Understandandspeakthelang

TheSkillsRequiredtoGetaJobI.Academicskills:【T1】【T1】1.Communicationskills—Understandandspeakthelang