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

admin2019-08-15 104

问题假设有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年召开的中共八大指出，我国国内主要矛盾的实质是()。
在4×100米接力赛中，4个运动员之间存在如下关系：运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交棒给运动员3；运动员3也只有接到运动员2传来的接力棒后才能往前跑，他跑完100米
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理，也可以产生类似的算法，不妨
在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。
将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题：(1)该TCP／IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

随机试题

输血后肝炎属于哪种感染慢性肝炎肝硬化合并自发性腹膜炎属于哪种感染
有关睑黄斑瘤，以下哪项是错误的
患者男性，48岁。手术后第二天，护士通过评估认为目前存在以下问题，属于首优问题的是
土工织物宽条拉伸试验的预负荷伸长是指在相当于最大负荷()的外加负荷下，所测的夹持长度的增加值，以mm表示。
下列关于和解的表述中，符合企业破产法规的有()。(2009年试题．旧)
查封、扣押物证、书证，就为了发现证明犯罪嫌疑人有罪的财物和文件。()
社会主义国家,促进社会主义经济迅速和健康发展的根本性问题是
编写如下程序：PrivateSubCommandl_Click()DimhumAsInteger．kAsInteger,nAsIntegernum=InputBox("请输入一个正整数：")k=
Cultureshockisapainfulexperiencewegothroughwhenweencountermanynewthingsinanothercountryandwe【1】______insom
ThespeedlimitonmostmajorhighwaysinMassachusettsis55mph/88kmwithsomesections,65mph/104kin.Whilemostnon-U.

最新回复(0)

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

计算机408

学硕统考专业

乾隆时期()明确规定了驻藏大臣监督办理西藏事务，地位与达赖、班禅相等，监督履行“金瓶掣签”等

1956年召开的中共八大指出，我国国内主要矛盾的实质是()。

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。

三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

输血后肝炎属于哪种感染慢性肝炎肝硬化合并自发性腹膜炎属于哪种感染

有关睑黄斑瘤，以下哪项是错误的

患者男性，48岁。手术后第二天，护士通过评估认为目前存在以下问题，属于首优问题的是

土工织物宽条拉伸试验的预负荷伸长是指在相当于最大负荷()的外加负荷下，所测的夹持长度的增加值，以mm表示。

下列关于和解的表述中，符合企业破产法规的有()。(2009年试题．旧)

查封、扣押物证、书证，就为了发现证明犯罪嫌疑人有罪的财物和文件。()

社会主义国家,促进社会主义经济迅速和健康发展的根本性问题是

编写如下程序：PrivateSubCommandl_Click()DimhumAsInteger．kAsInteger,nAsIntegernum=InputBox("请输入一个正整数：")k=

Cultureshockisapainfulexperiencewegothroughwhenweencountermanynewthingsinanothercountryandwe【1】______insom

ThespeedlimitonmostmajorhighwaysinMassachusettsis55mph/88kmwithsomesections,65mph/104kin.Whilemostnon-U.