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

admin2021-01-13 54

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下：分解：选择一个枢轴(pivot)元素划分数组。将数组A[p．．r]划分为两个子数组(可能为空)A[p．．q一1]和A[q+l_．r]，使得A[q]大于等于Alp．．q-1]

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

容量为64块的Cache采用组相联方式映像，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应为(7)位，主存区号应为(8)位。

某一确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|19，则以下字符串中，不能被该DFA接受的是(28)，与该DFA等价的正规式是(29)。(其中，ε表示空字符)①3857　　　　②1.2E+5　　　　③-123．　　　　④.576

两个公司希望通过Internet进行安全通信，保证从信息源到目的地之间的数据传输以密文形式出现，而且公司不希望由于在传输节点使用特殊的安全单元而增加开支，最合适的加密方式是(10)，使用的会话密钥算法应该是(11)。

关系R、S如下图所示，RS可由(54)基本的关系运算组成，RS=(55)。

如果希望别的计算机不能通过ping命令测试服务器的连通情况，可以(7)。如果希望通过默认的Telnet端口连接服务器，则下面对防火墙配置正确的是(8)。

设阶码8位(最左一位为符号位)，用移码表示，尾数为24位(最左一位为符号位)，用规格化补码表示，则它所能表示的最大正数的阶码为(27)，尾数为(28)；绝对值最小的负数的阶码为(29)，尾数为(30)。

分度头的蜗杆蜗轮啮合间隙应调整得越小越好，这样可提高分度精度。

为价值恢复或处置合理而对原材料、中间库存、最终产品及相关信息从消费地到起始点的有效实际流动所进行的计划、管理和控制过程被称为【】

骨骼肌纤维收缩时，其肌节的变化是()。

细胞内浓度高于细胞外浓度的离子是

旅游业的特点有()。

某软件设计师自行将他人使用C语言开发的控制程序转换为JaVa语言形式的控制程序并使用，该软件设计师的行为(9)。

Thatthosewhohadlearnedfromusnowsurpassuswasagreatchallenge.Theitalicizedpartfunctionsasa(n)______inthesente

Thenumberofstudentsinourdepartment(be)______morethan500.

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

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

软考中级

快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下：分解：选择一个枢轴(pivot)元素划分数组。将数组A[p．．r]划分为两个子数组(可能为空)A[p．．q一1]和A[q+l_．r]，使得A[q]大于等于Alp．．q-1]

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

容量为64块的Cache采用组相联方式映像，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应为(7)位，主存区号应为(8)位。

某一确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|19，则以下字符串中，不能被该DFA接受的是(28)，与该DFA等价的正规式是(29)。(其中，ε表示空字符)①3857 ②1.2E+5 ③-123． ④.576

两个公司希望通过Internet进行安全通信，保证从信息源到目的地之间的数据传输以密文形式出现，而且公司不希望由于在传输节点使用特殊的安全单元而增加开支，最合适的加密方式是(10)，使用的会话密钥算法应该是(11)。

关系R、S如下图所示，RS可由(54)基本的关系运算组成，RS=(55)。

如果希望别的计算机不能通过ping命令测试服务器的连通情况，可以(7)。如果希望通过默认的Telnet端口连接服务器，则下面对防火墙配置正确的是(8)。

设阶码8位(最左一位为符号位)，用移码表示，尾数为24位(最左一位为符号位)，用规格化补码表示，则它所能表示的最大正数的阶码为(27)，尾数为(28)；绝对值最小的负数的阶码为(29)，尾数为(30)。

分度头的蜗杆蜗轮啮合间隙应调整得越小越好，这样可提高分度精度。

为价值恢复或处置合理而对原材料、中间库存、最终产品及相关信息从消费地到起始点的有效实际流动所进行的计划、管理和控制过程被称为【】

骨骼肌纤维收缩时，其肌节的变化是()。

细胞内浓度高于细胞外浓度的离子是

旅游业的特点有()。

某软件设计师自行将他人使用C语言开发的控制程序转换为JaVa语言形式的控制程序并使用，该软件设计师的行为(9)。

Thatthosewhohadlearnedfromusnowsurpassuswasagreatchallenge.Theitalicizedpartfunctionsasa(n)______inthesente

Thenumberofstudentsinourdepartment(be)______morethan500.

某一确定性有限自动机(DFA)的状态转换图如下图所示，令d=0|1|2|…|19，则以下字符串中，不能被该DFA接受的是(28)，与该DFA等价的正规式是(29)。(其中，ε表示空字符)①3857　　　　②1.2E+5　　　　③-123．　　　　④.576