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

admin2017-01-04 76

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

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

计算机408

学硕统考专业

相关试题推荐

西哥特人图鲁兹建立起第一个得到罗马帝国承认的蛮族王国——西哥特王国的时间是()。
东欧国家的私有化方式一般有四种，其中波兰采取的主要方式是()
简述美苏争霸的三个阶段，并分析其影响与教训。
两次世界大战之间的国际关系是怎样维持的?
夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。
下列关于湘军的叙述中不正确的是()。
“两个凡是”
下图是三个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61．60．21．80的互联网地址)。LANA和LANB公用一个C类IP地址
设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。
在下面的应用中，通常使用栈的是()。　Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值

随机试题

鼻咽部横断面CT扫描的体位与基线是
在直线回归分析中，得到回归系数为-0.30，经检验有统计学意义，说明
进行2J检验时，u=2．58，选进行四格表X2检验时，X2=3．94，选
甲公司(上市公司)是一家以家电生产为主业的大型国有企业，总资产100亿元，净资产36亿元。最近3年净资产收益率平均超过了10％，经营现金流入持续保持较高水平。甲公司董事会为开拓新的业务增长点，分散经营风险，获得更多收益，决定从留存收益中安排2亿元实施投资。
下列各项中，属于用以风险评估常见的定性方法是()。
位于甲省某市区的一家建筑企业为增值税一般纳税人，在乙省某市区提供写字楼和桥梁建造业务，2019年8月具体经营业务如下：(1)该建筑企业对写字楼建造业务选择一般计税方法。按照工程进度及合同约定，本月取得含税金额3000万元并给业主开具了增值税专用发票。由于
用以反映债权债务或权利责任已经形成，但尚未涉及资金增减变化的会计事项以及保管债券、单证等事项的是()。
皮格马利翁效应体现了教师()对学生的影响。
费米悖论提出，银河系大约有2500亿(2．5×1011)颗恒星，可观测宇宙内则有70泽(7×1022)颗，即使智慧生命以很小的概率出现在围绕这些恒星的行星中，则在银河系内就应有相当大数量的地外文明存在；考虑到智慧生命克服资源稀缺的能力和对外扩张的倾向性，
下面是80x86宏汇编语言中关于SHORT和NEAR的叙述，()是正确的。

最新回复(0)

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

计算机408

学硕统考专业

西哥特人图鲁兹建立起第一个得到罗马帝国承认的蛮族王国——西哥特王国的时间是()。

东欧国家的私有化方式一般有四种，其中波兰采取的主要方式是()

简述美苏争霸的三个阶段，并分析其影响与教训。

两次世界大战之间的国际关系是怎样维持的?

夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。

下列关于湘军的叙述中不正确的是()。

“两个凡是”

设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。

在下面的应用中，通常使用栈的是()。 Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值

鼻咽部横断面CT扫描的体位与基线是

在直线回归分析中，得到回归系数为-0.30，经检验有统计学意义，说明

进行2J检验时，u=2．58，选进行四格表X2检验时，X2=3．94，选

下列各项中，属于用以风险评估常见的定性方法是()。

用以反映债权债务或权利责任已经形成，但尚未涉及资金增减变化的会计事项以及保管债券、单证等事项的是()。

皮格马利翁效应体现了教师()对学生的影响。

下面是80x86宏汇编语言中关于SHORT和NEAR的叙述，()是正确的。

在下面的应用中，通常使用栈的是()。　Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值