第七章 图 （答案版）

第七章 图 习题 一、选择题 1、 在一个无向图中，所有顶点的度数之和等于图的边数的____倍。 C A、1/2 B、1 C、2 D、4 2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 B A、1/2 B、1 C、2 D、4 3、有8个结点的无向图最多有____条边。 B A、14 B、28 C、56 D、112 4、有8个结点的无向连通图最少有____条边。 C A、5 B、6 C、7 D、8 5、有8个结点的有向完全图有____条边。 C A、14 B、28 C、56 D、112 6、用邻接表表示图进行广度优先遍历时，通常是采用____来实现算法的。 B A、栈 B、队列 C、树 D、图 7、用邻接表表示图进行深度优先遍历时，通常是采用____来实现算法的。 A A、栈 B、 队列 C、树 D、图 8、已知图的邻接矩阵如下，其顶点信息是由0-6七个数字组成，且其顺序表保存的次序也恰好是0-6，请根据算法思想，给出从顶点0出发按深度优先遍历的结点序列是： D A、 0 2 4 3 1 5 6 B、 0 1 3 5 6 4 2 C、 0 4 2 3 1 6 5 D、 0 1 3 4 2 5 6 9、已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是 B A、 0 2 4 3 6 5 1 B、 0 1 2 3 4 6 5 C、 0 4 2 3 1 5 6 D、 0 1 3 4 2 5 6 10、已知图的邻接表如下所示，根据算法，则从顶点V0出发按深度优先遍历的结点序列是 D A、V0 V1 V3 V2 B、V0 V2 V3 V1 C、V0 V3 V2 V1 D、V0 V1 V2 V3 11、 已知图的邻接表如下所示，根据算法，则从顶点V0出发按广度优先遍历的结点序列是 A A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2 A、V0 V3 V2 V1 B、V0 V1 V2 V3 C、V0 V1 V3 V2 D、V0 V3 V1 V2 二、填空题 1、 图有 邻接矩阵、邻接表 等存储结构，遍历图有_深度优先遍历、广度优先遍历等方法。 2、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。 3、 如果n个顶点的图是一个环，则它有 n 棵生成树。 4、 n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2)。 5、 n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。 6、设有一稀疏图G，则G采用 邻接表 存储较省空间。 7、设有一稠密图G，则G采用 邻接矩阵 存储较省空间。 8、 图的逆邻接表存储结构只适用于 有向 图。 9、 已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。 10、对于一个逻辑图而言，它的深度优先遍历序列 不是 惟一的。 11、 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为_ O(n2) ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。 12、拓扑排序算法是通过重复选择具有__0__个前驱顶点的过程来完成的。 三、简答题 1、 如图所示的有向图，请给出该图的:1）每个顶点的入/出度；2）邻接矩阵；3）邻接表；4）逆邻接表。 顶点 1 2 3 4 5 6 入度 出度 答：1） 顶点 11 22 33 44 55 66