4.2 图的存储及基本操作

4.2 图的存储及基本操作

　　考试大纲涉及本节的知识点有：邻接矩阵及其实现、邻接表及其实现。

一、选择题

　　1．选择题题目部分
　　● 对于一个具有n个节点的无向图，若采用邻接矩阵表示，该矩阵的大小是 （1） 。
　　（1）A．n B．(n-1)2 C．n-1 D．n2
　　● 用邻接表存储图所用的空间大小 （2） 。
　　（2）A．与图的顶点数和边数都有关 B．只与图的边数有关
　　C．只与图的顶点数有关 D．与边数的平方有关
　　● 采用邻接表表示一个有向图，若图中某顶点的入度和出度分别为d1和 d2，则该顶点对应的单链表的节点数为 （3）。
　　（3）A．d1 B．d2 C．d1d2 D．d1+d2
　　● 以下关于邻接矩阵的描述，正确的是 （4） 。
　　（4）A．无向图的邻接矩阵中非0元素数就是该图的边数
　　B．无向图的邻接矩阵中非0元素数就是该图所有顶点的度之和
　　C．有向图的邻接矩阵中第i行的非0元素之和是第i个顶点的入度
　　D．有向图的邻接矩阵中第i列的非0元素之和是第i个顶点的出度
　　● 从邻接矩阵 可以看出，该图共有 （5） 个顶点；如果是有向图，该图共有（6） 条弧；如果是无向图，则共有 （7） 条边。
　　（5）A．9 B．3 C．6 D．1
　　（6）A．5 B．4 C．3 D．2
　　（7）A．5 B．4 C．3 D．2
　　● n个节点的无向图的邻接表最多有 （8） 个表节点。
　　（8）A．n2 B．n(n-1) C．n(n+1) D．n
　　● 在有向图的邻接表存储结构中，顶点V在链表中出现的次数是 （9） 。
　　（9）A．顶点V的度 B．顶点V的出度
　　C．顶点V的入度 D．依附于顶点V的边数
　　● 含有n个顶点、e条边的有向图的邻接矩阵中非零元素有 （10） 个。
　　（10）A．n B．2e C．e D．n+e
　　2．选择题练习答案与分析
　　题号（1）
　　答案 D
　　习题分析：
　　邻接矩阵是用两个数组分别存储数据元素的信息和数据元素之间的关系的信息。当用二维数组表示n个顶点的图时，需要存放n个顶点信息和n2个弧信息。因此，该矩阵的大小是n2。
　　题号（2）
　　答案 A
　　习题分析：
　　邻接表法的空间复杂度为O(n+e)，与顶点数和边数都相关。
　　题号（3）
　　答案 B
　　习题分析：
　　由于邻接表是为每一个顶点建立一个单链表，n个顶点就要创建n个链表；除了头节点外，每个节点存放的都是其邻接的节点号。而在有向图中，第i个单链表的节点数只是顶点Vi的出度，因此答案为B。
　　题号（4）
　　答案 B
　　习题分析：
　　（1）无向图的邻接矩阵是一个对角线为0的对称矩阵，其非0元素数是图边数的两倍，选项A错误。
　　（2）有向图的邻接矩阵中第i行的非0元素之和是第i个顶点的出度，第i列的非0元素之和是第i个顶点的入度，选项C、D错误。因此答案为B。
　　题号（5）  （6）  （7）
　　答案 B  B  D
　　习题分析：
　　从习题1中邻接矩阵的定义可知，该图为3个节点。而当图是有向图时，邻接矩阵中的每个非0数字都表示一条弧的信息；当图是无向图时，邻接矩阵是一个对称矩阵，每条弧需要用两个非0数字来表示。
　　注意：无向图的邻接矩阵一定是对称矩阵，但邻接矩阵是对称矩阵的图不一定是无向图，如本题中的邻接矩阵，既可以是无向图，也可以是有向图。
　　题号（8）
　　答案 B
　　习题分析：
　　在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点Vi的边。也就是说，图中的每一条边，都需要一个表节点来表示。而在n个节点无向图中，最多可能有n(n-1)条边。因此，答案为B。
　　题号（9）
　　答案 C
　　习题分析：
　　根据题（8）对邻接表的描述可知，有向图邻接表第i个单链表中节点的个数表示顶点Vi的出度；而顶点V在整个邻接表中出现的次数则表示顶点Vi的入度。
　　题号（10）
　　答案 C
　　习题分析：
　　使用邻接矩阵存储有向图，有向图中的每一条弧分别用矩阵中的一个非0元素描述，因此邻接矩阵中的非0元素数就是有向图的边条数。
　　3．训练自测表（如表4-3所示）

表4-3  选择题练习自测表