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

admin2018-08-12 43

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

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

计算机408

学硕统考专业

相关试题推荐

中华人民共和国恢复了在联合国合法席位的时间是()。
“文化大革命”结束后，在纠正“文化大革命”错误的过程中，整个过程受到()的严重阻碍。
明太祖洪武年间与科举制相关的一次大案是()。
美国首次提出争夺世界霸权的纲领性文件是()。
对《魏玛宪法》的内容和影响叙述不正确的是()。
下列关于罗马共和国政治制度的叙述，不正确的是()。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理，也可以产生类似的算法，不妨
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路
以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条
判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是()。

随机试题

下列各项中，应列入利润表中“营业成本”项目的有()。
主报表最多可以包含______级子报表。
关于村民委员会，下列哪一说法是正确的？(2010—卷一—21，单)
事故预警的目标是通过对生产活动和安全管理进行()，警示生产过程中所面临的危害程度。
甲、乙、丙共同投资设立A有限合伙企业，合伙协议约定，甲、乙、丙各占1／3出资额，其中甲是有限合伙人，乙、丙是普通合伙人，后来因甲要定居国外，欲将自己在合伙企业中的财产份额转让给第三人丁，下列表述正确的是()。
银行风险中的国家风险不包括()。
在以下哪种情况下，咨询师要使用具体化的咨询策略?()
马克思主义哲学之所以是科学的，就在于它坚持了()。
下面不属于对象主要特征的是
ThreeEnglishdictionariespublishedrecentlyalllayclaimtopossessinga"new"feature.TheBBCEnglishDictionarycontainsb

最新回复(0)

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

计算机408

学硕统考专业

中华人民共和国恢复了在联合国合法席位的时间是()。

“文化大革命”结束后，在纠正“文化大革命”错误的过程中，整个过程受到()的严重阻碍。

明太祖洪武年间与科举制相关的一次大案是()。

美国首次提出争夺世界霸权的纲领性文件是()。

对《魏玛宪法》的内容和影响叙述不正确的是()。

下列关于罗马共和国政治制度的叙述，不正确的是()。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是()。

下列各项中，应列入利润表中“营业成本”项目的有()。

主报表最多可以包含______级子报表。

关于村民委员会，下列哪一说法是正确的？(2010—卷一—21，单)

事故预警的目标是通过对生产活动和安全管理进行()，警示生产过程中所面临的危害程度。

银行风险中的国家风险不包括()。

在以下哪种情况下，咨询师要使用具体化的咨询策略?()

马克思主义哲学之所以是科学的，就在于它坚持了()。

下面不属于对象主要特征的是

ThreeEnglishdictionariespublishedrecentlyalllayclaimtopossessinga"new"feature.TheBBCEnglishDictionarycontainsb