2013年9月份考试离散数学第二次作业

2013年9月份考试离散数学第二次作业

一、单项选择题（本大题共40分，共 20 小题，每小题 2 分）

1. 设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是（） A. 自反、对称、传递的 B. 自反、对称、反对称的 C. 对称、反对称、传递的 D. 只有对称性

2. 在下列命题中，为真的命题是（）

A. 汉密顿图一定是欧拉图

B. 无向完全图都是欧拉图

C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出

D. 有割点的连通图是汉密顿图

3. 设P：我去踢球，Q：明天下雨，命题“如果我踢球，当且仅当明天不下雨”的符号化表示为（）。

A. P→Q

B. Q→P

C.

D. P Q

4. 设A为一集合，（P(A),）为有补格，P(A)中每个元素的补元（）。

A. 存在且唯一

B. 不存在

C. 存在且不唯一

D. 可能存在

5. 下图哪个能一笔画？（）

A.

B.

C.

D.

6. 若X是Y的子集，则一定有（）。 A. X不属于Y B. X∈Y C. X真包含于Y D. X∩Y=X

7. 若集合A的基数|A|=10，则其幂集的基数为（）

A. 1024

B. 100

C. 20

D. 12

8. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）

A. 2是偶数或-3不是负数

B. 2是奇数或-3不是负数

C. 2不是偶数且-3不是负数

D. 2是奇数且-3不是负数

9. 对于下面某个偏序集的哈斯图，其中集合{a,b,c,e}的最大元是（）

A. c

B.

d

C.

e

D.

无

10. 设G是n个顶点的无向简单图，则下列说法不正确的是（）。 A. 若G是

树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇数度顶点 D. 若G中任意一对顶点的度数之和大于等于n-1,则G中有汉密顿路

11. 在谓词演算中，P(a)是∀xP(x)的有效结论，其理论根据是（）。

A. 全称指定规则（US）

B. 全称推广规则（UG）

C. 存在指定规则（ES）

D. 存在推广规则（EG）

12. 设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数（）

A. 7

B. 8

C. 9

D. 14

13. 函数的复合满足（）

A. 交换律

B. 结合律

C. 幂等律

D. 分配律

14. 以下叙述正确的是（）

A. 代数系统能构成半群，其中运算o定义为：aob=|a-b|。

B. 对于自然数集合，运算a*b=min{a,b}是可结合的。

C. 代数系统是半群，其中运算“-“表示普通的减法运算。

D. 以上的叙述均不对。

15. 以下叙述正确的是（）

A. {b, c, a, aa, ac, abb}是前缀码。

B. 在有界格中，若有一个元素有补元，则补元必唯一。

C. 在有向图中，结点间的可达关系是等价关系。

D. 连通图的最小生成树不一定是唯一的。

16. 以下叙述正确的是：（）。

A. 的幂集没有任何元素。

B. 整数集上关于加法运算的幺元是0。

C. 整数集上的任何元素x关于乘法运算均有逆元1/x。

D. 整数集上的关于乘法运算的幺元是0。

17. 命题公式P→ Q∧ R的对偶式为？（）

A. P →（ Q ∨R ）

B. P ∧（ Q ∨R ）

C. ⎤P ∨（ Q ∧R ）

D. ⎤ P∧（Q∨ R）

18. Q∧ (P∨⎤ Q) 主合取范式为（）

A. ⎤P ∨Q

B. P ∧⎤Q

C. (P ∨Q) ∧(P ∨⎤Q) ∧( ⎤P ∨Q)

D. (P∧ Q)∨ (P∧⎤ Q)∨ (⎤ P∧ Q)

19. 设Z+为正整数集合，S为正偶数集合，则与格（其中|表示整除关系）的关系为（）。

A. 自同构

B. 同构

C. 自同态

D. 非同构

20. 设G=为无环的无向图，|V|=6,|E|=16,则G是（）

A. 完全图

B. 零图

C. 简单图

D. 多重图

二、多项选择题（本大题共30分，共 10 小题，每小题 3 分）

1. 相容关系需要满足的特性为：（）

A. 对称性

B. 传递性

C. 自反性

D. 反对称性

2. 以下关系中哪些是A B的函数，其中A={a,b,c} B={1,2,3}( )

A. {,,}

B. {,,}

C. {,,}

D. {,,

3. 在下列命题中，为真的命题是（）

A. 具有6个结点的无向完全图共有15条边。

B. 无向完全图都是欧拉图。

C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出。

D. 有割点的连通图是汉密顿图。

4. 以下叙述正确的是（）。 A. 若A＝{φ,1,2}，则A的幂集有8个元素 B. 朋友关系是等价关系 C. 具有5个顶点的完全图，需要删去6条边才能得到树

D. 集合B = {{a},3,4,1}，E为全集，则φ{{a}}B E

5. 设Z是整数集合，+是一般加法，则下述函数中哪些是群（Z，+）的自同态？（）

A. f(x)=2x

B. f(x)=1000x

C. f(x)=|x|

D. f(x)=0

6. 以下表达方式正确的是：（）

A. 小明打开箱子并拿出一件衣服。

设P：小明打开箱子； Q：小明拿出一件衣服。原命题表示为：P Q

B. 如果骑自行车，我就没法按时到校。

设P：我骑自行车； Q：我按时到校；原命题可表示为：P→Q