首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-01-30
49
问题
假设有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
学硕统考专业
相关试题推荐
明成祖时期大力推崇理学,以国家力量编写了几部理学的大部头著作,下面不属于其中的是()。
北宋时期,对市场商品价格管理主要采取()。
抗日战争时期,敌后战场与正面战场发挥着不同的作用,下列不属于正面战场的战役是()。
下面哪项条约没有涉及德国的赔款问题?()
基辅罗斯国家对居民征税的方式是()。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
有二个处理机P1和P2,它们各自有一个cache和主存,分别为C1、C2和M1、M2,其性能见下表:若两个处理机的指令系统相同,指令的执行时间与存储器的平均存取周期成正比,当执行某程序时,cache的命中率为70%,则P1处理机的速度比
一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。
随机试题
宏观经济形势较好,企业比较容易获得较多资源,这样就降低了实施发展型战略的成本。
后现代公共行政管理的核心概念是()
PowerPoint放映演示文稿时,从当前幻灯片放映可以使用________键。
Alaska,whichwascalledRussianAmericabeforeitwassoldtotheUnitedStatesofAmerica,joinedtheunionastheforty-ninth
来自静脉系统的血栓栓子常可引起
患者,男,68岁,右侧胸背部疼痛1周,皮疹3天,查体可见右侧胸背部数片红斑基础上呈簇水疱,排列成带状1个月后,患者皮疹完全消退,但仍觉右侧胸背部疼痛难忍,最可能的原因是
在饱和软黏土地基中,由于邻近工程大面积降水而引起场地中基桩产生负摩阻力,下列( )项中的中性点深度及下拉荷载最大。
下列关于公积金个人住房贷款业务的职责分工的表述,正确的有()。
激励的方法有()。
Whendidthefightbegin?
最新回复
(
0
)