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

admin2017-01-04 99

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

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

计算机408

学硕统考专业

相关试题推荐

论述斯巴达的阶级结构、政治制度和社会风尚
简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。
1962年初，中共召开了中央工作会议，即“七千人大会”，其议题主要是()。
原始群是以()为纽带而组成的社会组织形式。
材料1942年5月，毛泽东指出，对于革命的文艺家，暴露的对象，只能是侵略者、剥削者、压迫者及其在人民中所遗留的恶劣影响，而不能是人民大众。人民大众也是有缺点的，这些缺点应当用人民内部的批评和自我批评来克服。1955年5月，毛泽东在《驳“舆论一律”
1854年，英国外交大臣致函英国驻华公使说：“为了适应外商对农业产品已增加了的需要，新的贸易市场尚待开辟。”1856年，法国外长则指令法国驻华代办强调“商业关系的推广”，并强调“这是一个关系到至高无上权益的问题”。这说明()。
在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。
下列叙述正确的个数是()。　1)向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
某模型机的通路结构如下图所示，用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

随机试题

下列叙述中正确的是()。
卡他性炎是指
正常人血浆pH为
男性，70岁。因听力逐渐减退一年多，来院就诊，经过医生检查发现其骨传导功能正常，空气传导功能障碍。进一步检查，下列哪一项可以不考虑
在以下关于国内生产总值的描述中，哪些描述是正确的?()
利益产品又称()。
美国的学制属于典型的()。
通报用于反映新情况、新问题，行文强调及时快捷。()
首次规定“八议”制度的封建成文法典是()。
YouaregoingtoreadatextaboutstudyingintheUnitedStates,followedbyalistofexamples.Choosethebestexamplefromt

最新回复(0)

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

计算机408

学硕统考专业

论述斯巴达的阶级结构、政治制度和社会风尚

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。

1962年初，中共召开了中央工作会议，即“七千人大会”，其议题主要是()。

原始群是以()为纽带而组成的社会组织形式。

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

下列叙述中正确的是()。

卡他性炎是指

正常人血浆pH为

男性，70岁。因听力逐渐减退一年多，来院就诊，经过医生检查发现其骨传导功能正常，空气传导功能障碍。进一步检查，下列哪一项可以不考虑

在以下关于国内生产总值的描述中，哪些描述是正确的?()

利益产品又称()。

美国的学制属于典型的()。

通报用于反映新情况、新问题，行文强调及时快捷。()

首次规定“八议”制度的封建成文法典是()。

YouaregoingtoreadatextaboutstudyingintheUnitedStates,followedbyalistofexamples.Choosethebestexamplefromt