首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。
假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。
admin
2019-12-10
73
问题
假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。
选项
A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)
答案
C
解析
考查邻接表的性质。和顶点v相关的边包括出边和入边，对于出边，只需要遍历v的顶点表即可；对于入边，则需要遍历整个邻接表。删除与某顶点v相关的所有边过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为，n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。
转载请注明原文地址:https://kaotiyun.com/show/7L3i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
以下关于CPU的叙述中，错误的是()。
下列序列中，执行第一趟快速排序的结果是()。
在单处理机的多进程系统中，进程什么时候占用处理机以及决定占用时间的长短是()。
编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：请说明系统并不一定死锁。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：请说明系统处于不安全状态；
若一组记录的排序码序列F={50，80，30，40，70，60}，利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为()。
某单位有1个总部和6个分部，各个部门都有自己的局域网。该单位申请了6个C类IP地址202．115．10．0／24～202．115．15．0／24，其中总部与分部4共用一个C类地址。网络采用R1～R7共7台路由器，采用动态路由协议OSPF，并划分了3个OSP
若某通信链路的数据传输速率为2400bit／s，采用4相位调制，则该链路的波特率是____。
下列几种类型的系统中，适合采用忙等待I／O方式的有()。Ⅰ．专门用来控制单I／O设备的系统Ⅱ．运行一个多任务操作系统的个人计算机Ⅲ．作为一个负载很大的网络服务器的工作站
随机试题
某些病毒的遗传物质是RNA(RNA病毒)，这些RNA病毒在反转录酶的作用下，以RNA指导合成DNA，即遗传信息也可以从RNA传递给DNA。反转录酶是一类
患者，女性，62岁，下颌义齿基托边缘锐利，下后牙前庭沟处可见一处深在溃疡，边缘隆起，疼痛不明显，最可能的诊断是()
溃疡性结肠炎治疗首选药物是()
A.钩藤B.金钱白花蛇C.鳖甲D.枇杷叶E.葫芦壳中药汤剂煎煮时需要包煎的饮片是
混凝土的抗渗等级是按标准试件在下列哪一个龄期所能承受的最大水压来确定的?
会计机构负责人、会计主管人员办理交接的由()监交。
在方法论上，以大量严格的科学实验结果为依据的理论流派是()。
A、9B、10C、11D、12C中间数字是外侧四个数字的平均数。(1＋4＋17＋30)÷4＝13，(8＋24＋29＋39)÷4＝25，(16＋9＋6＋5)÷4＝9，(32＋4＋5＋3)÷4＝(11)，答案为C。
Analystshavetheirgoathumor,andIhavereadsomeofthisinterpretativeliterature,(1)_____withoutbeinggreatlyinstruct
A、Happybirthday.B、Thankyou.C、Thesametoyou.D、That’sallright.B
最新回复
(
0
)
