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

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

A.無向圖

B.有向圖

C.強(qiáng)連通圖

D.無向連通圖

2.下列關(guān)于集合運(yùn)算的描述中，正確的是（）。

A.兩個(gè)集合的并集包含兩個(gè)集合中的所有元素

B.兩個(gè)集合的交集包含兩個(gè)集合中的所有元素

C.兩個(gè)集合的差集包含兩個(gè)集合中的所有元素

D.兩個(gè)集合的對(duì)稱差集包含兩個(gè)集合中的所有元素

3.下列關(guān)于集合的描述中，正確的是（）。

A.集合是無序的

B.集合是有序的

C.集合中的元素可以重復(fù)

D.集合中的元素不能重復(fù)

4.在計(jì)算機(jī)科學(xué)中，下列關(guān)于數(shù)制轉(zhuǎn)換的描述中，正確的是（）。

A.二進(jìn)制轉(zhuǎn)換為十進(jìn)制時(shí)，每位上的值乘以2的冪次

B.十進(jìn)制轉(zhuǎn)換為二進(jìn)制時(shí)，每位上的值乘以2的冪次

C.二進(jìn)制轉(zhuǎn)換為十六進(jìn)制時(shí)，每位上的值乘以16的冪次

D.十六進(jìn)制轉(zhuǎn)換為二進(jìn)制時(shí)，每位上的值乘以16的冪次

5.下列關(guān)于邏輯運(yùn)算的描述中，正確的是（）。

A.與運(yùn)算的結(jié)果為真當(dāng)且僅當(dāng)兩個(gè)運(yùn)算對(duì)象都為真

B.或運(yùn)算的結(jié)果為真當(dāng)且僅當(dāng)兩個(gè)運(yùn)算對(duì)象都為真

C.非運(yùn)算的結(jié)果為真當(dāng)且僅當(dāng)運(yùn)算對(duì)象為真

D.異或運(yùn)算的結(jié)果為真當(dāng)且僅當(dāng)兩個(gè)運(yùn)算對(duì)象都為真

6.下列關(guān)于算法復(fù)雜度的描述中，正確的是（）。

A.時(shí)間復(fù)雜度表示算法執(zhí)行時(shí)間的長短

B.空間復(fù)雜度表示算法所需存儲(chǔ)空間的大小

C.時(shí)間復(fù)雜度和空間復(fù)雜度是相互獨(dú)立的

D.時(shí)間復(fù)雜度和空間復(fù)雜度是相互關(guān)聯(lián)的

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

A.冒泡排序是一種穩(wěn)定的排序算法

B.快速排序是一種穩(wěn)定的排序算法

C.選擇排序是一種穩(wěn)定的排序算法

D.堆排序是一種穩(wěn)定的排序算法

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

A.路徑是指連接兩個(gè)頂點(diǎn)的邊的序列

B.簡單路徑是指不重復(fù)訪問任何頂點(diǎn)的路徑

C.環(huán)路是指起點(diǎn)和終點(diǎn)相同的路徑

D.回路是指起點(diǎn)和終點(diǎn)不同的路徑

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

A.遞歸算法是一種循環(huán)算法

B.遞歸算法是一種非循環(huán)算法

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

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

10.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的描述中，正確的是（）。

A.數(shù)據(jù)結(jié)構(gòu)是存儲(chǔ)數(shù)據(jù)的一種方式

B.數(shù)據(jù)結(jié)構(gòu)是一種算法

C.數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的基礎(chǔ)

D.數(shù)據(jù)結(jié)構(gòu)是一種編程語言

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

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

A.集合

B.關(guān)系

C.函數(shù)

D.圖

E.樹

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

A.連通性

B.距離

C.質(zhì)量數(shù)

D.頂點(diǎn)度數(shù)

E.路徑長度

3.下列哪些是常用的數(shù)制轉(zhuǎn)換方法？（）

A.十進(jìn)制轉(zhuǎn)二進(jìn)制

B.二進(jìn)制轉(zhuǎn)十進(jìn)制

C.二進(jìn)制轉(zhuǎn)十六進(jìn)制

D.十六進(jìn)制轉(zhuǎn)二進(jìn)制

E.十進(jìn)制轉(zhuǎn)十六進(jìn)制

4.下列關(guān)于邏輯代數(shù)的描述，正確的是？（）

A.邏輯代數(shù)是一種用于描述邏輯關(guān)系的數(shù)學(xué)工具

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

C.邏輯代數(shù)中的運(yùn)算符包括與、或、非等

D.邏輯代數(shù)可以用來簡化邏輯表達(dá)式

E.邏輯代數(shù)在電路設(shè)計(jì)中廣泛應(yīng)用

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

A.時(shí)間復(fù)雜度是衡量算法執(zhí)行時(shí)間的一個(gè)重要指標(biāo)

B.空間復(fù)雜度是衡量算法所需存儲(chǔ)空間大小的一個(gè)重要指標(biāo)

C.算法的漸進(jìn)時(shí)間復(fù)雜度通常用大O符號(hào)表示

D.算法的漸進(jìn)空間復(fù)雜度通常用大O符號(hào)表示

E.算法的時(shí)間復(fù)雜度和空間復(fù)雜度可以獨(dú)立考慮

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

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

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

3.在數(shù)制轉(zhuǎn)換中，將二進(jìn)制數(shù)1101轉(zhuǎn)換為十進(jìn)制數(shù)的結(jié)果是______。

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

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

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

1.計(jì)算以下二進(jìn)制數(shù)與十進(jìn)制數(shù)的等價(jià)值：

-(1101)?

-(101.101)?

-(101110)?

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

```

01110

10010

10010

11100

00000

```

3.已知圖G的頂點(diǎn)集合V={1,2,3,4,5}和邊的集合E={(1,2),(2,3),(3,4),(4,5),(5,1)}，構(gòu)造該圖對(duì)應(yīng)的鄰接表。

4.計(jì)算以下邏輯表達(dá)式的真值表：

```

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

```

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

```

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

```

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

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

1.C.強(qiáng)連通圖

-知識(shí)點(diǎn)：圖論中的連通性，強(qiáng)連通圖定義。

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

-知識(shí)點(diǎn)：集合論中的并集概念。

3.A.集合是無序的

-知識(shí)點(diǎn)：集合論中的集合性質(zhì)。

4.A.二進(jìn)制轉(zhuǎn)換為十進(jìn)制時(shí)，每位上的值乘以2的冪次

-知識(shí)點(diǎn)：數(shù)制轉(zhuǎn)換的基本原理。

5.A.與運(yùn)算的結(jié)果為真當(dāng)且僅當(dāng)兩個(gè)運(yùn)算對(duì)象都為真

-知識(shí)點(diǎn)：邏輯代數(shù)中的與運(yùn)算。

6.A.時(shí)間復(fù)雜度表示算法執(zhí)行時(shí)間的長短

-知識(shí)點(diǎn)：算法復(fù)雜度分析。

7.A.冒泡排序是一種穩(wěn)定的排序算法

-知識(shí)點(diǎn)：排序算法的性質(zhì)，穩(wěn)定性。

8.B.簡單路徑是指不重復(fù)訪問任何頂點(diǎn)的路徑

-知識(shí)點(diǎn)：圖論中的路徑概念。

9.B.遞歸算法是一種非循環(huán)算法

-知識(shí)點(diǎn)：遞歸算法的定義。

10.A.數(shù)據(jù)結(jié)構(gòu)是存儲(chǔ)數(shù)據(jù)的一種方式

-知識(shí)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念。

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

1.A,B,C,D,E

-知識(shí)點(diǎn)：離散數(shù)學(xué)的基本概念。

2.A,B,D,E

-知識(shí)點(diǎn)：圖論的基本屬性。

3.A,B,C,D,E

-知識(shí)點(diǎn)：數(shù)制轉(zhuǎn)換的方法。

4.A,B,C,D,E

-知識(shí)點(diǎn)：邏輯代數(shù)的基本概念和應(yīng)用。

5.A,B,C,D,E

-知識(shí)點(diǎn)：算法復(fù)雜度的分析。

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

1.元組

-知識(shí)點(diǎn)：笛卡爾積的定義。

2.強(qiáng)連通

-知識(shí)點(diǎn)：強(qiáng)連通圖的定義。

3.13

-知識(shí)點(diǎn)：二進(jìn)制轉(zhuǎn)十進(jìn)制的計(jì)算。

4.∧,0

-知識(shí)點(diǎn)：邏輯代數(shù)中的與運(yùn)算和真值表。

5.大O符號(hào)，大O符號(hào)

-知識(shí)點(diǎn)：算法復(fù)雜度的表示方法。

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

1.答案：

-(1101)?=13

-(101.101)?=5.625

-(101110)?=46

-知識(shí)點(diǎn)：二進(jìn)制轉(zhuǎn)十進(jìn)制的計(jì)算。

2.答案：

-頂點(diǎn)u到頂點(diǎn)v的最短路徑為u-v。

-知識(shí)點(diǎn)：迪杰斯特拉算法的應(yīng)用。

3.答案：

-鄰接表如下：

```

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

2:[(3,2)]

3:[(4,3)]

4:[(5,4)]

5:[(1,5)]

```

-知識(shí)點(diǎn)：鄰接表的構(gòu)建。

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

```

-知識(shí)點(diǎn)：邏輯表達(dá)式的真值表。

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=