首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-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题库学硕统考专业分类
0
计算机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
)