廣州大學離散數(shù)學試卷一、選擇題（每題1分，共10分）

1.在集合論中，集合A包含元素1,2,3，集合B包含元素2,3,4，則集合A和集合B的并集是？

A.{1,2,3}

B.{2,3,4}

C.{1,2,3,4}

D.{1,4}

2.下列哪個是命題？

A.今天天氣很好。

B.2+2=5

C.請開門

D.他很高

3.在命題邏輯中，命題p為“今天是星期一”，命題q為“明天是星期二”，則命題“如果今天是星期一，那么明天是星期二”的符號表示是？

A.p∧q

B.p→q

C.p?q

D.?p∧q

4.下列哪個是等價式？

A.p∧q?q∧p

B.p→q??p∨q

C.p∧(q∨r)?(p∧q)∨(p∧r)

D.p∨?p?q

5.在謂詞邏輯中，謂詞P(x)表示“x是偶數(shù)”，則命題“存在一個偶數(shù)x，使得x大于2”的符號表示是？

A.?xP(x)∧x>2

B.?xP(x)∧x>2

C.?x(P(x)∧x>2)

D.?x(P(x)∨x>2)

6.在圖論中，一個圖G包含n個頂點和m條邊，則圖G的度數(shù)序列是？

A.頂點的度數(shù)排列

B.邊的度數(shù)排列

C.頂點的度數(shù)之和

D.邊的度數(shù)之和

7.下列哪個是歐拉圖？

A.存在奇數(shù)度頂點的圖

B.每個頂點的度數(shù)都是偶數(shù)

C.連通且存在奇數(shù)度頂點的圖

D.連通且每個頂點的度數(shù)都是偶數(shù)

8.在樹論中，一個樹T包含n個頂點，則樹T的邊數(shù)是？

A.n-1

B.n

C.n+1

D.2n

9.在組合數(shù)學中，從n個不同元素中取出k個元素的組合數(shù)是？

A.C(n,k)=n!/(k!*(n-k)!)

B.P(n,k)=n!/(n-k)!

C.C(n,k)=k!/(n!*(k-n)!)

D.P(n,k)=k!/(n!*(k-n)!)

10.在數(shù)理邏輯中，下列哪個是重言式？

A.p∧?p

B.p∨?p

C.p→?p

D.?(p∧q)??p∨?q

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

1.下列哪些是集合論中的基本運算？

A.并集

B.交集

C.差集

D.補集

E.符號積

2.在命題邏輯中，下列哪些是永假式？

A.p∧?p

B.p∨?p

C.p→p

D.?(p∧q)??p∨?q

E.p∨p

3.在謂詞邏輯中，下列哪些是正確的量詞用法？

A.?xP(x)

B.?xP(x)

C.?x?yQ(x,y)

D.?x?yQ(x,y)

E.?x?y?Q(x,y)

4.在圖論中，下列哪些是圖的基本性質(zhì)？

A.頂點數(shù)

B.邊數(shù)

C.度數(shù)序列

D.連通性

E.歐拉性

5.在樹論中，下列哪些是樹的特征？

A.無環(huán)連通圖

B.有n個頂點的樹有n-1條邊

C.每個頂點都可以被唯一地訪問

D.樹的任意兩個頂點之間有唯一的一條路徑

E.樹的度數(shù)序列是唯一的

三、填空題（每題4分，共20分）

1.集合A包含元素1,2,3，集合B包含元素3,4,5，則集合A和集合B的交集是________。

2.在命題邏輯中，命題p為“今天下雨”，命題q為“我出門”，則命題“如果今天不下雨，那么我出門”的符號表示是________。

3.在謂詞邏輯中，謂詞P(x)表示“x是整數(shù)”，則命題“所有整數(shù)都是偶數(shù)”的符號表示是________。

4.在圖論中，一個圖G包含n個頂點和m條邊，如果圖G是連通的，且每個頂點的度數(shù)都是偶數(shù)，則圖G存在歐拉回路，這個結(jié)論被稱為________定理。

5.在樹論中，一個樹T包含n個頂點，則樹T的邊數(shù)是________。

四、計算題（每題10分，共50分）

1.設(shè)集合A={1,2,3,4}，集合B={3,4,5,6}，集合C={1,5,7}。求集合A∪(B∩C)的元素。

2.寫出命題“如果今天是星期五，那么我去看電影”的否定形式。

3.在謂詞邏輯中，謂詞P(x)表示“x是大學生”，謂詞Q(x)表示“x是聰明的”，寫出命題“所有大學生都是聰明的”的符號表示，并解釋其中量詞的含義。

4.給定一個圖G，頂點集V={v1,v2,v3,v4}，邊集E={(v1,v2),(v2,v3),(v3,v4),(v4,v1)}。求圖G的度數(shù)序列，并判斷圖G是否是歐拉圖。

5.給定一個樹T，樹T的頂點集V={v1,v2,v3,v4,v5}，邊集E={(v1,v2),(v1,v3),(v2,v4),(v2,v5)}。求樹T的高度，并畫出樹T的形態(tài)圖。

本專業(yè)課理論基礎(chǔ)試卷答案及知識點總結(jié)如下

一、選擇題答案

1.C

2.B

3.B

4.A

5.C

6.A

7.D

8.A

9.A

10.B

二、多項選擇題答案

1.A,B,C,D

2.A

3.A,B,C,D,E

4.A,B,C,D,E

5.A,B,D,E

三、填空題答案

1.{3}

2.?p→q

3.?x(P(x)→Q(x))

4.歐拉

5.n-1

四、計算題答案

1.解：B∩C={5}，所以A∪(B∩C)={1,2,3,4}∪{5}={1,2,3,4,5}。

答案：{1,2,3,4,5}

2.解：命題“如果今天是星期五，那么我去看電影”的否定形式是“今天是星期五且我不去看電影”。

答案：今天是星期五且我不去看電影

3.解：命題“所有大學生都是聰明的”的符號表示是?x(P(x)→Q(x))。其中，?表示全稱量詞，即對于所有x，如果x是大學生，那么x是聰明的。

答案：?x(P(x)→Q(x))

4.解：圖G的度數(shù)序列是{2,2,2,2}。因為每個頂點的度數(shù)都是偶數(shù)，且圖G是連通的，所以圖G是歐拉圖。

答案：度數(shù)序列為{2,2,2,2}，圖G是歐拉圖

5.解：樹T的高度是3。樹T的形態(tài)圖如下：

```

v1

/\

v2v3

/\

v4v5

```

答案：樹T的高度是3，形態(tài)圖如上圖所示

知識點總結(jié)

集合論：集合的基本運算（并集、交集、差集、補集），集合的性質(zhì)（冪集、子集、真子集），集合的等價關(guān)系。

命題邏輯：命題的定義，邏輯連接詞（與、或、非、蘊含、等價），命題公式，永真式和永假式，對偶式。

謂詞邏輯：謂詞的定義，量詞（全稱量詞、存在量詞），謂詞公式，謂詞邏輯的等價式和蘊含式。

圖論：圖的基本概念（頂點、邊、無向圖、有向圖），圖的表示方法（鄰接矩陣、鄰接表），圖的性質(zhì)（度數(shù)、連通性、歐拉圖、哈密頓圖），樹的基本概念（無環(huán)連通圖、根樹、森林），樹的應用（最小生成樹、二叉搜索樹）。

組合數(shù)學：組合數(shù)的計算（排列、組合、組合恒等式），二項式定理，鴿巢原理，斯特林數(shù)，貝爾數(shù)。

各題型所考察學生的知識點詳解及示例

選擇題：考察學生對集合論、命題邏輯、謂詞邏輯、圖論、樹論等基本概念的掌握程度。例如，選擇題第1題考察了集合的并集運算，第2題考察了命題的定義，第3題考察了命題邏輯中的蘊含式，第4題考察了命題邏輯中的等價式，第5題考察了謂詞邏輯中的存在量詞，第6題考察了圖論中的度數(shù)序列，第7題考察了圖論中的歐拉圖，第8題考察了樹論中的邊數(shù)計算，第9題考察了組合數(shù)學中的組合數(shù)計算，第10題考察了數(shù)理邏輯中的重言式。

多項選擇題：考察學生對多個知識點的綜合理解和應用能力。例如，第1題考察了集合論中的基本運算，第2題考察了命題邏輯中的永假式，第3題考察了謂詞邏輯中的量詞用法，第4題考察了圖論中的圖的基本性質(zhì)，第5題考察了樹論中的樹的特征。

填空題：考察學生對基本概念和公式的記憶和理解能力。例如，第1題考察了集合的交集運算，第2題考察了命題邏輯中的蘊含式，第3題考察