对有<em>n</em>个结点、<em>e</em>条边且采用数组表示法（即邻接矩阵存储）的无向图进..

2023年下半年上午试卷综合知识

第 59 题


知识点	矩阵深度优先遍历数组
关键词	遍历邻接矩阵深度优先时间复杂度数组
章/节	计算机软件知识

对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为（1）。

A. O(n+e)

B. O(e²)

C. O(n²)

D. O(n*e)

相关试题计算机软件知识

第28题

2010年下半年

某文件系统采用多级索引结构，若磁盘块的大小为512B，每个块号需占3B，那么根索引采用一级索引时的文件最大长度为（27) KB：采用二级索引时的文件最大长度为（28..

第40题

2021年上半年

最大尺寸和问题描述为，在n个整数(包含负数)的数组A中，求之和最大的非空连续子数组,如数组A=(-2,11,-4,13,-5,-2) ，其中子数组B=(11,-4,13)具有最大子段和20(11..

第53题

2015年上半年

（53）算法采用模拟生物进化的三个基本过程“繁殖（选择）-> 交叉（重组）->变异（突变）”。

知识点讲解

· 矩阵

· 深度优先遍历

· 数组

矩阵

特殊矩阵

若矩阵中元素（或非零元素）的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。

对称矩阵：若矩阵A_n_×_n中的元素有

a_ij=a_ji1≤i,j≤n

则称之为n阶对称矩阵。

上（下）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元素均为常数或零。

对角矩阵：矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。

稀疏矩阵

在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。存储稀疏矩阵的非零元素时必须同时存储其位置（行、列号），用三元组（i,j,a_ij）可唯一确定矩阵中的一个元素。因此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。

稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

深度优先遍历

从图G中任一个顶点v出发，深度优先遍历（DFS）的算法步骤如下。

（1）设立搜索指针p，使p指向顶点v。

（2）访问p顶点，并使p指向与p顶点相邻接的且尚未被访问过的顶点。

（3）若p不空，则重复步骤（2）；否则执行步骤（4）。

（4）沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的邻接顶点，然后重复步骤（2），直至所有的顶点均被访问为止。

这个算法的特点是尽可能先对纵深方向搜索，因此可以很容易得到其遍历的递归算法。

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

数组

数组的定义及基本运算

n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。

对数组进行的基本运算有以下两种。

（1）给定一组下标，存取相应的数据元素。

（2）给定一组下标，修改相应的数据元素中某个数据项的值。

数组的顺序存储

一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((i-1)n+(j-1))L

同样的，以列为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((j-1)m+(i-1))L

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5