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

admin2019-01-30 85

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

学硕统考专业

相关试题推荐

下列不属于延安整风运动的文件是()。
袁世凯在控制自己权力，实现对全国控制的过程中，主要颁布的法律不包括()。
下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府
红山文化的代表件墓葬形式为()。
下列关于《凡尔赛和约》的说法，全部错误的是()。①《凡尔赛和约》中不许德国设防区是莱茵河西岸50公里以内区域②《凡尔赛和约》中，战胜国处置德国的全部海外殖民地的方式是“托管制”③和约有关德国疆界问题，把原属波兰的领上基本上归还波兰④
一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：(1)请说明系统处于不安全状态；(2
某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
一131的1字节、2字节补码分别是()。
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

随机试题

男，20岁，8丨阻生，拔除术后3天，拔牙窝剧痛可能性最大的诊断是
与结核性积液相比，下列哪项不符合癌性积液的特点
A．葡萄球菌B．链球菌C．肺炎链球菌D．脑膜炎球菌E．淋球菌有典型的荚膜结构
关于不作为，下列哪一项说法不正确?
某工程有3个施工过程，分为3个施工段组织流水施工。3个施工过程的流水节拍依次为3、3、4天，5、2、1天和4、1、5天，则流水施工工期为()天。
某公司一辆已缴纳车辆购置税并办理了登记注册手续的富豪240GLE型小轿车，因车祸更换底盘，经国家税务总局核定的同类型新车最低计税价格为680000元，下列说法正确的有()。
下列各选项中，（　　　）是《专利法》保护的对象。
股份合作制经济是改革中的新生事物，不属于它的特征的是
设二元可微函数F(x，y)在直角坐标系中可写成F(x，y)=f(x)+g(y)，其中f(x)，g(y)均为可微函数．而在极坐标系中可写成，求二元函数F(x，y)．
Pentium微处理器的外部数据总线是几位?

最新回复(0)

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

计算机408

学硕统考专业

下列不属于延安整风运动的文件是()。

袁世凯在控制自己权力，实现对全国控制的过程中，主要颁布的法律不包括()。

下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府

红山文化的代表件墓葬形式为()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。

一131的1字节、2字节补码分别是()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

男，20岁，8丨阻生，拔除术后3天，拔牙窝剧痛可能性最大的诊断是

与结核性积液相比，下列哪项不符合癌性积液的特点

A．葡萄球菌B．链球菌C．肺炎链球菌D．脑膜炎球菌E．淋球菌有典型的荚膜结构

关于不作为，下列哪一项说法不正确?

某工程有3个施工过程，分为3个施工段组织流水施工。3个施工过程的流水节拍依次为3、3、4天，5、2、1天和4、1、5天，则流水施工工期为()天。

某公司一辆已缴纳车辆购置税并办理了登记注册手续的富豪240GLE型小轿车，因车祸更换底盘，经国家税务总局核定的同类型新车最低计税价格为680000元，下列说法正确的有()。

下列各选项中，（ ）是《专利法》保护的对象。

股份合作制经济是改革中的新生事物，不属于它的特征的是

设二元可微函数F(x，y)在直角坐标系中可写成F(x，y)=f(x)+g(y)，其中f(x)，g(y)均为可微函数．而在极坐标系中可写成，求二元函数F(x，y)．

Pentium微处理器的外部数据总线是几位?

下列各选项中，（　　　）是《专利法》保护的对象。