合肥学院离散数学试卷

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

1.在集合论中，集合A包含元素1,2,3，集合B包含元素2,3,4，则集合A和集合B的交集是？

A.{1,2,3,4}

B.{2,3}

C.{1}

D.∅

2.下列哪个是命题？

A.今天天气很好。

B.x+y=z

C.请进。

D.这个数很大。

3.在逻辑运算中，命题p为“今天是星期一”，命题q为“今天是晴天”，则命题“今天是星期一且今天是晴天”的逻辑表达式是？

A.p∧q

B.p∨q

C.¬p

D.¬q

4.在图论中，一个无向图G包含6个顶点，如果G是连通的，则G至少有多少条边？

A.5

B.6

C.7

D.8

5.在树的结构中，一个非平凡树T的顶点数为n，则T的边数是多少？

A.n-1

B.n

C.n+1

D.2n

6.在关系代数中，关系R的属性集合为A，关系S的属性集合为B，则关系R和关系S的笛卡尔积的属性集合是？

A.A∪B

B.A∩B

C.A×B

D.A-B

7.在组合数学中，从n个不同元素中取出k个元素的组合数记作C(n,k)，则C(n,k)等于？

A.n!

B.k!

C.(n-k)!

D.n!/(k!×(n-k)!)

8.在数理逻辑中，命题“如果今天下雨，那么地面会湿”的逆命题是？

A.如果地面湿，那么今天下雨。

B.如果今天不下雨，那么地面不会湿。

C.如果地面不湿，那么今天不下雨。

D.如果今天下雨，那么地面不会湿。

9.在概率论中，事件A和事件B互斥，且P(A)=0.3，P(B)=0.4，则P(A∪B)等于？

A.0.3

B.0.4

C.0.7

D.0.1

10.在布尔代数中，表达式A∧(B∨¬C)的等价表达式是？

A.(A∧B)∨(A∧¬C)

B.(A∨B)∧(A∨¬C)

C.(A∧B)∧(A∧C)

D.(A∨¬B)∧(A∨C)

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

1.下列哪些是命题？

A.2+3=5

B.今天会下雪吗？

C.x是偶数

D.请坐

2.在逻辑运算中，下列哪些是命题“p或q”的等价命题？

A.非p且非q

B.非p或非q

C.p且非q

D.非p且q

3.在图论中，下列哪些是连通图的特征？

A.图中任意两个顶点之间都有路径相连

B.图中至少存在一个环

C.图中没有任何环

D.图中顶点数大于等于边数

4.在树的结构中，下列哪些是二叉树的特征？

A.每个顶点最多有两个子顶点

B.每个顶点最多有一个子顶点

C.树中存在一个根顶点

D.树中不存在环

5.在关系代数中，下列哪些是关系运算？

A.并运算

B.交运算

C.笛卡尔积运算

D.除运算

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

1.集合A包含元素1,2,3，集合B包含元素3,4,5，则集合A和集合B的并集是________。

2.在逻辑运算中，命题p为“今天是星期一”，命题q为“今天是晴天”，则命题“今天不是星期一或今天不是晴天”的逻辑表达式是________。

3.在图论中，一个有向图G包含5个顶点，如果G是强连通的，则G至少有多少条边？________。

4.在树的结构中，一个非平凡树T的顶点数为n，则T的高度最多为________。

5.在关系代数中，关系R的属性集合为A，关系S的属性集合为B，则关系R和关系S的除运算的结果是一个关系，其属性集合为________。

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

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

2.写出命题“如果今天下雨，那么地面湿，并且如果地面湿，那么今天下雨”的命题公式，并判断该命题的真假值。

3.给定有向图G如下，其中顶点集V={a,b,c,d}，边集E={(a,b),(b,c),(c,d),(d,a)}。判断图G是否是强连通的，并说明理由。

4.给定一棵二叉树如下，其中每个顶点标有字母。求该二叉树的高度。

```

A

/\

BC

/\

DE

```

5.给定关系R和关系S如下，其中R的属性集合为{A,B}，S的属性集合为{B,C}。

R={(1,2),(3,4)}

S={(2,5),(4,6)}

求关系R和关系S的连接运算（自然连接）的结果。

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

一、选择题答案及解析

1.B

解析：集合A和集合B的交集是两个集合都包含的元素，即{2,3}。

2.A

解析：命题是能够判断真假的陈述句。“今天天气很好”是一个可以判断真假的陈述句。

3.A

解析：命题“今天是星期一且今天是晴天”的逻辑表达式是p∧q，表示p和q同时为真。

4.A

解析：一个无向连通图至少需要n-1条边才能保证所有顶点连通，这是树的基本性质。

5.A

解析：一个非平凡树（非空树）的边数等于顶点数减1，这是树的基本性质。

6.C

解析：关系R和关系S的笛卡尔积的属性集合是R的属性集合与S的属性集合的笛卡尔积，即A×B。

7.D

解析：组合数C(n,k)表示从n个不同元素中取出k个元素的组合数，公式为n!/(k!×(n-k)!)。

8.C

解析：命题“如果今天下雨，那么地面会湿”的逆命题是“如果地面不湿，那么今天不下雨”。

9.C

解析：事件A和事件B互斥，表示它们不能同时发生，P(A∪B)=P(A)+P(B)=0.3+0.4=0.7。

10.A

解析：根据分配律，A∧(B∨¬C)等价于(A∧B)∨(A∧¬C)。

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

1.A,D

解析：命题是能够判断真假的陈述句。“2+3=5”是真命题，“请坐”不是陈述句。

2.C,D

解析：命题“p或q”的等价命题是“非p且非q”的否定，即“非p或非q”和“非p且q”。

3.A,D

解析：连通图的特征是任意两个顶点之间都有路径相连，且顶点数大于等于边数。

4.A,C

解析：二叉树的特征是每个顶点最多有两个子顶点，且树中存在一个根顶点。

5.A,B,C,D

解析：关系运算包括并运算、交运算、笛卡尔积运算和除运算。

三、填空题答案及解析

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

解析：集合A和集合B的并集是两个集合的所有元素的集合，即{1,2,3,4,5}。

2.¬p∨¬q

解析：命题“今天不是星期一或今天不是晴天”的逻辑表达式是“今天不是星期一”或“今天不是晴天”，即¬p∨¬q。

3.5

解析：一个强连通的有向图至少需要5条边，即每个顶点都有出度和入度，形成闭环。

4.n-1

解析：二叉树的高度最多为n-1，这是满二叉树的性质。

5.A-{B}×C

解析：关系R和关系S的除运算的结果是一个关系，其属性集合为R的属性集合减去S的属性集合，即A-{B}×C。

四、计算题答案及解析

1.{4}

解析：(A∪B)={1,2,3,4,5,6}，(A∪B)∩C={4}。

2.(p∧q)∧(q∧p)

解析：命题公式为“如果今天下雨，那么地面湿，并且如果地面湿，那么今天下雨”，即(p∧q)∧(q∧p)。

真假值：假设今天下雨且地面湿，则p和q都为真，命题为真；否则为假。

3.不是强连通的

解析：图G中存在顶点对，如a和c，没有路径相连，因此图G不是强连通的。

4.3

解析：该二叉树的高度为3，即从根顶点A到最远叶顶点D或E的路径长度。

5.{(1,5),(3,6)}

解析：关系R和关系S的自然连接结果为{(1,2,5),(3,4,6)}，去掉重复属性后为{(1,5),(3,6)}。

知识点分类和总结

离散数学的理论基础部分主要包括集合论、逻辑代数、图论、树、关系代数等知识点。

集合论：包括集合的基本运算（并集、交集、差集、笛卡尔积）、集合的性质（幂集、子集）、集合的计数等。

逻辑代数：包括命题逻辑和谓词逻辑，涉及命题的真假值判断、逻辑运算（与、或、非、异或）、逻辑等价式、逻辑推理等。

图论：包括无向图和有向图的基本概念、图的表示方法、图的遍历、图的连通性、树的基本性质等。

树：包括二叉树、满二叉树、完全二叉树等概念，涉及树的性质、树的遍历（前序、中序、后序）、树的构造等。

关系代数：包括关系的表示方法、关系的基本运算（并、交、差、笛卡尔积、投影、选择、连接、除）等。

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

选择题：考察学生对基本概念和性质的理解，如集合运算、逻辑运算、图的基本性质等。

示例：集合A={1,2,3}，集合B={3,4,5}，则A∪B={1,2,3,4,5}。

多项选择题：考察学生对多个知识点综合应用的能力，如命题逻辑的等价式、图的连通性等。

示例：命题p为“今天下雨”，命题q为“今天晴天