齐齐哈尔离散数学试卷

齐齐哈尔离散数学试卷一、选择题（每题1分，共10分）

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

A.A=B

B.A≠B

C.A⊂B

D.B⊂A

2.下列哪个是命题？

A.今天天气很好。

B.请开门。

C.2+3=5

D.你好吗？

3.在逻辑运算中，命题p和命题q的合取（∧）运算的结果是？

A.p或q

B.p且q

C.非p

D.非q

4.下列哪个是谓词逻辑的量化符号？

A.∃

B.∀

C.∨

D.∧

5.在图论中，一个图G=(V,E)中，V表示？

A.边

B.顶点

C.权重

D.邻接矩阵

6.在树形结构中，一个非叶顶点的度数至少是？

A.0

B.1

C.2

D.3

7.在组合数学中，从n个不同元素中取出k个元素的组合数记作？

A.P(n,k)

B.C(n,k)

C.A(n,k)

D.G(n,k)

8.在数理逻辑中，命题p→q的等价形式是？

A.q→p

B.¬p∨q

C.¬p∧q

D.p∨¬q

9.在关系代数中，关系R的投影操作记作？

A.π

B.σ

C.×

D.∩

10.在算法分析中，一个算法的时间复杂度通常用哪个符号表示？

A.O

B.Ω

C.Θ

D.ε

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

1.下列哪些是命题逻辑的常见联结词？

A.与（∧）

B.或（∨）

C.非（¬）

D.蕴含（→）

E.等价（↔）

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

A.并集（∪）

B.交集（∩）

C.差集（−）

D.补集（'）

E.幂集（P(A)）

3.在图论中，下列哪些是图的常见性质？

A.顶点数（|V|）

B.边数（|E|）

C.度数序列

D.连通性

E.图的着色

4.在谓词逻辑中，下列哪些是量词的用法？

A.全称量词（∀）

B.存在量词（∃）

C.选择量词

D.谓词

E.个体变量

5.在组合数学中，下列哪些是常见的计数问题？

A.排列

B.组合

C.二项式系数

D.鸽巢原理

E.母函数

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

1.在命题逻辑中，符号“¬p”表示__________。

2.集合A={1,2,3}与集合B={3,4,5}的并集是__________。

3.在图论中，一个有n个顶点的树有__________条边。

4.谓词逻辑中的全称量词“∀x”表示__________。

5.从n个不同元素中取出k个元素的排列数记作__________。

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

1.设集合A={x|x是小于10的正偶数}，B={x|x是小于10的正奇数}。求A∪B和A∩B。

2.写出命题“今天下雨且天气很冷”的否定形式。

3.设集合A={1,2,3}，B={a,b}。求A×B。

4.画一个具有5个顶点的简单无向图，其中顶点集V={v1,v2,v3,v4,v5}，边集E={v1v2,v1v3,v2v4,v3v4,v4v5}，并标出每个顶点的度数。

5.计算从6个不同元素中取出3个元素的组合数，并写出计算过程。

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

一、选择题答案

1.A

2.C

3.B

4.B

5.B

6.C

7.B

8.B

9.A

10.A

二、多项选择题答案

1.A,B,C,D,E

2.A,B,C,D,E

3.A,B,C,D,E

4.A,B,D,E

5.A,B,C,D,E

三、填空题答案

1.非p命题

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

3.n-1

4.对于所有x，P(x)为真

5.P(n,k)

四、计算题答案

1.A∪B={1,2,3,4,5,6,7,8,9}，A∩B=∅

2.非p：今天不下雨或天气不冷

3.A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}

4.图略，度数分别为：v1=2,v2=2,v3=2,v4=3,v5=1

5.C(6,3)=6!/(3!3!)=20

知识点总结

集合论

-集合的基本概念：集合的表示法，集合间的关系（包含、相等），集合的基本运算（并集、交集、差集、补集、幂集）

-集合的性质：交换律、结合律、分配律、德摩根律

命题逻辑

-命题的概念：原子命题、复合命题

-联结词：与（∧）、或（∨）、非（¬）、蕴含（→）、等价（↔）

-命题公式：真值表、等价式、范式

谓词逻辑

-量词：全称量词（∀）、存在量词（∃）

-谓词公式：谓词、个体变量、量词的使用

图论

-图的基本概念：顶点、边、无向图、有向图、简单图、多重图

-图的性质：度数、路径、连通性、图的着色

-树：树的概念、性质、生成树

组合数学

-计数问题：排列、组合、二项式系数、鸽巢原理

-母函数：母函数的应用

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

一、选择题

-集合论：考察集合间的关系和运算，如集合相等、并集、交集等。

示例：集合A={1,2,3}与集合B={3,2,1}的关系是A=B。

-命题逻辑：考察命题的概念和联结词的使用，如复合命题的构成。

示例：命题“今天天气很好”是一个原子命题。

-谓词逻辑：考察量词的用法，如全称量词和存在量词的区别。

示例：谓词逻辑中的全称量词“∀x”表示对于所有x，P(x)为真。

-图论：考察图的基本概念和性质，如顶点数、边数、度数等。

示例：一个有n个顶点的树有n-1条边。

-组合数学：考察组合数的计算和常见计数问题，如排列、组合等。

示例：从n个不同元素中取出k个元素的排列数记作P(n,k)。

二、多项选择题

-集合论：考察集合的基本运算和性质，如并集、交集、差集等。

示例：集合A={1,2,3}与集合B={3,4,5}的并集是{1,2,3,4,5}。

-命题逻辑：考察联结词的使用和复合命题的构成，如与、或、非等。

示例：命题“今天下雨且天气很冷”的否定形式是“今天不下雨或天气不冷”。

-谓词逻辑：考察量词的用法和谓词公式，如全称量词和存在量词。

示例：谓词逻辑中的全称量词“∀x”表示对于所有x，P(x)为真。

-图论：考察图的基本概念和性质，如顶点数、边数、度数等。

示例：一个具有5个顶点的简单无向图，其中顶点集V={v1,v2,v3,v4,v5}，边集E={v1v2,v1v3,v2v4,v3v4,v4v5}，并标出每个顶点的度数。

-组合数学：考察常见的计数问题，如排列、组合、二项式系数等。

示例：从6个不同元素中取出3个元素的组合数是C(6,3)=20。

三、填空题

-命题逻辑：考察联结词的使用和复合命题的构成，如非命题。

示例：在命题逻辑中，符号“¬p”表示非p命题。

-集合论：考察集合的基本运算和性质，如并集。

示例：集合A={1,2,3}与集合B={3,4,5}的并集是{1,2,3,4,5}。

-图论：考察图的基本性质，如树的边数。

示例：一个有n个顶点的树有n-1条边。

-谓词逻辑：考察量词的用法和谓词公式，如全称量词。

示例：谓词逻辑中的全称量词“∀x”表示对于所有x，P(x)为真。

-组合数学：考察组合数的表示，如排列数的记法。

示例：从n个不同元素中取出k个元素的排列数记作P(n,k)。

四、计算题

-集合论：考察集合的基本运算，如并集和交集。

示例：集合A={x|x是小于10的正偶数}，B={x|x是小于10的正奇数}。求A∪B和A∩B。

-命题逻辑：考察复合命题的否定形式。

示例：写出命题“今天下雨且天气很冷”的否定形