北航離散數(shù)學試題及答案姓名：____________________

一、選擇題（每題2分，共20分）

1.設集合A={1,2,3}，B={2,3,4}，那么A∩B的結果是：

A.{2,3}

B.{1,2,3}

C.{2,3,4}

D.{1,2,3,4}

2.在關系R={(1,2),(2,3),(3,4)}中，下列哪個是R的逆關系？

A.{(1,2),(2,3),(3,4)}

B.{(2,1),(3,2),(4,3)}

C.{(1,2),(3,4),(2,3)}

D.{(1,3),(2,4),(3,2)}

3.一個圖G的鄰接矩陣是一個方陣，其中第i行第j列的元素表示：

A.G中頂點i和頂點j之間的邊數(shù)

B.G中頂點i到頂點j的最短路徑長度

C.G中頂點i和頂點j之間的距離

D.G中頂點i和頂點j之間是否存在邊

4.在二叉樹中，度為0的節(jié)點稱為：

A.葉子節(jié)點

B.內(nèi)部節(jié)點

C.根節(jié)點

D.子節(jié)點

5.設集合A={1,2,3}，B={2,3,4}，那么A∪B的結果是：

A.{1,2,3}

B.{2,3,4}

C.{1,2,3,4}

D.{}

6.在關系R={(1,2),(2,3),(3,4)}中，下列哪個是R的自反關系？

A.{(1,1),(2,2),(3,3)}

B.{(1,2),(2,3),(3,4)}

C.{(2,1),(3,2),(4,3)}

D.{(1,1),(2,2),(3,3),(4,4)}

7.一個有向圖G的鄰接矩陣是一個方陣，其中第i行第j列的元素表示：

A.G中頂點i到頂點j的邊數(shù)

B.G中頂點i到頂點j的最短路徑長度

C.G中頂點i和頂點j之間的距離

D.G中頂點i和頂點j之間是否存在邊

8.在二叉樹中，度為1的節(jié)點稱為：

A.葉子節(jié)點

B.內(nèi)部節(jié)點

C.根節(jié)點

D.子節(jié)點

9.設集合A={1,2,3}，B={2,3,4}，那么A-B的結果是：

A.{1,2,3}

B.{2,3,4}

C.{1,2,3,4}

D.{}

10.在關系R={(1,2),(2,3),(3,4)}中，下列哪個是R的反自反關系？

A.{(1,1),(2,2),(3,3)}

B.{(1,2),(2,3),(3,4)}

C.{(2,1),(3,2),(4,3)}

D.{(1,1),(2,2),(3,3),(4,4)}

二、填空題（每題2分，共20分）

1.設集合A={1,2,3}，B={2,3,4}，那么A∩B=__________，A∪B=__________，A-B=__________。

2.在關系R={(1,2),(2,3),(3,4)}中，R的逆關系是__________，R的自反關系是__________，R的反自反關系是__________。

3.在二叉樹中，度為0的節(jié)點稱為__________，度為1的節(jié)點稱為__________，度為2的節(jié)點稱為__________。

4.有向圖G的鄰接矩陣是一個方陣，其中第i行第j列的元素表示__________。

5.設集合A={1,2,3}，B={2,3,4}，那么A×B=__________。

三、簡答題（每題10分，共30分）

1.簡述集合的概念及其性質(zhì)。

2.簡述關系的概念及其性質(zhì)。

3.簡述圖的概念及其性質(zhì)。

四、應用題（每題15分，共30分）

1.已知集合A={1,2,3,4,5}，B={2,3,4,5,6}，求A與B的笛卡爾積A×B，并列舉出A×B中的前5個元素。

2.設關系R={(1,2),(2,3),(3,4)}，求R的逆關系R^-1，并判斷R是否為對稱關系。

五、證明題（每題15分，共30分）

1.證明：對于任意集合A，A的補集A'與A的并集A∪A'等于全集U。

2.證明：在一個有向圖中，如果存在一條從頂點i到頂點j的路徑，那么一定存在一條從頂點j到頂點i的路徑。

六、綜合題（每題20分，共40分）

1.設有向圖G的鄰接矩陣如下：

```

0100

1010

0101

0010

```

（1）請畫出圖G的圖形表示。

（2）求圖G的度序列。

（3）判斷圖G是否為連通圖，并說明理由。

2.設有二叉樹T，其節(jié)點度序列為1,2,3,4，請畫出滿足該度序列的二叉樹T，并計算T的節(jié)點總數(shù)。

試卷答案如下：

一、選擇題答案及解析思路：

1.A.解析：集合A和B的交集包含A和B共有的元素，即{2,3}。

2.B.解析：關系R的逆關系是將R中的所有元素順序顛倒。

3.A.解析：鄰接矩陣的第i行第j列表示頂點i和頂點j之間是否有邊。

4.A.解析：度為0的節(jié)點沒有子節(jié)點，因此稱為葉子節(jié)點。

5.C.解析：集合A和B的并集包含A和B的所有元素，即{1,2,3,4}。

6.A.解析：自反關系要求關系中包含所有元素對自身的關系。

7.A.解析：鄰接矩陣的第i行第j列表示頂點i到頂點j的邊數(shù)。

8.B.解析：度為1的節(jié)點有一個子節(jié)點，因此稱為內(nèi)部節(jié)點。

9.A.解析：集合A減去B的結果是A中不屬于B的元素，即{1}。

10.A.解析：反自反關系要求關系中不包含任何元素對自身的關系。

二、填空題答案及解析思路：

1.A∩B={2,3}，A∪B={1,2,3,4,5,6}，A-B={1}。

2.R^-1={(2,1),(3,2),(4,3)}，R自反關系是空集，R反自反關系是{(1,1),(2,2),(3,3),(4,4)}。

3.度為0的節(jié)點稱為葉子節(jié)點，度為1的節(jié)點稱為內(nèi)部節(jié)點，度為2的節(jié)點稱為子節(jié)點。

4.有向圖G的鄰接矩陣的第i行第j列的元素表示頂點i到頂點j的邊數(shù)。

5.A×B={(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5),(4,2),(4,3),(4,4),(4,5)}。

三、簡答題答案及解析思路：

1.集合是由若干確定的元素組成的整體，具有確定性、互異性和無序性。集合的性質(zhì)包括封閉性、交換律、結合律、冪等律、補集律等。

2.關系是兩個集合的元素之間的一種對應關系，可以用一個有序?qū)蟻肀硎?。關系的性質(zhì)包括自反性、對稱性、傳遞性等。

3.圖是由頂點和邊組成的集合，頂點表示實體，邊表示實體之間的關系。圖的性質(zhì)包括連通性、路徑、環(huán)等。

四、應用題答案及解析思路：

1.A×B={(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5),(4,2),(4,3),(4,4),(4,5)}。前5個元素為{(1,2),(1,3),(1,4),(1,5),(2,2)}。

2.R^-1={(2,1),(3,2),(4,3)}，R不是對稱關系，因為沒有{(2,3),(3,2)}在R中。

五、證明題答案及解析思路：

1.證明：對于任意集合A，A的補集A'與A的并集A∪A'等于全集U。

證明過程如下：

（1）對于任意元素x∈U，如果x∈A，那么x∈A∪A'；如果x?A，那么x∈A'，因此x∈A∪A'。所以A∪A'=U。

（2）對于任意元素x∈U，如果x∈A，那么x?A'；如果x?A，那么x∈A'。所以A∪A'=A。

因此，A的補集A'與A的并集A∪A'等于全集U。

2.證明：在一個有向圖中，如果存在一條從頂點i到頂點j的路徑，那么一定存在一條從頂點j到頂點i的路徑。

證明過程如下：

假設存在一條從頂點i到頂點j的路徑，路徑上的頂點序列為i=v1,v2,...,vk,j，其中vi是頂點序列上的頂點，k是頂點的數(shù)量。

我們可以構造一條從頂點j到頂點i的路徑，路徑上的頂點序列為j=vk,vk-1,...,v1,i。這條路徑是原始路徑的逆序，因此存在從頂點j到頂點i的路徑。

六、綜合題答案及解析思路：

1.（1）根據(jù)鄰接矩陣，畫出圖G的圖形表示如下：

```

1---2---3-