数据结构与算法（仲恺农业工程学院）答案2023秋

第六章测试

1.要连通具有n个顶点的有向图，至少需要（ ）条边。
A:n-1 B:2n C:n+1 D:n
答案:D
2.在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍
A:4 B:1 C:1/2 D:2 3.下列说法不正确的是（ ）
A:遍历的基本算法有两种：深度遍历和广度遍历  B:图的遍历是从给定的源点出发每一个顶点仅被访问一次  C:图的深度遍历不适用于有向图 D:图的深度遍历是一个递归过程 4.下列哪一种图的邻接矩阵是对称矩阵？（ ）
A:无向图 B:AOV网 C:有向图 D:AOE网 5.

已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，G的拓扑序列是（  ）。

A:

V1,V3,V4,V5,V2,V6,V7

B:

V1,V3,V4,V6,V2,V5,V7

C:

V1,V2,V5,V3,V4,V6,V7

D:

V1,V3,V2,V6,V4,V5,V7

6.关键路径是事件结点网络中（ ）
A:最短回路 B:最长回路 C:从源点到汇点的最长路径 D:从源点到汇点的最短路径 7.下列关于AOE网的叙述中，不正确的是（ ）。
A:某些关键活动提前完成，那么整个工程将会提前完成 B:所有的关键活动提前完成，那么整个工程将会提前完成 C:任何一个关键活动提前完成，那么整个工程将会提前完成 D:关键活动不按期完成就会影响整个工程的完成时间 8.任何一个带权无向连通图（ ）最小生成树
A:有一棵或多棵 B:一定有多棵 C:可能不存在 D:只有一棵 9.判断一个有向图是否存在回路除了可以使用拓扑排序算法，还可以使用（ ）
A:求关键路径的方法 B:深度优先遍历算法 C:广度优先遍历算法 D:求最短路径的Dijkstra算法 10.如果从无向图的任一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）
A:一棵树 B:有回路 C:连通图 D:完全图 11.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）算法
A:先序遍历 B:层序遍历 C:后序遍历 D:中序遍历 12.采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）算法
A:后序遍历 B:层序遍历 C:先序遍历 D:中序遍历 13.一个无向连通图的最小生成树是含有该连通图的全部顶点的（ ）
A:极小连通子图 B:极大子图 C:极小子图 D:极大连通子图 14.无权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ）。
A:第i列0的元素个数 B:第i行0的元素个数 C:第i列非0的元素个数 D:第i行非0的元素个数 15.设无向图的顶点个数为n，则该图最多有（ ）条边。
A:n-1 B:n*(n+1)/2  C: D:n*(n-1)/2  16.由n个顶点、e条边构成的图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（ ）。
A:O(n+e) B: C:O(n) D: 17.一个具有n个顶点的五项图，采用邻接矩阵表示，这该矩阵大小为（    ）。
A: B:n C: D:n-1 18.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（   ）。
A:aebcfd  B:aedfcb C:acfebd D:aedfbc 19.一个有n个结点的图，最少有（     ）个连通分量。
A:n B:n-1 C:1 D:0