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

admin2019-12-10 53

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

学硕统考专业

在CRC码中，接收端检查出某一位数据出错后，一般采用的纠正方法是()。

某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。(2

设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是()。

主机A向主机B连续发送了两个TCP报文段，其序号分别为70和100。试问：(1)第一个报文段携带了多少个字节的数据?(2)主机B收到第一个报文段后发回的确认中的确认号应当是多少?(3)如果主机B收到第二个报文段后发回的确认中的

关于DMA方式和通道方式，下列说法中错误的是()。

一个进程被唤醒意味着()。

关于B一树，下列说法不正确的是()。

已知某局域网采用CSMA／CD协议实现介质访问控制，数据传输速率为100Mbps。(1)此局域网采用了以太网，为了达到100Mbps的数据传送率，那么线路的带宽最小为多少?(2)如果信号在网络中的传播速度是200000km／s，那么该网

若某通信链路的数据传输速率为2400bit／s，采用4相位调制，则该链路的波特率是____。

A．黄连阿胶汤B．朱砂安神丸C．两者均是D．两者均非(1996年第115，116题)不寐，急躁易怒，日赤口苦，口渴喜饮，小思饮食，溲干便黄，脉弦数者，应选用()

女，30岁。在颈丛麻醉下施行了甲状腺腺瘤切除术，手术顺利。该病人返回病房后应采用的卧位是

以下关于苦参的描述，错误的是()。

根据有关法律规定，招标代理服务收费方式是()

班级管理的本质在于()。

下列行为中，属于单方行为的是()

为考生文件夹下SCREEN文件夹中的PENCEL．BAT文件建立名为BAT的快捷方式，存放在考生文件夹下。