首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-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题库学硕统考专业分类
0
计算机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
)