首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-12-10
30
问题
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
选项
A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)
答案
C
解析
考查邻接表的性质。和顶点v相关的边包括出边和入边,对于出边,只需要遍历v的顶点表即可;对于入边,则需要遍历整个邻接表。删除与某顶点v相关的所有边过程如下:先删除下标为v的顶点表结点的单链表,出边数最多为,n一1,对应时间复杂度为O(n),再扫描所有边表结点,删除所有的入边,对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。
转载请注明原文地址:https://kaotiyun.com/show/7L3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在CRC码中,接收端检查出某一位数据出错后,一般采用的纠正方法是()。
冯.诺依曼机工作方式的基本特点是()。
对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序,初始步长d=4的希尔排序法第一趟的结果的是()。
用链接方式存储的队列,在进行删除运算时,下面正确的是()。
如右图所示的有向图G的深度优先搜索得到的结点序列是()。
关于B一树,下列说法不正确的是()。
若一组记录的排序码序列F={50,80,30,40,70,60},利用快速排序方法,以第一个记录为基准,得到一趟快速排序的结果为()。
设图的邻接矩阵A如下所示。各顶点的度依次是
主机H通过快速以太网连接Internet,IP地址为192.168.0.8,服务器S的IP地址为211.68.71.80。H与S使用TCP通信时,在H上捕获的其中5个IP分组如表5-1所示。回答下列问题:根据表5-1中的IP分组,分析S已经收到的应
主机H通过快速以太网连接Internet,IP地址为192.168.0.8,服务器S的IP地址为211.68.71.80。H与S使用TCP通信时,在H上捕获的其中5个IP分组如表5-1所示。回答下列问题:表5-1中的IP分组中,哪几个是由H发送的?
随机试题
高桩码头构件安装时,主要应控制()。
企业采用低成本的方法,为某一特定顾客群提供服务的实施方法是()
(13一04,09一10)物质的唯一特性是_______。
勤奋与懒惰属于()。
Perhapsthedaysmaynotbelongincoming______allthevaluablesubstancesincoalandoilwillbefullyutilized.
下列哪项不是水痘的常见并发症
男性,60岁,长期吸烟史,3个月来间断上腹不适,与进食关系不密切,现转为胀痛,血CAl9—9262U/ml。如果此病进一步发展很可能出现
A.苯巴比妥钠B.硫喷妥钠C.琥珀酰胆碱D.维库溴铵E.阿曲库铵使咽喉支气管敏感性增加,易引起喉痉挛及支气管痉挛的药物是()
Gamblingislawfulinthisstate.
Contrarytowhatmanypeoplethink,depressionisnotanormalpartofgrowingolder.Orisithardertotreatinolderpeople.【
最新回复
(
0
)