2016年10月自考02324离散数学试题及答案含解析

离散数学年月真题

02324201610

1、【单选题】

A:

B:

C:

答D:案：C

解析：

给定一个谓词公式A，其中有一部分公式形如，则称它为A的x约束部

分，称B(x)为相应量词的作用域或辖域。

2、【单选题】设无向树T有3个度数为4的结点，其余结点都为树叶，则T的结点数为

10

11

A:

12

B:

13

C:

答D:案：B

解析：设无向树T的结点个数为x，则其树叶数为x-3。由握手定理及树的性质得方程：

3×4+（x-3）=2e=2(x-1)，解得x=11.

3、【单选题】设集合A有3个元素，则A中的划分有

3个

5个

A:

6个

B:

9个

C:

答D:案：B

解析：3个元素的集合可能产生的所有划分有如下几种情况：（1）划分块数为1的划分数

有1个；（2）划分块数为2的划分数有3个；（3）划分块数为3的划分数有1个。所以

共有5种不同的划分。

4、【单选题】下列关系不可能是相容关系的是

恒等关系

全域关系

A:

等价关系

B:

拟序关系

C:

答D:案：D

解析：满足自反性和对称性的关系称为相容关系。恒等关系、全域关系、等价关系均满足

自反性、对称性和传递性。满足反自反和传递性的关系称为拟序关系。所以，拟序关系可

能是相容关系。

5、【单选题】设论域为整数集，下列命题中真值为假的是

A:

B:

C:

答D:案：C

解析：选项A、D中，令x=0,y=0,则x+y=0，所以A为真，D也为真。选项B中令y=-x，

则B为真。故真值为假的是C。

6、【单选题】4个结点的非同构的无向树的数目是

5

4

A:

3

B:

2

C:

答D:案：D

解析：根据无向树的性质，4个结点的无向树有3条边。4个结点构成的无向树中的树叶

数（即度数为1的结点）可能有2个或3个两种情形。故其非同构的无向树的数目只能是

2个。

7、【单选题】下列命题公式是永真式的为

A:

B:

C:

答D:案：C

解析：

8、【单选题】下列语句是原子命题的为

x+y>xy

请给我来点掌声吧

A:

小明既爱唱歌又爱跳舞

B:

火星上有生物

C:

答D:案：D

解析：不能再分解成更简单的命题，称为原子命题。A中含有项，不是谓词逻辑中的原子

命题；B不是命题；C是复合命题；D是命题逻辑中的原子命题。

9、【单选题】设Z为整数集合，则下列集合关于数的加法运算不能构成独异点的是

A:

B:

C:

答D:案：C

解析：独异点是满足封闭、可结合、有幺元的代数系统。由于C中无幺元，故C不是独异

点。

10、【单选题】则既是S的

元素又是S的子集的为

A:

B:

C:

答D:案：B

解析：A中的{1}只是S的元素，而不是子集；C中的{Ф}既不是S的元素，也不是其子

集；D中的{1,2}只是S的元素。

11、【单选题】设p：他怕困难；q:他获得成功。命题“除非他不怕困难，否则他不会获得

成功”可符号化为

A:

B:

C:

答D:案：A

解析：原命题可翻译为“如果他获得成功，则他一定不怕困难”。

12、【单选题】在整数集Z上，下列运算满足结合律的是

A:

B:

C:

答D:案：D

解析：

13、【单选题】下列图对应的格是有补格的为

A:

B:

C:

答D:案：D

解析：设<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L使得a∧b=0和a∨b=1成立,

则称b是a的补元。4个选项均为有界格，1为全上界，0为全下界。但A中，b、c均没

有补元。B中b没有补元。C中d没有补元。D中a、b互为补元；c、d互为补元，所以D

是有补格。

14、【单选题】设G为连通的无向简单图。若G恰有2个奇度结点，则G一定具有

欧拉回路

欧拉通路

A:

哈密尔顿回路

B:

哈密尔顿通路

C:

答D:案：B

解析：图中行遍所有顶点且恰好经过每条边一次的通路称为欧拉通路。无向图G是半欧拉

图（即有欧拉通路）当且仅当G连通且恰有两个奇度顶点。

15、【单选题】设F（x）：x是火车；G（y）：y是汽车；H（x，y）：x比y快；则下列

语句可以表示成公式的是

每列火车都比所有汽车快

每列火车郡比某些汽车快

A:

某些火车比某些汽车快

B:

某些火车比所有汽车快

C:

答D:案：D

解析：存在量词表示“存在一个（些）”、“某些”。

16、【问答题】

答案：{<4,2>}

解析：复合运算有两种，左复合和右复合。本课程的教材中将复合约定成右复合。

17、【问答题】设G是一个有11个顶点的简单无向图。如果G恰有一个回路，则G的边数

最大是______________

答案：11

解析：删除G中回路上的任一条边，则G中无回路。此时，图中边数最大时，图G一定是

连通图，也即，删除G中回路上的任一条边后，得到一颗无向树，根据树的性质，其边数

为11-1=10，加上删除的回路上的边，G中共有11条边。

18、【问答题】

答案：{1,3,4}，{a,c,d}

解析：domR和ranR分别是关系R的定义域和值域。

19、【问答题】

答案：M100

解析：根据大项编码规则，其对应的大项应为M100

20、【问答题】

答案：{<a,b>,<b,a>,<b,c>,<c,b>}；{<a,b>,<b,c>,<a,c>}

解析：s(R)=R∪R-1,t(R)=R∪R2∪R3∪…∪Rn

21、【问答题】

答案：{1,4},{1,4,a,c}

解析：

22、【问答题】若连通平面图G有8条边，3个面，则G有___________个结点。

答案：7

解析：根据欧拉公式，设G为n阶m条边r个面的连通平面图，则n-m=2。因此，n=m-

r+2=8-3+2=7。

23、【问答题】

答案：2,16

解析：设º为S上的二元运算,如果存在e∈S，使得对任意x∈S都有eºx=xºe=x，则称e

是S中关于º运算的幺元（也称单位元）。2，4，8，16四个元素与2的最小公倍数分别是

2，4，8，16，根据定义，2是该代数系统的幺元。设º为S上的二元运算,如果存在

θ∈S，使得对任意x∈S都有θºx=xºθ=θ，则称θ是S中关于º运算的零元。2，4，8，

16四个元素与16的最小公倍数均为16，根据定义，16是该代数系统的零元。

24、【问答题】设论域是全体人类，F（x）：x能呼吸，要求只能使用存在量词，命题“所

有人都能呼吸”可符号化为___________________。

答案：

解析：

“所有人都能呼吸”可理解为“不存在不能呼吸的人”。也可先符号化“所有人都能呼

吸”为，然后再利用等值演算转化为只使用存在量词。

25、【问答题】含有n个命题变元的命题公式，共有_________________组指派

答案：2n

解析：设A是一命题公式，P1,P2,…,Pn为出现在A中的所有命题变元，对P1,P2,…,Pn

各指定一个真值，称为对A的一组指派或赋值。

26、【问答题】构造命题公式

的真值表。

答案：

解析：

构造真值表时，可先构造每个子公式的真值表。

27、【问答题】利用等值演算法求命题公式

的主析取范式。

答案：

解析：

用等值演算法求主析取范式，其具体步骤包括：①化归为析取范式。②除去析取范式中

所有永假的简单合取式。③在简单合取式中，将重复出现的合取项和相同变元合并。④

在简单合取式中补入没有出现的命题变元，即添加∧(p∨¬p)，再用分配律展开，最后合

并相同的小项。建议在利用等值演算法求完主范式后，再利用真值表法比

较一下结果是否相同？

28、【问答题】

答案：

解析：

（1）哈斯图是利用偏序自反、反对称、传递性简化的关系图。其实质是偏序关系的覆盖

关系的关系图。其特点是：每个结点没有环，两个连通的结点之间的序关系通过结点位置

的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边。

29、【问答题】设图G如题29图所示。（1）写出图G的邻接矩阵；（2）G中长度为4

的通路有几条？（3）上问中有几条回路？

答案：

解析：

30、【问答题】

答案：

解析：

31、【问答题】设无向图G有7个顶点，每个顶点的度数不是4就是5。证明：G中至少有5

个度数为4的顶点或至少有4个度数为5的顶点。

答案：

解析：握手定理的简单应用。任意无向图和有向图的所有顶点度数之和都等于边数的2

倍。

32、【问答题】

答案：

解析：

证明两个集合相等，最基本的方法是互为子集法。即要证明X=Y，即证明：

33、【问答题】证明：H关于

矩阵乘法构成一个群。

答案：

解析：代数系统是否为群，只需要逐一验证以下四个条件：(1)封闭性(2)结合律(3)有

幺元(4)每个元素有逆元

34、【问答题】今有a、b、c、d、e、f、g共7个球类运动爱好者，已知下列事实：a喜欢

篮球运动；b喜欢篮球运动和足球运动；c喜欢篮球、排球和乒乓球运动；d喜欢网球和足球

运动；e喜欢羽毛球和排球运动；f喜欢棒球、网球和乒乓球运动；g喜欢棒球和羽毛球运

动。试问：这7个人应如何围圆桌排座位，才能使每个人和他身边的人有共同球类爱好话

题。须写出所有可能方案。

答案：

解析：如果两个人爱好同一种球类，则用无向边连接它们，得到图34-1为按题意构造的

关系图；求解方案实际上是寻找图34-1中是否有哈密顿回路，该哈密顿图中每个结点的

度数均为2。所以在删边时应考虑删除度数大于2的结点关联的边。由此判断：因为结点

c的度数为4，所以必须删掉结点c关联的两条边，边bc、