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

admin2019-01-30 53

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

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

计算机408

学硕统考专业

相关试题推荐

阅读史料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为
下列哪一个不是罗马王政时代的管理机构?()
战国初期，上党地区在下列哪一个国家的控制范围之内?()
下列各组条约的时间排列顺序正确的是()。①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
试析第三次科学技术革命对人类社会和历史进程的影响。
电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：(1)请说明系统处于不安全状态；(2
在机器数中，正数的符号位用“1”表示的是()。

随机试题

能力是指能够完成某种活动所需的个性心理特征。
某患者因头痛、步态不稳3个月入院，行颅脑MRI检查提示后颅窝占位
女，24岁，因近1个月怕热、多汗、情绪激动，且经常腹泻、心悸而就诊。体检：甲状腺肿大，两手颤抖，眼球稍突。初步诊断为甲亢。该病人实验室检查可能会出现
最易发生休克的急腹症是
尿激酶产生抗凝血作用原理是
《安全生产法》规定，生产经营单位发生重大生产安全事故时，单位的安全负责人应当立即组织抢救，并不得在事故调查处理期间擅离职守（）
提出“白板说”的哲学家是()。
群众路线的领导方法是辩证唯物主义历史观和认识论在实际领导工作中的应用和体现。()
设置严格的日期格式的命令是
WhichofthefollowingstatementsaboutthetelephoneofthefutureisNOTtrue?

最新回复(0)

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

计算机408

学硕统考专业

下列哪一个不是罗马王政时代的管理机构?()

战国初期，上党地区在下列哪一个国家的控制范围之内?()

下列各组条约的时间排列顺序正确的是()。①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》

试析第三次科学技术革命对人类社会和历史进程的影响。

电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

在机器数中，正数的符号位用“1”表示的是()。

能力是指能够完成某种活动所需的个性心理特征。

某患者因头痛、步态不稳3个月入院，行颅脑MRI检查提示后颅窝占位

女，24岁，因近1个月怕热、多汗、情绪激动，且经常腹泻、心悸而就诊。体检：甲状腺肿大，两手颤抖，眼球稍突。初步诊断为甲亢。该病人实验室检查可能会出现

最易发生休克的急腹症是

尿激酶产生抗凝血作用原理是

《安全生产法》规定，生产经营单位发生重大生产安全事故时，单位的安全负责人应当立即组织抢救，并不得在事故调查处理期间擅离职守（）

提出“白板说”的哲学家是()。

群众路线的领导方法是辩证唯物主义历史观和认识论在实际领导工作中的应用和体现。()

设置严格的日期格式的命令是

WhichofthefollowingstatementsaboutthetelephoneofthefutureisNOTtrue?