復旦大學離散數學試卷一、選擇題（每題1分，共10分）

1.在圖論中，若一個有向圖中的任意兩個頂點都有一條路徑相連，則該圖被稱為（）。

A.無向圖

B.有向圖

C.強連通圖

D.無向連通圖

2.下列關于集合運算的描述中，正確的是（）。

A.兩個集合的并集包含兩個集合中的所有元素

B.兩個集合的交集包含兩個集合中的所有元素

C.兩個集合的差集包含兩個集合中的所有元素

D.兩個集合的對稱差集包含兩個集合中的所有元素

3.下列關于集合的描述中，正確的是（）。

A.集合是無序的

B.集合是有序的

C.集合中的元素可以重復

D.集合中的元素不能重復

4.在計算機科學中，下列關于數制轉換的描述中，正確的是（）。

A.二進制轉換為十進制時，每位上的值乘以2的冪次

B.十進制轉換為二進制時，每位上的值乘以2的冪次

C.二進制轉換為十六進制時，每位上的值乘以16的冪次

D.十六進制轉換為二進制時，每位上的值乘以16的冪次

5.下列關于邏輯運算的描述中，正確的是（）。

A.與運算的結果為真當且僅當兩個運算對象都為真

B.或運算的結果為真當且僅當兩個運算對象都為真

C.非運算的結果為真當且僅當運算對象為真

D.異或運算的結果為真當且僅當兩個運算對象都為真

6.下列關于算法復雜度的描述中，正確的是（）。

A.時間復雜度表示算法執行時間的長短

B.空間復雜度表示算法所需存儲空間的大小

C.時間復雜度和空間復雜度是相互獨立的

D.時間復雜度和空間復雜度是相互關聯的

7.下列關于排序算法的描述中，正確的是（）。

A.冒泡排序是一種穩定的排序算法

B.快速排序是一種穩定的排序算法

C.選擇排序是一種穩定的排序算法

D.堆排序是一種穩定的排序算法

8.下列關于圖論中路徑的描述中，正確的是（）。

A.路徑是指連接兩個頂點的邊的序列

B.簡單路徑是指不重復訪問任何頂點的路徑

C.環路是指起點和終點相同的路徑

D.回路是指起點和終點不同的路徑

9.下列關于遞歸算法的描述中，正確的是（）。

A.遞歸算法是一種循環算法

B.遞歸算法是一種非循環算法

C.遞歸算法必須滿足遞歸條件

D.遞歸算法不需要滿足遞歸條件

10.下列關于數據結構的描述中，正確的是（）。

A.數據結構是存儲數據的一種方式

B.數據結構是一種算法

C.數據結構是程序設計的基礎

D.數據結構是一種編程語言

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

1.下列哪些是離散數學中常用的基本概念？（）

A.集合

B.關系

C.函數

D.圖

E.樹

2.在圖論中，以下哪些性質是圖的重要屬性？（）

A.連通性

B.距離

C.質量數

D.頂點度數

E.路徑長度

3.下列哪些是常用的數制轉換方法？（）

A.十進制轉二進制

B.二進制轉十進制

C.二進制轉十六進制

D.十六進制轉二進制

E.十進制轉十六進制

4.下列關于邏輯代數的描述，正確的是？（）

A.邏輯代數是一種用于描述邏輯關系的數學工具

B.邏輯代數中的變量只能是0或1

C.邏輯代數中的運算符包括與、或、非等

D.邏輯代數可以用來簡化邏輯表達式

E.邏輯代數在電路設計中廣泛應用

5.下列關于算法分析的描述，正確的是？（）

A.時間復雜度是衡量算法執行時間的一個重要指標

B.空間復雜度是衡量算法所需存儲空間大小的一個重要指標

C.算法的漸進時間復雜度通常用大O符號表示

D.算法的漸進空間復雜度通常用大O符號表示

E.算法的時間復雜度和空間復雜度可以獨立考慮

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

1.在集合論中，兩個集合A和B的笛卡爾積表示為A×B，其包含所有可能的______對。

2.在圖論中，若一個無向圖G中任意兩個頂點都有一條路徑相連，則稱G為______圖。

3.在數制轉換中，將二進制數1101轉換為十進制數的結果是______。

4.邏輯運算中的“與”運算符用符號______表示，其真值表為：輸入(0,0)和(0,1)時，輸出均為______。

5.在算法設計中，時間復雜度通常用______表示，空間復雜度通常用______表示。其中，O(1)表示常數時間復雜度，O(n)表示線性時間復雜度。

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

1.計算以下二進制數與十進制數的等價值：

-(1101)?

-(101.101)?

-(101110)?

2.已知無向圖G的鄰接矩陣如下，計算圖G中頂點u到頂點v的最短路徑（使用迪杰斯特拉算法）。

```

01110

10010

10010

11100

00000

```

3.已知圖G的頂點集合V={1,2,3,4,5}和邊的集合E={(1,2),(2,3),(3,4),(4,5),(5,1)}，構造該圖對應的鄰接表。

4.計算以下邏輯表達式的真值表：

```

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

```

5.使用二分查找算法在一個有序數組中查找元素，數組元素如下，請寫出算法的偽代碼并給出查找元素3的步驟：

```

[1,2,3,4,5,6,7,8,9]

```

本專業課理論基礎試卷答案及知識點總結如下：

一、選擇題答案及知識點詳解

1.C.強連通圖

-知識點：圖論中的連通性，強連通圖定義。

2.A.兩個集合的并集包含兩個集合中的所有元素

-知識點：集合論中的并集概念。

3.A.集合是無序的

-知識點：集合論中的集合性質。

4.A.二進制轉換為十進制時，每位上的值乘以2的冪次

-知識點：數制轉換的基本原理。

5.A.與運算的結果為真當且僅當兩個運算對象都為真

-知識點：邏輯代數中的與運算。

6.A.時間復雜度表示算法執行時間的長短

-知識點：算法復雜度分析。

7.A.冒泡排序是一種穩定的排序算法

-知識點：排序算法的性質，穩定性。

8.B.簡單路徑是指不重復訪問任何頂點的路徑

-知識點：圖論中的路徑概念。

9.B.遞歸算法是一種非循環算法

-知識點：遞歸算法的定義。

10.A.數據結構是存儲數據的一種方式

-知識點：數據結構的基本概念。

二、多項選擇題答案及知識點詳解

1.A,B,C,D,E

-知識點：離散數學的基本概念。

2.A,B,D,E

-知識點：圖論的基本屬性。

3.A,B,C,D,E

-知識點：數制轉換的方法。

4.A,B,C,D,E

-知識點：邏輯代數的基本概念和應用。

5.A,B,C,D,E

-知識點：算法復雜度的分析。

三、填空題答案及知識點詳解

1.元組

-知識點：笛卡爾積的定義。

2.強連通

-知識點：強連通圖的定義。

3.13

-知識點：二進制轉十進制的計算。

4.∧,0

-知識點：邏輯代數中的與運算和真值表。

5.大O符號，大O符號

-知識點：算法復雜度的表示方法。

四、計算題答案及知識點詳解

1.答案：

-(1101)?=13

-(101.101)?=5.625

-(101110)?=46

-知識點：二進制轉十進制的計算。

2.答案：

-頂點u到頂點v的最短路徑為u-v。

-知識點：迪杰斯特拉算法的應用。

3.答案：

-鄰接表如下：

```

1:[(2,1),(3,1),(4,1)]

2:[(3,2)]

3:[(4,3)]

4:[(5,4)]

5:[(1,5)]

```

-知識點：鄰接表的構建。

4.答案：

-真值表如下：

```

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

---------------------------------------------------------

0|0|0|1|1|0|0|0|1

0|0|1|1|1|0|0|0|1

0|1|0|0|0|0|0|0|1

0|1|1|0|1|0|0|0|1

1|0|0|1|1|1|0|1|1

1|0|1|1|1|1|0|1|1

1|1|0|0|0|0|1|1|1

1|1|1|0|1|1|1|1|1

```

-知識點：邏輯表達式的真值表。

5.答案：

-偽代碼：

```

functionbinarySearch(arr,target):

low=0

high=length(arr)-1

whilelow<=high:

mid=(low+high)/2

ifarr[mid]==target:

returnmid

elseifarr[mid]<target:

low=mid+1

else:

high=mid-1

return-1

```

-查找元素3的步驟：

-初始：low=0,high=