首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-12-10
58
问题
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
选项
A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)
答案
C
解析
考查邻接表的性质。和顶点v相关的边包括出边和入边,对于出边,只需要遍历v的顶点表即可;对于入边,则需要遍历整个邻接表。删除与某顶点v相关的所有边过程如下:先删除下标为v的顶点表结点的单链表,出边数最多为,n一1,对应时间复杂度为O(n),再扫描所有边表结点,删除所有的入边,对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。
转载请注明原文地址:https://kaotiyun.com/show/7L3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器一存储器(R—M)二地址变址类型(地址码范围在-128
适合多道程序运行的存储管理方法中,存储保护主要是()。
某虚拟存储系统中有一个进程共有6页(0~5),其中代码占3页(0~2),数据占1页(3),数据堆占1页(4),用户栈占1页(5)。它们依次存放在外存的22,23,25,26存储块。当前,代码页已经分配在物理内存的66,67,87页,数据页为31,并已经进行
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:如果Cache为8行,主存16块,分别采用三种方式映射主存的第9块
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TCP/IP软件进行常规配置后,发现这两台机器上的网络应用程序不能够正常通信。这是为什么?
内部网关协议包括()。
甲乙两台主机通过TCP进行通信,甲方发送了一个带有FIN标志的数据段,所表示的含义是()。
下列关于IP路由器功能的描述中,正确的是I.运行路由协议,设置路由表Ⅱ.监测到拥塞时,合理丢弃IP分组Ⅲ.对收到的IP分组头进行差错校验,确保传输的IP分组不丢失Ⅳ.根据收到的IP分组的目的IP地址,将其转发到合适的输出线路上
当使用鼠标点取一个万维网文档时,若该文档除了有文本外,还有一个本地.gif图像和两个远地.gif图像,则需要建立()。
随机试题
试述楚辞的渊源及其文体特点。
某企业有某一低值易耗品,原价1000元,预计可使用8个月,至评估基准日已使用2个月,评估基准日该低值易耗品的市价为800元,则该低值易耗品的评估值为()
用盐酸滴定液滴定氨水时,使用的指示剂是
前颅底骨折特点
关于佛教、道教、伊斯兰教,说法错误的是()。
社会工作研究的范式包括()。
《秋千》《浴女》等绘画作品的作者,是18世纪__________国画家__________。
Theexperimentconductedbytheresearcherwasmeantto______.Whatisoneofthepossibleconclusionsoftheexperiment?
下列关于数据仓库的叙述中,哪一项是不正确的?______
Ittookmeexactlyaweektocompletethework.
最新回复
(
0
)