山东开放大学《离散数学》期末考试复习题及参考答案

2021学年第一学期期末考试《离散数学》试题

一、单选题（题数：10，共30.0分）

1

设集合A={1,2,3,4,5,6}上的二元关系R={a,b©a,bA,且a+b=8},则R具有的性质

为（）.（3.0分）

A、自反的

B、对称的

C、对称和传递的

D、反自反和传递的

正确答案：B

2

若集合A的元素个数为10,则其募集的元素个数为（）.（3.0分）

A、1024

B、10

C、100

D、1

正确答案：A

3

命题公式（PVQ）-R的析取范式是（）（3.0分）

A、0（PVQ）VR

B、（PAQ）VR

C、（PVQ）VR

D、（0PA0Q）VR

正确答案：D

4

下列公式（）为重言式.

（3.0分）

A、

-PA—OJPMO

B、

（2T（PV。））一（一QK（PV协

C、

D、

（一声（尸八。）3

正确答案：C

答案解析：

5

集合庆={1,2,3,4,5,6,7,8}_1_的关系"一{<"且"JW}•，则R的性质为（）.

（3.0分）

A、

自反的

B、

对称的

C、

传递且对称的

D、

反自反且传递的

正确答案：B

答案解析：

6

设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6},则集合B的最大元、最小元、

上界、下界依次为（）.（3.0分）

A、8、2、8、2

B、无、2、无、2

C、6、2、6、2

D、8、1、6、1

正确答案：B

7

无向图G存在欧拉通路，当且仅当（）.（3.0分）

A、G中所有结点的度数全为偶数

B、G中至多有两个奇数度结点

C、G连通且所有结点的度数全为偶数

D、G连通且至多有两个奇数度结点

正确答案：D

8

设G是有n个结点，m条边的连通图，必须删去G的（）条边，才能确定G的一棵生成树.（3.0

分）

A、m+n-1

B、m-n

C、m+n+1

D、n-m=l

正确答案：A

9

设集合A={1,2,3,4}上的二元关系

<2,2>,<2,3>,<4,4>},小

5={vl,l>,<2,2>,<2,3>,<3,2>,<4,4>},是R的()闭包.

(3.0分)

A、

自反

B、

传递

C、

对称

D、

以上都不对

正确答案：C

答案解析：

10

表达式力(尸(xJ)vQ(z))ABy(R(xty)->Vzg(z))中Vx的辖域是()・

(3.0分)

A、

P(x,y)

B、

P(x必2(z)

c、

皿)

D、

♦♦*・

PLx,y)+

正确答案：B

答案解析：

二、填空题(题数：5,共20.0分)

1

已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为().(4.0

分)

正确答案

第一空：5

我的答案：

2

设6=&1讣//&g匕是有6个结点，8条边的连通图，则从G中删去（）条边，可以确定图G的

一棵生成树.（4.0分）

正确答案

第一空：3

我的答案：

3

设集合A={a,b,c},A上的二元关系R={<a,b>,<b,a>,c>,<c,d>},则

二元关系R具有的性质是（）.（4.0分）

正确答案

第一空：反自反的

我的答案：

4

设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去（4.0分）

正确答案

第一空：4

我的答案：

5

设连通平面图G的结点数为5,边数为6,则面数为（）.（4.0分）

正确答案

第一空：3

我的答案：

三、判断题（题数：25,共50.0分）

1

自反关系的矩阵具有的主对角线元素全为。的特点;而关系图的每个结点都没有自回路.（2.0

分）

正确答案：X

2

集合A的补集是由属于全集E但不属于集合A的元素组成的集合.（2.0分）

正确答案：V

3

A不是A*的对偶式.（2.0分）

正确答案：X

4

如果非空集合A上的二元关系R和S是等价关系，则武,也是A上的等价关系.（2.0分）

正确答案：V

5

五={%＞，＜&§刁

二元关系具有反自反性。

（2.0分）

正确答案：X

答案解析：

6

等价关系的关系图的特征之一每个结点都有自回路。

（2.0分）

正确答案：V

答案解析：

7

在推导中，如果有一个或多个公式重言蕴含着公式C,则公式C可以作为前提在推导中引

用.。（2.0分）

正确答案：J

8

自反关系的矩阵具有主对角线元素全为1的特点，而关系图的每个结点都有自回路。（2.0

分）

正确答案：J

9

命题有时也可以用0表示假.（2.0分）

正确答案：J

10

自反性就是所有第一元素与第二元素相等的有序对都在二元关系R中，当然x应是集合A的

元素。

（2.0分）

正确答案：J

答案解析：

11

通过一些严格定义的形式化运算，由基本命题出发，逐步地构成复杂的复合命题。（2.0分）

正确答案：V

12

对称关系的矩阵是对称矩阵。（2.0分）

正确答案：J

13

入度为。的顶点称为树叶（2.0分）

正确答案：X

14

命题公式指用命题的形式变元和逻辑联结词所联结的复合命题的构造形式..（2.0分）

正确答案：J

15

树中次数为1的顶点称为树叶.•（2.0分）

正确答案：V

16

谓词逻辑，即命题内部组成的逻辑，其中不仅有命题变项（元），还有个体变项（元）与谓

词变项（元）。（2.0分）

正确答案：J

17

一个集合（或子集）的极小元可能有多个，而最小元可能没有。（2.0分）

正确答案：V

18

存在汉密尔顿回路的图就是汉密尔顿图。（2.0分）

正确答案：J

19

不含任何元素的集合为空集，空集是惟一的，它是任何集合的子集。（2.0分）

正确答案：V

20

一个集合（或子集）的极大元或极小元可能有多个，而最大元或最小元可能没有。（2.0分）

正确答案：J

21

主析取范式是极小项的析取，而极小项是合取式。（2.0分）

正确答案：J

22

有向图删去边的方向为树，该有向图就是有向树（2.0分）

正确答案：J

23

至少包含任何联结词的命题称为原子命题或基本命题，。（2.0分）

正确答案：X

24

一个无向图成为森林，如果它的每个连通分图是树.。（2.0分）

正确答案：J

25

最小上界会小于子集中的任一元素（2.0分）

正确答案；X

山东开放大学成人高等教育学习平台

首页

任务

统计

资料

通知

作业

考试

讨论

体验新版

离散数学课程评价

窗体顶端

返回

2021学年第一学期期末考试《离散数学》试题

姓名：韩佳静班级：2020年上学期成绩：0.0分最高成绩：0.0分作答记录

一、单选题（题数：10,共30.0分）

1

若集合A的元素个数为10,则其累集的元素个数为（）.（3.0分）

A、1024

B、10

C^100

D、1

正确答案：A

2

若集合A={a,{a},{1,2}},则下列表述正确的是（）.

（3.0分）

A、

{%{a}}eA

B、

闻之

c、

{21弘

D、

正确答案：C

答案解析：

3

命题公式（PVQ）-R的析取范式是（）（3.0分）

A、0（PVQ）VR

B、（PAQ）VR

C、（PVQ）VR

D、（0PA0Q）VR

正确答案：D

4

集合人={1,2,3,4,5,6,7,8}上的关系“=*"】＞盯=1°且工J%}•,则R的性质为（）.

（3.0分）

A、

自反的

B、

对称的

C、

传递且对称的

D、

反自反且传递的

正确答案：B

答案解析：

5

下列等价公式成立的为().

(3.0分)

A、

.一尸八一QoPv?

B、

C、

2T(Pv?)=_Q八(PvQ)

D、

Ty(P0)o。"1

正确答案：B

答案解析：

6

无向图G存在欧拉通路，当且仅当().(3.0分)

A、G中所有结点的度数全为偶数

B、G中至多有两个奇数度结点

C、G连通且所有结点的度数全为偶数

D、G连通且至多有两个奇数度结点

正确答案：D

7

无向简单图G是棵树，当且仅当().(3.0分)

A、G连通且边数比结点数少1

B、G连通且结点数比边数少1

C、G的边数比结点数少1

D、G中没有回路.

正确答案：A

8

设集合A={1,2,3,4}上的二元关系

<2,2>,<2,3>,<4,4>},

5={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>},是口的()闭包.

(3.0分)

A、

自反

B、

传递

C、

对称

D、

以上都不对

正确答案：C

答案解析：

9

表达式Vx(P(x,y)vQ(z))A->VzQQ))中Vx的辖域是(),

(3.0分)

A、

P(x,y)

B、

P(xy)vO(z)

C、

H(3)

D、

%•1z

P(3如风X,亦

正确答案：B

答案解析：

10

设G是连通平面图，有v个结点，e条边，r个面，则r=（）.（3.0分）

A、e—v+2

B、v+e—2

C、e-v—2

D、e+v+2

正确答案：A

二、填空题（题数：5,共20.0分）

1

命题公式的真值是（）.（4。分）

正确答案

第一空：T（或1）

我的答案：

2

设6=&出丫/&目七是有6个结点，8条边的连通图，则从G中删去（）条边，可以确定图G的

棵生成树.（4.0分）

正确答案

第一空：3

我的答案：

3

设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去（4.0分）

正确答案

第一空：4

我的答案：

4

无向图G存在欧拉回路，当且仅当G连通且（）.（4.0分）

正确答案

第一空；所有结点的度数全为偶数

我的答案：

5

设G是连通平面图,v,e,r分别表示G的结点数,边数和面数,则v,e和r满足的关系式（）.（4.0

分）

正确答案

第一空：v-e+r=2

我的答案：

三、判断题（题数：25,共50.0分）

1

通过一些严格定义的形式化运算，由基本命题出发，逐步地构成简单的复合命题。（2.0分）

正确答案：X

2

命题有时也可以用1表示真.（2.0分）

正确答案：V

3

在任何有向图中，所有的入度之和等于所有结点的出度之和.（2.0分）

正确答案：V

4

命题有时也可以用0表示假.（2.0分）

正确答案：V

5

元素与元素之间是一种包含关系。（2.0分）

正确答案：X

6

当a是集合A中的元素，则称a属于A,记作afA。（2.0分）

正确答案：J

7

给定命题公式，若其命题变元对应于所有指派，命题公式均取值为真，则称该命题公式为

矛盾式或永假式.（2.0分）

正确答案：X

8

一个图能画在平面上，除结点之外，再没有边与边相交.。（2。分）

正确答案：J

9

入度为。的顶点称为树叶（2.0分）

正确答案：X

10

在命题公式中，对于所有命题变元指派各种真值的可能组合，就确定7这个命题公式的各种

真值情况.（2.0分）

正确答案：V

11

任给公式，列出该公式的真值表，若真值表的最后一列全为1,则该公式为永真式。（2.0

分）

正确答案：J

12

谓词逻辑，即命题内部组成的逻辑，其中不仅有命题变项（元），还有个体变项（元）与谓

词变项（元）。（2.0分）

正确答案：V

13

入度为1出度为。的顶点称为内点（2.0分）

正确答案：X

14

一个集合（或子集）的极小元可能有多个，而最小元可能没有。（2.0分）

正确答案：V

15

在任意集合A上都可以定义笛卡尔积。（2.0分）

正确答案：J

16

任何一个集合都是一个二元关系。（2.0分）

正确答案：X

17

每条边都是无向边的图，记作G=<V,E>..（2.0分）

正确答案：J

18

不含任何元素的集合为空集，空集是惟一的，它是任何集合的子集。（2.0分）

正确答案：J

19

在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集.（2.0分）

正确答案：V

20

集合A与B的差集由属于A,而不属于B的所有元素组成的集合。（2.0分）

正确答案：V

21

中结点与边之间存在确定的连接关系，但在图示中，结点的位置是不确定的.（2.0分）

正确答案：J

22

在非空有限集合B中，极小元必定存在，但不一定唯一.。（2.0分）

正确答案：J

23

26、设A、B、C为合式公式，若；］____1B且A是重言式，则B也是重言式.。（2.0分）

正确答案：V

24

若能将V分成两个互不相交的子集VI与V2使得G中任一边的两端点都不在同一个Vi

（i=l,2）中的n阶无向图，记G=<Vl,V2,E>..（2.0分）

正确答案；V

25

具有欧拉通路但无欧拉回路的图称为欧拉图.。（2.0分）

正确答案：X

山东开放大学成人高等教育学习平台

首页

任务

统计

资料

通知

作业

考试

讨论

体验新版

离散数学课程评价

窗体顶端

返回

2021学年第一学期期末考试《离散数学》试题

姓名：韩佳静班级：2020年上学期成绩：0.0分最高成绩：0.0分作答记录

一、单选题（题数：10,共30.0分）

1

设集合A={1,2,3,4,5,6}上的二元关系R={a,baa,bA,且a+b=8},则R具有的性质

为（）.（3.0分）

A、自反的

B、对称的

C、对称和传递的

D、反自反和传递的

正确答案：B

2

若集合A的元素个数为10,则其幕集的元素个数为（）.（3.0分）

A、1024

B、10

C、100

D、1

正确答案：A

3

若集合A={a,{a},{1,2}},则下列表述正确的是（）.

（3.0分）

A、

{%{a}}eA

B、

闻之

c、

Qi弘

D、

正确答案：C

答案解析：

4

命题公式(PVQ)-R的析取范式是()(3.0分)

A、0(PVQ)VR

B、(PAQ)VR

C、(PVQ)VR

D、(0PA0Q)VR

正确答案：D

5

集合A={1,2,3,4,5,6,7,8}上的关系**"修此曰且工〕巳”.，则R的性质为().

(3.0分)

A、

自反的

B、

对称的

C、

传递且对称的

D、

反自反且传递的

正确答案：B

答案解析：

6

下列等价公式成立的为().

(3.0分)

A、

.一尸八一QoPv?

B、

C、

2T(Pv?)=_Q八(PvQ)

D、

-PV(PAO)O©

正确答案：B

答案解析：

7

设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6},则集合B的最大元、最小元、

上界、下界依次为（）.（3.0分）

A、8、2^8、2

B、无、2、无、2

C、6、2、6、2

D、8、1、6、1

正确答案：B

8

无向简单图G是棵树，当且仅当（）.（3.0分）

A、G连通且边数比结点数少1

B、G连通且结点数比边数少1

C、G的边数比结点数少1

D、G中没有回路.

正确答案：A

9

表达式Vx（尸（xj）v?（z））AR（&（x,y）->Vz2（z））中Vx的辖域是（）.

（3.0分）

A、

P（x,y）

B、

P（x必驹

C、

S）

D^

正确答案：B

答案解析：

10

设图则下列结论成立的是（）.

（3.0分）

A、

deg（V）=2%E%

B、

deg(V)=%E%

C、

2deg（v）=2|£|

v«F

D、

Zdeg（y）=|E卜

VeF

正确答案：c

答案解析：

二、填空题（题数：5,共20.0分）

1

命题公式的真值是（）.（4.0分）

正确答案

第•空：T（或1）

我的答案：

2

已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为（）.（4.0

分）

正确答案

第一空：5

我的答案：

3

设集合A={a,b,c},A上的二元关系R={<a,b>,<b,a>,<b,c>,<c,d>},则

二元关系R具有的性质是（）.（4.0分）

正确答案

第一空；反自反的

我的答案：

4

设A={a,b,c},B={1,2},作f：A-B,则不同的函数个数为（）.（4.0分）

正确答案

第一空：8

我的答案：

5

设连通平面图G的结点数为5,边数为6,则面数为（）.（4.0分）

正确答案

第一空：3

我的答案：

三、判断题（题数：25,共50.0分）

1

任意两个函数f、g都能进行复合，（2.0分）

正确答案：X

2

在书写谓词时，不可以将个体变元的个体域定义为全域，。（2.0分）

正确答案：X

3

设B是A的子集，如果在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容

类.

（2.0分）

正确答案：V

答案解析：

4

图的表示主要有三种方法，即集合表示、图示、矩阵表示.三种表示形式是等同的，不可以

互相转换.。（2.0分）

正确答案：X

5

命题有时也可以用1表示假..（2.0分）

正确答案：X

6

每边带权的图称为带权图.。（2.0分）

正确答案：V

7

集合A与B的对称差由分别属于集合A与B的元素但不属于它们公共元素组成的集合。（2.0

分）

正确答案：J

8

通过一些严格定义的形式化运算，由基本命题出发，逐步地构成复杂的复合命题。（2.0分）

正确答案；V

9

利用基本等价式，对给定公式进行等值推导，若该公式的真值为0,则该公式为永假式。（2.0

分）

正确答案：J

10

对称关系的矩阵是对称矩阵。（2.0分）

正确答案：J

11

集合A和B的并集是既属于A又属于B的所有元素组成的集合.（2.0分）

正确答案：X

12

紧接于量词之后最小的子公式称为量词的辖域（或作用域）。（2.0分）

正确答案：V

13

上界与下界不可在子集之外确定（2.0分）

正确答案：X

14

图是由称为结点的集合、边的集合，以及边集到结点偶对集上的函数来确定的一个三元组,

其中的函数表明了结点与边之间的连接关系，通常连接关系可以用结点的偶对来表示。（2.0

分）

正确答案：J

15

给定一命题公式，若其命题变元对应于所有指派，命题公式均取值为假，则称该命题公式为

重言式或永真式.（2.0分）

正确答案：X

16

如果把有向图中每条有向边都看作无向边，就得一个无向图，此无向图称为原有向图的零

图.（2.0分）

正确答案：X

17

（复合运算）任意二个关系R，S都能复合吗？如果R和S能复合，那么R・S一定是非空集

合。（2.0分）

正确答案：X

18

无向图G中，结点u,v存在通路，则u,v是连通的。（2.0分）

正确答案：J

19

函数（也叫做映射）是一种特定类型的二元关系，它建立了从一个集合到另一个集合的一种

变换关系，计算机执行任何类型的程序都是这样一种变换.。（2.0分）

正确答案：J

20

若能将V分成两个互不相交的子集VI与V2使得G中任一边的两端点都不在同一

个Vi（/=1,2）中的«阶有向图，记GYP1,F2,E>,。，

（2.0分）

正确答案：X

答案解析：

21

任意两个函数f、g不一定都能进行复合。

（2.0分）

正确答案：J

答案解析：

22

集合A与B的差集由属于A,而不属于B的所有元素组成的集合。（2.0分）

正确答案：J

23

利用基本等价式，对给定公式进行等值推导，既非永真，也非用假，成为非永真的可满足式

（2.0分）

正确答案：J

24

结点数相等是两图同构的必要条件。（2.0分）

正确答案：J

25

个体变元就-•般用小写字母x、y、z等表示。（2.0分）

正确答案：J

山东开放大学成人高等教育学习平台

首页

任务

统计

资料

通知

作业

考试

讨论

体验新版

离散数学课程评价

窗体顶端

返回

2021学年第一学期期末考试《离散数学》试题

姓名：韩佳静班级：2020年上学期成绩：0.0分最高成绩：0.0作答记录

一、单选题（题数：10,共30.0分）

1

若集合A的元素个数为10,则其解集的元素个数为（）.（3.0分）

A、1024

B、10

C、100

D、1

正确答案：A

2

命题公式（PVQ）-R的析取范式是（）（3.0分）

A、0（PVQ）VR

B、（PAQ）VR

C、（PVQ）VR

D、（0PA0Q）VR

正确答案：D

3

下列公式（）为重言式.

（3.0分）

A、

—P^^Q^PvQ

B、

9T（Pv。））一（一。八仍处

c、

（2T（—°fP））WYTPT。））

D、

（一声（尸心一㊁

正确答案：C

答案解析：

4

设完全图K有n个结点（n22）,m条边，当（）时，K中存在欧拉回路.（3.0分）

A、m为奇数

B、n为偶数

C、n为奇数

D、m为偶数

正确答案：C

5

设A={1,2,3,4,5,6,7,8},R是A上的整除关系，B={2,4,6},则集合B的最大元、最小元、

上界、下界依次为（）.（3.0分）

A、8、2、8、2

B、无、2、无、2

C、6、2、6、2

D、8、1、6、1

正确答案：B

6

若集合A={a,b,{1,2}},B={1,2},则（）.

（3.0分）

A、

{&{a}}eA

B、

•⑵》

c、

D、

正确答案：B

答案解析：

7

无向图G存在欧拉通路，当且仅当（）.（3.0分）

A、G中所有结点的度数全为偶数

B、G中至多有两个奇数度结点

C、G连通且所有结点的度数全为偶数

D、G连通且至多有两个奇数度结点

正确答案：D

8

设集合A={1,2,3,4}上的二元关系

<2,2>,<2,3>,<4,4>},

<2,2>,<2,3>,<3,2>,<4,4>},是R的（）闭包.

（3.0分）

A、

自反

B、

传递

C、

对称

D、

以上都不对

正确答案：C

答案解析：

9

设G是连通平面图，有v个结点，e条边，r个面，则r=（）.（3.0分）

A、e—v+2

B、v+e—2

C、e-v-2

D、e+v+2

正确答案：A

10

设图G=（P，&,则下列结论成立的是（）.

（3.0分）

A、

deg（V）=2%E%

B、

deg（V）=%E%

C、

2deg（v）=2|£|

v«F

D、

Zdeg（y）=|E卜

VeF

正确答案：c

答案解析：

二、填空题（题数：5,共20.0分）

1

已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为（）.（4.0

分）

正确答案

第一空：5

我的答案：

2

设A={a,b,c},B={1,2},作f：A-B,则不同的函数个数为（）.（4.0分）

正确答案

第一空；8

我的答案：

3

设连通平面图G的结点数为5,边数为6,则面数为（）.（4.0分）

正确答案

第一空：3

我的答案：

4

已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是

（）.（4.0分）

正确答案

第一空：15

我的答案:

5

设有向图D为欧拉图，则图D中每个结点的入度（）.（4.0分）

正确答案

第一空：等于出度

我的答案：

三、判断题（题数：25,共50.0分）

1

n个结点的连通图G,每边指定一正数，称为权。（2.0分）

正确答案：J

2

谓词一般用大写字母P、Q、R等表示。（2。分）

正确答案：J

3

从树根到T的任顶点v的通路（顶点不同的路）的长度称为v顶点的层数。（2.0分）

正确答案：J

4

集合A与B的对称差由分别属于集合A与B的元素但不属于它们公共元素组成的集合。（2.0

分）

正确答案：J

5

谓词命名式不可以看成是一个命题函数.（2.0分）

正确答案：X

6

在谓词公式中常包含命题变元与个体变元，当个体变元用确定的个体取代，命题变元用确定

的命题取代时，就称为对谓词公式的赋值.谓词公式经过赋值，就成为有确定真值的命题。

（2.0分）

正确答案：V

7

握手定理表明图中结点的度数之和与边数之间的关系，即图的结点度数之和为边数的两倍

（2.0分）

正确答案：V

8

一个图能画在平面上，除结点之外，再没有边与边相交.。（2.0分）

正确答案：V

9

在命题公式中，对于所有命题变元指派各种真值的可能组合，就确定7这个命题公式的各种

真值情况.（2.0分）

正确答案：J

10

反自反性就是所有第一元素与第二元素相等的有序对都不在二元关系R中。

（2.0分）

正确答案：J

答案解析：

最小上界是所有上界中最小者（2.0分）

正确答案：J

12

入度为1出度为0的顶点称为内点（2.0分）

正确答案：X

13

函数（也叫做映射）是一种特定类型的二元关系，它建立了从一个集合到另一个集合的一种

变换关系，计算机执行任何类型的程序都是这样一种变换.。（2.0分）

正确答案：J

14

列举法是将集合中元素的共同属性描述出来.（2.0分）

正确答案：X

15

任何个集合都是个二元关系。（2.0分）

正确答案：X

16

集合与其元素之间存在属于或不属于关系。（2.0分）

正确答案：J

17

对任意两个集合A和B,若A中的每个元素都是B中的元素，则称B为A的子集。（2.0分）

正确答案：X

18

一个集合（或子集）的极大元或极小元可能有多个，而最大元或最小元可能没有。（2.0分）

正确答案：J

19

任给公式，列出该公式的真值表，若真值表的最后一列全为0,则该公式是永假式；。（2.0

分）

正确答案；V

20

（公式的主析取范式有2n个极大项（即无极小项），则该公式是永真式；。（2.0分）

正确答案：X

21

主析取范式是极小项的析取，而极小项是合取式。（2.0分）

正确答案：V

22

中结点与边之间存在确定的连接关系，但在图示中，结点的位置是不确定的.（2.0分）

正确答案：J

23

偏序集中最小元与极小元是不一样的.（2.0分）

正确答案：J

24

任意命题公式都存在与之等值的范式，存在与之等值的主范式，且是不惟一的（2.0分）

正确答案：X

25

一个无向图成为森林，如果它的每个连通分图是树.。（2.0分）

正确答案：J

山东开放大学成人高等教育学习平台

首页

任务

统计

资料

通知

作业

考试

讨论

体验新版

离散数学课程评价

窗体顶端

返回

2021学年第一学期期末考试《离散数学》试题

姓名：韩佳静班级：2020年上学期成绩：0.0分最高成绩：0.0分作答记录

一、单选题（题数：10,共30.0分）

1

设集合A={1,2,3,4,5,6}上的二元关系R={a,bea,bA,且a+b=8},则R具有的性质

为（）.（3.0分）

A、自反的

B、对称的

C、对称和传递的

D、反自反和传递的

正确答案：B

2

若集合A的元素个数为10,则其森集的元素个数为（）.（3。分）

A、1024

B、10

C、100

D、1

正确答案：A

3

如果R1和R2是A上的自反关系，则R1UR2,R1PR2,R1-R2中自反关系有（）个.（3.0

分）

A、0

B、2

C、1

D、3

正确答案：B

4

下列公式（）为重言式.

（33分）

A、

-PA—OJPMO

B、

9T（PV0））一（一刎外纱

C、

（2T（-0TP））T-£TPT。））

D、

（一声（尸心一㊁

正确答案：C

答案解析：

5

集合A={1,2,3,4,5,6,7,8}上的关系h{"'A"10且无蚱/}..则R的性质为（）.

（3.0分）

A、

自反的

B、

对称的

C、

传递且对称的

D、

反自反且传递的

正确答案：B

答案解析：

6

下列等价公式成立的为（）.

（3.0分）

A、

.一尸八一QoPvQ

B、

3T（「OfP）=df（Pf0）<

c、

2T（Pv?）=_Q八（PvQ）

D、

Ty（P0）o。"1

正确答案：B

答案解析：

7

无向图G存在欧拉通路，当且仅当（）.（3.0分）

A、G中所有结点的度数全为偶数

B、G中至多有两个奇数度结点

C、G连通且所有结点的度数全为偶数

D、G连通且至多有两个奇数度结点

正确答案：D

8

设G是有n个结点，m条边的连通图，必须删去G的（）条边，才能确定G的一棵生成树.（3.0

分）

A、m+n-1

m-n

C、m+n+1

D、n-m=l

正确答案；A

9

设集合A={1,2,3,4}上的二元关系

<2,2>,<2,3>,<4,4>},

5={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>},是R的（）闭包.

（3.0分）

A、

自反

B、

传递

C、

对称

D、

以上都不对

正确答案：C

答案解析：

10

设G是连通平面图，有v个结点，e条边，r个面，则r=（）.（3.0分）

A^e-v+2

B、v+e—2

C、e-v-2

D、e+v+2

正确答案：A

二、填空题（题数：5,共20.0分）

1

设集合A={a,b,c}>A上的二元关系R={<a,b>,a>〃d>,},则

二元关系R具有的性质是（）.（4.0分）

正确答案

第一空：反自反的

我的答案：

2

谓词命题公式”）（P（x）-Q（x）VR（x,y））中的约束变元为（）.（4.0分）

正确答案

第一空：x

我的答案：

3

设连通平面图G的结点数为5,边数为6,则面数为（）.（4.0分）

正确答案

第一空：3

我的答案：

4

给定一个序列集合{000,001，01，10,0}，若去掉其中的元素（），则该序列集合构成前缀码.（4.0

分）

正确答案

第一空：0

我的答案：

5

设有向图D为欧拉图，则图D中每个结点的入度（）.（4.0分）

正确答案

第一空：等于出度

我的答案：

三、判断题（题数：25,共50.0分）

1

自反关系的矩阵具有的主对角线元素全为。的特点;而关系图的每个结点都没有自回路.（2.0

分）

正确答案：X

2

在书写谓词时，不可以将个体变元的个体域定义为全域，。（2.0分）

正确答案：X

3

五={">—>}

二元关系具有反自反性。

（2.0分）

正确答案：X

答案解析：

4

一棵有向树T，若恰有一个顶点的入度为0,其余顶点的入度都为1，该树为根树..（2.0

分）

正确答案：J

5

自反关系的矩阵具有主对角线元素全为1的特点，而关系图的每个结点都有自回路。（2.0

分）

正确答案：J

6

谓词一般用大写字母P、Q、R等表示。（2。分）

正确答案：V

7

个体一般用小写字母a、b、c等表示。（2.0分）

正确答案：V

8

给定两个命题公式A与B,设Pl,P2,…，Pn为所有出现于A与B中的原子变元，若给P1,

P2,…，Pn任一组真值指派，A与B的真值均相同，则称公式A与B是等价的或逻辑相等.

（2.0分）

正确答案：J

答案解析：

9

若a不是集合A中的元素，则称a不属于A,记作aiA“（2.0分）

正确答案：J

10

在谓词公式中常包含命题变元与个体变元，当个体变元用确定的个体取代，命题变元用确定

的命题取代时，就称为对谓词公式的赋值.谓词公式经过赋值，就成为有确定真值的命题。

（2.0分）

正确答案：J

11

中结点与边之间存在确定的连接关系，但在图示中，结点的位置是确定的.（2.0分）

正确答案：X

12

寻找一种简单而有效的方法来判断图的同构，是图论中一个重要而已经解决的问题。（2.0

分）

正确答案：X

13

上界与下界不可在子集之外确定（2。分）

正确答案：X

14

反自反性就是所有第一元素与第二元素相等的有序对都不在二元关系R中。

（2.0分）

正确答案：J

答案解析：

15

最小上界是所有上界中最小者（2.0分）

正确答案：J

16

公式的主析取（或合取）范式的极小项（或极大项）个数大于。小于2n,,则该公式是可满

足式.（2.0分）

正确答案：J

17

笛卡儿积的运算一般不能交换。（2.0分）

正确答案：J

18

（公式的主析取范式有2n个极大项（即无极小项），则该公式是永真式；。（2.0分）

正确答案：X

19

主析取范式是极小项的析取，而极小项是合取式。（2.0分）

正确答案：V

20

每条边都是有向边的图，记作'="4.

（2.0分）

正确答案：J

答案解析：

21

在命题演算中，任一永真公式中的同一命题变元，用同一公式取代时，其结果仍然是永真公

式.。（2.0分）

正确答案：J

22

偏序集中最小元与极小元是不一样的.（2.0分）

正确答案：J

23

最小上界会小于子集中的任一元素（2.0分）

正确答案：X

24

若能将V分成两个互不相交的子集VI与V2使得G中任一边的两端点都不在同一个Vi

（i=l,2）中的n阶无向图，记G=<VI,V2,E>..（2.0分）

正确答案：V

25

该公式的主合取范式有2n个极小项（即无极大项），则该公式是永假式；.（2.0分）

正确答案：X

山东开放大学成人高等教育学习平台

首页

任务

统计

资料

通知

作业

考试

讨论

体验新版

离散数学课程评价

窗体顶端

返回

2021学年第一学期期末考试《离散数学》试题

姓名：韩佳静班级：2020年上学期成绩：0.0分最高成绩：0.0分作答记录

一、单选题（题数：10,共30.0分）

1

若集合A的元素个数为10,则其凝集的元素个数为（）.（3.0分）

A、1024

B、10

C、100

D、1

正确答案：A

2

如果R1和R2是A上的自反关系，则R1UR2,R1DR2,R1-R2中自反关系有（）个.（3.0

分）

A、0

B、2

C、1

D、3

正确答案：B

3

下列公式（）为重言式.

（3.0分）

A、

—P^^Q^PvQ

B、

9f（Pv。））一（一6（Pv0）＞

c、

（2T（-0TP））T-£TPT。））

D、

（一声（P八g））3

正确答案：c

答案解析：

4

设完全图K有n个结点（n22）,m条边，当（）时，K中存在欧拉回路.（3.0分）

A、m为奇数

B、n为偶数

C、n为奇数

D、m为偶数

正确答案：C

5

下列等价公式成立的为（）.

（3.0分）

A、

.一尸八一QoPv?

B、

C、

2T（Pv?）=_Q八（PvQ）

D、

-Py(P/\O)o21

正确答案：B

答案解析：

6

设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6},则集合B的最大元、最小元、

上界、下界依次为().(3.0分)

A、8、2、8、2

B、无、2、无、2

C、6、2、6、2

D、8、1、6、1

正确答案：B

7

无向简单图G是棵树，当且仅当().(3.0分)

A、G连通且边数比结点数少1

B、G连通且结点数比边数少1

C、G的边数比结点数少1

D、G中没有回路.

正确答案：A

8

表达式Vx(P(x,y)v2(z))A->VzQQ))中Vx的辖域是(),

(3.0分)

A、

P(x,y)

B、

P(X必。⑵

五（x,0

D、

%•1z

P(3如风X,亦

正确答案：B

答案解析：

9

设.4(x):x是人，3(x):x是学生，则命题“不是所有人都是学生”可符号化为().

(3.0分)

A、

(Vx)(A(x)AB(x))

B、

n(EX)(A(X)AB(X))

C、

IW)(N(x)fB(x))

D、

-I(3x)(^(x)AnB(x))

正确答案：C

答案解析：

io

设图G=<0,E>,则下列结论成立的是().

(3.0分)

A、

deg(V)=2%E%

B、

deg(V)=%E%

C、

2deg(v)=2|E|

VeF

D、

Zdeg(y)=|E卜

VeF

正确答案：C

答案解析：

二、填空题(题数：5,共20.0分)

1

设集合上的二元关系则

A={a,b,c},AR={<afb>,<b,a>f<b,c>,<c,d>},

二元关系R具有的性质是().(4.0分)

正确答案

第一空：反自反的

我的答案：

2

设A={a,b,c},B={1,2},作f：A-B,则不同的函数个数为（）.（4.0分）

正确答案

第一空：8

我的答案：

3

设连通平面图G的结点数为5,边数为6,则面数为（）.（4.0分）

正确答案

第一空：3

我的答案：

4

设有向图D为欧拉图，则图D中每个结点的入度（）.（4.0分）

正确答案

第一空：等于出度

我的答案；

5

设集合A有n个元素，那么A的塞集合P（A）的元素个数为（）.（4.0分）

正确答案

第一空：2n

我的答案：

三、判断题（题数：25,共50.0分）

1

有向图中，任意一对结点之间至少有一个结点可达另一结点是三侧连通.（2.0分）

正确答案：X

2

在书写谓词时，不可以将个体变元的个体域定义为全域，。（2.0分）

正确答案；X

3

命题有时也可以用1表示真.（2.0分）

正确答案：J

4

在任何有向图中，所有的入度之和等于所有结点的出度之和.（2.0分）

正确答案：V

5

设B是A的子集，如果在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容

类.

（2.0分）

正确答案：J

答案解析：

6

G的生成树T的所有边的权之和是生成树T的权，记作W（T）.（2.0分）

正确答案：J

7

命题有时也可以用1表示假..（2.0分）

正确答案：X

8

每边带权的图称为带权图.。（2.0分）

正确答案：J

9

个体一般用小写字母a、b、c等表示。（2.0分）

正确答案：J

10

通过图G的每条边一次且仅一次，而且走遍每个结点的通路（回路），就是欧拉通路（回

路）.。（2.0分）

正确答案：J

11

寻找种简单而有效的方法来判断图的同构，是图论中个重要而已经解决的问题。（2.0

分）

正确答案：X

12

单独的个体和谓词不能构成命题，故能将它们分开以表示命题.（2.0分）

正确答案：X

13

给定一命题公式，若其命题变元对应于所有指派，命题公式均取值为真，则称该命题公式为

矛盾式或永假式.（2.0分）

正确答案：X

14

设T是一棵根树，若T的每个分支点的出度至多为m,该树为m叉枕（2.0分）

正确答案：V

15

任给公式，列出该公式的真值表，若真值表的最后一列全为1,则该公式为永真式。（2.0

分）

正确答案：J

16

如果把有向图中每条有向边都看作无向边，就得一个无向图，此无向图称为原有向图的零

图.（2.0分）

正确答案：X

17

列举法是将集合中元素的共同属性描述出来.（2.0分）

正确答案：X

18

集合与其元素之间存在属于或不属于关系。（2.0分）

正确答案：J

19

对任意两个集合A和B,若A中的每个元素都是B