《数据结构》课程教学资源（作业习题）练习题及答案7

（C)1.在一个图中，所有顶点的度数之和等于图的边数的倍。 4.12 B.1 C2 D.4 （B)2在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍 A.12 B.1 C.2 D.4 (B)3.有8个结点的无向图最多有条边。 A.14 B.28 C56 D.112 (C)4.有8个结点的无向连通图最少有条边。 A.5 B.6 C.7 D.8 (C)5.有8个结点的有向完全图有条边。 4.14 B.28 C.56 D.112 (B)6.用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A.栈 B.队列 C.树 D.图 (A)7.用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A.栈 B.队列 C.树 D.图 （日)8.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先滤历的结点序列是 「01111017 1001001 A.0243156 000100 B.0136542 1100110 C.0423165 1011010 D.0361542 0001101 1100010 建议：0134256 （D)12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 12刀 A.0132 B.0231 032口 C.0321 D.0123 02 （A)13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遗历的结点序列是 31 2 1 A.0321 B.0123 230 C.0132 D.0312 3 1☐0☑ 20 （A)14.深度优先遍历类似于二叉树的 A先序遍历 B中序遍历 C后序遍历D.层次遍历 (D)15.广度优先遗历类似于二叉树的 A.先序遍历 B中序历C.后序遮历D.层次通历

1 （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）3. 有 8 个结点的无向图最多有 条边。 A．14 B. 28 C. 56 D. 112 （ C ）4. 有 8 个结点的无向连通图最少有 条边。 A．5 B. 6 C. 7 D. 8 （ C ）5. 有 8 个结点的有向完全图有 条边。 A．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 （ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点 0 出发按深度优先遍历的结点序列是 （ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是 （ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结点序列是 （ A ）14. 深度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ D ）15. 广度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 A．0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D. 0 3 6 1 5 4 2  建议：0 1 3 4 2 5 6      1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1 A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3 A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2

二、填空题（每空1分，共20分） 1.图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历_、广度优先適历_等方法 2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。 3.如果n个顶点的图是一个环，则它有”棵生成树。（以任意一顶点为起点，得到m1条边） 日n个顶点条边的图，若采用邻接矩阵存储，则空间复杂度为0一· 3n个顶点e条边的图，若采用邻接表存储，则空间复杂度为Oe。 10.图的深度优先遗历序列不是惟一的。 11.n个顶点©条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为①山：若采用邻接 表存储时，该算法的时间复杂度为O+e一。 12.n个顶点ε条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为0：若采用邻接 表存储，该算法的时间复杂度为_0+ 14.用普里姆(Pim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O}用克鲁 斯卡尔Kruskal算法的时间复杂度是O(eog心) 三、简答题（每题6分，共24分） 1.【严题集7.1①】已知如图所示的有向图，请给出该图的 (1)每个顶点的入V出度： 顶点23456 1 (2) 邻接矩阵： (3 入度 邻接表 出度 (4)逆邻接表。 答案： 7.1(1) (2)邻接矩阵 顶点123456 0000007 入度321122 100100 010001 出度022313 001011 100000 山110010 (3)邻接表 (4)逆邻接表 6 6 2A 回0 A

2 二、填空题（每空 1 分，共 20 分） 1. 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。 2. 有向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 出度 。 3. 如果 n 个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点，得到 n-1 条边） 4. n 个顶点 e 条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2 ) 。 5. n 个顶点 e 条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。 10. 图的深度优先遍历序列 不是 惟一的。 11. n 个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2 ) ；若采用邻接 表存储时，该算法的时间复杂度为 O(n+e) 。 12. n 个顶点 e 条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2 ) ；若采用邻接 表存储，该算法的时间复杂度为 O(n+e) 。 14. 用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为 O(n2 ) ；用克鲁 斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。 三、简答题（每题 6 分，共 24 分） 1. 【严题集 7.1①】已知如图所示的有向图，请给出该图的: （1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。 答案： 顶点 1 2 3 4 5 6 入度 出度

3.【严愿集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遭历所 得的深度优先生成树和广度优先生成树。 |12345678910 深度优先生成树 广度优先生成树 1010 ① 23 0 ⊙ 4567 0, ⊙ 。1 ⊙ 81 ⊙ 00 00010 90000101001 o 101000010000 四、【2001年计考研题】给定下列网G:(10分) A 112 (B 20 4 E F (G0 D 1试着找出网G的最小生成树，画出其逻辑结构图： 用两种不同的 成树可直接 2.可用邻接矩阵和邻接表来描述： 020 89 020015 012 10 ∠ 8 00 00 00600 60 9 060 12106060c0 邻接表为 a +b2 b 12 c20 f9 d g 12 4 f 6 g 12 d10 2

3 3. 【严题集 7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点 1 出发进行遍历所 得的深度优先生成树和广度优先生成树。 四、 【2001 年计考研题】给定下列网 G: （10 分） 1 试着找出网 G 的最小生成树，画出其逻辑结构图； 2 用两种不同的表示法画出网 G 的存储结构图； 解：1. 最小生成树可直接画出，如右图所示。 2. 可用邻接矩阵和邻接表来描述：                                                      12 10 9 6 4 8 6 15 10 20 15 12 12 20 8 9 12 4 邻接表为： a → b 12 → e 4 ^ b → a 12 → c 20 → e 8 → f 9 ^ c → b 20 → d 15 → g 12 ^ d → c 15 → g 10 ^ e → a 4 → b 8 → f 6 ^ f → b 9 → e 6 ^ g → c 12 → d 10 A B———————C E————F G————D