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

admin2019-08-15 91

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

学硕统考专业

相关试题推荐

南宋理学家()认为一切封建秩序和伦理纲常都是人“本心”所固有的。而不是来自朱熹等人所说的“天理”。他的这一学说被称为“心学”。
下列关于戌戌维新运动论述不正确的是()。
编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1
若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如下表所示，该机有8位和16位两种指令字长，采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型，16位字长指令为寄存器～存储器(R—M)二地址变址类型(地址码范围在一12
有效容量为128KB的Cache，每块16字节，8路组相联。字节地址为1234567H的单元调入该Cache，其Tag应是()。
进程P0和P1的共享变量定义及其初值为：booleanflag[2]：intturn=0：flag[0]=FALSE；flag[1]=FALSE；若进程P0和P1访问临界资源的类C伪代码实现如下：则并发执行进程P0和P1时产生的情形是____。
假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为()。

随机试题

关于肾素说法正确的是
WHO推荐妊娠及哺乳期妇女每日碘摄入量为()。
下列哪一行为应以妨害公务罪论处?(2016年卷二19题，单选)
甲股份有限责任公司(以下简称“甲公司”)为上市公司，发生以下交易：(1)2014年12月20日，甲公司购进一台不需要安装的设备，设备价款为730万元，另发生运杂费2万元，专业人员服务费23万元，款项均以银行存款支付；没有发生其他相关税费。该设备于当日
专家分析认为，随着国家调控政策的效果显现，物价上涨过快的势头会得到一定遏制。受到物价上涨的惯性影响，预期2011年初CPI同比可能会继续小幅上涨，全年价格总水平将呈现温和上涨态势。下列表述符合上述这段话意思的是()。
根据幻觉涉及的感受器官的不同，幻觉类型包括（）。
允许法律关系参加者自行确定其权利和义务的法律规范是()。
Whatisthepossiblereasonthatsomefoodspromotethebrainperformance?
Beijingisfilledwithpeoplefrom______(vary)partsoftheworld.
Thehusbandhasalmostbeendrivenmadbyhiswife’s(end)______complaints.

最新回复(0)

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

计算机408

学硕统考专业

南宋理学家()认为一切封建秩序和伦理纲常都是人“本心”所固有的。而不是来自朱熹等人所说的“天理”。他的这一学说被称为“心学”。

下列关于戌戌维新运动论述不正确的是()。

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

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

若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

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

进程P0和P1的共享变量定义及其初值为：booleanflag[2]：intturn=0：flag[0]=FALSE；flag[1]=FALSE；若进程P0和P1访问临界资源的类C伪代码实现如下：则并发执行进程P0和P1时产生的情形是____。

假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为()。

关于肾素说法正确的是

WHO推荐妊娠及哺乳期妇女每日碘摄入量为()。

下列哪一行为应以妨害公务罪论处?(2016年卷二19题，单选)

根据幻觉涉及的感受器官的不同，幻觉类型包括（）。

允许法律关系参加者自行确定其权利和义务的法律规范是()。

Whatisthepossiblereasonthatsomefoodspromotethebrainperformance?

Beijingisfilledwithpeoplefrom______(vary)partsoftheworld.

Thehusbandhasalmostbeendrivenmadbyhiswife’s(end)______complaints.