)12.已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是 2[31门 A.0132 B.0231 2/ C.0321 D.0123 0□00 ()13.已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是 T[2 A.0321 B.0123 0/ C.0132 D.0312 ()14.深度优先遍历类似于二叉树的 先序遍历 B.中序遍历C.后序遍历D.层次遍历 ()15.广度优先遍历类似于二叉树的 先序遍历B.中序遍历C.后序遍历 层次遍历 ()16.任何一个无向连通图的最小生成树 A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在 填空题(每空1分,共20分) 图有 等存储结构,遍历图有 等方 法 2.有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的 3.如果n个顶点的图是一个环,则它有 棵生成树。 4.n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为 5.n个顶点e条边的图,若采用邻接表存储,则空间复杂度为 6.设有一稀疏图G,则G采用 存储较省空间。 7.设有一稠密图G,则G采用 存储较省空间。 8.图的逆邻接表存储结构只适用于 图 9.已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是 10.图的深度优先遍历序列 惟一的。2 （ ）12. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是 （ ）13. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结点序列是 （ ）14. 深度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ ）15. 广度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ ）16. 任何一个无向连通图的最小生成树 A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 二、填空题（每空 1 分，共 20 分） 1. 图有 、 等存储结构，遍历图有 、 等方 法。 2. 有向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 。 3. 如果 n 个顶点的图是一个环，则它有 棵生成树。 4. n 个顶点 e 条边的图，若采用邻接矩阵存储，则空间复杂度为 。 5. n 个顶点 e 条边的图，若采用邻接表存储，则空间复杂度为 。 6. 设有一稀疏图 G，则 G 采用 存储较省空间。 7. 设有一稠密图 G，则 G 采用 存储较省空间。 8. 图的逆邻接表存储结构只适用于 图。 9. 已知一个图的邻接矩阵表示，删除所有从第 i 个顶点出发的方法是 。 10. 图的深度优先遍历序列 惟一的。 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