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

admin2018-08-12 33

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

学硕统考专业

相关试题推荐

中华人民共和国恢复了在联合国合法席位的时间是()。
国际组织的“民主集中制”原则，是在()文献中首次规定的。
下列人物中与康熙收复台湾没有关系的是()。
世界近代史上，世界经济发展经历了两次大的飞跃，即第一次工业革命和第二次工业革命。阅读下面两段材料，回答问题：材料一工业革命的主角——蒸汽机，是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产，主要依靠以人力和经
在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响
一个TCP连接总是以1KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是
IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。
若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。
m阶B一树是一棵()。

随机试题

Althoughtheyhadaquarreltheotherday,PeterandJimarenowonfriendlyterms________.
患者，男性，76岁。血清PSA(前列腺特异性抗原)为9．8ng／ml(正常值为4ng／ml)，前列腺未扪及结节。要求进行超声检查。该患者的可能诊断为
关于结核性腹膜炎的病理分型，下列哪项是错误的
男，56岁。突发呕吐1小时。呕吐量约500ml，鲜红色，可见血块，伴大汗、心慌。查体：T38.5℃，P112次／分，R26次／分，BP114／80mmHg。巩膜轻度黄染，肝掌(+)，胸部见蜘蛛痣，心肺未见明显异常，腹胀，肝肋下未触及。脾肋下3cm，移动性浊
早产常见的病因有()。
单价分析应首先计算出工程中拟使用的人工、材料、施工机具使用费的基础单价，还要选择好适用的工程定额，然后对工程量清单中每一个分项进行分析与计算。单价分析通常采用的方法是()。
资料假设某商业银行的业务如下：1．各项存款2000万元。2．各项贷款1000万元。3．库存现金100万元。4．向央行办理票据再贴现100万元。5．开办信托投资业务150万元。6．发行金融债券300万元
下列各项中，需要缴纳土地增值税的有()。
把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是()。
“就在21世纪的钟声即将敲响之前，从神州大地上消除了最后一块帝国主义侵略造成的殖民地的残痕，完整而彻底地完成了民族独立的历史使命。”完成这一历史使命的根本保证是()

最新回复(0)

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

计算机408

学硕统考专业

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

国际组织的“民主集中制”原则，是在()文献中首次规定的。

下列人物中与康熙收复台湾没有关系的是()。

在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

m阶B一树是一棵()。

Althoughtheyhadaquarreltheotherday,PeterandJimarenowonfriendlyterms________.

患者，男性，76岁。血清PSA(前列腺特异性抗原)为9．8ng／ml(正常值为4ng／ml)，前列腺未扪及结节。要求进行超声检查。该患者的可能诊断为

关于结核性腹膜炎的病理分型，下列哪项是错误的

早产常见的病因有()。

单价分析应首先计算出工程中拟使用的人工、材料、施工机具使用费的基础单价，还要选择好适用的工程定额，然后对工程量清单中每一个分项进行分析与计算。单价分析通常采用的方法是()。

资料假设某商业银行的业务如下：1．各项存款2000万元。2．各项贷款1000万元。3．库存现金100万元。4．向央行办理票据再贴现100万元。5．开办信托投资业务150万元。6．发行金融债券300万元

下列各项中，需要缴纳土地增值税的有()。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是()。

“就在21世纪的钟声即将敲响之前，从神州大地上消除了最后一块帝国主义侵略造成的殖民地的残痕，完整而彻底地完成了民族独立的历史使命。”完成这一历史使命的根本保证是()