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

离散数学年月真题

02324201710

1、【单选题】令P：他怕困难，q：他战胜困难，命题“他战胜困难是因为他不怕困难”的

符号化形式为（）。

A:

B:

C:

答D:案：A

解析：“他不怕困难”是“他怕困难”的否定式，命题“他战胜困难是因为他不怕困难”

化成基本结构为“因为他不怕困难，所以他战胜困难”，典型的蕴涵式。因此，符号化形

式为，选A。

2、【单选题】令F(x)：x为苹果，H(x,y)：x与y完全相同，L(x,y):x=y，则命题“没有完

全相同的苹果”的符号化形式为（）。

A:

B:

C:

答D:案：B

解析：

本题命题“没有完全相同的苹果”中，没有指明个体域，因而采用全总个体域。其中“相

同的苹果”需要任意两个苹果进行比较，即是“两个苹果”同时“非同一个苹果”且“完

全相同”，符号化为“”；“没有”为否定词；则“没有完全相同的苹

果”符号化为“”，因此选B。

3、【单选题】一棵树有2个4度结点，3个3度结点，其余为树叶，则该树中树叶个数是

（）。

7

8

A:

9

B:

10

C:

答D:案：C

解析：根据无向树的定义，2个4度结点可以组成“艹”树状，3个3度节点可以通过

“艹”6个结点中选择任意3个结点上分别悬挂2片树叶即可。这样树叶总个数为9。故

选C。

4、【单选题】设集合A={a,b,c,d}，现有A上的二元关系R={<a,b>,<b,c>,<c,b>,<

b,a>,}，则A是（）。

自反的

对称的

A:

反对称的

B:

传递的

C:

答D:案：B

解析：

二元关系R中典型满足即满足对称的关系的定义。故选B。

5、【单选题】下图中为欧拉图的是（）。

A:

B:

C:

答D:案：C

解析：根据欧拉图的定义，具有欧拉回路的图为欧拉图，其充分必要条件是连通的且不含

有奇度顶点。而ABD三个选项中均有奇度顶点，故选C。

6、【单选题】下列谓词公式中，不是前束范式的为（）。

A:

B:

C:

答D:案：D

解析：根据一阶逻辑前束范式的定义，所有约束量词只能在公式最前面，后面公式不能出

现量词，排除选项ABC，故选D。

7、【单选题】表示集合之间关系的图是（）。

文氏图

哈斯图

A:

欧拉图

B:

树

C:

答D:案：A

解析：根据集合代数理论，表示集合之间关系与运算的图为文氏图，故选A。

8、【单选题】无向完全图的

边的条数为（）。

10

15

A:

20

B:

30

C:

答D:案：B

解析：根据无向完全图的定义，可以6结点中每一个都与其余5个相邻接，其边数计算公

式为n(n-1)/2，带入n=6，则为15，故选B。

9、【单选题】设T是n阶树(n≥2)，则T不具有的性质是（）。

连通图

哈密顿图

A:

有n－1条边

B:

至少有两片树叶

C:

答D:案：B

解析：根据树的定义及等价命题，n阶树一定是连通的，且有n-1条边，至少有两片树

叶，但不会有回路，因此不是哈密顿图（具有哈密顿回路的图），故选B。

10、【单选题】设R、S均为集合A上的二元关系，下面命题正确的是（）。

A:

B:

C:

答D:案：A

解析：根据二元关系的运算规律，两个二元关系的右复合只有自反性保持不变，故选A。

11、【单选题】以下关于图的矩阵的描述，正确的是（）。

邻接矩阵即关系矩阵

可达矩阵是针对无向图的

A:

无向图有邻接矩阵

B:

可达矩阵是针对有向图的

C:

答D:案：C

解析：根据图的矩阵的描述理论，邻接矩阵与关系矩阵是不同的，无向图与有向图都有关

系矩阵，邻接矩阵仅应用于有向图，故选C。

12、【单选题】一个6阶连通图的边数至少为（）。

4

5

A:

6

B:

7

C:

答D:案：B

解析：根据连通图的概念，必须存在6个顶点至少经过一次的通路，最简单的通路就是6

个点用5条线连接而没有圈的情况，故选B。

13、【单选题】下列关于反函数的命题，正确的是（）。

单射函数有反函数

任意函数均有反函数

A:

满射函数有反函数

B:

双射函数有反函数

C:

答D:案：D

解析：根据反函数的定义，双射函数有反函数，双射函数的反函数也是双射函数，故选

D。

14、【单选题】一个6阶图，其各结点度数之和不可能为（）。

10

12

A:

15

B:

20

C:

答D:案：C

解析：根据欧拉握手定理，无向图的各结点度数之和等于边数的2倍，因此总度数不会是

奇数，故选C。

15、【单选题】在整数集合Z上定义*运算如下：a、b∈Z，a*b=a+b－10，则代数系统<Z,*>

是（）。

格

环

A:

域

B:

群

C:

答D:案：D

解析：根据运算规律a*b=a+b－10，可以看到具有单位元：由a*e=a推出e=10，同时具有

逆元：由a*a-1=e推出a-1=20-a，既有单位元又有逆元，恰为群的定义，故选D。

16、【问答题】设Σ={a,b}是字母表，Σ*表示由Σ上的字符构成的有限长度的串的集合

（包含长度为0的串，即空串在内），A={a,b,aa,bb,aaa,bbb}，

B={ω∣ω∈Σ*∧│ω│≥2}，C={ω∣ω∈Σ*∧│ω│≤2}，则A－(B∩C)=________。

答案：{a,b,aaa,bbb}

解析：根据题意，B∩C=｛所有长度为2的字符串｝=｛aa,bb,ab,ba｝，则A－(B∩C)=

{a,b,aaa,bbb}。

17、【问答题】在整数域中，命题公式

的真值为________，命题公式

的真值为________。

答案：T，F

解析：根据命题公式的意义，第一个公式表示对任意一个x存在一个y与之相乘为0，显

然在整数域中只要取y=0即可满足，因此是正确的；第二个公式表示存在一个x与任意一

个y相乘为1，显然在整数域是不可能实现的，因此是错误的。

18、【问答题】设A为非空有限集合，P(A)为A的幂集，∪为集合的并运算，群<P(A)，∪>

中，单位元是________，零元是________。

答案：

解析：

根据单位元定义，设任意集合则由即为单位

元；根据零元的定义，设任意集合即A为零元。

19、【问答题】一个手镯等距离地镶嵌着5颗彩珠，每颗彩珠可以从红、白、蓝、绿、黄5

种颜色中挑选。如果要求手镯上的彩珠颜色都不相同，则可以构成________种不同颜色彩珠

分布的手镯。

答案：120

解析：颜色集合由红、白、蓝、绿、黄5种颜色组成，根据排列组合知识可得5！=120。

20、【问答题】某连通平面图有6个顶点，其平面表示中共有8个面，则其边有________

条。

答案：12

解析：根据连通平面图的欧拉定理：顶点数－边数＋面数=2，可得边数=6+8-2=12。

21、【问答题】设有集合A={a,b,c,d}上的二元关系R={<a,b>,<b,a>,<c,c>,<

d,d>}，则R2=______，R3=______。

答案：{<a,a>,<b,b>,<c,c>,<d,d>}，{<a,b>,<b,a>,<c,c>,<d,d>}

解析：

于是R2={<a,a>,<b,b>,<c,c>,<d,d>}，R3={<a,b>,<b,a>,<

c,c>,<d,d>}

22、【问答题】为了从无向完全图K6中得到其生成树，至少需要删除_______条边

答案：10

解析：无向完全图K6共有边数为n(n-1)/2=15条，而有n个顶点的树有n－1条边，即有

6－1=5条边，所以至少要删除15－5=10条边。

23、【问答题】设有集合A={a,b,c}上的二元关系

则R1的自反闭包

r(R1)=_______，R1的对称闭包s(R1)=_______。

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

{<a,b>,<a,c>,<c,b>,<b,a>,<c,a>,<b,c>}

解析：

于是r(R1)={<a,b>,<a,c>,<c,b>,<a,a>,<b,b>,<c,c>}，

s(R1)={<a,b>,<a,c>,<c,b>,<b,a>,<c,a>,<b,c>}

24、【问答题】一个无向图有21条边，有3个4度结点，其余结点均为3度，则其结点共

有________个。

答案：13

解析：根据欧拉握手定理，无向图的各结点度数之和等于边数的2倍，设共有x个节点，

3*4+（x－3）*3=21*2，则x=13。

25、【问答题】设集合A={1,2,3}，集合B={a,b,c,d,e}，则│A×B│=________，而

│P(A)×B│=________。

答案：15，40

解析：│A│=3，│B│=5，所以│A×B│=3×5=15│P(A)│=2│A│=23=8，│B│=5，所

以│P(A)×B│=8×5=40

26、【问答题】用列真值表的方法说明下列逻辑等价式成立

答案：

解析：逻辑等价式必须具有相同的真值表，这是等价式的充分必要条件。

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

的主析取范式。

答案：

解析：利用等值式的运算规律与置换原则转换成主析取范式。

28、【问答题】设解释Ⅰ为：个体域D={a,b}，F(x)与G(x)为2个一元谓词，且

F(a)=0，F(b)=1，G(a)=1，G(b)=0。在Ⅰ下，求命题公式

的真值。

答案：

29、【问答题】设集合S={1,2,3}，题29图为S上的二元关系R的关系图

（1）写出R的集合表达

式；（2）写出R的关系矩阵。

答案：

解析：根据二元关系R的关系图的集合表达式方法与关系矩阵构造方法即得。

30、【问答题】求下述集合等式成立的充要条件，并证明结论

。

答案：

解析：根据集合的运算规律证明即可

31、【问答题】设n阶无向简单图G=<V,E>，其中边数满足：│E│>(n－1)(n－2)/2，证明

G是连通图。

答案：证明：假设G不是连通图，不妨设G有两个连通分支G1<V1,E1>和G2<V2,E2>，且

│V1│=n1，│V2│=n2，易见n1+n2=n，由于n1≥1，n2≥1，所以n1*n2-(n1+n2)+1≥0

（*）而│E1│≤n1(n1-1)/2,│E2│≤n2(n2-1)/2，从而│E│=│E1│+│E2│