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

admin2019-08-15 115

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

学硕统考专业

相关试题推荐

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：建隆二年，赵匡胤采取了()的措施，收夺武将的兵权
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()
二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化以及相关考古遗址的发现和研究，是近年来史学界关注的一个热点。二里头文化的年代断限是()
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑，分取指周期、取第一操作数周期，取第二操作数周期、执行周期四个机器周期，每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0，(R1)完成功
在一个8级中断的系统中，硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8，通过中断屏蔽技术，将中断处理优先顺序设置为1→3→5→7→2→4→6→8，如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达，CPU在按优先顺序处理到第
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。
设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。
以下关于计算机存储器件的叙述，()是不正确的。
若x=103，y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是_______。

随机试题

灌注桩混凝土水下灌注时，其混凝土顶面标高至少要比设计标高高出()。
磺基水杨酸比色法测水中含铁量(三价铁离子)时，控制溶液的pH值为()。
在下列题中求各微分方程的通解或特解
肝气郁结型胁痛的主症特点是：瘀血阻络型胁痛的主症特点是：
A．有效性B．共享性C．层次性D．不完全性E．经济性以下分别属于信息的什么特性?时间上要及时、数量上要适当、质量上要准确、内容上要适用
茯苓的加工方法是（）。
滑模施工铁路桥墩时，模板高度宜设置为()。
下列不属于银行业金融机构的重组方式的是()。
班主任苏老师发现，承担本班数学教学任务的林老师经常让学生罚站。面对这种情况，苏老师应该()。
根据下表，回答以下问题下列哪类人员2009年网民人数比上年有所减少?()

最新回复(0)

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

计算机408

学硕统考专业

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：建隆二年，赵匡胤采取了()的措施，收夺武将的兵权

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化以及相关考古遗址的发现和研究，是近年来史学界关注的一个热点。二里头文化的年代断限是()

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

设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

以下关于计算机存储器件的叙述，()是不正确的。

若x=103，y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是_______。

灌注桩混凝土水下灌注时，其混凝土顶面标高至少要比设计标高高出()。

磺基水杨酸比色法测水中含铁量(三价铁离子)时，控制溶液的pH值为()。

在下列题中求各微分方程的通解或特解

肝气郁结型胁痛的主症特点是：瘀血阻络型胁痛的主症特点是：

A．有效性B．共享性C．层次性D．不完全性E．经济性以下分别属于信息的什么特性?时间上要及时、数量上要适当、质量上要准确、内容上要适用

茯苓的加工方法是（）。

滑模施工铁路桥墩时，模板高度宜设置为()。

下列不属于银行业金融机构的重组方式的是()。

班主任苏老师发现，承担本班数学教学任务的林老师经常让学生罚站。面对这种情况，苏老师应该()。

根据下表，回答以下问题下列哪类人员2009年网民人数比上年有所减少?()