具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

admin2009-02-15 23

问题具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

选项 A、O(n²)
B、O(n)
C、O(n-1)
D、O(n+1)

答案B

解析不论是深度优先还是广度优先搜索遍历，图中n个顶点都必须被访问一次。从某个顶点出发，要搜索到其他顶点，必须沿着图中的边去找。用邻接矩阵做图的存储结构时，这些边是分布在一个n阶方阵中，要检测出这些边，必须对矩阵中n²个元素进行检测，因此，其时间复杂度为O(n²)。若用邻接表作为存储结构，只需对代表e条无向边的2e个边表结点进行检测，其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号，每个顶点都要进栈一次，故n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号，每个顶点都要进队一次，故队列长度为n，所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。

转载请注明原文地址:https://jikaoti.com/ti/Eza7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

设信道带宽为3000Hz，根据尼奎斯特(Nyquist)定理，理想信道的波特率为(16)波特，若采用QPSK调制，其数据速率应为(17)，如果该信道信噪比为30dB，则该信道的带宽约为(18)。设信道误码率为10-5，帧长为10Kb，差错为单个错，则帧出错

在Windows2000操作系统中，配置IP地址的命令是(53)。若用ping命令来测试本机是否安装了TCP/IP协议，则正确的命令是(54)。如果要列出本机当前建立的连接，可以使用的命令是(55)。

在域名服务器中，下列(61)负责非本地域名的地址查询。

在某单CPU的计算机系统中，采用可抢占优先级的任务调度方案，且所有任务可以并行使用I/O通道。内存中有A1、A2两个任务，按照A1、A2的次序运行，其内部计算和I/O操作时间如表1-1所示。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(59)，采用CSMA/CA技术是指(60)，MAC层的分布式协调功能提供(61)，站点发出的确认帧ACK，要在(62)间隔发送。为解决隐蔽站带来的问题，802.11允许(63)。

在双绞线布线后要进行测试，一般情况，下面(43)不是测试的项目。光纤测试的内容不包括(44)项目。

A．凝固性坏死B．液化性坏死C．湿性坏疽D．干酪样坏死E．干性坏疽坏疽性阑尾炎属于

施工图首页一般由图样目录、()组成。

支撑高度超过10m时，应在外侧周边和内部每隔()间距设置剪刀撑。

下列属于结构吊装中综合吊装法特点的是()。

建设工程安全生产管理制度中的最基本制度是()。

账户按用途和结构分类，现金账户属于(　　)。

下列账户余额一般在借方的是（）。

“两耳不闻窗外事，一心只读圣贤书”，这体现了注意具有()

Liberal(自由)educationisbecomingthetaskofteachers.Itis【C1】______notonlytoteachandlearnknowledge,butalsotodevel

MuslimSudanisoneoftheIslamized【B1】______regions.InEastAfricamusicalformsshowingAraborIslamicinfluencearefound

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

软考中级

设信道带宽为3000Hz，根据尼奎斯特(Nyquist)定理，理想信道的波特率为(16)波特，若采用QPSK调制，其数据速率应为(17)，如果该信道信噪比为30dB，则该信道的带宽约为(18)。设信道误码率为10-5，帧长为10Kb，差错为单个错，则帧出错

在Windows2000操作系统中，配置IP地址的命令是(53)。若用ping命令来测试本机是否安装了TCP/IP协议，则正确的命令是(54)。如果要列出本机当前建立的连接，可以使用的命令是(55)。

在域名服务器中，下列(61)负责非本地域名的地址查询。

在某单CPU的计算机系统中，采用可抢占优先级的任务调度方案，且所有任务可以并行使用I/O通道。内存中有A1、A2两个任务，按照A1、A2的次序运行，其内部计算和I/O操作时间如表1-1所示。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(59)，采用CSMA/CA技术是指(60)，MAC层的分布式协调功能提供(61)，站点发出的确认帧ACK，要在(62)间隔发送。为解决隐蔽站带来的问题，802.11允许(63)。

在双绞线布线后要进行测试，一般情况，下面(43)不是测试的项目。光纤测试的内容不包括(44)项目。

A．凝固性坏死B．液化性坏死C．湿性坏疽D．干酪样坏死E．干性坏疽坏疽性阑尾炎属于

施工图首页一般由图样目录、()组成。

支撑高度超过10m时，应在外侧周边和内部每隔()间距设置剪刀撑。

下列属于结构吊装中综合吊装法特点的是()。

建设工程安全生产管理制度中的最基本制度是()。

账户按用途和结构分类，现金账户属于( )。

下列账户余额一般在借方的是（）。

“两耳不闻窗外事，一心只读圣贤书”，这体现了注意具有()

Liberal(自由)educationisbecomingthetaskofteachers.Itis【C1】______notonlytoteachandlearnknowledge,butalsotodevel

MuslimSudanisoneoftheIslamized【B1】______regions.InEastAfricamusicalformsshowingAraborIslamicinfluencearefound

账户按用途和结构分类，现金账户属于(　　)。