首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-01-30
67
问题
假设有n个顶点e条边的有向图用邻接表表示,则删除与某个顶点v相关的所有边的时间复杂度为( )。
选项
A、O(n)
B、O(e)
C、O(n+e)
D、O(ne)
答案
C
解析
删除与某顶点v相关的所有边的过程如下:先删除下标为v的顶点表结点的单链表,出边数最多为n一1,对应时间复杂度为O(n),再扫描所有边表结点,删除所有的入边,对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。
转载请注明原文地址:https://www.kaotiyun.com/show/vdRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“二战”后,美国以经济手段扶植和控制西欧的表现是()。
简述按照恩格斯的划分方法人类的起源与进化。
红山文化的代表件墓葬形式为()。
洋务派创办军事工业的方式是()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
下列网络设备中,能够抑制广播风暴的是____。I.中继器Ⅱ.集线器Ⅲ.网桥Ⅳ.路由器
设无向图G=(V,E)和G’=(V’,E’),如果G’是G的生成树,则下面说法中错误的是()。
随机试题
下列项目中,应计人存货成本的有()
CT机主计算机设备的特点包括
危害最大,且可引起死亡的致泻性大肠埃希菌是
一个良好班集体的建立必须通过各种活动来实现。()
试结合国际教育改革的趋势,具体分析我国当前基础教育课程改革的基本特征。
(1995年)设则级数
设R和S是两个关系,与关系代数表达式R×S等价的SQL语句是【】。
Theunfortunatedeathofthegeniuspoetcaused______losstothiscountry.
TurningVividDreamsIntoRealityResearchersatStanfordUniversityarenowdevelopingsoftwaretohelppeoplebecomeaware
A.claimB.advancedC.challengeD.butE.constantlyF.declareG.pilesupH.limitedI.significanceJ.hesitatedK.andL.
最新回复
(
0
)