复旦大学离散数学试卷

复旦大学离散数学试卷一、选择题（每题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=