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

admin2019-08-15 97

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

学硕统考专业

相关试题推荐

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。
在4×100米接力赛中，4个运动员之间存在如下关系：运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交棒给运动员3；运动员3也只有接到运动员2传来的接力棒后才能往前跑，他跑完100米
在集中式总线仲裁中，()方式响应时间最快。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理，也可以产生类似的算法，不妨
已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列
若线性表最常用的运算是查找第i个元素及其前驱的值，则采用()存储方式节省时间。
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路
下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是()。
偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是_______。

随机试题

A．头低卧位B．高半坐位C．低半坐位D．侧卧位E．平卧位(2004年第108题)胃大部切除术全麻清醒后，病人应采取的体位是
关于经皮输精管注射粘堵法，下列哪项叙述错误
下列各项，不属瘿痈特征的是
患者，男性，53岁。腹痛腹胀，呕吐胃内容物及胆汁3小时。近4个月来时有腹胀，大便带黏液，大便次数增加，每日2～3次，无排便不尽及里急后重感。体检：T36℃，P90次／分钟，BP115／70mmHg；腹膨隆，未见肠型，腹软，右下腹可触及一斜行肿块，质韧
甲、乙签订了一份合同，约定由丙向甲履行债务，但丙履行债务的行为不符合合同的约定，甲可以请求丙或乙承担违约责任。()
山东省推进工业转型升级路径中所指出的培植发展4大新兴产业不包括：
三次产业分类法是根据社会生产活动历史发展的顺序对产业结构划分的方法。()
设A，B是两个事件，且令求问X，Y是否相互独立．
声卡的组成很简单，主要由一块主音频处理芯片、一块音频混合芯片和一块放大器电路组成。波形声音输入计算机时，模拟信号的取样与量化是由(　　　)完成。
JonathanGlater,avisitingassistantprofessoroflawattheUniversityofCalifornia,Irvine,andaformerreporterattheNew

最新回复(0)

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

计算机408

学硕统考专业

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

在集中式总线仲裁中，()方式响应时间最快。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

若线性表最常用的运算是查找第i个元素及其前驱的值，则采用()存储方式节省时间。

下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是()。

偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是_______。

A．头低卧位B．高半坐位C．低半坐位D．侧卧位E．平卧位(2004年第108题)胃大部切除术全麻清醒后，病人应采取的体位是

关于经皮输精管注射粘堵法，下列哪项叙述错误

下列各项，不属瘿痈特征的是

甲、乙签订了一份合同，约定由丙向甲履行债务，但丙履行债务的行为不符合合同的约定，甲可以请求丙或乙承担违约责任。()

山东省推进工业转型升级路径中所指出的培植发展4大新兴产业不包括：

三次产业分类法是根据社会生产活动历史发展的顺序对产业结构划分的方法。()

设A，B是两个事件，且令求问X，Y是否相互独立．

声卡的组成很简单，主要由一块主音频处理芯片、一块音频混合芯片和一块放大器电路组成。波形声音输入计算机时，模拟信号的取样与量化是由( )完成。

JonathanGlater,avisitingassistantprofessoroflawattheUniversityofCalifornia,Irvine,andaformerreporterattheNew

声卡的组成很简单，主要由一块主音频处理芯片、一块音频混合芯片和一块放大器电路组成。波形声音输入计算机时，模拟信号的取样与量化是由(　　　)完成。