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

admin2013-05-11 58

问题假设—个有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)。

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

软考中级

假设用户Q1有2000台主机，则必须给他分配(1)个C类网络，如果分配给用户Q1的超网号为200．9．64．0，则指定给Q1的地址掩码为(2)；假设给另一用户Q2分配的C类网络号为200．0．16．0～200．9．31．0，如果路由器收到一个目标地址为11

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

采用ADSL虚拟拨号接入方式中，用户端需要安装__________软件。(2011年上下半年试题)

利用__________可以对软件的技术信息、经营信息提供保护。(2010年下半年试题)

某局域网采用SNMP进行网络管理，所有被管设备在15min内轮询一次，网络没有明显拥塞，单个轮询时间为0．4s，则该管理站最多可支持__________个设备。(2010年上半年试题)

廉价磁盘冗余阵列RAID利用冗余技术实现高可靠性，其中RAIDl的磁盘利用率为(1)。如果利用4个盘组成RAID3阵列，则磁盘利用率为(2)。(2009年上半年试题)(2)

在Windows客户端运行nslookup命令，结果如下图所示。为www．softwaretest．com提供解析的是(33)。在DNS服务器中，ftp．softwaretest．com记录通过(34)方式建立。C

[函数]intDeleteNode(Bitreer，inte){Bitreep=r，pp，s，c；while((1)){/从树根结点出发查找键值为e的结点/

辩证否定的实质是()

在Excel2010中，不能实现为单元格定义名称的是()

挫折理论是由下列哪个人提出的?()

关于蜕膜的概念，正确的是

A．滋阴潜阳药B．清热凉血药C．温阳、益气、健脾药D．行气和营药E．苦寒泻下药

A．长期口服维生素DB．钙制剂＋维生素D＋阿仑膦酸盐C．单独使用降钙素D．单独使用钙制剂E．钙制剂＋维生素D＋雌激素(或雌激素受体调节剂)抗癫痫药所致的骨质疏松治疗

在债的各种担保方式中，(　　)属于物的担保。

调号相同的调称为()

依次填入下列各句横线处的词语，恰当的一组是(　　)。①图书市场上部分作品从内容、写作手法到包装、宣传都极力媚俗，为文学界乃至许多读者所。②产品销售额一落千丈，形势的迫使他必须当机立断，停止生产。

A、 B、 C、 A

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

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

软考中级

假设用户Q1有2000台主机，则必须给他分配(1)个C类网络，如果分配给用户Q1的超网号为200．9．64．0，则指定给Q1的地址掩码为(2)；假设给另一用户Q2分配的C类网络号为200．0．16．0～200．9．31．0，如果路由器收到一个目标地址为11

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

采用ADSL虚拟拨号接入方式中，用户端需要安装__________软件。(2011年上下半年试题)

利用__________可以对软件的技术信息、经营信息提供保护。(2010年下半年试题)

某局域网采用SNMP进行网络管理，所有被管设备在15min内轮询一次，网络没有明显拥塞，单个轮询时间为0．4s，则该管理站最多可支持__________个设备。(2010年上半年试题)

廉价磁盘冗余阵列RAID利用冗余技术实现高可靠性，其中RAIDl的磁盘利用率为(1)。如果利用4个盘组成RAID3阵列，则磁盘利用率为(2)。(2009年上半年试题)(2)

在Windows客户端运行nslookup命令，结果如下图所示。为www．softwaretest．com提供解析的是__________(33)。在DNS服务器中，ftp．softwaretest．com记录通过__________(34)方式建立。C

[函数]intDeleteNode(Bitree*r，inte){Bitreep=*r，pp，s，c；while((1)){/*从树根结点出发查找键值为e的结点*/

辩证否定的实质是()

在Excel2010中，不能实现为单元格定义名称的是()

挫折理论是由下列哪个人提出的?()

关于蜕膜的概念，正确的是

A．滋阴潜阳药B．清热凉血药C．温阳、益气、健脾药D．行气和营药E．苦寒泻下药

A．长期口服维生素DB．钙制剂＋维生素D＋阿仑膦酸盐C．单独使用降钙素D．单独使用钙制剂E．钙制剂＋维生素D＋雌激素(或雌激素受体调节剂)抗癫痫药所致的骨质疏松治疗

在债的各种担保方式中，( )属于物的担保。

调号相同的调称为()

依次填入下列各句横线处的词语，恰当的一组是( )。①图书市场上部分作品从内容、写作手法到包装、宣传都极力媚俗，为文学界乃至许多读者所______。②产品销售额一落千丈，形势的______迫使他必须当机立断，停止生产。

A、 B、 C、 A

在Windows客户端运行nslookup命令，结果如下图所示。为www．softwaretest．com提供解析的是(33)。在DNS服务器中，ftp．softwaretest．com记录通过(34)方式建立。C

[函数]intDeleteNode(Bitreer，inte){Bitreep=r，pp，s，c；while((1)){/从树根结点出发查找键值为e的结点/

在债的各种担保方式中，(　　)属于物的担保。

依次填入下列各句横线处的词语，恰当的一组是(　　)。①图书市场上部分作品从内容、写作手法到包装、宣传都极力媚俗，为文学界乃至许多读者所。②产品销售额一落千丈，形势的迫使他必须当机立断，停止生产。