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

admin2019-08-15 93

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

选项 A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)

答案C

解析删除与某顶点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

转载请注明原文地址:https://kaotiyun.com/show/EOCi777K

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

计算机408

学硕统考专业

相关试题推荐

“葡萄牙人在非洲海岸、印度和整个远东寻找的是黄金，黄金一词是驱使西班牙人横渡大西洋到美洲去的咒语；黄金是白人刚踏上一个新发现的海岸时所要的第一件东西。”欧洲人对黄金的贪婪追求从本质上反映了()
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()
在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns，命中率为p1；若Cache未命中，CPU需直接访问主存，访问时间为t2ns，主存命中率为p2；若所需数据字不在主存中，则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。
若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。
以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条
已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：写出图G的邻接矩阵A。
设有一个双向链表h，每个结点中除有prior，data和next三个域外，还有一个访问频度域freq，在链表被起用之前，每个结点中的freq域都被初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域中的值加一，并调整表中
若x=103，y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是_______。

随机试题

四分位数间距主要用于()
10个月患儿，已在当地医院诊断为佝偻病活动期，给予治疗，效果不好。为进一步判定诊断是否正确，不需要做下列哪些检查
儿童哮喘诊断标准不正确的是
龋病的形成与下列哪些因素有关A．变形链球菌是主要的致病菌B．血链球菌与唾液链球菌也与龋病有关C．根面龋与粘性放线菌有关D．牙菌斑中的细菌代谢蔗糖产生酸性产物E．以上全部都是
建筑安装工程造价指数一般采用()的形式来表示。
市政公用工程施工中，每一个单位(子单位)工程完成后，应进行()测量。
某地铁区间隧道采用盾构法施工，盾构直径6.5m，盾构区间长1328m，隧道平均覆土11.5m。项目部采取了以下职业健康安全管理措施：措施一、对参加盾构施工的机械工和辅助生产工人进行安全技术知识的教育；措施二、在隧道内安装了轴流式通风机和照明设施；措施
根据海关规定，进出口货物报关单的“贸易方式”栏填写未列名的贸易方式时，应填为“其他贸易”。在下列几种贸易方式中不可填写为“其他贸易”的有()。
Thereiswidespreadconsensusamongscholarsthatsecondlanguageacquisition(MB1SLA)emergedasadistinctfieldofresearchfr
He______awellmeantbutunsuccessfulcampaigntoeaseEastWesttensionscallingforarmsreductionandasummitofthenuclea

最新回复(0)

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

计算机408

学硕统考专业

“葡萄牙人在非洲海岸、印度和整个远东寻找的是黄金，黄金一词是驱使西班牙人横渡大西洋到美洲去的咒语；黄金是白人刚踏上一个新发现的海岸时所要的第一件东西。”欧洲人对黄金的贪婪追求从本质上反映了()

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：写出图G的邻接矩阵A。

若x=103，y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是_______。

四分位数间距主要用于()

10个月患儿，已在当地医院诊断为佝偻病活动期，给予治疗，效果不好。为进一步判定诊断是否正确，不需要做下列哪些检查

儿童哮喘诊断标准不正确的是

龋病的形成与下列哪些因素有关A．变形链球菌是主要的致病菌B．血链球菌与唾液链球菌也与龋病有关C．根面龋与粘性放线菌有关D．牙菌斑中的细菌代谢蔗糖产生酸性产物E．以上全部都是

建筑安装工程造价指数一般采用()的形式来表示。

市政公用工程施工中，每一个单位(子单位)工程完成后，应进行()测量。

根据海关规定，进出口货物报关单的“贸易方式”栏填写未列名的贸易方式时，应填为“其他贸易”。在下列几种贸易方式中不可填写为“其他贸易”的有()。

Thereiswidespreadconsensusamongscholarsthatsecondlanguageacquisition(MB1SLA)emergedasadistinctfieldofresearchfr

He______awellmeantbutunsuccessfulcampaigntoeaseEastWesttensionscallingforarmsreductionandasummitofthenuclea