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

1.在集合論中，集合A包含于集合B的符號(hào)表示是？

A.A∩B

B.A∪B

C.A?B

D.A?B

2.下列哪個(gè)命題是永假式？

A.P∨?P

B.P∧?P

C.P→P

D.?P→P

3.在命題邏輯中，聯(lián)結(jié)詞“與非”可以表示為？

A.∧

B.∨

C.?

D.↑

4.下列哪個(gè)是命題公式？

A.P∧Q∨R

B.(P∧Q)∨R→S

C.P∧(Q∨R)∨S

D.P∧Q→R∧S

5.在圖論中，一個(gè)無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)之和等于多少？

A.圖的邊數(shù)

B.2倍圖的邊數(shù)

C.圖的頂點(diǎn)數(shù)

D.2倍圖的頂點(diǎn)數(shù)

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

A.存在奇數(shù)度頂點(diǎn)的連通圖

B.所有頂點(diǎn)度數(shù)均為偶數(shù)的連通圖

C.不存在歐拉回路的連通圖

D.不存在歐拉路徑的連通圖

7.在樹(shù)論中，一個(gè)樹(shù)的邊數(shù)是多少？

A.頂點(diǎn)數(shù)-1

B.頂點(diǎn)數(shù)+1

C.2倍頂點(diǎn)數(shù)

D.頂點(diǎn)數(shù)的平方

8.下列哪個(gè)是哈密頓圖？

A.存在哈密頓回路的連通圖

B.所有頂點(diǎn)度數(shù)均大于等于頂點(diǎn)數(shù)/2的連通圖

C.不存在哈密頓回路的連通圖

D.不存在哈密頓路徑的連通圖

9.在關(guān)系論中，函數(shù)關(guān)系是？

A.每個(gè)自變量對(duì)應(yīng)多個(gè)因變量

B.每個(gè)自變量對(duì)應(yīng)一個(gè)因變量

C.每個(gè)因變量對(duì)應(yīng)多個(gè)自變量

D.每個(gè)因變量對(duì)應(yīng)一個(gè)自變量

10.在代數(shù)結(jié)構(gòu)中，群的定義是什么？

A.一個(gè)非空集合和一個(gè)二元運(yùn)算，滿足結(jié)合律

B.一個(gè)非空集合和一個(gè)二元運(yùn)算，滿足交換律

C.一個(gè)非空集合和一個(gè)二元運(yùn)算，滿足封閉性和單位元

D.一個(gè)非空集合和一個(gè)二元運(yùn)算，滿足逆元和結(jié)合律

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

1.下列哪些是命題邏輯中的基本聯(lián)結(jié)詞？

A.與（∧）

B.或（∨）

C.非（?）

D.蘊(yùn)含（→）

E.等價(jià)（?）

2.在集合論中，下列哪些是正確的集合運(yùn)算？

A.交集（∩）

B.并集（∪）

C.補(bǔ)集（'）

D.差集（?）

E.對(duì)稱(chēng)差（△）

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

A.頂點(diǎn)（Vertex）

B.邊（Edge）

C.度數(shù)（Degree）

D.鄰接矩陣（AdjacencyMatrix）

E.歐拉回路（EulerianCircuit）

4.在樹(shù)論中，下列哪些是正確的性質(zhì)？

A.樹(shù)是無(wú)環(huán)連通圖

B.樹(shù)的邊數(shù)等于頂點(diǎn)數(shù)減1

C.樹(shù)的任意兩個(gè)頂點(diǎn)之間有唯一路徑

D.樹(shù)可以包含多個(gè)根節(jié)點(diǎn)

E.樹(shù)的子圖也是樹(shù)

5.在關(guān)系論中，下列哪些是函數(shù)關(guān)系的特點(diǎn)？

A.每個(gè)自變量對(duì)應(yīng)一個(gè)因變量

B.每個(gè)因變量對(duì)應(yīng)一個(gè)自變量

C.關(guān)系是單射的

D.關(guān)系是滿射的

E.關(guān)系是雙射的

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

1.在命題邏輯中，公式P∧Q的否定是________。

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

3.在圖論中，一個(gè)有n個(gè)頂點(diǎn)的無(wú)向完全圖有________條邊。

4.在樹(shù)論中，一個(gè)有n個(gè)頂點(diǎn)的樹(shù)有________條邊。

5.在關(guān)系論中，一個(gè)關(guān)系R是函數(shù)關(guān)系當(dāng)且僅當(dāng)對(duì)于任意x，存在唯一的y使得________。

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

1.對(duì)于命題公式P=(Q→R)∧(?Q∨R)，求其真值表。

2.設(shè)集合A={1,2,3},B={x|x∈N,1≤x≤4},C={2,4}，求(A∪B)×C。

3.給定圖G，頂點(diǎn)集V={a,b,c,d},邊集E={{a,b},{a,c},{b,c},{b,d},{c,d}}，求每個(gè)頂點(diǎn)的度數(shù)，并判斷圖G是否是連通圖。

4.給定一棵樹(shù)T，頂點(diǎn)集V={1,2,3,4,5,6},邊集E={{1,2},{1,3},{2,4},{2,5},{3,6}}，求樹(shù)T的高度。

5.給定關(guān)系R={(1,a),(2,b),(3,b),(4,c)}，判斷關(guān)系R是否是函數(shù)關(guān)系，如果是，請(qǐng)說(shuō)明是哪種類(lèi)型的函數(shù)關(guān)系（單射、滿射、雙射）。

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

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

1.C.A?B

解析：集合A包含于集合B表示A中的所有元素都在B中。

2.B.P∧?P

解析：P與它的否定?P同時(shí)為真是不可能的，因此是永假式。

3.D.↑

解析：“與非”邏輯運(yùn)算符用符號(hào)↑表示。

4.D.P∧Q→R∧S

解析：其他選項(xiàng)存在語(yǔ)法錯(cuò)誤或不是完整的命題公式。

5.B.2倍圖的邊數(shù)

解析：根據(jù)握手定理，無(wú)向圖中所有頂點(diǎn)的度數(shù)之和等于2倍圖的邊數(shù)。

6.B.所有頂點(diǎn)度數(shù)均為偶數(shù)的連通圖

解析：歐拉圖是指存在歐拉回路的連通圖，當(dāng)且僅當(dāng)所有頂點(diǎn)度數(shù)均為偶數(shù)。

7.A.頂點(diǎn)數(shù)-1

解析：樹(shù)是最簡(jiǎn)單的連通圖，邊數(shù)等于頂點(diǎn)數(shù)減1。

8.A.存在哈密頓回路的連通圖

解析：哈密頓圖是指存在經(jīng)過(guò)所有頂點(diǎn)的簡(jiǎn)單回路。

9.B.每個(gè)自變量對(duì)應(yīng)一個(gè)因變量

解析：函數(shù)關(guān)系要求每個(gè)自變量有唯一確定的因變量。

10.D.一個(gè)非空集合和一個(gè)二元運(yùn)算，滿足逆元和結(jié)合律

解析：群的定義包括封閉性、結(jié)合律、單位元和逆元。

**二、多項(xiàng)選擇題答案及詳解**

1.A.與（∧），B.或（∨），C.非（?），D.蘊(yùn)含（→），E.等價(jià)（?）

解析：這些都是命題邏輯的基本聯(lián)結(jié)詞。

2.A.交集（∩），B.并集（∪），C.補(bǔ)集（'），D.差集（?），E.對(duì)稱(chēng)差（△）

解析：這些都是集合論的基本運(yùn)算。

3.A.頂點(diǎn)（Vertex），B.邊（Edge），C.度數(shù)（Degree），D.鄰接矩陣（AdjacencyMatrix），E.歐拉回路（EulerianCircuit）

解析：這些都是圖論的基本概念。

4.A.樹(shù)是無(wú)環(huán)連通圖，B.樹(shù)的邊數(shù)等于頂點(diǎn)數(shù)減1，C.樹(shù)的任意兩個(gè)頂點(diǎn)之間有唯一路徑

解析：D錯(cuò)誤，樹(shù)只有一個(gè)根節(jié)點(diǎn)；E錯(cuò)誤，子圖不一定是樹(shù)。

5.A.每個(gè)自變量對(duì)應(yīng)一個(gè)因變量，C.關(guān)系是單射的，D.關(guān)系是滿射的，E.關(guān)系是雙射的

解析：B錯(cuò)誤，函數(shù)關(guān)系要求每個(gè)自變量對(duì)應(yīng)一個(gè)因變量，不要求每個(gè)因變量對(duì)應(yīng)一個(gè)自變量。

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

1.?(P∧Q)或?P∨?Q

解析：根據(jù)德摩根定律，P∧Q的否定是?P∨?Q。

2.{2,3}

解析：交集是兩個(gè)集合共有的元素。

3.n(n-1)/2

解析：無(wú)向完全圖中每個(gè)頂點(diǎn)與其他所有頂點(diǎn)相連。

4.n-1

解析：樹(shù)邊數(shù)等于頂點(diǎn)數(shù)減1。

5.xRy

解析：關(guān)系R是函數(shù)關(guān)系當(dāng)且僅當(dāng)對(duì)于任意x，存在唯一的y使得(x,y)∈R。

**四、計(jì)算題答案及詳解**

1.真值表：

|Q|R|?Q|?Q∨R|Q→R|(?Q∨R)∧(Q→R)|

|---|---|-----|--------|-------|-------------------|

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

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

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

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

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

解析：A∪B={1,2,3,4}，(A∪B)×C是所有可能的有序?qū)Α?/p>

3.度數(shù)：deg(a)=3,deg(b)=3,deg(c)=2,deg(d)=1

連通圖：是

解析：圖是連通的，因?yàn)槿我鈨蓚€(gè)頂點(diǎn)之間有路徑。

4.樹(shù)T的高度：3

解析：從根節(jié)點(diǎn)1到最遠(yuǎn)葉子節(jié)點(diǎn)6的路徑長(zhǎng)度為3。

5.關(guān)系R是函數(shù)關(guān)系，是滿射

解析：每個(gè)自變量（1,2,3,4）都對(duì)應(yīng)唯一的因變量，且所有因變量（a,b,c）都被覆蓋。

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

1.**命題邏輯**：基本聯(lián)結(jié)詞、真值表、命題公式、永假式、蘊(yùn)含式等。

2.**集合論**：集合運(yùn)算（交集、并集、補(bǔ)集、差集、對(duì)稱(chēng)差）、集合關(guān)系（包含、相等）、笛卡爾積等。

3.**圖論**：基本概念（頂點(diǎn)、邊、度數(shù)）、特殊圖（歐拉圖、哈密頓圖）、樹(shù)（性質(zhì)、高度）、圖表示（鄰接矩陣）等。

4.**關(guān)系論**：關(guān)系定義、函數(shù)關(guān)系（單射、滿射、雙射）、關(guān)系性質(zhì)（自反性、對(duì)稱(chēng)性、傳遞性）等。

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

1.**選擇題**：考察學(xué)生對(duì)基本概念和定理的理解，如命題邏輯的基本聯(lián)結(jié)詞、集合運(yùn)算、圖論的基本概念等。

示例：命題邏輯中，公式P∧Q的否定是?P∨?Q。

2.**多項(xiàng)選擇題**：考察學(xué)生對(duì)多個(gè)相