首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2017-01-04
91
问题
假设有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/tQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
布雷顿森林体系是如何建立的,包括哪些内容?
简述士族的源流和在西晋的发展过程。
简述士族的源流和在西晋的发展过程。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
袁世凯得以复辟帝制不是因为()
下列关于清朝军机处的叙述,不正确的是()。
隋唐科举制的进士科最先出现在()。
已知散列函数为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散列
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。写出4种寻址方式下,有效地址EA的表达式。
随机试题
交换积分次序.
患者女性,42岁,反复低热并盗汗2个月。查体:左颈部锁骨上可及一3.0cm×3.5cm包块,无压痛,双侧腋窝多发肿大淋巴结。血常规无异常。B超示脾大,腹膜后、髂内外及双侧腹股沟区多发肿大淋巴结。TB-Ab阴性。肿瘤标志物蛋白芯片C12均在正常水平。左颈部锁
基底细胞液化常见于
碘解磷定对下列药物中毒疗效差或无效的是()。
某生产企业当年实现自产产品销售收入500万元,当年发生广告费60万元,发生业务招待费5万元,已知企业上年有35万元的广告费超标,广告费和业务招待费合计调整应纳税所得额()万元。
AmongthemorecolorfulcharactersofLeadville’sgoldenagewereH.A.W.Taborandhissecondwife,ElizabethMcCourt,better
信息呈现的顺序会对社会认知产生影响,这种现象是()
《诗经》:诗集()
古人云:“凡事预则立,不预则废。”有了计划,才能够胸中有______,行动有目标,工作有程序,才能够增强自觉性,减少______性,调动积极性。
关于实时操作系统(RTOS)的任务调度器,以下描述中正确的是(45)。
最新回复
(
0
)