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

admin2019-12-10 72

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

选项 A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)

答案C

解析考查邻接表的性质。和顶点v相关的边包括出边和入边，对于出边，只需要遍历v的顶点表即可；对于入边，则需要遍历整个邻接表。删除与某顶点v相关的所有边过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为，n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

转载请注明原文地址:https://kaotiyun.com/show/7L3i777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列关于主存储器的描述中，正确的是()。I．CPU访存时间由存储器容量决定Ⅱ．ROM和RAM在存储器中是统一编址的Ⅲ．ROM中任意一个单元可以随机访问Ⅳ．DRAM是破坏性读出，因此需要读后重写

设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。

已知加权有向图G如下，回答下列问题：(1)画出该有向图G的邻接矩阵；(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

如下图所示为一个带宽为50kbps的卫星信道，它的往返传播延时为500ms。现在有一个网络架设在该信道上，网络使用1000bit长度的帧和停止一等待协议，请回答如下问题：该网络发送一帧的发送延时和传输延时分别是多少?

下图所示为一个局域网的连接图，每个计算机的IP地址和物理地址如下表所示：该分组的以太网帧的源地址、目的地址和协议类型域各是什么?(用16进制表示)

在不同网络结点的对等层之间通信需要的是()。

计算机要对声音信号进行处理时，必须将它们转换成数字声音信号。最基本的声音信号数字化方法是取样一量化法。若量化后的每个声音样本用2个字节表示，则量化分辨率是()。

时宜惊醒，不易安卧属于

患者，女，50岁。虚烦不眠，触事易惊，终日惕惕，伴气短自汗，倦怠无力，舌淡，脉弦细。治疗应首选的方剂是()

下列哪项为阴虚火旺型心悸的主症

A．周期延后，经量少，色淡，质清稀B．周期延后，经量少，色暗，有块C．周期延后，经量少，色淡，质黏D．周期延后，经量多，色淡，质清稀E．以上都不是虚寒月经后期，月经的改变应是

居民生活使用的各类用气设备应采用以下何种燃气?(2003，96)

证券公司存在()情形的，不会被暂停签订新的集合及定向资产管理合同。

个人质押贷款的对象主要满足的条件包括()。

1959年底至1960年初，毛泽东在读苏联《政治经济学教科书》时。认为社会主义社会的发展阶段有

EconomicReforminChinaMoreUSsinologistshaveexpressedconfidenceinChina’seconomicreformandtheprospectsforChina’s

FlagDay,June14,isthebirthdayofAmericanflag.Onthisdatein1777,theContinentalCongress【C1】______aresolutionstatin