假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )

admin2023-02-06 61

问题假设有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/4IwD777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

某校为谋取利益，违反法律规定，为不具备条件的人员颁发学位证书。对此，下列说法正确的是()。
李磊和几个平时关系不错的同班同学经常一起玩耍，久而久之便形成了一个小群体。他们组成的小群体经常会与班主任和班委会对抗，还不参加集体活动。他们这个群体属于()。
班级授课制是指学生按年龄和文化程度分成固定人数的班级，教师根据课程计划和规定时间表进行教学的一种组织形式。下列不属于班级教学的优点的是()。
学生的认知发展虽然具有一定的方向和先后顺序，但是这种发展是可逆的。()
①发动机为了持续提供稳定的动力，需要曲轴、机油过滤器、交流发电机、风扇、分电盘、阀门、线圈和气缸等零部件的配合②每一个零部件，都会增加动力的损耗③汽车是工业社会发展至今最复杂的工业产品，是数以千计机械部件的精密集合体④因为这么复杂的机械结构，机械汽车
在数宁化多媒体时代，媒介参与的深度和广度日渐拓展，数字技术应用于文化遗产的保护已从原始的简单记录发展到对文化遗产的精准________，运用数字输入、摄像等各种数字化技术对文化遗产进行多形式的________，建立数字化的文化遗产档案和“非遗”博物馆等，都
文化是怎么来的?似乎是一些学者、作家、艺术家、宗教家折腾出来的，其实这一看法过于________。往深层次看，所有文化形态后面都有某种生态的条件和诱因，广义的生态元素——包括地理、气候、物种等——总是参与对文化形成的制约和________。填入画横线部分最
2020年9月1日，习近平总书记在中央全面深化改革委员会第十五次会议上强调，加快形成以国内大循环为主体、国内国际双循环相互促进的新发展格局，是根据我国发展阶段、环境、条件变化作出的战略决策，是事关全局的()变革。
下列二叉排序树中，满足平衡二叉树定义的是()。

随机试题

画出连续精馏塔流程的典型图。
治疗散发性甲状腺功能减低症治疗Ⅱ型糖尿病
关于多囊卵巢综合征下述哪项是正确的
患者，女，28岁。近日感外阴痒、阴道分泌物增多就诊，妇科检查：白带呈豆渣样，阴道黏膜红肿并附有白膜，考虑感染的病原体是
　　男性，30岁，1年前下岗。近5个月来觉得邻居都在议论他，常不怀好意地盯着他，有时对着窗外大骂，自语、自笑，整天闭门不出，拨110电话要求保护。有诊断意义的症状还包括
城镇燃气管道按输送燃气的压力分级，其中低压燃气管道的压力范围是()。
关于建设用地的取用及使用年限，下列说法中正确的是()。
中国人自古以来就被人称为“炎黄子孙”，其中“黄”指的是（）。
In2012,IhadjustrecoveredfromaseriousillnesswhenIreceivedaninvitationtoawriter’sconferenceinOrlando,FloridA
Foryears,nonprofithospitalshaveshiedawayfromquantifyingtheamountofcharitablecaretheyprovidecommunities.Hospit

最新回复(0)

假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )

计算机408

学硕统考专业

某校为谋取利益，违反法律规定，为不具备条件的人员颁发学位证书。对此，下列说法正确的是()。

李磊和几个平时关系不错的同班同学经常一起玩耍，久而久之便形成了一个小群体。他们组成的小群体经常会与班主任和班委会对抗，还不参加集体活动。他们这个群体属于()。

班级授课制是指学生按年龄和文化程度分成固定人数的班级，教师根据课程计划和规定时间表进行教学的一种组织形式。下列不属于班级教学的优点的是()。

学生的认知发展虽然具有一定的方向和先后顺序，但是这种发展是可逆的。()

下列二叉排序树中，满足平衡二叉树定义的是()。

画出连续精馏塔流程的典型图。

治疗散发性甲状腺功能减低症治疗Ⅱ型糖尿病

关于多囊卵巢综合征下述哪项是正确的

患者，女，28岁。近日感外阴痒、阴道分泌物增多就诊，妇科检查：白带呈豆渣样，阴道黏膜红肿并附有白膜，考虑感染的病原体是

男性，30岁，1年前下岗。近5个月来觉得邻居都在议论他，常不怀好意地盯着他，有时对着窗外大骂，自语、自笑，整天闭门不出，拨110电话要求保护。有诊断意义的症状还包括

城镇燃气管道按输送燃气的压力分级，其中低压燃气管道的压力范围是()。

关于建设用地的取用及使用年限，下列说法中正确的是()。

中国人自古以来就被人称为“炎黄子孙”，其中“黄”指的是（）。

In2012,IhadjustrecoveredfromaseriousillnesswhenIreceivedaninvitationtoawriter’sconferenceinOrlando,FloridA

Foryears,nonprofithospitalshaveshiedawayfromquantifyingtheamountofcharitablecaretheyprovidecommunities.Hospit

　　男性，30岁，1年前下岗。近5个月来觉得邻居都在议论他，常不怀好意地盯着他，有时对着窗外大骂，自语、自笑，整天闭门不出，拨110电话要求保护。有诊断意义的症状还包括