2. 考研
  3. 下面关于图的存储结构的叙述中正确的是( )。

下面关于图的存储结构的叙述中正确的是( )。

admin2019-08-15  37
问题 下面关于图的存储结构的叙述中正确的是(    )。
选项 A、用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关
B、用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关
C、用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关
D、用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关
答案A
解析 邻接矩阵法的基本思想是对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[j]存放的是顶点i到顶点j之间关系的信息。
  
  邻接表法的基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。
第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。
邻接表法的特点
·表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目。
·在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间。
·在无向图中，顶点Vi的度是第i个链表的结点数。
·对有向图可以建立正邻接表或逆邻接表。
·正邻接表是以顶点Vi为出度(即为弧的起点)而建立的邻接表。
·逆邻接表是以顶点Vi为人度(即为弧的终点)而建立的邻接表。
·在有向图中，第i个链表中的结点数是顶点Vi的出(或入)度；求入(或出)度，须遍历整个邻接表。
·在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点。
转载请注明原文地址:https://jikaoti.com/ti/JYGjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)