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

admin2019-08-15 129

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

选项 A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)

答案C

解析删除与某顶点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

转载请注明原文地址:https://kaotiyun.com/show/EOCi777K

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

计算机408

学硕统考专业

相关试题推荐

如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：(1)为了使IP不分片，主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。
某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。
一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。
简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的值至少为()。
下列关于图的叙述中，正确的是____。I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；
设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。
若x=103，y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是_______。

随机试题

下列有关现代教育的叙述，错误的是【】
企业总机构和分支机构不在同一县市的，分支机构申报纳税的主管税务机关是()
下列疾病与肝癌的发生有关的是
滤线栅铅条延长线的聚焦线到栅平面的距离称为
在幼儿园里，一男孩2岁，发热伴咳嗽2～3天，初拟诊为上呼吸道感染，次日体温更高，皮肤可见红色斑丘疹，考虑麻疹，即送回家。
背景资料：某施工单位承接了高速公路施工，K8+126处有一座主跨为9×30m预应力混凝土简支空心板梁桥，该桥为旱桥，中间桥墩位于低洼地带，地下水较低，地质条件为硬土。基础采用人工挖孔桩施工工艺，上部结构采用预制吊装，梁体采用后张法施工。
大型回旋曲式可用下列()图式表示。
学会安静地听同伴说话，不随便插嘴是对()年龄段的要求。
AnAmericanweddingbeginswithengagement.Traditionally,ayoungmanasksthefatherofhis【S1】______forpermissiontomarry
Moreandmoreforeignstudentsexperiencetheirindependentlifeinthequesttogainawesterneducation.They【B1】______anunfa

最新回复(0)

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

计算机408

学硕统考专业

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。

简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的值至少为()。

下列关于图的叙述中，正确的是____。I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

若x=103，y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是_______。

下列有关现代教育的叙述，错误的是【】

企业总机构和分支机构不在同一县市的，分支机构申报纳税的主管税务机关是()

下列疾病与肝癌的发生有关的是

滤线栅铅条延长线的聚焦线到栅平面的距离称为

在幼儿园里，一男孩2岁，发热伴咳嗽2～3天，初拟诊为上呼吸道感染，次日体温更高，皮肤可见红色斑丘疹，考虑麻疹，即送回家。

大型回旋曲式可用下列()图式表示。

学会安静地听同伴说话，不随便插嘴是对()年龄段的要求。

AnAmericanweddingbeginswithengagement.Traditionally,ayoungmanasksthefatherofhis【S1】______forpermissiontomarry

Moreandmoreforeignstudentsexperiencetheirindependentlifeinthequesttogainawesterneducation.They【B1】______anunfa