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

admin2019-08-15 100

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

学硕统考专业

相关试题推荐

1908年8月，清政府颁布()，规定皇帝具有至高无上的权力。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：在甲骨文的研究流域，对甲骨文研究作出了重大贡献，被后人称为“甲骨四堂”的四位学者是(
乾隆时期()明确规定了驻藏大臣监督办理西藏事务，地位与达赖、班禅相等，监督履行“金瓶掣签”等
从“鲁尔危机”的发生到《道威斯计划》的实施，西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。
在集中式总线仲裁中，()方式响应时间最快。
某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
指令系统字长16位，每个地址码为6位，采用扩展操作码的方式，试设计14条二地址指令，100条一地址指令，100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图，其中只给出了二地址指令的译码逻辑，试补全一地址指令和零地址指令的
某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1
有效容量为128KB的Cache，每块16字节，8路组相联。字节地址为1234567H的单元调入该Cache，其Tag应是()。

随机试题

舞蹈作品：舞剧《丝路花雨》
关于外阴阴道假丝酵母菌的特征，正确的是
散发性甲状腺功能减低性早熟
患者男，45岁，近3天大便秘结，身热，腹满胀痛，拒按，舌红，苔黄燥，脉滑而数。其治法应为
全科医学的主要特征不包括
X线机控制电路不设有哪种保护
图纸会审是由()单位负责组织。
出入境检验检疫机构签发的检验检疫证明具有法律效用，对买卖双方都有约束力。(　　)
反映多个项目或变量变动的相对数是()。
ElectromagneticEnergy1Whitelightseemstobeacombinationofallcolors.Theenergythatcomesfromasourceoflighti

最新回复(0)

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

计算机408

学硕统考专业

1908年8月，清政府颁布()，规定皇帝具有至高无上的权力。

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

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

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

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1

有效容量为128KB的Cache，每块16字节，8路组相联。字节地址为1234567H的单元调入该Cache，其Tag应是()。

舞蹈作品：舞剧《丝路花雨》

关于外阴阴道假丝酵母菌的特征，正确的是

散发性甲状腺功能减低性早熟

患者男，45岁，近3天大便秘结，身热，腹满胀痛，拒按，舌红，苔黄燥，脉滑而数。其治法应为

全科医学的主要特征不包括

X线机控制电路不设有哪种保护

图纸会审是由()单位负责组织。

出入境检验检疫机构签发的检验检疫证明具有法律效用，对买卖双方都有约束力。( )

反映多个项目或变量变动的相对数是()。

ElectromagneticEnergy1Whitelightseemstobeacombinationofallcolors.Theenergythatcomesfromasourceoflighti

出入境检验检疫机构签发的检验检疫证明具有法律效用，对买卖双方都有约束力。(　　)