假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

admin2013-05-11 89

问题假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

选项 A、O(n)
B、O(e)
C、O(n+e)
D、O(n*e)

答案C

解析与某个顶点、相关的所有弧是指所有以vi为尾和所有以　vi为头的弧。n个顶点的有向图的邻接表含有n个出边表，每个顶点有且只有一个出边表，第i个出边表中的结点表示以顶点v1为尾的弧。每个出边表设置一个头结点，所有头结点构成一个向量，该向量称为顶点表。因为弧是有方向的，所以每一条弧只用一个边表结点来表示，e条弧则有p个结点，因此有，n个顶点和e条弧的有向图的邻接表含有　n个顶点表结点和vi个边表结点。要删除以顶点vi为尾的弧只要删除第i个出边表中的结点就行了，但要删除以顶点vi为头的弧则需在其他出边表中查找顶点信息域为i的结点。为此，需对n个顶点表结点和e个边表结点进行通遍扫描，故其时间复杂度为O(n+e)。

转载请注明原文地址:https://kaotiyun.com/show/knRZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

假设—个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi(下标)相关的所有弧的时间复杂度是(55)。

软件设计师上午基础知识考试

软考中级

一个运行CSMA／CD协议的以太网，数据速率为1Gbit／s，网段长1km，信号速率为200000km／s，则最小帧长是____________比特。

网络管理系统的配置管理最主要的功能是(1)。下列选项中不属于网络管理系统安全管理部分功能的是(2)，不属于网络管理协议的是(3)。(3)

某报文的长度是1000字节，利用MD5计算出来的报文摘要长度是(1)位，利用SHA计算出来的报文摘要长度是(2)位。(2010年下半年试题)(2)

程序的3种基本控制结构是__________。(2010年上半年试题)

下列关于软件著作权中翻译权的叙述不正确的是：翻译权是指__________的权利。(2011年上半年试题)

当异步通信采用奇校验时，每一个字符(包含校验位)中含有1的个数是__________。

在面向对象的软件工程中，一个组件(component)包含了(10)。

患者，女，75岁。因“冠心病，不稳定型心绞痛”入院，为了解患者的心功能，护士需特别关注的辅助检查是

A．当日有效B．不得超过3天C．2日极量D．7日用量E．3日用量处方一般不得超过()

确定项目设备来源方案要考虑国内设备制造厂家的业绩及研发能力。对于国内有制造能力、且有制造业绩的设备，设备来源方案应为()。

属于债务收入的财政收入有()。

某初中生物老师在指导学生完成“探究种子萌发的环境条件”实验中采用合作学习的教学策略，在进行实验分组时，应遵循的原则是()。

在VisualBasic中，6+10mod10\9/3+2^3的结果为________。

Inthelastfewyears,there______greatchangesinthecountry.

集中统一的打击行动，多数情况下由各省、自治区、直辖市从当地社会治安情况出发，主动地和有节奏、有准备、有重点地开展集中打击或专项斗争。()

YourLifeTheirHandsAOnbenchesinparks,youcanbuythethingsyousimplycan’tfindinstores.Aftermethamphetamine,the