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

admin2013-05-11 51

问题假设—个有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://jikaoti.com/ti/dbf7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

POP3协议采用(1)模式，当客户机需要服务时，客户端软件(OutlookExpress或Fox．Mail)与POP3服务器建立(2)连接。(2011年下半年试题)(2)

ARPAnetisawideareanetwork(WAN)．AnetworkthatconnectedDepartmentofDefenseresearchsitesacross(1)．Createdin1969wit

在Linux系统中，采用(1)命令查看进程输出的信息，得到下图所示的结果。系统启动时最先运行的进程是(2)，下列关于进程xinetd的说法中正确的是(3)。(2009年下半年试题)(3)

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

IEEE802．11定义了无线局域网的两种工作模式，其中的(1)模式是一种点对点连接的网络，不需要无线接入点和有线网络的支持。IEEE802．11g的物理层采用了扩频技术，工作在(2)频段。(2008年上半年试题)(2)

在IEEE802．11标准中使用了扩频通信技术，下面选项中有关扩频通信技术说法正确的是__________。(2011年上半年试题)

杀毒软件报告发现病毒Macro．Melissa，由该病毒名称可以推断出病毒类型是(1)，这类病毒主要感染目标是(2)。(1)

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

稳定性考察中，影响药物稳定性的因素包括()

患者，女，21岁，未婚。月经17岁初潮，量少、色淡红，渐至闭经1年余，头晕耳鸣，腰膝酸软，舌淡红，少苔，脉细涩。其中医证型是()

与振动病发病率高低有密切关系的振动参数是

审判的时候怀孕的妇女依法不适用死刑。对这—规定的理解，下列哪一选项是错误的?（）

砌体工程施工中，砌体中上下皮砌块搭楼长度小于规定数值的竖向灰缝被称为：(2018年第81题)

债券基金的分析指标有()。

把下面的六个图形分成两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

Whoistheman?

MassStrandingsofWhales1.Thetidegoesoutsuddenly,【T1】thewhales【T1】2.Mas

A、Universitysystemsvaryfromcountrytocountry.B、Efficiencyisessentialtouniversitymanagement.C、Itishardtosaywhich

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

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

软考中级

POP3协议采用(1)模式，当客户机需要服务时，客户端软件(OutlookExpress或Fox．Mail)与POP3服务器建立(2)连接。(2011年下半年试题)(2)

ARPAnetisawideareanetwork(WAN)．AnetworkthatconnectedDepartmentofDefenseresearchsitesacross(1)．Createdin1969wit

在Linux系统中，采用(1)命令查看进程输出的信息，得到下图所示的结果。系统启动时最先运行的进程是(2)，下列关于进程xinetd的说法中正确的是(3)。(2009年下半年试题)(3)

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

IEEE802．11定义了无线局域网的两种工作模式，其中的(1)模式是一种点对点连接的网络，不需要无线接入点和有线网络的支持。IEEE802．11g的物理层采用了扩频技术，工作在(2)频段。(2008年上半年试题)(2)

在IEEE802．11标准中使用了扩频通信技术，下面选项中有关扩频通信技术说法正确的是__________。(2011年上半年试题)

杀毒软件报告发现病毒Macro．Melissa，由该病毒名称可以推断出病毒类型是(1)，这类病毒主要感染目标是(2)。(1)

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

稳定性考察中，影响药物稳定性的因素包括()

患者，女，21岁，未婚。月经17岁初潮，量少、色淡红，渐至闭经1年余，头晕耳鸣，腰膝酸软，舌淡红，少苔，脉细涩。其中医证型是()

与振动病发病率高低有密切关系的振动参数是

审判的时候怀孕的妇女依法不适用死刑。对这—规定的理解，下列哪一选项是错误的?（）

砌体工程施工中，砌体中上下皮砌块搭楼长度小于规定数值的竖向灰缝被称为：(2018年第81题)

债券基金的分析指标有()。

把下面的六个图形分成两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

Whoistheman?

MassStrandingsofWhales1.Thetidegoesoutsuddenly,【T1】________thewhales【T1】________2.Mas

A、Universitysystemsvaryfromcountrytocountry.B、Efficiencyisessentialtouniversitymanagement.C、Itishardtosaywhich

MassStrandingsofWhales1.Thetidegoesoutsuddenly,【T1】thewhales【T1】2.Mas