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

admin2019-08-15 102

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

学硕统考专业

相关试题推荐

认识到乾嘉时期人口膨胀带来的系列问题，明确指出这种弊端的是()
鸦片战争失败后，西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点，对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:中国与外国签订的第一个同盟条约是()
1977年4月，对“两个凡是”提出批评，开全党思想解放先河的是()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB，按字节编址，缓存容量为32KB，采用组相联方式进行地址映射与变换，主存与缓存的每一块为64B，缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
给定序列{3，5，7，9，11，13，15，17)，(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情
若线性表最常用的运算是查找第i个元素及其前驱的值，则采用()存储方式节省时间。
有效容量为128KB的Cache，每块16字节，8路组相联。字节地址为1234567H的单元调入该Cache，其Tag应是()。
设有一个双向链表h，每个结点中除有prior，data和next三个域外，还有一个访问频度域freq，在链表被起用之前，每个结点中的freq域都被初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域中的值加一，并调整表中
下列叙述正确的个数是()。1)向二排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值

随机试题

男，32岁。会阴部骑跨伤5小时。随后会阴部疼痛，尿道口滴血，不能自行排尿。生命体征稳定，阴囊肿大、青紫。该患者适宜的处理方法是()
按CJJ1-2008规定，下列选项中属于无机结合料稳定基层质量主控项目的有()等。
招标人和中标人在签订合同的谈判中，为了防范货币贬值或者通货膨胀的风险，一般通过()约定风险承担方式。
乙建筑公司采用累计实际发生的合同成本占合同预计总成本的比例确定合同完工进度，并采用完工百分比法确认合同收入和合同成本。20×2年1月1日，乙建筑公司签订一项总金额为480万元的建造合同，合同期为3年。20×2年12月31日，乙建筑公司实际发生合同成本100
“应收账款”总账借方余额12000万元，其明细账借方余额合计18000万元，贷方明细账余额合计6000万元；“预收账款”总账贷方余额15000万元，其明细账贷方余额合计27000万元，借方明细账余额合计12000万元。“坏账准备”科目余额为3000万元(均
化学学习方法中的类推法是由已学知识通过迁移构建新知识的方法。下列类推正确的是()。
说明如何培养运动员的技术风格。
【B1】【B4】
YouaresupposedtogetanMAdegreethissemesterandyouwanttoapplyforajobasanEnglishteacherinauniversity.Nowwr
帧中继网的虚电路建立在(58)，与X.25相比，因为(59)从而在网上的延迟时间更小。这种网络没有流量控制功能，但增加了拥塞控制功能。如果沿着帧传送方向出现拥塞，则把帧地址字段的(60)位设置为1，这样接收方就可通过(61)协议要求发送方降低数据速率。最适

最新回复(0)

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

计算机408

学硕统考专业

认识到乾嘉时期人口膨胀带来的系列问题，明确指出这种弊端的是()

1977年4月，对“两个凡是”提出批评，开全党思想解放先河的是()。

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

若线性表最常用的运算是查找第i个元素及其前驱的值，则采用()存储方式节省时间。

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

男，32岁。会阴部骑跨伤5小时。随后会阴部疼痛，尿道口滴血，不能自行排尿。生命体征稳定，阴囊肿大、青紫。该患者适宜的处理方法是()

按CJJ1-2008规定，下列选项中属于无机结合料稳定基层质量主控项目的有()等。

招标人和中标人在签订合同的谈判中，为了防范货币贬值或者通货膨胀的风险，一般通过()约定风险承担方式。

化学学习方法中的类推法是由已学知识通过迁移构建新知识的方法。下列类推正确的是()。

说明如何培养运动员的技术风格。

【B1】【B4】

YouaresupposedtogetanMAdegreethissemesterandyouwanttoapplyforajobasanEnglishteacherinauniversity.Nowwr