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

admin2019-08-15 94

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

学硕统考专业

相关试题推荐

认识到乾嘉时期人口膨胀带来的系列问题，明确指出这种弊端的是()
赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：宋朝废除了过去统领禁军大权的殿前都点检，把禁军的领兵机构析为()，分掌禁军，合称“三衙”。
从“鲁尔危机”的发生到《道威斯计划》的实施，西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
西周的分封制相当发达，是西周的重要政治制度，也是西周历史的一个显著特点。根据所学知识，回答问题西周建立之后，派遣同姓贵族和异姓贵族及归顺的异族首领到各地区，建立国家以藩屏护卫周室，()分封诸侯的规模最大
古代两河流域最具代表性的文学作品是()。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()
下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据，进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位，这些数据块均存储在同一个磁盘上，因此，SPOO
下面关于进程的叙述中，正确的是()。
假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为()。

随机试题

10～17岁青少年IDA发病率为
尖锐湿疣的病原是
小儿厌食脾运失健证的用方是小儿厌食胃阴不足证的用方是
A．亲和力及内在活性都强B．具有一定亲和力但内在活性弱C．与亲和力和内在活性无关D．有亲和力、无内在活性，与受体不可逆性结合E．有亲和力、无内在活性，与激动剂竞争相同受体效价高、效能强的激动剂
管道工程施工应遵循()、水管让风管的配管原则。
甲公司有关业务如下：(1)2010年10月20日，甲公司自公开市场取得—项权益性投资，支付价款2000万元，作为交易性金融资产核算。2010年12月31日，该投资的市价为2200万元，2010年税前会计利润为1000万元。(2)2011年12月31日，
2014年，12358全国价格举报管理系统将实现()联网，进一步提升价格监管的信息化水平。
下列关于《矛盾论》表述正确的是()。
某超市以每千克7元的价格购入水果200千克，并以每千克10元的价格售出150千克，剩下可出售的水果按八折甩卖一空。经计算，销售本批水果共获利300元。那么，这批水果的折损率是多少？
以下叙述中，错误的是(　　　)。

最新回复(0)

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

计算机408

学硕统考专业

认识到乾嘉时期人口膨胀带来的系列问题，明确指出这种弊端的是()

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：宋朝废除了过去统领禁军大权的殿前都点检，把禁军的领兵机构析为()，分掌禁军，合称“三衙”。

西周的分封制相当发达，是西周的重要政治制度，也是西周历史的一个显著特点。根据所学知识，回答问题西周建立之后，派遣同姓贵族和异姓贵族及归顺的异族首领到各地区，建立国家以藩屏护卫周室，()分封诸侯的规模最大

古代两河流域最具代表性的文学作品是()。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

下面关于进程的叙述中，正确的是()。

假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为()。

10～17岁青少年IDA发病率为

尖锐湿疣的病原是

小儿厌食脾运失健证的用方是小儿厌食胃阴不足证的用方是

A．亲和力及内在活性都强B．具有一定亲和力但内在活性弱C．与亲和力和内在活性无关D．有亲和力、无内在活性，与受体不可逆性结合E．有亲和力、无内在活性，与激动剂竞争相同受体效价高、效能强的激动剂

管道工程施工应遵循()、水管让风管的配管原则。

甲公司有关业务如下：(1)2010年10月20日，甲公司自公开市场取得—项权益性投资，支付价款2000万元，作为交易性金融资产核算。2010年12月31日，该投资的市价为2200万元，2010年税前会计利润为1000万元。(2)2011年12月31日，

2014年，12358全国价格举报管理系统将实现()联网，进一步提升价格监管的信息化水平。

下列关于《矛盾论》表述正确的是()。

某超市以每千克7元的价格购入水果200千克，并以每千克10元的价格售出150千克，剩下可出售的水果按八折甩卖一空。经计算，销售本批水果共获利300元。那么，这批水果的折损率是多少？

以下叙述中，错误的是( )。

以下叙述中，错误的是(　　　)。