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

admin2019-08-15 96

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

学硕统考专业

相关试题推荐

鸦片战争失败后，西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点，对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:规定外国人在中国可以不受中国法律管束的不平等条约是()
在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据，进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位，这些数据块均存储在同一个磁盘上，因此，SPOO
荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路
下面关于图的存储的叙述中，正确的是()。
假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。

随机试题

代谢性骨疾病应归属于
黑龙江的作用是()
急性自血病M1～M7的FAB分型主要根据
在投资决策中，非贴现的分析评价方法有(　　)。按照投资回收期法，应选择(　　)。
“坏账准备”账户期末余额不在资产负债表上列示，它在本质上是“应收账款”的备抵项目。()
根据有关规定,中外合资经营企业外方合营者以机器设备或其他物料出资的,必须符合的条件有()。
甲公司的某项固定资产原价为1000万元，采用年限平均法计提折旧，使用寿命为10年，预计净残值为0，在第4年年末企业对该项固定资产进行更新改造，并对某一主要部件进行更换，发生支出合计500万元，符合准则规定的固定资产确认条件，被更换的部件的原价为300万元
()总执天道；()执掌天地经纬、日月星辰和四时气候；()执掌南北极和天地人三才，并主持人间兵革之事；()执掌阴阳生育、万物之美和大地山河之秀。
下列说法错误的是()。
下列选项中，属于宋朝继承方式的有()。

最新回复(0)

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

计算机408

学硕统考专业

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。

下面关于图的存储的叙述中，正确的是()。

假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。

代谢性骨疾病应归属于

黑龙江的作用是()

急性自血病M1～M7的FAB分型主要根据

在投资决策中，非贴现的分析评价方法有( )。按照投资回收期法，应选择( )。

“坏账准备”账户期末余额不在资产负债表上列示，它在本质上是“应收账款”的备抵项目。()

根据有关规定,中外合资经营企业外方合营者以机器设备或其他物料出资的,必须符合的条件有()。

()总执天道；()执掌天地经纬、日月星辰和四时气候；()执掌南北极和天地人三才，并主持人间兵革之事；()执掌阴阳生育、万物之美和大地山河之秀。

下列说法错误的是()。

下列选项中，属于宋朝继承方式的有()。

在投资决策中，非贴现的分析评价方法有(　　)。按照投资回收期法，应选择(　　)。