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

admin2019-01-30 79

问题假设有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://www.kaotiyun.com/show/vdRi777K

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

计算机408

学硕统考专业

相关试题推荐

提出天人关系应当“交相胜，还相用”的观点是()。
下列法律文件中，规定内阁对君主负责的是()。
希腊化时代控制希腊半岛的是()。
下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑，分取指周期、取第一操作数周期，取第二操作数周期、执行周期四个机器周期，每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0，(R1)完成功
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：(1)请说明系统处于不安全状态；(2
给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。
IEEE754标准规定的64位浮点数格式中，符号位为1位，阶码为11位，尾数为52位。则它所能表示的最小规格化负数为()。
什么是单重分组和双重分组跳跃进位链?一个按3，5，3，5分组的双重分组跳跃进位链(最低位为第O位)，试问大组中产生的是哪几位进位?与4，4，4，4分组的双重分组跳跃进位链相比，试问产生全部进位的时间是否一致?为什么?
某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。

随机试题

特别行政区行政长官任期为()
简述管理心理学与普通心理学的关系。
A1引用样式是Excel默认的引用样式，列以大写英文字母表示，从A开始到IV结束，共计_________列。
依沙吖啶羊膜腔内注射引产时从穿刺针回抽为血液，针头最有可能刺入
方位术语中小腿内侧常称为
患者，男性，30岁，渔民。3周来高热，疲乏不适，腹胀，食欲减退，应用抗生素后发热逐渐消退，症状好转。今天下午突感腹部剧痛，面色苍白，随后高热、呕吐来诊。体检：T39℃，全腹肌紧张明显，压痛及反跳痛阳性。血白细胞12．5×109／L，中性粒细胞84％，淋巴细
患儿，3岁，因肺炎入院。经治疗好转又突发高热39．5℃，呼吸困难，右肺叩诊浊音。该患儿可能并发了()
心理咨询师在咨询中使用的提问方式不包括()。施测WAIS-RC，一般做法是()。
一个消费者有49元用以购买X和Y，X和Y都是离散商品，X的价格是每单位5元，Y的价格是每单位11元，他的效用函数为U(X，Y)=3X2+6Y2，他将如何选择他的消费组合?()(2013年上海财经大学80l经济学)
ComeSeptember,thecampusesofAmericawillbeswarmingnotjustwithreturningundergraduates,butalsowithemployersseton

最新回复(0)

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

计算机408

学硕统考专业

提出天人关系应当“交相胜，还相用”的观点是()。

下列法律文件中，规定内阁对君主负责的是()。

希腊化时代控制希腊半岛的是()。

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

IEEE754标准规定的64位浮点数格式中，符号位为1位，阶码为11位，尾数为52位。则它所能表示的最小规格化负数为()。

什么是单重分组和双重分组跳跃进位链?一个按3，5，3，5分组的双重分组跳跃进位链(最低位为第O位)，试问大组中产生的是哪几位进位?与4，4，4，4分组的双重分组跳跃进位链相比，试问产生全部进位的时间是否一致?为什么?

某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。

特别行政区行政长官任期为()

简述管理心理学与普通心理学的关系。

A1引用样式是Excel默认的引用样式，列以大写英文字母表示，从A开始到IV结束，共计_________列。

依沙吖啶羊膜腔内注射引产时从穿刺针回抽为血液，针头最有可能刺入

方位术语中小腿内侧常称为

患儿，3岁，因肺炎入院。经治疗好转又突发高热39．5℃，呼吸困难，右肺叩诊浊音。该患儿可能并发了()

心理咨询师在咨询中使用的提问方式不包括()。施测WAIS-RC，一般做法是()。

一个消费者有49元用以购买X和Y，X和Y都是离散商品，X的价格是每单位5元，Y的价格是每单位11元，他的效用函数为U(X，Y)=3X2+6Y2，他将如何选择他的消费组合?()(2013年上海财经大学80l经济学)

ComeSeptember,thecampusesofAmericawillbeswarmingnotjustwithreturningundergraduates,butalsowithemployersseton