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

admin2009-02-15 50

问题具有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://kaotiyun.com/show/NtxZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

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

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

ATM协议将网络分为多个功能层，信元生成由(44)层完成，汇聚子层属于(45)层。对OC-12接口标准，ATM网络的有效数据率(去掉信元中的开销位)约为(46)Mbit/s。A类服务是指(47)。在ATM网络内部(NNI中)，允许的虚电路数为(48)。

已知函数y=f(x)满足y″+2y′+5y=0，且f(0)=1，f′(0)=﹣1．设

我国社会主义初级阶段实行按劳分配的直接原因是()。

下列有关流行性乙型脑炎流行病学的描述，错误的是

下列选项中属于《安全生产法》规定的生产经营单位安全生产责任的有()。

当固定资产发生下列变动时，企业不需要做会计估计变更处理的是(　　)。

根据政府采购法律制度的规定，政府采购的投诉人对政府采购监督管理部门的投诉处理决定不服或者政府采购监督管理部门逾期未作处理的，可以采取的救济途径有()。

人民警察纪律的侧重点是警民关系，是对人民警察在履行职责的基础上提出的进一步的要求，即履行职责的职业道德要求。()

讨论方程axex+b=0(a＞0)实根的情况．

Everyyear,malaria(疟疾)【S1】______aboutfivehundredmillionpeople.Morethanonemillionofthemdie,mostlyyoungchildrenand

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

软考中级

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

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

ATM协议将网络分为多个功能层，信元生成由(44)层完成，汇聚子层属于(45)层。对OC-12接口标准，ATM网络的有效数据率(去掉信元中的开销位)约为(46)Mbit/s。A类服务是指(47)。在ATM网络内部(NNI中)，允许的虚电路数为(48)。

已知函数y=f(x)满足y″+2y′+5y=0，且f(0)=1，f′(0)=﹣1．设

我国社会主义初级阶段实行按劳分配的直接原因是()。

下列有关流行性乙型脑炎流行病学的描述，错误的是

下列选项中属于《安全生产法》规定的生产经营单位安全生产责任的有()。

当固定资产发生下列变动时，企业不需要做会计估计变更处理的是( )。

根据政府采购法律制度的规定，政府采购的投诉人对政府采购监督管理部门的投诉处理决定不服或者政府采购监督管理部门逾期未作处理的，可以采取的救济途径有()。

人民警察纪律的侧重点是警民关系，是对人民警察在履行职责的基础上提出的进一步的要求，即履行职责的职业道德要求。()

讨论方程axex+b=0(a＞0)实根的情况．

Everyyear,malaria(疟疾)【S1】______aboutfivehundredmillionpeople.Morethanonemillionofthemdie,mostlyyoungchildrenand

当固定资产发生下列变动时，企业不需要做会计估计变更处理的是(　　)。