惠州学院离散数学试卷

惠州学院离散数学试卷一、选择题（每题1分，共10分）

1.下列哪一项不是命题逻辑的基本联结词？

A.否定

B.合取

C.蕴含

D.模糊

2.在集合论中，集合A={1,2,3}与集合B={3,4,5}的并集是？

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

B.{1,2}

C.{3,4,5}

D.{1,2,3}

3.下列哪一项是图论中的基本概念？

A.群论

B.线性代数

C.最小生成树

D.概率论

4.在命题逻辑中，命题公式P→Q的等价形式是？

A.P∧Q

B.¬P∨Q

C.P∨¬Q

D.¬P∧¬Q

5.在关系代数中，关系R的投影操作符号是？

A.π

B.σ

C.⋈

D.×

6.下列哪一项是图论中的欧拉路径？

A.经过每条边一次的路径

B.经过每个顶点一次的路径

C.连接两个顶点的路径

D.环形路径

7.在集合论中，集合A的补集记作？

A.A∪B

B.A∩B

C.A-B

D.A'

8.在命题逻辑中，命题公式P∧Q的等价形式是？

A.P∨Q

B.¬P∨Q

C.P∧¬Q

D.¬P∧¬Q

9.在图论中，连通无向图的最小生成树算法是？

A.Dijkstra算法

B.Floyd-Warshall算法

C.Kruskal算法

D.Bellman-Ford算法

10.在关系代数中，关系R的连接操作符号是？

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.投影

C.连接

D.并

E.积

5.下列哪些是图论中的最小生成树算法？

A.Kruskal算法

B.Prim算法

C.Dijkstra算法

D.Floyd-Warshall算法

E.Bellman-Ford算法

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

1.在命题逻辑中，命题公式P∨Q的否定形式是______。

2.在集合论中，集合A包含n个元素，集合A的幂集的基数是______。

3.在图论中，一个无向图G是连通的，当且仅当G中存在一条经过______的路径。

4.在关系代数中，关系R和关系S的笛卡尔积记作______。

5.在图论中，Prim算法用于构造连通无向图的______。

四、计算题（每题10分，共50分）

1.已知命题公式P→Q和¬P，求证公式Q为真。

2.设集合A={1,2,3}，集合B={2,3,4}，集合C={3,4,5}，求(A∩B)∪C。

3.给定图G的邻接矩阵如下，求图G中顶点1到顶点4的所有可能路径及其长度。

```

0101

1011

0101

1110

```

4.设关系R和关系S如下，分别写出关系R的选择操作（选择R中年龄大于30的元组）和关系S的投影操作（投影S中的姓名和部门列）。

R:(姓名,年龄,部门)

{张三,25,销售}

{李四,35,研发}

{王五,28,市场}

S:(姓名,部门,薪水)

{张三,销售,5000}

{李四,研发,8000}

{赵六,市场,6000}

5.使用Kruskal算法构造下面无向图的最小生成树（请列出每一步选择的边及其权重，并画出最终的生成树）。

```

顶点:A,B,C,D,E

边及权重:AB-1,AC-3,AD-3,BC-2,BD-4,CD-1,CE-5,DE-2

```

本专业课理论基础试卷答案及知识点总结如下

一、选择题答案及详解

1.D.模糊

解析：命题逻辑的基本联结词包括否定（¬）、合取（∧）、析取（∨）、蕴含（→）、等价（↔）。模糊不是命题逻辑的基本联结词。

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

解析：并集是指两个集合中所有元素的集合，不重复。A∪B={1,2,3}∪{3,4,5}={1,2,3,4,5}。

3.C.最小生成树

解析：图论的基本概念包括顶点、边、路径、环、连通图、最小生成树等。最小生成树是图论中的一个重要概念。

4.B.¬P∨Q

解析：命题公式P→Q的等价形式是¬P∨Q，根据蕴涵的定义，P→Q当且仅当¬P或Q为真。

5.A.π

解析：关系代数中的投影操作符号是π，用于选择关系中的某些列。

6.A.经过每条边一次的路径

解析：欧拉路径是指经过图中每条边恰好一次的路径。欧拉回路是经过每个顶点恰好一次的回路。

7.D.A'

解析：集合A的补集是指在全集中不属于A的元素组成的集合，记作A'或A补。

8.C.P∧¬Q

解析：命题公式P∧Q的否定形式是¬(P∧Q)，根据德摩根定律，等价于¬P∨¬Q。但题目要求的是等价形式，所以应该是P∧¬Q。

9.C.Kruskal算法

解析：Kruskal算法是一种构造连通无向图的最小生成树的算法。Dijkstra算法用于求单源最短路径，Floyd-Warshall算法用于求所有顶点对之间的最短路径，Bellman-Ford算法用于求单源最短路径，允许负权边。

10.C.⋈

解析：关系代数中的连接操作符号是⋈，用于将两个关系根据某个条件进行连接。π是投影，σ是选择，×是笛卡尔积。

二、多项选择题答案及详解

1.A.否定,B.合取,C.蕴含

解析：命题逻辑的基本联结词包括否定（¬）、合取（∧）、析取（∨）、蕴含（→）、等价（↔）。模糊不是命题逻辑的基本联结词。

2.A.并集,B.交集,C.补集,D.差集

解析：集合的基本运算包括并集、交集、补集、差集。积集不是集合的基本运算。

3.A.顶点,B.边,C.邻接矩阵,D.欧拉回路

解析：图论的基本概念包括顶点、边、邻接矩阵、欧拉回路、欧拉路径等。距离不是图论的基本概念。

4.A.选择,B.投影,C.连接,D.并,E.积

解析：关系代数的基本操作包括选择、投影、连接、并、交、差、笛卡尔积等。

5.A.Kruskal算法,B.Prim算法

解析：Kruskal算法和Prim算法都是构造连通无向图的最小生成树的算法。Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法用于求最短路径。

三、填空题答案及详解

1.¬P∧¬Q

解析：命题公式P∨Q的否定形式是¬(P∨Q)，根据德摩根定律，等价于¬P∧¬Q。

2.2^n

解析：集合A包含n个元素，集合A的幂集的基数是2的n次方，即2^n。

3.所有顶点

解析：一个无向图G是连通的，当且仅当G中存在一条经过所有顶点的路径。

4.R×S

解析：关系R和关系S的笛卡尔积记作R×S，是所有R的元组与S的元组的组合。

5.最小生成树

解析：Prim算法用于构造连通无向图的最小生成树。

四、计算题答案及详解

1.证明Q为真：

假设P→Q和¬P为真，根据P→Q的定义，如果P为真，则Q为真；如果P为假，则Q可以为真或假。但¬P为真，所以P为假，Q可以为真或假。这与题目矛盾，所以假设不成立，Q必须为真。

2.(A∩B)∪C={1,2,3}∩{2,3,4}∪{3,4,5}={2,3}∪{3,4,5}={2,3,4,5}

3.图G中顶点1到顶点4的所有可能路径及其长度：

路径1：1-2-4，长度为2

路径2：1-3-4，长度为2

路径3：1-2-3-4，长度为3

4.选择操作：σ年龄>30(R)

投影操作：π姓名,部门(S)

5.Kruskal算法构造最小生成树：

第一步：选择边AB-1，当前生成树{AB}

第二步：选择边CD-1，当前生成树{AB,CD}

第三步：选择边BD-4，当前生成树{AB,CD,BD}

第四步：选择边DE-2，当前生成树{AB,CD,BD,DE}

第五步：选择边AC-3，当前生成树{AB,CD,BD,DE,AC}

最终最小生成树包含边AB,CD,BD,DE,AC，总权重为1+1+4+2+3=11。

知识点分类和总结

1.命题逻辑：

-基本联结词：否定、合取、析取、蕴含、等价

-命题公式等价形式

-范式转换

2.集合论：

-集合的基本运算：并集、交集、补集、差集

-幂集、基数

-集合关系

3.图论：

-基本概念：顶点、边、路径、环、连通图

-最小生成树算法：Kruskal、Prim

-欧拉路径和回路

4.关系代数：

-基本操作：选择、投影、连接、并、交、差、笛卡尔积

-关系运算

各题型所考察学生的知识点详解及示例

1.选择题：考察学生对基本概念的掌握，如命题逻辑的联结词、集合的基本运算、图论的基本概念、关系代数的基本操作等。

示例：命题公式P→Q的等价形式是¬P∨Q，考察学生对蕴涵的定义和等价形式的掌握。

2.多项选择题：考察学生对多个相关概念的掌握，要求学生能够区分和选择正确的选项。

示例：Kruskal算法和Prim算法都是构造最小生成树的算法