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

admin2019-01-30 73

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

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

计算机408

学硕统考专业

相关试题推荐

阅读材料，回答以下问题：重庆中央党部，暨中央执监委员诸同志均鉴：今年4月，临时全国代表大会宣言，说明此次抗战之原因，曰：“自塘沽协定以来，吾人所以忍辱负重与倭国周旋，无非欲停止军事行动，采用和平方法，先谋北方各省之保全，再进而谋东北四省问题之合理解决，
提出天人关系应当“交相胜，还相用”的观点是()。
下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
下列历史事件发生的先后顺序是()。①“铁幕”演说②马歇尔计划③北大西洋公约
著名的网络OSI七层模型是由()组织提出来的。
就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。
已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。
在网络中计算机接收的信号是()。
在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，最后一个结点下标为k(起
设无向图G＝(V，E)和G’＝(V’，E’)，如果G’是G的生成树，则下面说法中错误的是()。

随机试题

下列哪种酶在TSH促进甲状腺激素合成的过程中起关键性作用
PCM系统与相位对比叠加使不同物质临界达到下列哪项效果
下列属于刺激性气体的是
管道吹扫过程中不得先于吹扫的设备是()。
我国建筑业和基本建设领域应用信息技术与工业发达国家相比，尚存在较大的数字鸿沟，它反映在()。
如果投保人逾期不交纳保险费,保险人能否强制投保人交纳,应该()
Inatelephonesurveyofmorethan2,000adults,21%saidtheybelievedthesunrevolved(旋转)aroundtheearth.An【C1】______7%
圣女贞德
甲于2008年8月17日上午11时，同装卸工乙、丙等3人驾驶解放牌大卡车由某乡向市里送货(该货车核准载重8吨，该批货物重13吨多)。大卡车超速行驶，当开到某乡政府的十字路口时，将前方同方向骑车的丁连人带车撞出20多米，造成丁重伤(后因抢救不及时，在被他人送
某系统总体结构图如下图所示：该系统总体结构图的深度是()。

最新回复(0)

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

计算机408

学硕统考专业

提出天人关系应当“交相胜，还相用”的观点是()。

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

下列历史事件发生的先后顺序是()。①“铁幕”演说②马歇尔计划③北大西洋公约

著名的网络OSI七层模型是由()组织提出来的。

就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

在网络中计算机接收的信号是()。

设无向图G＝(V，E)和G’＝(V’，E’)，如果G’是G的生成树，则下面说法中错误的是()。

下列哪种酶在TSH促进甲状腺激素合成的过程中起关键性作用

PCM系统与相位对比叠加使不同物质临界达到下列哪项效果

下列属于刺激性气体的是

管道吹扫过程中不得先于吹扫的设备是()。

我国建筑业和基本建设领域应用信息技术与工业发达国家相比，尚存在较大的数字鸿沟，它反映在()。

如果投保人逾期不交纳保险费,保险人能否强制投保人交纳,应该()

Inatelephonesurveyofmorethan2,000adults,21%saidtheybelievedthesunrevolved(旋转)aroundtheearth.An【C1】______7%

圣女贞德

某系统总体结构图如下图所示：该系统总体结构图的深度是()。