具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。

admin2021-01-13 34

问题具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。

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

答案D

解析本题考查数据结构基础知识。深度优先和广度优先遍历图的过程实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n²)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为 O(n+e)。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。

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

软考中级

阅读下列说明和C++代码，将应填入(1)～(5)处的字句写在答题纸的对应栏内。【说明】生成器(Builder)模式的意图是将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。图6所示为其类图。【C++代码】#

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足

若对象A可以给对象B发送消息，那么(48)。

多媒体电子出版物创作的主要过程可分为(62)。基于内容检索的体系结构可分为两个子系统：(63)。

由一个单独的管理者负责整个网络管理工作的网络管理的实现结构是(62)。(63)的客户端不需安装网络操作系统。(64)不是网络操作系统的系统模型。

判断防烟排烟系统的工作状态，需要的操作程序应包括()。

如何全面理解马克思主义关于人的本质的观点?

患儿，男性，生后发现脐部中央脐带部位有一直径6cm的肿物，表面无皮肤，仅有透明囊膜覆盖。下列处理中除哪项外均是正确的

A．手少阴心经病证B．足少阴肾经病证C．手太阴肺经病证D．足太阴脾经病证E．足厥阴肝经病证

《建设工程监理规范》是()。

对高收入者必须进行严格的征收管理，以下属于税法重点监控的高收入领域或个人的有(　　)。

Mr.Johnsonhasahabitofaskingquestions______.

如图，在平面直角坐标系xOy中，设三角形ABC的顶点分别为A(0，a)、B(b，0)、C(c，0)，点P(0，p)是线段AO上的一点(异于端点)，这里a、b、c、P均为非零实数，设直线BP、CF分别与边AC、AB交于点E、F。(1)若BE⊥AC，求证：C

当发现主机受到ARP攻击时需清除ARP缓存，使用的命令是____________。

具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。

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

软考中级

阅读下列说明和C++代码，将应填入(1)～(5)处的字句写在答题纸的对应栏内。【说明】生成器(Builder)模式的意图是将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。图6所示为其类图。【C++代码】#

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足

若对象A可以给对象B发送消息，那么(48)。

多媒体电子出版物创作的主要过程可分为(62)。基于内容检索的体系结构可分为两个子系统：(63)。

由一个单独的管理者负责整个网络管理工作的网络管理的实现结构是(62)。(63)的客户端不需安装网络操作系统。(64)不是网络操作系统的系统模型。

判断防烟排烟系统的工作状态，需要的操作程序应包括()。

如何全面理解马克思主义关于人的本质的观点?

患儿，男性，生后发现脐部中央脐带部位有一直径6cm的肿物，表面无皮肤，仅有透明囊膜覆盖。下列处理中除哪项外均是正确的

A．手少阴心经病证B．足少阴肾经病证C．手太阴肺经病证D．足太阴脾经病证E．足厥阴肝经病证

《建设工程监理规范》是()。

对高收入者必须进行严格的征收管理，以下属于税法重点监控的高收入领域或个人的有( )。

Mr.Johnsonhasahabitofaskingquestions______.

如图，在平面直角坐标系xOy中，设三角形ABC的顶点分别为A(0，a)、B(b，0)、C(c，0)，点P(0，p)是线段AO上的一点(异于端点)，这里a、b、c、P均为非零实数，设直线BP、CF分别与边AC、AB交于点E、F。(1)若BE⊥AC，求证：C

当发现主机受到ARP攻击时需清除ARP缓存，使用的命令是____________。

对高收入者必须进行严格的征收管理，以下属于税法重点监控的高收入领域或个人的有(　　)。