首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2018-08-12
28
问题
假设有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/QMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于清朝军机处的叙述,不正确的是()。
三大战役的先后顺序是()
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
中国共产党在下列哪次会议上规定了党的最高纲领和最低纲领?()
下面哪项条约没有涉及德国的赔款问题?()
对《魏玛宪法》的内容和影响叙述不正确的是()。
全国高校院系调整的具体时间是()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
随机试题
按照劳动合同期限的不同,劳动合同可分为()
胃肠激素的生理作用包括
组成中含有半夏、黄芩的方剂有
患者,男,24岁。夏秋季因饮食不慎出现泄泻腹痛,泻而不爽,胸腹满闷,口干不欲饮,舌苔微黄而腻,脉濡缓。此时应诊断为
限定放大摄影的放大倍数,取决于
某设备三年前购买的原始成本是90000元,目前的账面价值为40000元,经过评估,该设备现在的净残值为18000元。则在设备更新方案比选中,该设备的沉没成本是(A)元。
如何克服文学批评中的主观主义?如何恢复批评的尊严和功能?解决问题的办法,从根本上来说,还是要提高批评家的______素质。
有以下程序:#includeintf(intx,inty){return((y—x)*x);}voidmain(){inta=3,b=4,c=5,d;d=f(f(a,b),f(a,c));
A、 B、 C、 A
ThismonthSingaporepassedabillthatwouldgivelegalteethtothemoralobligationtosupportone’sparents.CalledastheM
最新回复
(
0
)