第7章习题(带答案).pdf

1. 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个( )A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵2. 有 n 个顶点的无向连通图中最少有n-1 条边，最多有n(n-1)/2条边3. 在有 n个顶点的有向图的邻接表中顶点I 的入度为顶点 I 在所有邻接点单链表中出现的次数，顶点 I 的出度为顶点 I 的邻接点单链表中结点的个数4. 有 n 个顶点的强连通图中最少有n条边，最多有n(n-1) 条边5. 在有 n 个顶点的有向图的邻接矩阵中顶点I 的入度为第 I 列 1的个数，最顶点 I 的出度为第 I 行 1 的个数6. 对 AOV网进行拓扑排序，则其拓扑排序序列一定包含图中的所有顶点错）7.Prim （普里姆）算法适用于求__稠密性 ____网的最小生成树； kruskal （克鲁斯卡尔）算法适用于求 __稀疏性 _____网的最小生成树8. 具有 10 个顶点的无向图，边的总数最多为45_ ，最少为0 9.G 是一个非连通无向图，共有28条边，则该图至少有 __8__个顶点10.n 个顶点的强连通图至多有( )条边A) 2 （n-1）B)n（n-1）C)n－1 D)2n(n-1) 11. 在一个有向图中，所有顶点入度之和等于所有顶点出度之和的( )倍A)1/2 B) 1 C) 2 D) 4 12. 下列关于无向连通图特性的叙述中，正确的是：Ⅰ. 所有顶点的度之和为偶数Ⅱ. 边数大于顶点数减1 Ⅲ. 至少有一个顶点的度为1 A.只有Ⅰ B.只有Ⅱ C.Ⅰ和Ⅱ D.Ⅰ和Ⅲ13. （）方法可以判断出一个有向图中是否有环( 回路)。

A.深度优先遍历 B. 求关键路径 C.求最短路径 D. 拓扑排序14. 下列有关图遍历的说法中不正确的是( )A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每一顶点仅被访问一次15.在一个无向图中，所有顶点的度数之和等于所有边数的2 倍，在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的1 倍16.一个带权的无向连通图的最小生成树（）A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在17. 具有 n 个顶点的无向图 G最少应该有 n-1 条边才能确保是一个连通图18. 带权有向图 G用邻接矩阵 A[][]存储，则顶点 i 的入度等于 A中________A ．第 i 行非∞的元素之和 B．第 i 行非∞的元素个数C．第 i 列非∞的元素之和D ．第 i 列非∞的元素个数19. 图的广度优先遍历类似于二叉树的按层次遍历20. 已知一个图如下，则由该图得到的一种拓扑序列为（） A、1,4,6,2,5,3 B、1,2,3,4,5,6 C、1,4,2,3,6,5 D、1,2,4,6,3,5 21. 已知一有向图的邻接表存储结构如下图所示，根据图的深度优先搜索遍历算法，从顶点 v1 出发，得到的顶点序列为（） 。

A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2 22.若无向图中度为 1 的顶点有 3 个, 度为 2 的顶点有 4 个, 度为 3 的顶点有 3 个, 度为 4 的顶点有 1 个, 则该无向图有 __12___条边23.某无向图的邻接表如下图所示, 从 A 开始深度优先搜索遍历所得到的结点序列为__AEDCB 从 B 开始广度优先搜索遍历所得到的结点序列为BCADE 24. 图的邻接矩阵表示法适用于表示( ) A．无向图B．有向图C．稠密图D．稀疏图25. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 ___边_____的数目正相关26. 将 1-N 排成一个圈，使任意相邻两个数之和为素数N为任意大于 1 的正整数；如有解，求出所有满足条件的解以及解的个数当 N=5时，没有解当 N=6时， 有 2组满足条件的解：1 4 3 2 5 6 1 6 5 2 3 4 当 N=7时，没有解当 N=8时，有 4 组满足条件的解：1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 0 A 1 B 2 C 3 D 4 E 4 3 1 ^ 2 0 ^ 3 1 ^ 4 2 0 ^ 3 0 ^ 。