鲁东大学离散数学试卷

鲁东大学离散数学试卷一、选择题（每题1分，共10分）

1.下列哪个命题是永真式？

A.p∨¬p

B.p∧¬p

C.¬(p∧q)↔¬p∨¬q

D.(p→q)∧(q→p)

2.在集合论中，A×B表示什么？

A.A和B的并集

B.A和B的交集

C.A和B的笛卡尔积

D.A和B的差集

3.下列哪个图是欧拉图？

A.完全图K3

B.有向图中有环

C.连通图且每个顶点的度数为偶数

D.不连通图

4.在命题逻辑中，下列哪个是重言式？

A.(p∨q)→p

B.(p∧q)→p

C.(p→q)→(q→p)

D.(p↔q)↔(q↔p)

5.下列哪个是偏序集？

A.(N,≤)

B.(Z,<)

C.(R,≠)

D.(Q,∨)

6.在图论中，树的最小生成树的构造算法是？

A.Dijkstra算法

B.Floyd-Warshall算法

C.Kruskal算法

D.Bellman-Ford算法

7.下列哪个是可判定的？

A.哥尼斯堡七桥问题

B.哈密顿路径问题

C.旅行商问题

D.判定一个图是否是二分图

8.在集合论中，A∪B表示什么？

A.A和B的并集

B.A和B的交集

C.A和B的差集

D.A和B的补集

9.下列哪个是布尔代数？

A.(Z,+,×)

B.(B,∨,∧,¬)

C.(R,+,×)

D.(N,+,×)

10.在图论中，下列哪个是平面图？

A.完全图K5

B.五色定理的图

C.四色定理的图

D.哥尼斯堡七桥问题中的图

二、多项选择题（每题4分，共20分）

1.下列哪些是命题逻辑中的基本连接词？

A.∧（与）

B.∨（或）

C.→（蕴含）

D.↔（等价）

E.¬（非）

2.在集合论中，下列哪些运算是补运算？

A.A∪B

B.A∩B

C.A-B

D.A'

E.B-A

3.下列哪些图是连通图？

A.完全图K4

B.有向环

C.树

D.不连通图

E.孤立点

4.在图论中，下列哪些算法用于求图的最小生成树？

A.Kruskal算法

B.Prim算法

C.Dijkstra算法

D.Floyd-Warshall算法

E.Bellman-Ford算法

5.下列哪些是偏序集的性质？

A.自反性

B.反对称性

C.传递性

D.满足三歧性

E.满足连通性

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

1.在命题逻辑中，p∧q的真值表中有______个真值组合。

2.集合A={1,2,3}和B={3,4,5}的笛卡尔积A×B=______。

3.一个具有n个顶点的树有______条边。

4.在偏序集(P,≤)中，如果对于任意a,b∈P，都有a≤b或b≤a，则称该偏序关系为______。

5.哈密顿路径是一个经过图中所有顶点恰好一次的______。

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

1.对于命题公式(p∧¬q)∨(¬p∧q)，请写出其真值表，并判断该公式是永真式、矛盾式还是可满足式。

2.给定集合A={1,2,3}，B={2,3,4}，C={3,4,5}，请计算A∪(B∩C)和(A∪B)∩(A∪C)。

3.考虑一个无向图G，其顶点集V={v1,v2,v3,v4}，边集E={{v1,v2},{v1,v3},{v2,v4},{v3,v4}}。请画出该图，并判断它是否是树。

4.给定偏序集(P,≤)，其中P={a,b,c,d}，偏序关系≤如下所示（用五角形表示小于或等于关系）：

a

/\

bc

\/

d

请写出该偏序集的所有极大元和极小元。

5.对于以下图G，请使用Kruskal算法构造其最小生成树：

(顶点：A,B,C,D,E)

(边及其权重：AB-1,AC-2,AD-3,BC-4,BD-5,CD-6,CE-7,DE-8)

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

一、选择题答案

1.A

2.C

3.C

4.B

5.A

6.C

7.D

8.A

9.B

10.C

二、多项选择题答案

1.A,B,C,D,E

2.C,D

3.A,B,C

4.A,B

5.A,B,C

三、填空题答案

1.4

2.{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5)}

3.n-1

4.全序关系

5.路径

四、计算题答案及过程

1.真值表：

|p|q|¬p|¬q|p∧¬q|¬p∧q|(p∧¬q)∨(¬p∧q)|

|---|---|----|----|--------|--------|----------------------|

|T|T|F|F|F|F|F|

|T|F|F|T|T|F|T|

|F|T|T|F|F|T|T|

|F|F|T|T|F|F|F|

该公式是可满足式。

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

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

3.图略。该图是树，因为它是一个连通的无向图，且没有环。

4.极大元：{a,b,c}

极小元：{d}

5.Kruskal算法步骤：

-按边的权重升序排列：AB-1,AC-2,BC-4,BD-5,CD-6,AD-3,CE-7,DE-8

-选择AB-1,AC-2,BC-4

-下一个边AD-3与当前生成树不构成环，加入

-结束，最小生成树边集：{AB-1,AC-2,BC-4,AD-3}

知识点总结

集合论：集合的基本运算（并、交、差、补）、笛卡尔积、集合的性质。

命题逻辑：基本连接词、真值表、永真式、矛盾式、可满足式。

图论：欧拉图、连通图、树、最小生成树（Kruskal算法、Prim算法）、平面图。

偏序集：偏序关系、自反性、反对称性、传递性、极大元、极小元、全序关系。

算法：图的最小生成树构造算法、判定问题。

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

选择题：考察学生对基本概念的掌握，如命题逻辑的基本连接词、集合论的基本运算、图论的基本性质等。

多项选择题：考察学生对多个相关概念的理解和区分，如命题逻辑的基本连接词、集合论的基本运算、图论的基本性质等。

填空题：考察学生对基本概念的精确记忆，如真值组合的数量、集合的笛卡尔积、树的基本性质、偏序关系的基本性质、路径的定义等。

计算题：考察学生运用所学知识解决实际问题的能力，如命题逻辑的真值表计算、集合的运算、图的最小生成树构造、偏序集的极大元和极小元求解等。

示例

命题逻辑：p∧q的真值表中有4个真值组合，分别是(T,T),(T,F),(F,T),(F,F)。

集合论：集合A={1,2,3}和B={3,4,5}的笛卡尔积A×B={(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5)}。

图论：无向图G的顶点集V={v1,v2,v3,v4}，边集E={{v1,v2},{v1,v3},