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

admin2023-02-06 80

问题假设有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://www.kaotiyun.com/show/4IwD777K

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

计算机408

学硕统考专业

相关试题推荐

下列关于课程计划编制原则的说法正确的是()。
()的领导方式认为，学生对集体的喜爱、期望、归属感、团结性与作业水平及学习成绩有关，班主任应信赖集体，将班级作为教育的对象，而不是一对一地去对待每个学生。
课外辅导是帮助和指导学生学习的活动。下列关于课外辅导的说法错误的是()。
强调迁移的条件是两种学习必须遵循共同的内在原理，这是()。
课程标准与教材的关系是()。　①教材编写必须依据课程标准，教师必须领会和掌握本学科课程标准的基本思想和内容，并在教材中予以充分体现　②课程标准是教材的编写指南和评价依据，教材是课程标准的主要载体　③课程标准只是一个最低限度的要求，
有5支足球队进行单循环比赛，每场比赛胜者得3分，负者不得分，平局双方各得1分。比赛结束后，若5支球队的总得分为25分，冠军得12分，则亚军得：
线上阅读建立起四通八达的内容传播渠道，让我们获取信息的种类和数量更多了，但其并非唯一的阅读形式。事实上，传统的纸质阅读仍是一种不可或缺、具有独特优势、更适合进行深度阅读的重要阅读形式。以下哪项如果为真，最能支持上述观点?
最小最大堆(minmaxHeap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。(1)画出在图中插入关键字为5的结点后的最小最大
写一个HeapInsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。提示：将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。
已知一个带有头结点的单链表L，其结点结构由两部分组成：数据域data，指针域link。设计一个算法，以最高效的方法实现在单链表中删除数据域最小值结点。(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注

随机试题

企业兼并动机的效率理论的分支包括()
一公司为股份制企业，认为行政机关作出的决定侵犯企业经营自主权，下列哪些主体有权以该公司的名义提起行政诉讼?()(司考2013．2．82)
某书画院2008年2月，将其书画院大厅和部分展览厅租赁给某画家举办个人书画活动，取得个人上交的使用费12万元；馆内设置的保龄球馆取得经营收入8万元；书画院自办国内名家书画展，取得第一道门票收入3万元。该书画院当月应纳营业税为(　　)。
下列各项，应当计入工业企业产品成本的是()。
送外国旅游团出境时，全陪可在()离开机场。
奥尔夫()的基本原则逐渐发展成为其音乐教育的核心观念和奥尔夫体系的突出特点。
西南战争
Theotherdayanacquaintanceofmine,agregariousandcharmingman,toldmehehadfoundhimselfunexpectedlyaloneinNewYor
Sincetheadversityquotientconsiderablycontributestoourlifeandsocialprogress,weareobligatedtotrainourselvessoas
A、Theywouldhaveenjoyedahappierlife.B、Theywouldhavehaddifficultybeingpromoted.C、Theywouldhavebeenshiftedaround

最新回复(0)

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

计算机408

学硕统考专业

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

()的领导方式认为，学生对集体的喜爱、期望、归属感、团结性与作业水平及学习成绩有关，班主任应信赖集体，将班级作为教育的对象，而不是一对一地去对待每个学生。

课外辅导是帮助和指导学生学习的活动。下列关于课外辅导的说法错误的是()。

强调迁移的条件是两种学习必须遵循共同的内在原理，这是()。

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

企业兼并动机的效率理论的分支包括()

一公司为股份制企业，认为行政机关作出的决定侵犯企业经营自主权，下列哪些主体有权以该公司的名义提起行政诉讼?()(司考2013．2．82)

下列各项，应当计入工业企业产品成本的是()。

送外国旅游团出境时，全陪可在()离开机场。

奥尔夫()的基本原则逐渐发展成为其音乐教育的核心观念和奥尔夫体系的突出特点。

西南战争

Theotherdayanacquaintanceofmine,agregariousandcharmingman,toldmehehadfoundhimselfunexpectedlyaloneinNewYor

Sincetheadversityquotientconsiderablycontributestoourlifeandsocialprogress,weareobligatedtotrainourselvessoas

A、Theywouldhaveenjoyedahappierlife.B、Theywouldhavehaddifficultybeingpromoted.C、Theywouldhavebeenshiftedaround