离散数学2017年4月考试真题(02324)

有向图D如图所示。

(1)求2到5的长度为2的通路数;

(2)求5到5的长度为4的回路数;

(3)求D中长度为4的通路数;

(4)求D中长度为4的回路数。

今有a，b，c，d，e，f共6人，已知下列事实：a会讲德语、英语、法语和汉语;b会讲德语、朝鲜语和意大利语;c会讲俄语、意大利语、西班牙语和葡萄牙语;d会讲俄语、日语和法语;e会讲葡萄牙语、日语和英语;f会讲汉语、朝鲜语和西班牙语。试问这6个人应如何排座位，才能使每个人和他身边的人用同种语言交流?列出所有可能的排座方案。

设图G有n个结点，n+1条边。证明：图G中至少有一个结点度数≥3。

下面是某偏序集的哈斯图

写出集合A和偏序关系R的表达式。

设R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}是集合A={1，2，3，4}上的二元关系。(1)画出R的关系图;

(2)写出R的关系矩阵;

(3)说明R是否具有自反、反自反、对称、反对称性质。

下题24图的格中，b的补元是_______，c的补元是_______。

求1000以内既不能被5或6整除，也不能被8整除的正整数有多少个。

一颗n阶(n>2)无向树T，其最大度数△(T)的最小值为_______，△(T)的最大值为_______。

一个简单无向连通图，有n个结点，m条边，则边数m的最大值为_______，边数m的最小值为_______。

实数集R中的运算 * 定义如下：a*b=a+b-5ab，则*运算的单位元为_______; * 运算的零元为_______。

集合A={1，2，3}上的划分共有_______种，其中划分S={{1}，{2，3}}中有序对的个数为_______。

完全图K₄是平面图，其面数r为_____，记结点数为n，边数为m，则n-m+r=______。

设R={<1,4>,<3,5>,<2,5>} 和S={<4,2>,<5,1>,<2,3>} 是集合A={1，2，3，4，5}上的两个关系，则R。S=_______，S。R=_______。

下列关于欧拉图的描述正确的是()

• A.K₄是欧拉图
• B.K₅是欧拉图
• C.完全图都是欧拉图
• D.K₆是欧拉图

设X={1，2，3，6}，D是X上的整除运算，下列关于代数系统的描述正确的是()

• A.格
• B.群
• C.半群
• D.二元关系

设R₁、R₂是A上的两个二元关系，则下列描述不正确的是()

• A.
• B.
• C.
• D.

一颗无向树有5片树叶，有3个2度结点，其余都是3度结点，那么这颗树得结点数是()

• A.10
• B.11
• C.12
• D.13

设f：X→Y,g：Y→Z都是双射函数，则下列性质不正确的是()

• A.(f。g)^-1=f^-1。g^-1
• B.f^-1。f=I_Y
• C.(f^-1)^-1=f
• D.f。f^-1=I_X

下列的度数列，可以简单图化的是()

• A.5，5，4，4，2，1
• B.5，4，3，2，2
• C.3，3，3，1
• D.4，4，3，3，2，2

对任意集合A、B，关于其幂集的下列叙述不正确的是()

• A.
• B.
• C.
• D.

下列一阶逻辑等效变换不正确的是()

• A.
• B.
• C.
• D.

在整数集Z上，下列定义的运算 * 能构成一个群的是()

• A.a*b=a+b-2
• B.a*b=a-b
• C.a*b=min{a，b}
• D.a*b=ab

关于笛卡尔积，下列陈述不正确的是()

• A.A×(B∪C)=(A×B)∪(A×C)
• B.A×(B ∩ C)=(A×B)∩(A×C)
• C.P(A)×P(A)=P(A×A)
• D.(A∪B)×C=(A×C)∪(B×C)

设A-B=A，则有()

• A.
• B.
• C.
• D.

命题公式A中含n个命题变项，A为矛盾式的条件是A的主合取范式含()

• A.2ⁿ个极大项
• B.1个极大项
• C.2ⁿ个极小项
• D.1个极小项

下列关于整数集合上的整除关系描述不正确的是()

• A.自反的
• B.对称的
• C.反对称的
• D.传递的

设F(x)：x是在美国的留学生，G(y)：y是亚洲人。命题“并不是所有在美国的留学生都是亚洲人”可符号化为()

• A.
• B.
• C.
• D.

下列命题公式为重言式的是()

• A.(P→Q)∧ Q ∧ R
• B.(P→￢P)→￢Q
• C.￢(Q→R)∧ R
• D.(P→Q)∧(Q→R)→(P→R)