数据结构答案2023

第六章测试

1.具有4个顶点的无向完全图有（ ）条边。
A:6 B:16 C:12 D:20

答案:A
2.具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。
A:5 B:6 C:7 D:8
3.在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
A:4
B:1/2 C:2 D:1 4.任何一个无向连通图的最小生成树（ ）。
A:有一棵或多棵 B:可能不存在
C:一定有多棵 D:只有一棵 5.设无向图G=（V，E），G'=（V'，E'），如果G'是G的生成树，则下面说法错误的是（ ）。
6.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定不是对称矩阵。（ ）
A:对 B:错 7.某无向图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)），对该图进行深度优先遍历，则顶点序列正确的是（ ）。
A:a,b,e,c,d,f B:a,e,d,f,c,b
C:a,e,b,c,f,d D:a,c,f,e,b,d 8.已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6},E={＜v1,v2＞,＜v1,v4＞,＜v2,v6＞,
＜v3,v1＞,＜v3,v4＞,＜v4,v5＞,＜v5,v2＞,＜v5,v6＞},G的拓扑序列是（ ）。
A:v1,v3,v4,v5,v2,v6 B:v3,v4,v1,v5,v2,v6
C:v1,v4,v3,v5,v2,v6
D:v3,v1,v4,v5,v2,v6 9.关键路径是事件结点网络中（ ）。
A:最短的回路
B:最长的回路 C:从源点到汇点的最长路径
D:从源点到汇点的最短路径 10.

普里姆算法是一种通过选点法构造最小生成树的算法。时间复杂度为（ ）。

A:O（n+e） B:O（e^2）  
C:O（n^2） D:O（eloge）