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

admin2023-02-06 39

问题假设有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://jikaoti.com/ti/RkPiFFFM

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

计算机408

学硕统考专业

相关试题推荐

和平共处五项原则是我国发展对外关系的根本原则。()
在教小学数学“按比例分配”时，教师在讲新课前向全班提问：“把12棵树分给两个组去栽，每个小组分几棵?”学生齐声回答：“6棵!”教师问：“有没有不同意见呢?”发现孙同学眉头微蹙，教师就提醒说：“大家要认真思考，有同学可能把你们的答案推翻了哦。”学生们于是开始
在时间上，家庭教育是()。
教师在教育教学中确定目标，建立班集体，制订和贯彻规章制度，维持班级纪律，组织班级活动，协调人际关系等。这些活动中，教师扮演着()。
给定资料1．近年来，学校的学业负担让很多学生不堪重负，长时间的课业学习不仅让学生们得不到充分的休息，也让本应属于他们的欢快的课余生活被枯燥的课业学习所取代。减负政策的实行仿佛让学生们看到了希望的曙光，但在减负政策逐步推行的过程中，部分政策其实并没有真正落
有5支足球队进行单循环比赛，每场比赛胜者得3分，负者不得分，平局双方各得1分。比赛结束后，若5支球队的总得分为25分，冠军得12分，则亚军得：
不同于西方的砖石建筑，榫卯结构的结点，即木构件之间的连接处允许产生略微的形变，这使得建筑能够承受较大的荷载，即使遇到地震也能安然无恙。其中饱含的，又何尝不是以柔克刚的道理?作为木结构之间的连接件，榫卯结构并不显山露水，而是静静隐匿于屋檐下或家具中，理性又深
某次会议邀请4所高校每所各2位学者做报告。在某日上午、下午和晚上的三个时间段分别安排3位、3位和2位学者依次做报告，且同一所高校的2位学者不安排在同一时间段内做报告。问：8人的报告次序有多少种不同的安排方式?
写一个HeapInsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。提示：将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。

随机试题

外商投资企业，不包括以下哪种【】
新中国成立之初，我国社会主义国营经济建立的主要途径与手段是（）
败血症患儿行静脉输液时应特别强调
女，20岁，下腰背痛3个月，两踝关节肿痛2个月。ESR：50mm/小时，CLIP：8mS/L，RF(-)，WBC：8×109/L，Hb：120g/L，尿常规(-)。双侧4字实验(+)，HLAB27(+)。该患者最可能的诊断是
风心病并发心律失常最多见的是(　　)风心病左房室瓣狭窄并发栓塞最常见的是(　　)
A．丘脑腹外侧核B．脊髓后角细胞C．延髓薄束核与楔束核D．脊髓前角细胞E．后根神经节痛觉和温度觉传导通路的第二级神经元是
下列施工成本分析依据中，属于既可对已发生的，又可对尚未发生或正在发生的经济活动进行核算的是()。
社会主义旅游业职业道德的政治意识主要包括()
A.ThistouriSthechanceoflifetime．B.ItgoesalloverNorthAmericaandSouthAmerica.C.Itlookslikeyou’redreamingabou
课堂对话

最新回复(0)

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

计算机408

学硕统考专业

和平共处五项原则是我国发展对外关系的根本原则。()

在时间上，家庭教育是()。

教师在教育教学中确定目标，建立班集体，制订和贯彻规章制度，维持班级纪律，组织班级活动，协调人际关系等。这些活动中，教师扮演着()。

有5支足球队进行单循环比赛，每场比赛胜者得3分，负者不得分，平局双方各得1分。比赛结束后，若5支球队的总得分为25分，冠军得12分，则亚军得：

某次会议邀请4所高校每所各2位学者做报告。在某日上午、下午和晚上的三个时间段分别安排3位、3位和2位学者依次做报告，且同一所高校的2位学者不安排在同一时间段内做报告。问：8人的报告次序有多少种不同的安排方式?

外商投资企业，不包括以下哪种【】

新中国成立之初，我国社会主义国营经济建立的主要途径与手段是（）

败血症患儿行静脉输液时应特别强调

女，20岁，下腰背痛3个月，两踝关节肿痛2个月。ESR：50mm/小时，CLIP：8mS/L，RF(-)，WBC：8×109/L，Hb：120g/L，尿常规(-)。双侧4字实验(+)，HLAB27(+)。该患者最可能的诊断是

风心病并发心律失常最多见的是( )风心病左房室瓣狭窄并发栓塞最常见的是( )

A．丘脑腹外侧核B．脊髓后角细胞C．延髓薄束核与楔束核D．脊髓前角细胞E．后根神经节痛觉和温度觉传导通路的第二级神经元是

下列施工成本分析依据中，属于既可对已发生的，又可对尚未发生或正在发生的经济活动进行核算的是()。

社会主义旅游业职业道德的政治意识主要包括()

A.ThistouriSthechanceoflifetime．B.ItgoesalloverNorthAmericaandSouthAmerica.C.Itlookslikeyou’redreamingabou

课堂对话

风心病并发心律失常最多见的是(　　)风心病左房室瓣狭窄并发栓塞最常见的是(　　)