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

admin2019-08-15 99

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

学硕统考专业

相关试题推荐

1908年8月，清政府颁布()，规定皇帝具有至高无上的权力。
古代两河流域最具代表性的文学作品是()。
就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50
荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，最后一个结点下标为k(起
设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。
若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；
在微指令的编码方式中，若微命令数相同，下列叙述中正确的是()。I．直接控制方式与编码控制方式的微指令长度相等Ⅱ．最短编码控制和直接控制方式不影响微指令字长Ⅲ．编码控制方式的微指令比直接控制方式的微指令短Ⅳ．

随机试题

PowerPoint的母版有__________。
冠状动脉瘘的超声心动图表现，错误的是
女性，34岁。2个月来胸骨后烧灼样不适与反胃就诊。反流物呈酸性，胃灼热与反胃常发生在餐后，进食时胸骨后有梗塞感。此种病人最适宜体位是
女性，26岁，双侧乳房胀疼1年，并触及不规则乳房肿块，伴有触痛，月经后症状有好转。诊断为
当分部工程较大或较复杂时，可按()等将其划分为若干子分部工程。
下列有关市场主体退出市场秩序的内容，错误的是()。
设有如下所示的某商场购物记录集合，每个购物篮中包含若干商品：现在要基于该数据集进行关联规则挖掘。如果设置最小支持度为60％，最小置信度为80％，则如下关联规则中，符合条件的是()。
数据库三级模式体系结构的划分，有利于保持数据库的【】。
YouwillhearaninterviewwithProf.JesseAusubelabouthisoptimisticattitudestowardsenvironmentalissuestoday.Asyouli
TextAfterlunch,withoutpermissionfromtheirparents,thetwoboyssetofftoexplorethepartofthebeachwhich【C1】_____

最新回复(0)

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

计算机408

学硕统考专业

1908年8月，清政府颁布()，规定皇帝具有至高无上的权力。

古代两河流域最具代表性的文学作品是()。

就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

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

PowerPoint的母版有__________。

冠状动脉瘘的超声心动图表现，错误的是

女性，34岁。2个月来胸骨后烧灼样不适与反胃就诊。反流物呈酸性，胃灼热与反胃常发生在餐后，进食时胸骨后有梗塞感。此种病人最适宜体位是

女性，26岁，双侧乳房胀疼1年，并触及不规则乳房肿块，伴有触痛，月经后症状有好转。诊断为

当分部工程较大或较复杂时，可按()等将其划分为若干子分部工程。

下列有关市场主体退出市场秩序的内容，错误的是()。

设有如下所示的某商场购物记录集合，每个购物篮中包含若干商品：现在要基于该数据集进行关联规则挖掘。如果设置最小支持度为60％，最小置信度为80％，则如下关联规则中，符合条件的是()。

数据库三级模式体系结构的划分，有利于保持数据库的【】。

YouwillhearaninterviewwithProf.JesseAusubelabouthisoptimisticattitudestowardsenvironmentalissuestoday.Asyouli

TextAfterlunch,withoutpermissionfromtheirparents,thetwoboyssetofftoexplorethepartofthebeachwhich【C1】_____