首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-01-30
61
问题
假设有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/5ZRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述路德“唯信称义”与加尔文“预定论”的关系与区别。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,其名义是()。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
第二次工业与第一次工业革命相比较,其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级
关于罗马奴隶制,下列说法不正确的是()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
假设计算机系统采用CSCAN(循环扫描)磁盘调度策略,使用2KB的内存空间记录16384个磁盘块的空闲状态。如果将磁盘替换为随机访问的Flash半导体存储器(如u盘、SSD等),是否有比CSCAN更高效的磁盘调度策略?若有,给出磁盘调度策略的名称并说明
随机试题
下列可以引起全身淋巴结肿大的疾病是( )
2015年5月和10月中国甲公司与法国乙公司分别签订了两份合同,由甲公司向乙公司出售一批食品。合同订立后,甲公司即分别发运了第一批货物的全部及第二批合同项下的部分货物。货物发运后,乙公司以资金周转困难为由,要求变更付款条件为汇付。甲公司表示同意,而乙公司在
有关对分项工程项目编码数字表示的叙述中,说法不正确的是()。
某矿建施工单位承担了一井筒的施工任务,根据业主提供的地质资料,表土无流砂,厚度不到30m,基岩部分最大涌水量不到30m3/h,因此施工单位决定采用普通井圈背板施工法进行表土施工,基岩采用钻眼爆破法施工,采用吊泵进行排水。在井筒表土施工时,施工单位
纳税人欠缴税款,同时,纳税人的债权人请求清偿债权的行为、债权人被行政机关决定处以罚款的行为同时存在,应优先()。
某省政府机关有办公用房一幢,房产价值5000万元。2005年将其中的四分之一对外出租,取得租金收入100万元。已知该省统一规定计算房产余值时的减除幅度为20%,该政府机关当年应纳的房产税为()。
A公司管理层2016年11月1日决定停产某车间的生产任务,提出职工没有选择权的辞退计划,规定拟辞退生产工人100名、车间管理人员10名,总部管理人员5名,并于2017年1月1日执行。该辞退计划已经通知相关职工,并经董事会批准,辞退补偿为生产工人每人5万元、
三年前陈某与村委会签订了110亩土地农业承包合同,经营期限为20年。乡政府为了兴建花卉种植基地,决定收回陈某承包的土地,陈某不服。下列说法正确的是()。
如右图所示,四边形ABCD的对角线BD被E、F两点三等分,且四边形AECF的面积为15平方厘米。四边形ABCD的面积是:
______的三大运动定律和万有引力定律创立了经典力学体系。
最新回复
(
0
)