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

admin2023-02-06 59

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

学硕统考专业

相关试题推荐

根据下面资料，回答下列问题。【资料】9岁的田田是一个很聪明的孩子，语言表达能力比较突出，思维清晰、反应敏捷。在学校里有时与同学有小纠纷，他总说是别人的错而不反思自己的问题。他平时喜欢做手工和小种植，在学习上却不愿意花精力投入。家长对孩子的管理是粗
在教小学数学“按比例分配”时，教师在讲新课前向全班提问：“把12棵树分给两个组去栽，每个小组分几棵?”学生齐声回答：“6棵!”教师问：“有没有不同意见呢?”发现孙同学眉头微蹙，教师就提醒说：“大家要认真思考，有同学可能把你们的答案推翻了哦。”学生们于是开始
品德是由道德认识、道德情感、道德意志、道德行为等四个要素构成的综合体。下列关于四者关系的表述，正确的有()。
德育原则和德育规律的关系是()。
习近平总书记在北京师范大学看望教师和学生时说：“一个人遇到好老师是人生的幸运，一个学校拥有好老师是学校的光荣，一个民族源源不断涌现出一批叉一批好老师则是民族的希望。”好老师关系到民族的振兴与发展，习近平总书记提出“四有”好老师，“四有”即有理想信念、有道德
站在新的历史起点上，展望建设现代化国际瓷都的未来，拥有2000年冶陶史、1000年官窑史、600年御窑史及新中国成立以来70年陶瓷生产史的景德镇，必将继续传承陶瓷文化，深度挖掘千年瓷都人文________，创新陶瓷产业，构建新时代陶瓷产品和话语体系，扩大陶
过去你可能有想不起要买什么的时刻，现在不会了，每一样内容里都________了营销，别人购物发了朋友圈会启发你也想买，还有各种各样的广告。现代人就像转笼里的仓鼠，在工作、消费的循环里________。依次填入画横线部分最恰当的一项是：
微生物是地球最早出现的生命形式。这种简单而古老的生命决定了地球演化的方向和进程，推动了土壤的发生和发育，孕育了人类的文明。事实上，土壤中蕴藏的微生物的多样性，被称为地球关键元素循环过程的引擎，是联系大气圈、水圈、岩石圈及生物圈物质与能量交换的重要纽带，维系
有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈的次序不包括()。

随机试题

Itisreportedthatcrimesaremostlikelytohappenincities______alargepercentageofunemployment.
A、规范器官移植的国际文献B、体现我国唐代大医学家孙思邈的医德思想的医德文献C、体现古希腊医学家HippoCrates的医德思想的医德文献D、作为国际上进行基因疗法行为规范的文件E、规范人体实验行为的国际文件《大医
股份具有以下主要特点()。
计算机与手工账务处理的记账和结账等程序是完全相同的。()
【给定资料】1.在A市C区商务委，一张“蔬菜地图”正在绘制中，地图上密密麻麻分布着1282个菜站。2018年，这张地图上还将再增加至少60个网点，到2019年年底，每个社区将拥有不少于两个菜站，且每千人拥有50平方米以上售菜区。平房乡福
许多国家的著名城市都是沿河而建的，下列组合正确的是：
计算机中对数据进行加工与处理的部件通常称为【】。
如下表所示，在某DHCP客户机执行ipeonfig／release和ipconfig／renew命令时捕获了5条报文，表中列出报文的部分信息并对第4条报文进行了解析。若执行命令前后客户机的IP地址没有改变，分析表中的信息并补全空白处的信息。
若有以下程序#includechar*a＝"you"；charb[]＝"WelcomeyoutoChina!"；main(){inti,j＝0；char*p；for(i＝0；b[i]!＝’＼0’；i＋＋
oil

最新回复(0)

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

计算机408

学硕统考专业

品德是由道德认识、道德情感、道德意志、道德行为等四个要素构成的综合体。下列关于四者关系的表述，正确的有()。

德育原则和德育规律的关系是()。

有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈的次序不包括()。

Itisreportedthatcrimesaremostlikelytohappenincities______alargepercentageofunemployment.

A、规范器官移植的国际文献B、体现我国唐代大医学家孙思邈的医德思想的医德文献C、体现古希腊医学家HippoCrates的医德思想的医德文献D、作为国际上进行基因疗法行为规范的文件E、规范人体实验行为的国际文件《大医

股份具有以下主要特点()。

计算机与手工账务处理的记账和结账等程序是完全相同的。()

许多国家的著名城市都是沿河而建的，下列组合正确的是：

计算机中对数据进行加工与处理的部件通常称为【】。

如下表所示，在某DHCP客户机执行ipeonfig／release和ipconfig／renew命令时捕获了5条报文，表中列出报文的部分信息并对第4条报文进行了解析。若执行命令前后客户机的IP地址没有改变，分析表中的信息并补全空白处的信息。

若有以下程序#includechar*a＝"you"；charb[]＝"WelcomeyoutoChina!"；main(){inti,j＝0；char*p；for(i＝0；b[i]!＝’＼0’；i＋＋

oil

若有以下程序#includechara＝"you"；charb[]＝"WelcomeyoutoChina!"；main(){inti,j＝0；charp；for(i＝0；b[i]!＝’＼0’；i＋＋