数据结构图练习试题

图练习: 1. 图中有关路径的定义是（ ）。 A. 由顶点和相邻顶点序偶构成的边所形成的序列 B. 由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是 2•设无向图的顶点个数为m则该图最多有（）条边。 2 • n. n （n+1）/2 D. 0 EA. n-1 个n个顶点的连通无向图，其边的个数至少为（ A. nT B. n C. n+1 4. 要连通具有n个顶点的有向图，至少需要（ A. n-l B. n C. n+l 5. n个结点的完全有向图含有边的数目（）o A. n*n B . n （n+ 1 ） C. n / 2 B. n(n~1)/2 C3.— )o D. nlogn； )条边。 D. 2n D. n* (n—I) 6. 一个有n个结点的图，最少有（ 分量。 ）个连通分量，最多有（ ）个连通 A. 0 B. 1 C. n-1 D. n 7. 在一个无向图中，所有顶点的度数之和等于所有边数（ 向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍，在一个有 ）倍。 A. 1/2 B. 2 C. 1 D. 4 8. 下列说法不正确的是（ ）o A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次 C.图的深度遍历 不适用于有向图 B. 遍历的基本算法有两种：深度遍历和广度遍历 D.图的深度遍历 是一个递归过程 9. 无向图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）｝,对该图 进行深度优先遍历，得到的顶点序列正确的是（ ）。 C. a. e. b. c. f. d A. a. b. e, c. d. f B. a, c. f. e. b, d D・ a. e. d. f. c. b 10. 关键路径是事件结点网络中（ ）o A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C. 最长回路 D.最短回路 10A 9D 8C 二判断题 1 •树中的结点和图中的顶点就是指数据结构中的数据元素。（ ） 2. 在n个结点的无向图中，若边数大于门-1・则该图必是连通图。（） 3. 对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e二。（ ） 4. 有e条边的无向图，在邻接表中有e个结点。（ ） 5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（） 6. 强连通图的各顶点间均可达。（） 7. 邻接多重表是无向图和有向图的链式存储结构。（） 8. 十字链表是无向图的一种存储结构。（ ） 9. 用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ） 10•有n个顶点的无向图，采用邻接矩阵表示.图中的边数等于邻接矩阵中非零 元素之和的一半。（ ） 门.有向图的邻接矩阵是对称的。（ ） 12. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 （ ） 13. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图, 而只能使用邻接表存储形式来存储它。（ ） 14. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间 大小与图中结点个数有关，而与图的边数无关。（ ） 15. 广度遍历生成树描述了从起点到各顶点的最短路径。（ ） 16. 任何无向图都存在生成树。（） 17. 不同的求最小生成树的方法最后得到的生成树是相同的.（ ） 18. 带权无向图的最小生成树必是唯一的。（ ） 19. 最小代价生成树是唯一的。（ ） 20. 一个网（带权图）都有唯一的最小生成树。（ ） 21. 连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 22. 带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（） 23. 带权的连通无向图的最小代价生成树是唯一的。（ ） 24. 最小生成树问题是构造连通网的最小代价生成树。（ ） 1. V 2・ X 3. X 4. X 5. X 6. V 7X 8X 9. X 10. 1112. XXV 2423 V13・ 21. 18. 16. 14. 15. 17. 19. 22. 20. V X X X X X X X V X X 三、填空题 匚判断一个无向图是一棵树的条件是 O 2. 有向图G的强连通分量是指 o . 3. 一个连通图的 是一个极小连通子图。. 4. 具有10个顶点的无向图，边的总数最多为 o . 5. 若用n表示图中顶点数目，则有 条边的无向图成为完全图。. 6•设无向图G有n个顶点和e条边，每个顶点Vi的度为di (1<=i<=n\则 7. G是一个非连通无向图，共有28条边，则该图至少有 个顶点。. 8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 条弧。 9. 在有n个顶点的有向图中，每个顶点的度最大可达 o . 10•设G为具有N个顶点的无向连通图，则G中至少有 条边。. 11. n个顶点的连通无向图，其边的条数至少为 o・ 12. 如果含n个顶点的图形形成一个坏，则它有 棵生成树。. 13. N个顶点的连通图的生成树含有 条边。. 条弧。 个结点的强连通图，至少有n.构造14 15. 有N个顶点的有向图，至少需要量 条弧… 才能保证是连通的。 16. 右图中的强连通分量的个数为( )个。 17. N个顶点的连通图用邻接矩阵表示时，该矩阵 至少有 个非零元素。. 18. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说 等于该顶点的 ;对于有向图来说等于该顶点的 o .. 19. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是 o . 20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为 ,邻接表的边结点个数为 。.. 21. 已知一无向图 G二(V, E),其中 V={a,b.c.d.e } E={(a,b), (a.d), (a.c). (d. c), (b.e))现用某一种图遍历方法从顶点a开始遍历 图，得到的序列为abecd,则采用的是 遍历方法。. 答案： 1•有n个顶点，nT条边的无向连通图 2. 有向图的极大强连通子图 3.生成树 4. 45 5. n (n-1 )/2 6 7. 9 8. n 9. 2(n-1) 10. NT 11. n-1 15. N 16. 3 17. 2 (N-1) 18.度出度 22.深度优先 23.宽度优先遍历 12. n 13. N-1 14. n 19.第I列非零元素个数 2e 四、应用题 1. (D.如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？ G1最少有多少 条边？ (2) .如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？ G2最少有多少 条边？ (3) .如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？ G3最少有多少 条边？ 2. n个顶点的无向连通图最少有多少条边？ n个顶点的有向连通图最少有多少条边？ 3. 首先将如下图所示的无向图给岀其存储结构的邻接链表表示，然后写出对其分别进行深度, 广度优先遍历的结果。 23 4 4 32 76 5 8 5 76 9 98 10 G： 4.给出图G的邻接表表示图；1).画出(的深度优先生成树和广度优先生成树。).根据 你画出的邻接表，以顶点①为根，画出G2 (.对一个图进行遍历可以得到不同的遍历序列，那 么导致得到的遍历序列不唯一的因素有5哪些？.考虑下图：6出发，求它的深度优先生成树 (1) 从顶点A岀发，求它的广度优先生成树从顶点E(2)点开始从A)根据普利姆(Prim)算法, 求它的最小生成树3 ( kruskal算法，求它的最小生成树(4)根据 7.考虑下图：(1)从顶点A出发，求它的深度优先生成树 (2) 从顶点E出发，求它的广度优先生成树 (3) 根据普利姆(Prim)算法，求它的最小生成树从1点开始 (4) 根据kruskal算法，求它的最小生成树 答案： 1. (D 61最多n(n-1)/2条边，最少nT条边 条边n条边，最少n(n-1)最多 (2) G2. (3) G3最多n(n-1)条边，最少nT条边(注：弱连通有向图指把有向图看作无向图时，仍是 连通的) 2. n~1, n 3. 深度优先遍历序列：4 宽度优先遍历序列：9 注：(1)邻接表不唯一，这里顶点的邻接点按升序排列 (2)在邻接表确定后，深度优先和宽度优先遍历序列唯一 (3)这里的遍历，均从顶点1开始 4•略 5. 遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不 同。 6. 设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列 (DABGFDEC (2) EACFBDG 略7.