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

admin2023-02-06 40

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

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

计算机408

学硕统考专业

相关试题推荐

下列关于课程计划编制原则的说法正确的是()。
下列关于公文格式页码的说法，正确的有()。
化学学习中，钾、钠等属于同一抽象和概括层次的金属元素在学习中互相影响。这种学习的迁移叫作()。
德育原则和德育规律的关系是()。
过滤气泡是指以大数据与算法推荐为底层架构，根据用户的使用时间、地区以及浏览习惯生成用户画像，并通过算法技术为其呈现独一无二的界面体验。网络上这种针对个人化搜索而提供筛选后结果的推荐算法，被称为过滤气泡。根据上述定义，下列不属于过滤气泡的是：
在数宁化多媒体时代，媒介参与的深度和广度日渐拓展，数字技术应用于文化遗产的保护已从原始的简单记录发展到对文化遗产的精准________，运用数字输入、摄像等各种数字化技术对文化遗产进行多形式的________，建立数字化的文化遗产档案和“非遗”博物馆等，都
与其他生命形式一样，适宜、稳定的自然环境，是人类文明得以存在和延续的重要外部条件。纵观地球生命的进化史，仅仅由于温度、水汽循环或者氧气含量的变化超出了当时地球生命的承受范围，就造成了四次生物大灭绝事件。我们人类的形成历史仅有500万年，在此期间，虽然没有发
微生物是地球最早出现的生命形式。这种简单而古老的生命决定了地球演化的方向和进程，推动了土壤的发生和发育，孕育了人类的文明。事实上，土壤中蕴藏的微生物的多样性，被称为地球关键元素循环过程的引擎，是联系大气圈、水圈、岩石圈及生物圈物质与能量交换的重要纽带，维系
小张、小王、小李三人相约骑自行车出去旅行，出发时约好某地集合。小张、小王两个人早上5时从约好的地点出发，小张每小时骑行18千米，小王每小时骑行14．4千米。小李因有事耽搁，早上7时才从约好的地点出发，结果下午5时小张、小李同时到达目的地。假设三人的骑行速度
下面关于m阶B树的说法中，正确的是()。①每个结点至少有两棵非空子树。②树中每个结点至多有m-1个关键字。③所有叶子在同一层上。④当插入一个数据项引起B树结点分裂后，树长高一层。

随机试题

维生素D缺乏性佝偻病初期的症状不包括()
关于绒毛膜促性腺激素(HCG)，哪项是正确的
橘皮主治
根据《公路法》的规定，下列关于该法律的主要内容表述不正确的是()
电缆桥架在安装时，其水平敷设应按(　　)选取最佳跨距进行支撑。
关于面分类的优点，正确的是()。
下岗工人将获得7万美元补偿，这相当于普通蓝领工人两年的税后年薪。仅靠这笔钱，在美元疲软、物价上涨的时代并不能______，不过尚能维持一个家庭几年的正常生活。填入划横线部分最恰当的一项是()。
法律制裁是由特定的国家机关对违法者(或违约者)依其所应承担的法律责任而实施的强制惩罚措施。根据违法行为和法律责任的性质不同，法律制裁可以分为司法制裁(包括民事制裁、刑事制裁)、行政制裁和违宪制裁。根据以上定义判断，下列各项中属于法律制裁的一项是()
设随机变量X1与X2相互独立，其分布函数分别为则X1+X2的分布函数F(x)=
Asthesupplyofgeneticallymodified(GM)foodincreases,manypeopleareunawarethatsomefoodtheyareeatingisaproductof

最新回复(0)

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

计算机408

学硕统考专业

下列关于课程计划编制原则的说法正确的是()。

下列关于公文格式页码的说法，正确的有()。

化学学习中，钾、钠等属于同一抽象和概括层次的金属元素在学习中互相影响。这种学习的迁移叫作()。

德育原则和德育规律的关系是()。

下面关于m阶B树的说法中，正确的是()。①每个结点至少有两棵非空子树。②树中每个结点至多有m-1个关键字。③所有叶子在同一层上。④当插入一个数据项引起B树结点分裂后，树长高一层。

维生素D缺乏性佝偻病初期的症状不包括()

关于绒毛膜促性腺激素(HCG)，哪项是正确的

橘皮主治

根据《公路法》的规定，下列关于该法律的主要内容表述不正确的是()

电缆桥架在安装时，其水平敷设应按( )选取最佳跨距进行支撑。

关于面分类的优点，正确的是()。

下岗工人将获得7万美元补偿，这相当于普通蓝领工人两年的税后年薪。仅靠这笔钱，在美元疲软、物价上涨的时代并不能______，不过尚能维持一个家庭几年的正常生活。填入划横线部分最恰当的一项是()。

设随机变量X1与X2相互独立，其分布函数分别为则X1+X2的分布函数F(x)=

Asthesupplyofgeneticallymodified(GM)foodincreases,manypeopleareunawarethatsomefoodtheyareeatingisaproductof

电缆桥架在安装时，其水平敷设应按(　　)选取最佳跨距进行支撑。