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

admin2021-01-13 28

问题具有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://jikaoti.com/ti/3DG7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

阅读下列说明和E—R图，回答问题l至问题3，将解答填入答题纸的对应栏内。【说明】某学校的教学系统描述如下：学生信息包括：学号(SNo)、姓名(Sname)、性别(Sex)、年龄(Age)、入学年份(Year)、主修专业(Major)，其中学号是入学时

函数intToplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：ty

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】计算两个字符串x和y的最长公共子串(LongestCommonSubstring)。假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j

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

在UML提供的图中，可以采用(30)对逻辑数据库模式建模：(31)用于接口、类和协作的行为建模，并强调对象行为的事件顺序；(32)用于系统的功能建模，并强调对象间的控制流。

ARP协议的作用是(61)，ARP报文封装在(62)中传送。

在过程式程序设计(①)、数据抽象程序设计(②)、面向对象程序设计(③)、泛型(通用)程序设计(④)中，C++语言支持(16)，C语言支持(17)。

《巴塞尔协议》对商业银行的资本及其构成有哪些规定?

脑脊液中氯化物显著减少最常见于的疾病是

浆膜腔积液中黏蛋白的等电点(pI)为

急性心衰动物突然倒地，急救多选用()加入葡萄糖液中缓慢静脉滴注。

下列各项，与血液和神志关系最密切的是

在某幼儿园，当王老师刚刚走上教育工作岗位的时候，他教的班级有个淘气的幼儿。每当教师讲课时，他总爱低头玩他桌子上放的“宝贝”横笛儿，有时候还会轻轻地吹一声“嘟——嘟——”。对此，最恰当的处理方式是()。

下列分别对应图中推力和拉力的是()。①劳动力成本上升②优惠的税收政策③环境污染严重④市场广阔

幼儿把香蕉、玉米归为一类，认为它们都是“黄颜色的”。这反映了幼儿()

(辽宁)函数f(x)=x3+sinx+1(x∈R)，若f(a)=2，则f(-a)的值为()．

在死刑缓期执行减为有期徒刑或者无期徒刑减为有期徒刑的时候，应当把________________的期限改为3年以上10年以下。