圖論考試題及答案

圖論考試題及答案一、選擇題（8題，每題3分，共24分）

1.在圖論中，下列哪一項不是圖的性質(zhì)？

A.無向性

B.有向性

C.算法性

D.連通性

2.一個圖中有n個頂點和m條邊，該圖被稱為？

A.完全圖

B.樹

C.多重圖

D.簡單圖

3.在圖論中，哪個概念用于描述從一個頂點到另一個頂點的路徑長度？

A.頂點度

B.路徑長度

C.環(huán)

D.連通分量

4.下列哪個算法用于尋找無向圖中所有頂點對之間的最短路徑？

A.拓?fù)渑判?/p>

B.Dijkstra算法

C.Floyd-Warshall算法

D.Kruskal算法

5.在有向圖中，哪個概念用于描述一個頂點到另一個頂點的最短路徑？

A.路徑長度

B.頂點度

C.有向環(huán)

D.強(qiáng)連通分量

6.一個無向圖中，如果每個頂點的度數(shù)都是n-1，那么這個圖被稱為？

A.完全圖

B.樹

C.多重圖

D.簡單圖

7.在圖論中，哪個概念用于描述一個圖中所有頂點的度數(shù)之和？

A.頂點度

B.邊數(shù)

C.路徑長度

D.圖的階

8.下列哪個算法用于尋找無向圖中的最小生成樹？

A.拓?fù)渑判?/p>

B.Dijkstra算法

C.Kruskal算法

D.Floyd-Warshall算法

二、（一）多項選擇題（5題，每題4分，共20分）

1.下列哪些是圖論中的基本概念？

A.頂點

B.邊

C.環(huán)

D.路徑

E.算法

2.下列哪些算法可以用于尋找圖中的最短路徑？

A.Dijkstra算法

B.Floyd-Warshall算法

C.Kruskal算法

D.拓?fù)渑判?/p>

E.Bellman-Ford算法

3.下列哪些是圖的性質(zhì)？

A.無向性

B.有向性

C.連通性

D.算法性

E.頂點度

4.下列哪些是圖論中的基本概念？

A.頂點

B.邊

C.環(huán)

D.路徑

E.算法

5.下列哪些算法可以用于尋找圖中的最小生成樹？

A.Kruskal算法

B.Prim算法

C.Dijkstra算法

D.Floyd-Warshall算法

E.Bellman-Ford算法

（二）判斷題（5題，每題2分，共10分）

1.在圖論中，一個圖的頂點度是指與該頂點相連的邊的數(shù)量。（對）

2.在有向圖中，一個頂點的入度是指進(jìn)入該頂點的邊的數(shù)量。（對）

3.在圖論中，一個樹是一個沒有環(huán)的連通圖。（對）

4.在圖論中，一個完全圖是一個每個頂點都與所有其他頂點相連的圖。（對）

5.在圖論中，一個圖的連通分量是指圖中最大的連通子圖。（錯）

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

1.在圖論中，一個圖的頂點度是指與該頂點相連的邊的數(shù)量。

2.在有向圖中，一個頂點的入度是指進(jìn)入該頂點的邊的數(shù)量。

3.在圖論中，一個樹是一個沒有環(huán)的連通圖。

4.在圖論中，一個完全圖是一個每個頂點都與所有其他頂點相連的圖。

5.在圖論中，一個圖的連通分量是指圖中所有互相連通的頂點集合。

（二）計算題（3題，每題5分，共15分）

1.給定一個無向圖，頂點分別為A、B、C、D，邊分別為AB、AC、BC、CD，求每個頂點的度數(shù)。

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，求該圖的所有強(qiáng)連通分量。

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

1.分析Dijkstra算法的基本思想，并說明其在尋找最短路徑時的優(yōu)缺點。

2.分析Kruskal算法的基本思想，并說明其在尋找最小生成樹時的優(yōu)缺點。

答案部分：

一、選擇題

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.在圖論中，一個圖的頂點度是指與該頂點相連的邊的數(shù)量。

2.在有向圖中，一個頂點的入度是指進(jìn)入該頂點的邊的數(shù)量。

3.在圖論中，一個樹是一個沒有環(huán)的連通圖。

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.強(qiáng)連通分量:{1,2,3,4,5}

五、材料分析題

1.Dijkstra算法的基本思想是通過貪心策略，從起始頂點出發(fā)，逐步擴(kuò)展最短路徑的集合，直