图论考试题及答案

图论考试题及答案一、选择题（8题，每题3分，共24分）

1.在图论中，下列哪一项不是图的性质？

A.无向性

B.有向性

C.算法性

D.连通性

2.一个图中有n个顶点和m条边，该图被称为？

A.完全图

B.树

C.多重图

D.简单图

3.在图论中，哪个概念用于描述从一个顶点到另一个顶点的路径长度？

A.顶点度

B.路径长度

C.环

D.连通分量

4.下列哪个算法用于寻找无向图中所有顶点对之间的最短路径？

A.拓扑排序

B.Dijkstra算法

C.Floyd-Warshall算法

D.Kruskal算法

5.在有向图中，哪个概念用于描述一个顶点到另一个顶点的最短路径？

A.路径长度

B.顶点度

C.有向环

D.强连通分量

6.一个无向图中，如果每个顶点的度数都是n-1，那么这个图被称为？

A.完全图

B.树

C.多重图

D.简单图

7.在图论中，哪个概念用于描述一个图中所有顶点的度数之和？

A.顶点度

B.边数

C.路径长度

D.图的阶

8.下列哪个算法用于寻找无向图中的最小生成树？

A.拓扑排序

B.Dijkstra算法

C.Kruskal算法

D.Floyd-Warshall算法

二、（一）多项选择题（5题，每题4分，共20分）

1.下列哪些是图论中的基本概念？

A.顶点

B.边

C.环

D.路径

E.算法

2.下列哪些算法可以用于寻找图中的最短路径？

A.Dijkstra算法

B.Floyd-Warshall算法

C.Kruskal算法

D.拓扑排序

E.Bellman-Ford算法

3.下列哪些是图的性质？

A.无向性

B.有向性

C.连通性

D.算法性

E.顶点度

4.下列哪些是图论中的基本概念？

A.顶点

B.边

C.环

D.路径

E.算法

5.下列哪些算法可以用于寻找图中的最小生成树？

A.Kruskal算法

B.Prim算法

C.Dijkstra算法

D.Floyd-Warshall算法

E.Bellman-Ford算法

（二）判断题（5题，每题2分，共10分）

1.在图论中，一个图的顶点度是指与该顶点相连的边的数量。（对）

2.在有向图中，一个顶点的入度是指进入该顶点的边的数量。（对）

3.在图论中，一个树是一个没有环的连通图。（对）

4.在图论中，一个完全图是一个每个顶点都与所有其他顶点相连的图。（对）

5.在图论中，一个图的连通分量是指图中最大的连通子图。（错）

三、（一）填空题（5题，每题3分，共15分）

1.在图论中，一个图的顶点度是指与该顶点相连的边的数量。

2.在有向图中，一个顶点的入度是指进入该顶点的边的数量。

3.在图论中，一个树是一个没有环的连通图。

4.在图论中，一个完全图是一个每个顶点都与所有其他顶点相连的图。

5.在图论中，一个图的连通分量是指图中所有互相连通的顶点集合。

（二）计算题（3题，每题5分，共15分）

1.给定一个无向图，顶点分别为A、B、C、D，边分别为AB、AC、BC、CD，求每个顶点的度数。

2.给定一个有向图，顶点分别为1、2、3、4，边分别为1->2、2->3、3->4、4->1，求每个顶点的入度和出度。

3.给定一个无向图，顶点分别为A、B、C、D，边分别为AB、AC、BC、CD，求该图的最小生成树。

四、综合题（2题，每题15分，共30分）

1.给定一个无向图，顶点分别为A、B、C、D、E，边分别为AB、AC、AD、BC、BD、CD、CE，求该图的所有连通分量。

2.给定一个有向图，顶点分别为1、2、3、4、5，边分别为1->2、2->3、3->4、4->5、5->1，求该图的所有强连通分量。

五、材料分析题（2题，每题17分，共34分）

1.分析Dijkstra算法的基本思想，并说明其在寻找最短路径时的优缺点。

2.分析Kruskal算法的基本思想，并说明其在寻找最小生成树时的优缺点。

答案部分：

一、选择题

1.C

2.D

3.B

4.C

5.A

6.A

7.B

8.C

二、（一）多项选择题

1.A,B,D,E

2.A,B,E

3.A,B,C,E

4.A,B,D,E

5.A,B

（二）判断题

1.对

2.对

3.对

4.对

5.错

三、（一）填空题

1.在图论中，一个图的顶点度是指与该顶点相连的边的数量。

2.在有向图中，一个顶点的入度是指进入该顶点的边的数量。

3.在图论中，一个树是一个没有环的连通图。

4.在图论中，一个完全图是一个每个顶点都与所有其他顶点相连的图。

5.在图论中，一个图的连通分量是指图中所有互相连通的顶点集合。

（二）计算题

1.A:3,B:2,C:3,D:2

2.1:出度1，入度0；2:出度1，入度1；3:出度1，入度1；4:出度1，入度1；5:出度0，入度1

3.AB,AC,AD,BC,BD,CD

四、综合题

1.连通分量:{A,B,C,D,E}

2.强连通分量:{1,2,3,4,5}

五、材料分析题

1.Dijkstra算法的基本思想是通过贪心策略，从起始顶点出发，逐步扩展最短路径的集合，直