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

1.設(shè)集合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.下列哪個(gè)命題是永真式？

A.p∧?p

B.p∨?p

C.p→?p

D.?(p∨q)→?p

3.在命題邏輯中，命題p的否定表示為？

A.p∧q

B.p∨q

C.?p

D.p?q

4.設(shè)有向圖G=(V,E)，其中V={a,b,c,d}，E={<a,b>,<b,c>,<c,d>,<d,a>}，則G的環(huán)數(shù)（環(huán)的個(gè)數(shù)）為？

A.0

B.1

C.2

D.3

5.完全二叉樹(shù)的高度為h，則該二叉樹(shù)的最大節(jié)點(diǎn)數(shù)為？

A.2^h

B.2^(h+1)-1

C.2h

D.2^(h-1)

6.在圖論中，最小生成樹(shù)是指？

A.邊數(shù)最少的樹(shù)

B.節(jié)點(diǎn)數(shù)最少的樹(shù)

C.邊權(quán)最小的生成樹(shù)

D.節(jié)點(diǎn)權(quán)最小的生成樹(shù)

7.下列哪個(gè)是有效的謂詞邏輯公式？

A.?x?yP(x,y)

B.?x?yP(x,y)

C.?x?yP(x,y)→?xP(x)

D.?x?yP(x,y)→?yP(y)

8.在集合論中，笛卡爾積A×B的定義是？

A.A∪B

B.A∩B

C.{<a,b>|a∈A,b∈B}

D.{<b,a>|a∈A,b∈B}

9.設(shè)有理數(shù)集合Q，則Q在實(shí)數(shù)集合R中的基數(shù)是？

A.|Q|

B.|R|

C.|Q|=|R|

D.|Q|<|R|

10.在數(shù)理邏輯中，命題“如果今天下雨，那么地面濕”的逆命題是？

A.如果地面濕，那么今天下雨

B.如果今天不下雨，那么地面不濕

C.如果地面不濕，那么今天不下雨

D.今天下雨或地面不濕

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

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

A.頂點(diǎn)

B.邊

C.?環(huán)

D.權(quán)重

E.謂詞

2.在集合論中，下列哪些運(yùn)算是常見(jiàn)的集合運(yùn)算？

A.并集

B.交集

C.差集

D.笛卡爾積

E.聯(lián)合

3.謂詞邏輯中，下列哪些是量詞的表示方法？

A.?（全稱(chēng)量詞）

B.?（存在量詞）

C.→（蘊(yùn)涵）

D.∧（合取）

E.∨（析?。?/p>

4.在樹(shù)結(jié)構(gòu)中，下列哪些是樹(shù)的基本性質(zhì)？

A.樹(shù)中沒(méi)有環(huán)

B.樹(shù)中每個(gè)節(jié)點(diǎn)有唯一父節(jié)點(diǎn)

C.樹(shù)中有且只有一個(gè)根節(jié)點(diǎn)

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

E.樹(shù)的高度與節(jié)點(diǎn)數(shù)成正比

5.最小生成樹(shù)算法中，下列哪些是常用的算法？

A.克魯斯卡爾算法

B.普里姆算法

C.拓?fù)渑判蛩惴?/p>

D.Dijkstra算法

E.快速排序算法

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

1.在命題邏輯中，符號(hào)“∧”表示_________。

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

3.在圖論中，一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有_________條邊。

4.謂詞邏輯中的量詞“?x”表示_________。

5.完全二叉樹(shù)的第h層有_________個(gè)節(jié)點(diǎn)。

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

1.已知集合A={x|x∈N且x<5}，B={x|x∈Z且-2<x<3}，求A∪B和A∩B。

2.寫(xiě)出命題公式(p∧q)→?r的等價(jià)形式。

3.給定有向圖G的鄰接矩陣如下：

```

0100

0010

0001

1000

```

求圖G中頂點(diǎn)a到頂點(diǎn)d的所有可能路徑。

4.已知一棵二叉樹(shù)的先序遍歷序列為ABCD，中序遍歷序列為BADC，求該二叉樹(shù)的后序遍歷序列。

5.使用克魯斯卡爾算法求圖G的最小生成樹(shù)，圖G的邊及其權(quán)重如下：

```

邊權(quán)重

AB2

AC3

AD1

BC4

BD5

CD6

```

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

一、選擇題答案及詳解

1.C{1,2,3,4}并集是兩個(gè)集合中所有的元素，包括重復(fù)的元素。

2.Bp∨?p根據(jù)排中律，p與它的否定?p至少有一個(gè)為真，所以p∨?p永真。

3.C?p否定命題p就是?p。

4.B1圖中存在一個(gè)環(huán)<?,a>。

5.B2^(h+1)-1完全二叉樹(shù)的最大節(jié)點(diǎn)數(shù)是2^(h+1)-1。

6.C邊權(quán)最小的生成樹(shù)最小生成樹(shù)是權(quán)值和最小的生成樹(shù)。

7.A?x?yP(x,y)全稱(chēng)量詞?表示對(duì)所有x，存在一個(gè)y使得P(x,y)成立。

8.C{<a,b>|a∈A,b∈B}笛卡爾積是所有形如<a,b>的有序?qū)Φ募?，a來(lái)自A，b來(lái)自B。

9.D|Q|<|R|有理數(shù)集Q是可數(shù)無(wú)限的，而實(shí)數(shù)集R是不可數(shù)無(wú)限的，所以|Q|<|R|。

10.A如果地面濕，那么今天下雨逆命題是將原命題的結(jié)論和條件互換。

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

1.ABD頂點(diǎn)、邊和權(quán)重是圖論的基本概念。

2.ABCD集合的并集、交集、差集和笛卡爾積都是常見(jiàn)的集合運(yùn)算。

3.AB量詞用?和?表示。

4.ABC樹(shù)的基本性質(zhì)是沒(méi)有環(huán)、每個(gè)節(jié)點(diǎn)有唯一父節(jié)點(diǎn)和有唯一根節(jié)點(diǎn)。

5.AB克魯斯卡爾算法和普里姆算法都是求最小生成樹(shù)的算法。

三、填空題答案及詳解

1.合取合取符號(hào)“∧”表示邏輯與。

2.{3}交集是兩個(gè)集合中都存在的元素。

3.n-1無(wú)向連通圖至少需要n-1條邊才能連接所有頂點(diǎn)。

4.對(duì)所有x都成立全稱(chēng)量詞“?x”表示對(duì)所有x的情況。

5.2^(h-1)完全二叉樹(shù)的第h層有2^(h-1)個(gè)節(jié)點(diǎn)。

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

1.A∪B={-2,-1,0,1,2,3}，A∩B={1,2}并集是所有元素，交集是共同元素。

2.(?p∨?q)∨?r根據(jù)蘊(yùn)涵的等價(jià)形式p→q≡?p∨q。

3.a→b→d,a→d根據(jù)鄰接矩陣，a可以到b，b可以到d；a也可以直接到d。

4.BCDA后序遍歷是左子樹(shù)、右子樹(shù)、根節(jié)點(diǎn)。

5.AB,D,CD按照克魯斯卡爾算法，先選權(quán)重最小的邊AB，再選AD，然后選BC，最后選CD。

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

集合論：集合的基本運(yùn)算（并集、交集、差集、笛卡爾積），集合的性質(zhì)（冪集、子集、補(bǔ)集），基數(shù)理論（可數(shù)集與不可數(shù)集）。

命題邏輯：命題的基本連接詞（合取∧、析取∨、蘊(yùn)涵→、等價(jià)?、否定?），量詞（全稱(chēng)量詞?、存在量詞?），命題公式及其等價(jià)形式，重言式與矛盾式。

圖論：無(wú)向圖與有向圖，頂點(diǎn)、邊、環(huán)、路徑、度數(shù)、連通性、歐拉圖、哈密頓圖，樹(shù)結(jié)構(gòu)與性質(zhì)，最小生成樹(shù)（克魯斯卡爾算法、普里姆算法），最短路徑（迪杰斯特拉算法）。

謂詞邏輯：謂詞與量詞的應(yīng)用，謂詞公式及其解釋?zhuān)壿嬐评砼c證明。

數(shù)理邏輯基礎(chǔ)：邏輯等價(jià)式，推理規(guī)則，證明方法（直接證明、間接證明、數(shù)學(xué)歸納法）。

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

選擇題：考察學(xué)生對(duì)基本概念的掌握程度，如集合運(yùn)算、邏輯連接詞、圖的基本性質(zhì)等。

示例：在集合論中，選擇題可以考察集合的并集、交集、差集等基本運(yùn)算，學(xué)生需要理解這些運(yùn)算的定義并能夠正確應(yīng)用。

多項(xiàng)選擇題：考察學(xué)生對(duì)多個(gè)相關(guān)概念的綜合理解能力，如圖論中的基本概念、集合運(yùn)算的種類(lèi)、謂詞邏輯中的量詞等。

示例：在圖論中，多項(xiàng)選擇題可以考察圖的頂點(diǎn)、邊、權(quán)重等基本概念，學(xué)生需要理解這些概念的含義并能夠正確識(shí)別。

填空題：考察學(xué)生對(duì)重要定義、公式、定理的記憶和應(yīng)用能力，如邏輯連接詞的定義、集合的基數(shù)、樹(shù)的