首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2017-01-04
66
问题
假设有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
学硕统考专业
相关试题推荐
简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。
论述尼德兰革命的背景、主要过程及影响
简述工农武装割据存在与发展的原因和条件。
简述第二次世界大战对战后国际关系的影响。
标志着南京国民政府在全国范围内形式上完成统一的事件是()。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
有研究者提出,1850年以后的34年中,流人中国的白银是之前34年的两倍。出现这一现象的原因是()
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
设有一个带头结点的循环单链表,其结点值均为正整数。试设计一个算法,反复找出单链表中结点值最小的结点,并输出之,然后将该结点从中删除,直到单链表空为止,最后再删除表头结点。
某计算机的主存地址空间大小为256MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下:假定int类型数据用32位补码表示,程序
随机试题
健康教育计划实施质量控制的方法不包括
COPD诊断最有意义的检查为
A.推动作用B.温煦作用C.防御作用D.固摄作用E.气化作用气的哪种作用失常能影响整个物质代谢过程
股权投资基金信息披露义务人披露基金信息时,不得存在下列()行为。
明达公司2005年1月1日购入一项计算机软件程序,入账价值为525万元,预计使用年限为5年,法律规定有效使用年限为7年,明达公司在2005年12月31日为维护该计算机软件程序又支出12万元的升级更新费用,2006年12月31日该无形资产的可收回金额为320
1,2,3,6,12,24,()
学习《雨霖铃》,教师先以排比句幽默吟诵,引出“以情带景、情景交融”的手法,然后小结:“有人说,柳词之美,美在有景、有物、有人、有情,惟有情,才使万物富有神韵。这节课我们一起领略了落魄才子柳永哀怨缠绵的千古离歌。当然,这只是起到抛砖引玉的作用,希望大家在以后
公安工作的群众,广义的理解是()。
一些人说,公务员过着“两眼一睁直到熄灯”的生活,繁忙的工作导致没有时间学习。请问你如何看待工作与学习的关系?
曲面z=13一x2一y2将球面x2+y2+z2=25分成三部分,求这三部分曲面面积之比.
最新回复
(
0
)