首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2017-01-04
101
问题
假设有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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
导致俄国革命去和平发展可能的事件是()。
中共八大的召开有怎样的历史意义?
结合诸条约内容简述中国社会沦为半殖民地半封建社会的过程。
中共十一届三中全会后对外开放开始起步,1980年中央决定设立()。
斯蒂文逊负责勘测和修建的世界上的第一条公共交通铁路通车于()。
宁夏回族自治区的设立时间是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
随机试题
设函数f(x)=ax(a>0,a≠1),求[f(1)f(2)…f(n)].
主要存在于室内的空气污染物是
正常骨髓造血功能受抑制表现
口腔黏膜带状疱疹的临床表现是()
未规定有空气洁净级别要求的区域需要对尘粒及微生物数量进行控制的房间(区域),其建筑结构、装备及其使用均具有减少该区域内污染源的介入、产生和滞留的功能
基金业协会的职责不包括()。
某增值税一般纳税人从某农业生产者手中购进玉米一批,收购价格为10000元,取得普通发票,并支付运费3000元,装卸费500元,取得货运企业开具的普通发票;验收入库后,因管理人员保管不善损失l/4,则该项业务准予抵扣的进项税额为()元。
下列土地可以由省、自治区、直辖市地方税务局确定减免城镇土地使用税的是()。
实践基础上的理论创新是社会发展和变革的先导。通过理论创新推动制度创新、科技创新、文化创新以及其他各方面的创新,不断在实践中探索前进是()
设函数f(x)=x+aln(1+x)+bxsinx,g(x)=kx3.若f(x)与g(x)在x→0时是等价无穷小,求a,b,k的值.
最新回复
(
0
)