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

1.在集合論中，以下哪個(gè)概念表示“至少包含一個(gè)元素”？

A.空集

B.單元素集

C.非空集

D.全集

2.設(shè)集合A={1,2,3}，集合B={2,4,6}，則A∩B的結(jié)果是：

A.{1,2,3}

B.{2}

C.{1,2,3,4,6}

D.空集

3.設(shè)集合A={1,2,3,4}，集合B={1,2,3}，則A-B的結(jié)果是：

A.{1,2,3,4}

B.{1,2,3}

C.{1,2,3,4,5}

D.空集

4.在圖論中，以下哪個(gè)術(shù)語表示圖中兩個(gè)頂點(diǎn)之間的一條邊？

A.弧

B.邊

C.路徑

D.連通

5.設(shè)圖G中有5個(gè)頂點(diǎn)，以下哪個(gè)說法是正確的？

A.G一定有5條邊

B.G至少有5條邊

C.G最多有5條邊

D.G的邊數(shù)與頂點(diǎn)數(shù)無關(guān)

6.在組合數(shù)學(xué)中，以下哪個(gè)公式表示組合數(shù)C(n,m)？

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

B.C(n,m)=m!/(n!*(m-n)!)

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

D.C(n,m)=(n+m)!/(n!*m!)

7.在數(shù)理邏輯中，以下哪個(gè)公式表示命題p且命題q的合??？

A.p∧q

B.p∨q

C.p→q

D.p≡q

8.在遞歸關(guān)系中，以下哪個(gè)術(shù)語表示遞歸的終止條件？

A.遞歸函數(shù)

B.遞歸基

C.遞歸關(guān)系

D.遞歸變量

9.在算法設(shè)計(jì)中，以下哪個(gè)術(shù)語表示算法的執(zhí)行過程？

A.時(shí)間復(fù)雜度

B.空間復(fù)雜度

C.輸入

D.輸出

10.在集合論中，以下哪個(gè)概念表示集合中所有元素的笛卡爾積？

A.并集

B.交集

C.子集

D.笛卡爾積

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

1.下列哪些是離散數(shù)學(xué)中的基本概念？

A.集合

B.函數(shù)

C.圖

D.矩陣

E.數(shù)列

2.在圖論中，以下哪些是圖的類型？

A.有向圖

B.無向圖

C.有權(quán)圖

D.無權(quán)圖

E.有環(huán)圖

3.下列哪些是排列組合的基本公式？

A.排列數(shù)公式P(n,k)=n!/(n-k)!

B.組合數(shù)公式C(n,k)=n!/[k!*(n-k)!]

C.排列組合的乘法原理

D.排列組合的加法原理

E.稀疏矩陣的存儲(chǔ)方法

4.下列哪些是數(shù)理邏輯中的命題聯(lián)結(jié)詞？

A.合?。ˋND）

B.析?。∣R）

C.蘊(yùn)含（IMPLIES）

D.等價(jià)（EQUIVALENT）

E.非命題

5.下列哪些是算法分析中的基本概念？

A.時(shí)間復(fù)雜度

B.空間復(fù)雜度

C.輸入/輸出

D.算法效率

E.算法穩(wěn)定性

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

1.在集合論中，如果一個(gè)集合A中的每個(gè)元素都屬于另一個(gè)集合B，則稱A為B的______。

2.在圖論中，一個(gè)無向圖中的頂點(diǎn)對(u,v)之間的最短路徑長度被稱為______。

3.在排列組合中，從n個(gè)不同元素中取出k個(gè)元素的排列數(shù)記作______，而組合數(shù)記作______。

4.在數(shù)理邏輯中，一個(gè)命題的真值表包含所有可能的______和______。

5.在算法分析中，一個(gè)算法的時(shí)間復(fù)雜度通常用______來表示，它描述了算法執(zhí)行時(shí)間隨著輸入規(guī)模的增長而變化的趨勢。

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

1.計(jì)算下列集合的并集、交集和差集：

集合A={1,3,5,7,9}

集合B={2,4,6,8,10}

2.設(shè)有圖G如下所示，請計(jì)算圖中頂點(diǎn)v1到頂點(diǎn)v5的最短路徑長度。

```

A---B---C

||

v1---v2-v3

||

D---E---F

|

v5

```

3.從集合{1,2,3,4,5,6}中選出3個(gè)元素，計(jì)算所有可能的排列數(shù)和組合數(shù)。

4.設(shè)有一個(gè)遞歸函數(shù)f(n)=2f(n-1)+3，其中f(1)=2。請計(jì)算f(5)的值。

5.設(shè)有一個(gè)有向圖G，如下所示，請計(jì)算圖G的頂點(diǎn)度數(shù)序列。

```

A---B

|/\

v3v4---C

|

v5

```

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

一、選擇題答案及知識點(diǎn)詳解

1.C.非空集

知識點(diǎn)：集合論中的基本概念，非空集是指至少包含一個(gè)元素的集合。

2.B.{2}

知識點(diǎn)：集合的交集，交集是指同時(shí)屬于兩個(gè)集合的元素組成的集合。

3.B.{1,2,3}

知識點(diǎn)：集合的差集，差集是指屬于一個(gè)集合而不屬于另一個(gè)集合的元素組成的集合。

4.B.邊

知識點(diǎn)：圖論中的基本概念，邊是連接圖中頂點(diǎn)的線段。

5.C.G最多有5條邊

知識點(diǎn)：圖論中的基本概念，無向圖的邊數(shù)最多等于頂點(diǎn)數(shù)乘以頂點(diǎn)數(shù)除以2。

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

知識點(diǎn)：組合數(shù)的計(jì)算公式，表示從n個(gè)不同元素中取出m個(gè)元素的組合數(shù)。

7.A.p∧q

知識點(diǎn)：數(shù)理邏輯中的命題聯(lián)結(jié)詞，合取表示兩個(gè)命題同時(shí)為真。

8.B.遞歸基

知識點(diǎn)：遞歸關(guān)系中的基本概念，遞歸基是遞歸關(guān)系中遞歸終止的條件。

9.A.時(shí)間復(fù)雜度

知識點(diǎn)：算法分析中的基本概念，時(shí)間復(fù)雜度描述了算法執(zhí)行時(shí)間隨著輸入規(guī)模的增長而變化的趨勢。

10.D.笛卡爾積

知識點(diǎn)：集合論中的基本概念，笛卡爾積是指兩個(gè)集合中所有可能的有序?qū)M成的集合。

二、多項(xiàng)選擇題答案及知識點(diǎn)詳解

1.ABCDE

知識點(diǎn)：離散數(shù)學(xué)中的基本概念，包括集合、函數(shù)、圖、矩陣和數(shù)列。

2.ABCD

知識點(diǎn)：圖論中的基本概念，包括有向圖、無向圖、有權(quán)圖和無權(quán)圖。

3.ABCD

知識點(diǎn)：排列組合的基本公式，包括排列數(shù)公式、組合數(shù)公式、乘法原理和加法原理。

4.ABCD

知識點(diǎn)：數(shù)理邏輯中的命題聯(lián)結(jié)詞，包括合取、析取、蘊(yùn)含和等價(jià)。

5.ABCD

知識點(diǎn)：算法分析中的基本概念，包括時(shí)間復(fù)雜度、空間復(fù)雜度、輸入/輸出、算法效率和算法穩(wěn)定性。

三、填空題答案及知識點(diǎn)詳解

1.子集

知識點(diǎn)：集合論中的基本概念，子集是指一個(gè)集合的所有元素都屬于另一個(gè)集合。

2.最短路徑

知識點(diǎn)：圖論中的基本概念，最短路徑是指圖中兩個(gè)頂點(diǎn)之間距離最短的路徑。

3.排列數(shù)P(n,k)，組合數(shù)C(n,k)

知識點(diǎn)：排列組合的基本公式，排列數(shù)和組合數(shù)分別表示從n個(gè)不同元素中取出k個(gè)元素的排列數(shù)和組合數(shù)。

4.命題，真值

知識點(diǎn)：數(shù)理邏輯中的基本概念，命題是真值表中的元素，真值是指命題的真假值。

5.時(shí)間復(fù)雜度

知識點(diǎn)：算法分析中的基本概念，時(shí)間復(fù)雜度描述了算法執(zhí)行時(shí)間隨著輸入規(guī)模的增長而變化的趨勢。

四、計(jì)算題答案及知識點(diǎn)詳解

1.并集：{1,2,3,4,5,6,7,8,9,10}

交集：{2}

差集：{1,3,5,7,9}

知識點(diǎn)：集合的并集、交集和差集的計(jì)算。

2.最短路徑長度：3

知識點(diǎn)：圖論中的最短路徑算法，例如迪杰斯特拉算法或貝爾曼-福特算法。

3.排列數(shù)：120，組合數(shù)：20

知識點(diǎn)：排列組合的計(jì)算，排列數(shù)和組合數(shù)的計(jì)算公式。

4.f(5)=64

知識點(diǎn)：遞歸函數(shù)的計(jì)算，根據(jù)遞歸定義和遞歸基計(jì)算函數(shù)值。

5.頂點(diǎn)度數(shù)序列：3,2,3,2,2

知識點(diǎn)：圖論中的頂點(diǎn)度數(shù)，頂點(diǎn)度數(shù)是指連接一個(gè)頂點(diǎn)的邊的數(shù)量。

本試卷涵蓋了離