首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2018-08-12
60
问题
假设有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
学硕统考专业
相关试题推荐
“文化大革命”结束后,在纠正“文化大革命”错误的过程中,整个过程受到()的严重阻碍。
西北战场的关键一仗,由此,西北野战军由防御转入进攻,掌握了战争的主动权的战役是()
巴黎和会召开的时间是()。
下列人物中与康熙收复台湾没有关系的是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
下列关于20世纪历史的叙述,全部错误的是()。①朝鲜建国的时间早于中国②1948年3月,英国、法网、比利时、荷兰、卢森堡5国缔结了《合作和集体防御条约》即《五国和约》③1950年,周恩来到达莫斯科,中苏缔结了《中苏互不侵犯条约》,标志着社会主义阵
下列哪一事件之后,明与蒙古之间出现了“自宣大至甘肃,不用兵者二十年”的情形?()
判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用的是()。
下列叙述正确的个数是()。(1)m=2的平衡m路查找树是AVL树(2)m=3的平衡m路查找树是2—3树(3)m=2的平衡m路查找树的叶结点不一定在同一层(4)m阶B一树的叶结点必须在同一层(5)m阶B一树是平衡m路查找树(6)平衡m路查
随机试题
糖皮质激素对血液成分的影响有()。
为了增加X射线拍片的灵敏度,焊缝余高值不能太大。()
管道水锤有什么危害性?
个体劳动者的主要收入属于()
塔器类设备的机械化吊装机械有()起重机。
信用证是指银行有条件的付款承诺,即开证银行依照客户(开证申请人)的要求和指示,承诺在符合信用证条款的情况下,凭规定的单据()。
准备在甲、乙两地间竖电杆,当两杆间隔为30米比间隔40米时多用电杆30根。求甲、乙两地相距多少米?()
阅读下列材料,回答下列题。2010年一季度,我国水产品贸易进出口总量158.7万吨,进出口总额40.9亿美元,同比分别增长14.2%和29.0%。其中,出口量67.1万吨,出口额26.5亿美元,同比分别增长11.7%和24.9%;进口量91.6万吨
将时间上连续,频带有限的声音信号转化为时间上离散的一组值的过程称为______。
A、 B、 C、 A
最新回复
(
0
)