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

admin2019-12-10 30

问题假设有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码中，接收端检查出某一位数据出错后，一般采用的纠正方法是()。

冯.诺依曼机工作方式的基本特点是()。

对于序列(49，38，65，97，76，13，27，50)按由小到大进行排序，初始步长d＝4的希尔排序法第一趟的结果的是()。

用链接方式存储的队列，在进行删除运算时，下面正确的是()。

如右图所示的有向图G的深度优先搜索得到的结点序列是()。

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

若一组记录的排序码序列F={50，80，30，40，70，60}，利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为()。

设图的邻接矩阵A如下所示。各顶点的度依次是

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的IP地址为211．68．71．80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如表5-1所示。回答下列问题：根据表5-1中的IP分组，分析S已经收到的应

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的IP地址为211．68．71．80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如表5-1所示。回答下列问题：表5-1中的IP分组中，哪几个是由H发送的?

高桩码头构件安装时，主要应控制()。

企业采用低成本的方法，为某一特定顾客群提供服务的实施方法是()

(13一04，09一10)物质的唯一特性是_______。

勤奋与懒惰属于()。

Perhapsthedaysmaynotbelongincoming______allthevaluablesubstancesincoalandoilwillbefullyutilized.

下列哪项不是水痘的常见并发症

男性，60岁，长期吸烟史，3个月来间断上腹不适，与进食关系不密切，现转为胀痛，血CAl9—9262U／ml。如果此病进一步发展很可能出现

A．苯巴比妥钠B．硫喷妥钠C．琥珀酰胆碱D．维库溴铵E．阿曲库铵使咽喉支气管敏感性增加，易引起喉痉挛及支气管痉挛的药物是()

Gamblingislawfulinthisstate.

Contrarytowhatmanypeoplethink,depressionisnotanormalpartofgrowingolder.Orisithardertotreatinolderpeople.【