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. PQ

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}}BE

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

A. f(x)=2x

B. f(x)=1000x

C. f(x)=|x|

D. f(x)=0

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

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

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

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

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

C. 我打开门，走了进来。

设M：我打开门； N：我走进来。 原命题为：M→N

D. 小红和小华是好朋友。 

设H：小红是好朋友； J：小华是好朋友；原命题为：HJ

7. 设偏序集<,≤> 的哈斯图如下所示，若A的子集B = {2,3,4},则元素为B的极大元为( )。

 A. 5 B. 6 C. 3 D. 4

8. 对于下列各式，是永真式的有（ ）。

A. (P∧(P→Q))→Q

B. P→(P∨Q)

C. Q→(P∧Q)

D. ((P∧(P(Q))→Q

E. (P→Q)→Q

9. 设集合A={1,2,3,…10}，下面定义的哪种运算关于集合A是封闭的（ ）

A. x*y=max{x,y}

B. x*y=min{x,y}

C. x*y=GCD(x,y) 即x,y的最大公约数

D. x*y=LCM(x,y) 即x,y的最小公倍数

10. 设T是一棵具有n个结点m条边（n2）的树，则T（ ）。 A. 连通 B. 包含有环 C. m=n-1 D. 至少有两个度为1的结点

三、判断题（本大题共30分，共 10 小题，每小题 3 分）

1. {1，01，001，000}是前缀码。（ ）

2. 若f：NN, f(x)=x2+2，则f是满射函数。（ ）

3. 能一笔画出的图一定是欧拉图。（ ）

4. 为矛盾式。（ ）

5. 交换群必是循环群。（ ）

6. 任何图中必有偶数个度数为奇数的结点。（ ）

7. 设S={0,1},S是关于普通的加法和乘法运算，则S上的加法与乘法运算满足封闭性、结合性。（ ）

8. 为重言式。（ ）

9. 设是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在幺元e和零元，则e。（ ）

10. 设e为无向连通图G中的一条边，e在G的任何生成树中，则e是桥。（ ）

答案：

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

1. C 2. C 3. C 4. A 5. D 6. D 7. A 8. C 9. D 10. B 11. A 12. B 13. B 14. B 15. D 16. B 17. D 18. C 19. B 20. D 

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

1. AC 2. BC 3. AC 4. ACD 5. ABD 6. BC 7. CD 8. ABD 9. ABC 10. ACD 

三、判断题（30分，共 10 题，每小题 3 分）

1. √ 2. × 3. × 4. √ 5. × 6. √ 7. × 8. √ 9. √ 10. √