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

admin2019-08-15 105

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

学硕统考专业

相关试题推荐

1956年11月，中共八届二中全会决定开展的全党整风运动要反对的错误倾向是()。
认识到乾嘉时期人口膨胀带来的系列问题，明确指出这种弊端的是()
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现
设一段正文由字符集{A，B，C，D，E，F)中的字母组成，这6个字母在正文中出现的次数分别为{12，18，26，6，4，34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字
在AOE网络中关键路径叙述正确的是()。
某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR，MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
下面关于图的存储的叙述中，正确的是()。
假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。
设有一个双向链表h，每个结点中除有prior，data和next三个域外，还有一个访问频度域freq，在链表被起用之前，每个结点中的freq域都被初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域中的值加一，并调整表中
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享卡H同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点，链表结点结构为请设计一个时间上尽可能高效的算法，找出

随机试题

汉语方言之间的差异，突出表现在()方面。
降职程序的主要步骤。
下列关于腹裂，描述正确的有
发生压疮的最主要原因是
工厂造价构成中，设备及工器具购置费包括()。
某公司经理程某2006年1月个人收入情况如下：(1)取得工资6000元，年终业绩兑现奖金90000元；(2)在企业家论坛讲座取得收入8000元，当即通过政府部门向农村义务教育捐赠5000元；(3)取得定期存款利息8000元，其中19
张女士为A市甲超市(增值税一般纳税人)财务管理人员，她从2017年12月份开始建立家庭消费电子账，12月份从甲超市购买了下列商品：(1)高档粉底液一盒，支出400元。(2)白酒1000克，支出640元。(3)食品支出1010元，其中：橄榄油25
下列做法中符合新型工业化道路发展要求的是()。
28个连续奇数的和是2016，则这28个连续奇数最大的一个是()．
构建社会主义和谐社会最根本的政治保证是()

最新回复(0)

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

计算机408

学硕统考专业

1956年11月，中共八届二中全会决定开展的全党整风运动要反对的错误倾向是()。

认识到乾嘉时期人口膨胀带来的系列问题，明确指出这种弊端的是()

在AOE网络中关键路径叙述正确的是()。

下面关于图的存储的叙述中，正确的是()。

假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。

汉语方言之间的差异，突出表现在()方面。

降职程序的主要步骤。

下列关于腹裂，描述正确的有

发生压疮的最主要原因是

工厂造价构成中，设备及工器具购置费包括()。

某公司经理程某2006年1月个人收入情况如下：(1)取得工资6000元，年终业绩兑现奖金90000元；(2)在企业家论坛讲座取得收入8000元，当即通过政府部门向农村义务教育捐赠5000元；(3)取得定期存款利息8000元，其中19

张女士为A市甲超市(增值税一般纳税人)财务管理人员，她从2017年12月份开始建立家庭消费电子账，12月份从甲超市购买了下列商品：(1)高档粉底液一盒，支出400元。(2)白酒1000克，支出640元。(3)食品支出1010元，其中：橄榄油25

下列做法中符合新型工业化道路发展要求的是()。

28个连续奇数的和是2016，则这28个连续奇数最大的一个是()．

构建社会主义和谐社会最根本的政治保证是()