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

1.下列哪個(gè)命題是永真的？

A.p∨?p

B.p∧?p

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

D.(p→q)?(?q→?p)

2.設(shè)集合A={1,2,3}，B={2,3,4}，則A∩B等于：

A.{1,2}

B.{3,4}

C.{2,3}

D.{1,4}

3.下列哪個(gè)是偏函數(shù)？

A.f:A→B，對(duì)于每個(gè)a∈A，都有唯一的b∈B使得f(a)=b

B.f:A→B，對(duì)于每個(gè)a∈A，都有唯一的b∈B使得f(a)=b，且對(duì)于每個(gè)b∈B，都存在至少一個(gè)a∈A使得f(a)=b

C.f:A→B，對(duì)于每個(gè)a∈A，都有唯一的b∈B使得f(a)=b，且對(duì)于每個(gè)b∈B，都有唯一的a∈A使得f(a)=b

D.f:A→B，對(duì)于每個(gè)a∈A，都有唯一的b∈B使得f(a)=b，且對(duì)于每個(gè)b∈B，都存在唯一的a∈A使得f(a)=b

4.下列哪個(gè)是歐拉圖？

A.一個(gè)連通圖，所有頂點(diǎn)的度數(shù)都是偶數(shù)

B.一個(gè)連通圖，存在奇數(shù)度的頂點(diǎn)

C.一個(gè)不連通圖，所有頂點(diǎn)的度數(shù)都是偶數(shù)

D.一個(gè)不連通圖，存在奇數(shù)度的頂點(diǎn)

5.設(shè)有向圖G=(V,E)，其中V={v1,v2,v3}，E={(v1,v2),(v2,v3),(v3,v1)}，則G的強(qiáng)連通分量是：

A.{v1,v2,v3}

B.{v1},{v2},{v3}

C.{v1,v2}

D.{v2,v3}

6.下列哪個(gè)是可判定問(wèn)題？

A.哥尼斯堡七橋問(wèn)題

B.哈密頓回路問(wèn)題

C.旅行商問(wèn)題

D.四色定理

7.設(shè)有自然數(shù)n，則n的階乘n!等于：

A.n×(n-1)×...×2×1

B.n×(n-1)×...×2

C.n×(n-1)×...×1

D.1

8.下列哪個(gè)是圖G的生成樹(shù)？

A.圖G的一個(gè)子圖，包含G的所有頂點(diǎn)，且是連通的

B.圖G的一個(gè)子圖，包含G的所有邊，且是連通的

C.圖G的一個(gè)子圖，包含G的所有頂點(diǎn)，且是連通的，且邊數(shù)最少

D.圖G的一個(gè)子圖，包含G的所有邊，且是連通的，且邊數(shù)最少

9.設(shè)有集合A={1,2,3}，B={2,3,4}，則A×B等于：

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

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

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

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

10.下列哪個(gè)是圖G的鄰接矩陣？

A.一個(gè)n×n的矩陣，其中第i行第j列的元素表示頂點(diǎn)i和頂點(diǎn)j之間是否有邊

B.一個(gè)n×n的矩陣，其中第i行第j列的元素表示頂點(diǎn)i和頂點(diǎn)j之間邊的數(shù)量

C.一個(gè)n×n的矩陣，其中第i行第j列的元素表示頂點(diǎn)i和頂點(diǎn)j之間邊的權(quán)重

D.一個(gè)n×n的矩陣，其中第i行第j列的元素表示頂點(diǎn)i和頂點(diǎn)j之間是否連通

二、多項(xiàng)選擇題（每題4分，共20分）

1.下列哪些是命題邏輯的推理規(guī)則？

A.假言推理

B.合取引入

C.附加

D.拒絕式

E.拉斯假言

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

A.頂點(diǎn)

B.邊

C.度數(shù)

D.路徑

E.矩陣

3.下列哪些是組合數(shù)學(xué)中的基本概念？

A.排列

B.組合

C.階乘

D.二項(xiàng)式系數(shù)

E.鴿巢原理

4.下列哪些是圖論中的算法？

A.深度優(yōu)先搜索

B.廣度優(yōu)先搜索

C.最小生成樹(shù)算法

D.最短路徑算法

E.旅行商問(wèn)題算法

5.下列哪些是可計(jì)算性問(wèn)題？

A.哥尼斯堡七橋問(wèn)題

B.哈密頓回路問(wèn)題

C.旅行商問(wèn)題

D.四色定理

E.停機(jī)問(wèn)題

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

1.在命題邏輯中，聯(lián)結(jié)詞“非”的符號(hào)表示是______。

2.設(shè)集合A和B的笛卡爾積為A×B，若A={a,b}，B={1,2,3}，則A×B=______。

3.一個(gè)有向圖G如果存在一條經(jīng)過(guò)所有頂點(diǎn)的有向路，則稱該圖為_(kāi)_____。

4.在圖論中，一個(gè)圖G的生成樹(shù)是G的一個(gè)子圖，它包含G的所有頂點(diǎn)，并且是______。

5.在組合數(shù)學(xué)中，從n個(gè)不同元素中取出k個(gè)元素的組合數(shù)，記作C(n,k)，其計(jì)算公式為_(kāi)_____。

四、計(jì)算題（每題10分，共50分）

1.給定命題公式(p∧q)→?r和r→(?p∨?q)，使用真值表證明這兩個(gè)公式是等價(jià)的。

2.設(shè)集合A={1,2,3,4}，B={2,4,6}，C={3,4,5}。計(jì)算(A∪B)×(B∩C)。

3.給定有向圖G如下，其中頂點(diǎn)集V={a,b,c,d}，邊集E={(a,b),(b,c),(c,d),(d,a),(a,c)}。求圖G的所有強(qiáng)連通分量。

4.計(jì)算組合數(shù)C(10,3)和C(10,7)，并解釋組合數(shù)的含義。

5.使用Prim算法求下面無(wú)向帶權(quán)圖的最小生成樹(shù)，并給出最終的最小生成樹(shù)及其總權(quán)值。圖的頂點(diǎn)為A,B,C,D,E，邊及權(quán)值如下：

A-B:1

A-C:3

B-C:1

B-D:4

C-E:2

D-E:5

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

一、選擇題答案

1.A

2.C

3.A

4.A

5.A

6.D

7.A

8.C

9.C

10.A

二、多項(xiàng)選擇題答案

1.A,B,C,D

2.A,B,C,D,E

3.A,B,C,D,E

4.A,B,C,D,E

5.A,B,C,D,E

三、填空題答案

1.?

2.{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}

3.哈密頓圖

4.無(wú)環(huán)

5.n!/(k!×(n-k)!)

四、計(jì)算題答案及解題過(guò)程

1.真值表證明：

p|q|r|?r|?p|?q|?p∨?q|(?p∨?q)∧r|(p∧q)→?r|(r→(?p∨?q))|等價(jià)性

—|—|—|——|——|——|——|——|——|——|——

T|T|T|F|F|F|F|F|F|F|T

T|T|F|T|F|F|F|F|T|T|T

T|F|T|F|F|T|T|T|F|F|F

T|F|F|T|F|T|T|F|T|T|T

F|T|T|F|T|F|F|F|T|F|F

F|T|F|T|T|F|F|F|T|T|T

F|F|T|F|T|T|T|T|T|F|F

F|F|F|T|T|T|T|F|T|T|T

從真值表可以看出，(p∧q)→?r和r→(?p∨?q)在所有情況下的真值都相同，因此它們是等價(jià)的。

2.計(jì)算(A∪B)×(B∩C)：

A∪B={1,2,3,4}

B∩C={4}

(A∪B)×(B∩C)={(1,4),(2,4),(3,4),(4,4)}

3.圖G的強(qiáng)連通分量：

圖G的強(qiáng)連通分量是{a,b,c,d}，因?yàn)榇嬖谝粭l經(jīng)過(guò)所有頂點(diǎn)的有向路。

4.計(jì)算組合數(shù)：

C(10,3)=10!/(3!×(10-3)!)=120

C(10,7)=10!/(7!×(10-7)!)=120

組合數(shù)的含義是從n個(gè)不同元素中取出k個(gè)元素的組合數(shù)，不考慮順序。

5.使用Prim算法求最小生成樹(shù)：

初始時(shí)，選擇頂點(diǎn)A作為起點(diǎn)。

A-B:1

A-C:3

選擇最小邊A-B，當(dāng)前最小生成樹(shù)邊集T={(A,B)}

剩余頂點(diǎn){C,D,E}

B-C:1(已存在)

A-C:3

B-D:4

選擇最小邊A-C，當(dāng)前最小生成樹(shù)邊集T={(A,B),(A,C)}

剩余頂點(diǎn){D,E}

C-E:2

B-D:4

選擇最小邊C-E，當(dāng)前最小生成樹(shù)邊集T={(A,B),(A,C),(C,E)}

剩余頂點(diǎn){D}

D與當(dāng)前最小生成樹(shù)沒(méi)有直接連接的邊，因此最小生成樹(shù)完成。

最小生成樹(shù)邊集T={(A,B),(A,C),(C,E)}

總權(quán)值=1+3+2=6

知識(shí)點(diǎn)分類和總結(jié)

離散數(shù)學(xué)的理論基礎(chǔ)部分主要包括以下知識(shí)點(diǎn)：

1.命題邏輯

-命題及其聯(lián)結(jié)詞

-真值表

-推理規(guī)則

-等價(jià)式

2.集合論

-集合的基本概念

-集合的運(yùn)算（并、交、差、補(bǔ)）

-笛卡爾積

-集合的性質(zhì)

3.圖論

-圖的基本概念（頂點(diǎn)、邊、度數(shù)）

-圖的表示方法（鄰接矩陣、鄰接表）

-圖的遍歷（深度優(yōu)先搜索、廣度優(yōu)先搜索）

-圖的連通性（連通分量、生成樹(shù)）

-最優(yōu)圖算法（最小生成樹(shù)、最短路徑）

4.組合數(shù)學(xué)

-排列與組合

-階乘與二項(xiàng)式系數(shù)

-組合恒等式

-鴿巢原理

-遞推關(guān)系

各題型所考察學(xué)生的知識(shí)點(diǎn)詳解及示例

一、選擇題

-考察學(xué)生對(duì)命題邏輯、集合論、圖論、組合數(shù)學(xué)等基本概念的掌握程度。

-示例：判斷一個(gè)命題公式是否為永真式，考察學(xué)生對(duì)命題邏輯推理規(guī)則的掌握。

二、多項(xiàng)選