首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-08-15
129
问题
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
选项
A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)
答案
C
解析
删除与某顶点v相关的所有边的过程如下:先删除下标为v的顶点表结点的单链表,出边数最多为n一1,对应时间复杂度为O(n),再扫描所有边表结点,删除所有的入边,对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。
转载请注明原文地址:https://kaotiyun.com/show/EOCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
某阅览室晚间开放,第一个进入的读者开灯,最后一个离开的读者关灯。利用P、V原语操作实现读者进程。
一台主机申请了一个到www.ab@C@edu.cn的连接,为了获取服务器的IP地址,首先要进行DNS查询,下图为本次查询的过程,请回答如下问题:(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
设有一个带头结点的循环单链表,其结点值均为正整数。试设计一个算法,反复找出单链表中结点值最小的结点,并输出之,然后将该结点从中删除,直到单链表空为止,最后再删除表头结点。
简单无向图的邻接矩阵是对称的,可以对其进行压缩存储。若无向图G有n个结点,其邻接矩阵为A[1..n,1..n],且压缩存储在B[1..k],则k的值至少为()。
下列关于图的叙述中,正确的是____。I.回路是简单路径Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间Ⅲ.若有向图中存在拓扑序列,则该图不存在回路
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
若x=103,y=-25,则下列表达式采用8位定点补码运算实现时,会发生溢出的是_______。
随机试题
下列有关现代教育的叙述,错误的是【】
企业总机构和分支机构不在同一县市的,分支机构申报纳税的主管税务机关是()
下列疾病与肝癌的发生有关的是
滤线栅铅条延长线的聚焦线到栅平面的距离称为
在幼儿园里,一男孩2岁,发热伴咳嗽2~3天,初拟诊为上呼吸道感染,次日体温更高,皮肤可见红色斑丘疹,考虑麻疹,即送回家。
背景资料:某施工单位承接了高速公路施工,K8+126处有一座主跨为9×30m预应力混凝土简支空心板梁桥,该桥为旱桥,中间桥墩位于低洼地带,地下水较低,地质条件为硬土。基础采用人工挖孔桩施工工艺,上部结构采用预制吊装,梁体采用后张法施工。
大型回旋曲式可用下列()图式表示。
学会安静地听同伴说话,不随便插嘴是对()年龄段的要求。
AnAmericanweddingbeginswithengagement.Traditionally,ayoungmanasksthefatherofhis【S1】______forpermissiontomarry
Moreandmoreforeignstudentsexperiencetheirindependentlifeinthequesttogainawesterneducation.They【B1】______anunfa
最新回复
(
0
)