隴南師專離散數(shù)學(xué)試卷一、選擇題（每題1分，共10分）

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

A.{1}B.{2,3}C.{3,4}D.{1,4}

2.下列哪個命題是重言式？

A.p∧?pB.p∨?pC.p→?pD.?(p∨?p)

3.設(shè)命題公式p為“今天是星期一”，q為“我去看電影”，則公式“如果今天不是星期一，那么我去看電影”的符號化形式是？

A.p→qB.?p→qC.q→pD.?q→p

4.下列哪組命題是等價的？

A.p∨q，?p∨qB.p∧q，?p∧?qC.p→q，?p∧qD.p→q，?q→?p

5.設(shè)集合A有5個元素，B有3個元素，則從A到B的不同函數(shù)個數(shù)是？

A.15B.8C.125D.35

6.下列哪個是偏序關(guān)系？

A.<B.>C.=D.≠

7.設(shè)有向圖G包含n個頂點，則G中最多有多少條邊？

A.nB.n(n-1)C.n(n+1)/2D.2^n

8.完全二叉樹有7個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)是？

A.13B.14C.15D.16

9.下列哪個是圖G的鄰接矩陣？

A.

[[0,1,0,1],

[1,0,1,0],

[0,1,0,1],

[1,0,1,0]]

B.

[[0,0,0,0],

[0,0,0,0],

[0,0,0,0],

[0,0,0,0]]

C.

[[1,1,1,1],

[1,1,1,1],

[1,1,1,1],

[1,1,1,1]]

D.

[[0,1,1,0],

[1,0,1,1],

[1,1,0,1],

[0,1,1,0]]

10.下列哪個是正確的邏輯推理？

A.前提：p∨q，結(jié)論：p

B.前提：p→q，q，結(jié)論：p

C.前提：p∧q，結(jié)論：p∨q

D.前提：p→q，結(jié)論：?p→?q

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

1.下列哪些是命題？

A.今天天氣很好。B.x+y=5。C.2是偶數(shù)。D.請開門。

2.設(shè)集合A={a,b,c}，下列哪些是A的子集？

A.{a}B.{b,c}C.?D.{a,b,c,d}

3.下列哪些是等價式？

A.p→q≡?p∨qB.p?q≡(p→q)∧(q→p)C.?(p∧q)≡?p∨?qD.p∨?p≡⊥

4.下列哪些是歐拉圖？

A.有向圖，每個頂點的入度等于出度。B.無向圖，每個頂點的度數(shù)都是偶數(shù)。C.有n個頂點，n條邊的圈。D.無向圖，連通且無奇數(shù)環(huán)。

5.下列哪些是樹？

A.連通無向圖，無環(huán)。B.有n個頂點，n-1條邊的無向圖。C.每個頂點的度數(shù)最多為2。D.有向圖，根結(jié)點唯一，且從根結(jié)點到任意結(jié)點有唯一路徑。

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

1.設(shè)命題p為“天下雨”，q為“我?guī)恪?，則“如果天下雨，那么我不帶傘”的符號化形式是________。

2.集合A={1,2,3}與B={a,b}的笛卡爾積A×B的元素個數(shù)是________。

3.若集合A有m個元素，B有n個元素，則從A到B的不同函數(shù)個數(shù)是________。

4.一個有向圖G包含5個頂點，如果G是強(qiáng)連通的，則G中至少有________條邊。

5.設(shè)T是一個深度為4的滿二叉樹，則T的總結(jié)點數(shù)是________。

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

1.化簡命題公式(p∧q)∨(?p∧q)∨(p∧?q)。

2.設(shè)集合A={1,2,3}，B={a,b}，構(gòu)造從A到B的所有的函數(shù)，并說明其中雙射函數(shù)的個數(shù)。

3.判斷下列關(guān)系式是否為偏序關(guān)系，如果是，說明其是否為全序關(guān)系。

R={(1,1),(1,2),(2,2),(3,3),(2,3),(3,2)}。

4.給定無向圖G的鄰接矩陣如下，求圖G中頂點1的度數(shù)，并畫出該圖。

[[0,1,1,0],

[1,0,1,1],

[1,1,0,0],

[0,1,0,0]]

5.設(shè)有一個二叉樹，其前序遍歷序列為ABDACE，中序遍歷序列為DBAECF，請畫出該二叉樹。

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

**一、選擇題答案及解析**

1.B

解析：A∩B表示A和B的共同元素，即{2,3}。

2.B

解析：p∨?p表示p或非p，根據(jù)排中律，這總是為真。

3.B

解析：“今天不是星期一”是?p，“我去看電影”是q，所以公式為?p→q。

4.A

解析：p∨q和?p∨q都等價于q∨?p，根據(jù)交換律，它們是等價的。

5.C

解析：從A到B的函數(shù)個數(shù)是B的元素個數(shù)的A的元素次方，即3^5=125。

6.D

解析：≠表示不相等關(guān)系，滿足自反性、對稱性和傳遞性，是偏序關(guān)系。

7.B

解析：有向圖的最大邊數(shù)是n(n-1)，因為每個頂點可以指向其他n-1個頂點。

8.A

解析：完全二叉樹的總結(jié)點數(shù)等于葉子結(jié)點數(shù)加上非葉子結(jié)點數(shù)，葉子結(jié)點數(shù)為7，非葉子結(jié)點數(shù)為6，總計13。

9.A

解析：鄰接矩陣表示圖中頂點之間的連接關(guān)系，A選項表示頂點1與2、4相連，頂點2與1、3相連，頂點3與2、4相連，頂點4與1、3相連。

10.D

解析：根據(jù)反證法，如果?q為真，則?p也為真，所以?p→?q成立。

**二、多項選擇題答案及解析**

1.A,C

解析：命題是能夠判斷真假的陳述句，A和C都是命題。

2.A,B,C

解析：子集是原集合的元素的任意組合，包括空集和原集合本身，但不包括元素個數(shù)多于原集合的集合，所以A、B、C是子集。

3.A,B,C

解析：這些都是邏輯等價式，可以通過真值表驗證。

4.B,C

解析：B是無向圖，每個頂點的度數(shù)都是偶數(shù)，所以是歐拉圖；C是n個頂點n條邊的圈，也是歐拉圖。

5.A,B,D

解析：樹是連通無環(huán)的無向圖，B是樹的定義，D是根樹的定義，A是樹的性質(zhì)。

**三、填空題答案及解析**

1.?p→?q

解析：根據(jù)題意，p是“天下雨”，q是“我?guī)恪?，所以命題是“如果天下雨，那么我不帶傘”，符號化形式為?p→?q。

2.6

解析：笛卡爾積A×B的元素個數(shù)是A的元素個數(shù)乘以B的元素個數(shù)，即3×2=6。

3.n^m

解析：從A到B的函數(shù)個數(shù)是B的元素個數(shù)的A的元素次方，即n^m。

4.4

解析：強(qiáng)連通圖是指任意兩個頂點之間都有路徑，至少需要4條邊才能保證5個頂點都互相可達(dá)。

5.31

解析：滿二叉樹的總結(jié)點數(shù)公式為2^(h+1)-1，其中h是深度，所以總結(jié)點數(shù)是2^(4+1)-1=31。

**四、計算題答案及解析**

1.q

解析：通過分配律和結(jié)合律，(p∧q)∨(?p∧q)∨(p∧?q)可以化簡為q∨(p∧?p)，而p∧?p總是假，所以化簡為q。

2.共8個函數(shù)，雙射函數(shù)有6個。

解析：從A到B的函數(shù)共有3^2=9個，雙射函數(shù)是指每個A的元素都唯一對應(yīng)B的元素，可以列舉出6個。

3.是偏序關(guān)系，但不是全序關(guān)系。

解析：R滿足自反性、反對稱性和傳遞性，所以是偏序關(guān)系；但存在(2,3)和(3,2)，所以不是全序關(guān)系。

4.頂點1的度數(shù)為2，圖如下：

```

1--2

||

4--3

```

解析：鄰接矩陣的第一行表示頂點1與其他頂點的連接關(guān)系，1和4相連，所以度數(shù)為2。

5.二叉樹如下：

```

A

/\

BC

/\

DE

/

F

```

解析：前序遍歷是根節(jié)點先訪問，中序遍歷是左子樹先訪問，右子樹后訪問，根據(jù)這兩個序列可以重建二叉樹。

**知識點分類和總結(jié)**

離散數(shù)學(xué)的理論基礎(chǔ)主要包括邏輯基礎(chǔ)、集合論、圖論和組合數(shù)學(xué)等部分。

**邏輯基礎(chǔ)**：主要學(xué)習(xí)命題邏輯和謂詞邏輯，包括命題、聯(lián)結(jié)詞、真值表、邏輯等價式、推理規(guī)則等。邏輯基礎(chǔ)是離散數(shù)學(xué)的基石，用于描述和推理數(shù)學(xué)命題。

**集合論**：主要學(xué)習(xí)集合的概念、運算、關(guān)系等，包括集合的并、交、差、補、笛卡爾積等運算，以及集合的性質(zhì)和運算律。集合論是離散數(shù)學(xué)的重要工具，用于描述和研究離散對象的結(jié)構(gòu)和關(guān)系。

**圖論**：主要學(xué)習(xí)圖的概念、性質(zhì)、遍歷、最短路徑、最小生成樹等，包括無向圖、有向圖、歐拉圖、哈密頓圖、樹等特殊圖。圖論是離散數(shù)學(xué)的重要應(yīng)用領(lǐng)域，用于描述和研究離散對象之間的復(fù)雜關(guān)系。

**組合數(shù)學(xué)**：主要學(xué)習(xí)計數(shù)、排列、組合、生成函數(shù)等，包括排列組合的基本原理、二項式定理、組合恒等式等。組合數(shù)學(xué)是離散數(shù)學(xué)的重要工具，用于解決計數(shù)和組合問題。

**各題型所考察學(xué)生的知識點詳解及示例**

**選擇題**：主要考察學(xué)生對基本概念和定理的理解，以及簡單的推理和判斷能力。例如，選擇題中的命題邏輯部分考察學(xué)生對命題、聯(lián)結(jié)詞、真值表等概念的理解；集合論部分考察學(xué)生對集合運算、關(guān)系等概念的理解。

**多項選擇題**：主要考察學(xué)生對復(fù)雜概念和定理的綜合理解和應(yīng)用能力，以及多角度思考問題的能力。例如，多項