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

admin2023-02-06 38

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

学硕统考专业

相关试题推荐

一个好的教师必须挚爱自己的职业，对教学有极大的热情，这样他才可能积极地投入到教学工作中去。这体现了()是成为好教师的关键。
晓阳的母亲在做饭时，晓阳为了帮助母亲便递给其一个碟子，母亲接过晓阳手中的碟子，晓阳很高兴，认为自己帮了母亲一个大忙。根据埃里克森对人的心理发展的阶段划分，此例中的晓阳可能处于()。
按照我国婚姻法的规定，结婚必须具备的条件包括()。
关于发展性教师评价，以下说法正确的有()。
学生李明在上学的路上，因帮助突然生病的路人而迟到。老师征询大家的意见，是否按班规对李明进行处罚。张阳认为，李明帮助别人是对的，不应该处罚他。张阳的道德发展水平最可能处于()。
深度学习是指在模仿人脑机制的神经网络中，对人工神经元的层进行了“多层处理”。深度学习不仅可以让AI(人工智能)读取大量图片，还可以让AI自主提取图片特征。得益于深度学习技术的面世，只要有大量数据，AI就能以极高的准确率进行学习，从而大幅度拓展了AI的应用范
微生物是地球最早出现的生命形式。这种简单而古老的生命决定了地球演化的方向和进程，推动了土壤的发生和发育，孕育了人类的文明。事实上，土壤中蕴藏的微生物的多样性，被称为地球关键元素循环过程的引擎，是联系大气圈、水圈、岩石圈及生物圈物质与能量交换的重要纽带，维系
设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。
若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是()。
在线索二叉树中，结点*p没有左子树的充要条件是()。

随机试题

Excel中，设置两个条件的排序目的是______。
下列关于有氧运动的注意事项错误的是
电雷管的电阻值应用()逐个检验，电阻值应符合产品说明书的规定值。
某投资方案的净现金流量如下表，其静态投资回收期为()年。
现行的增值税实行的是价内税，因此产品成本中包括外购投入物所支付的进项税。()
企业向租赁公司租入一台设备，价值500万元，合同约定租赁期满时残值5万元归租赁公司所有，租期为5年，租费综合率为12％。若采用先付租金的方式，则平均每年支付的租金为()万元。[已知：(P／A，12％，4)=3．0373，(P／A，12％，5)=3．
指出材料1中的错误及其原因。指出材料2所坚持的错误道路。
有以下程序　　　　#include＜string.h＞　　　　main()　　　　{　char　p[20]={’a’，’b’，’c’，’d’}，q[]="abc"，r[]="abcde"；　　　　　　strcat(p，r)；strcpy(p+strlen(
HowmanypeoplewereshotinthemilitarybaseinTexas?
A、Itscustomsvaryfromonecountrytoanother.B、Itisarrangedbyparentsinsomecountries.C、Ithasnothingtodowithther

最新回复(0)

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

计算机408

学硕统考专业

一个好的教师必须挚爱自己的职业，对教学有极大的热情，这样他才可能积极地投入到教学工作中去。这体现了()是成为好教师的关键。

晓阳的母亲在做饭时，晓阳为了帮助母亲便递给其一个碟子，母亲接过晓阳手中的碟子，晓阳很高兴，认为自己帮了母亲一个大忙。根据埃里克森对人的心理发展的阶段划分，此例中的晓阳可能处于()。

按照我国婚姻法的规定，结婚必须具备的条件包括()。

关于发展性教师评价，以下说法正确的有()。

学生李明在上学的路上，因帮助突然生病的路人而迟到。老师征询大家的意见，是否按班规对李明进行处罚。张阳认为，李明帮助别人是对的，不应该处罚他。张阳的道德发展水平最可能处于()。

设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。

若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是()。

在线索二叉树中，结点*p没有左子树的充要条件是()。

Excel中，设置两个条件的排序目的是______。

下列关于有氧运动的注意事项错误的是

电雷管的电阻值应用()逐个检验，电阻值应符合产品说明书的规定值。

某投资方案的净现金流量如下表，其静态投资回收期为()年。

现行的增值税实行的是价内税，因此产品成本中包括外购投入物所支付的进项税。()

指出材料1中的错误及其原因。指出材料2所坚持的错误道路。

有以下程序 #include＜string.h＞ main() { char p[20]={’a’，’b’，’c’，’d’}，q[]="abc"，r[]="abcde"； strcat(p，r)；strcpy(p+strlen(

HowmanypeoplewereshotinthemilitarybaseinTexas?

A、Itscustomsvaryfromonecountrytoanother.B、Itisarrangedbyparentsinsomecountries.C、Ithasnothingtodowithther

有以下程序　　　　#include＜string.h＞　　　　main()　　　　{　char　p[20]={’a’，’b’，’c’，’d’}，q[]="abc"，r[]="abcde"；　　　　　　strcat(p，r)；strcpy(p+strlen(