数据结构图习题

05 图【单选题】1. 设无向图 G 中有五个顶点，各顶点的度分别为 2、4、3、1、2，则 G 中边数为（C）。Ａ、4 条 Ｂ、5 条 Ｃ、6 条 Ｄ、无法确定2. 含 n 个顶点的无向完全图有（D）条边；含 n 个顶点的有向图最多有（C）条弧；含 n 个顶点的有向强连通图最多有（C）条弧；含 n 个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有 n 个顶点，则要接通全部顶点至少需（G）条边。A、n2 B、n(n+1) C、n(n-1) D、n(n-1)/2 E、n+1 F、n G、n-13. 对下图从顶点 a 出发进行深度优先遍历，则（A）是可能得到的遍历序列。A、acfgdeb B、abcdefg C、acdgbef D、abefgcd 对下图从顶点 a 出发进行广度优先遍历，则（D）是不可能得到的遍历序列。A、abcdefg B、acdbfge C、abdcegf D、adcbgef4. 设图 G 的邻接矩阵 A=，则 G 中共有（C）个顶点；若 G 为有向图，则 G 中共有（D）条弧；若 G 为无向图，则 G 中共有（B）条边。A、1 B、2 C、3 D、4 E、5 F、9 G、以上答案都不对5. 含 n 个顶点的图，最少有（B）个连通重量，最多有（D）个连通重量。A、0 B、1 C、n-1 D、n6. 用邻接表存储图所用的空间大小（A）。A、与图的顶点数和边数都有关 B、只与图的边数有关C、只与图的顶点数有关 D、与边数的平方有关7. n 个顶点的无向图的邻接表最多有（B）个表结点。A、n2 B、n(n-1) C、n(n+1) D、n(n-1)/28. 无向图 G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D）。A、a,b,e,c,d,f B、a,c,f,e,b,d C、a,e,b,c,f,d D、a,e,d,f,c,b9. 图的 BFS 生成树的树高比 DFS 生成树的树高（A）。A、小或相等 B、小 C、大或相等 D、大10. 下列不正确的是（C）。(1)求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2)利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n3)；（图用邻接矩阵表示）(3)Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。A、(1),(2),(3) B、(1) C、(1),(3) D、(2),(3)11. 当各边上的权值（A）时，BFS 算法可用来解决单源最短路径问题。A、均相等 B、均互不相等 C、不一定相等12. 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（C）。A、对称矩阵...