2008《离散数学》考试试卷（A卷）

海南大学2008-2009学年度第1学期试卷

科目：《离散数学》试题(A卷)

姓名： 学 号： 学院： 信息科学技术学院 专业班级： 07级计算机

成绩登记表（由阅卷教师用红色笔填写） 大题号 得分

一 二 三 四 五 六 七 八 九 十 总分 阅卷教师： 200 年 月 日

考试说明：本课程为闭卷考试，可携带 计算器 。

得分 阅卷教师 一、选择题：（每题2分，共20分）在以下各小题中画有（）处填上答案。

1. 下述哪一个不是命题？（ ）。

A.在整数集中不存在最大奇数； B.海口是海南省的省会； C.若我有空，我就运动； D.x+8=10。 2. 命题?x?y(x2?y2?1)的意义是（ ）。

A.对任何x均存在y使得x2+y2=1； B.对任何y均存在x使得x2+y2=1； C.存在y对任何x均使得x2+y2=1； D.存在x对任何y均使得x2+y2=1； 3. 设S={1, 2, 3, 4, 5}，则下列集合中是S的真子集的是（ ）。

A.{1, 2, 3, 4} B.{x | x是整数且x2≤25} C.{x | x是正整数且x≤5} D.{x | x是有理数且x≤5}

4. 设A={a,b,c}，B={1,2,3}，以下哪一个关系是从A到B的一一对应函数？（ ）

1

A. f={,,} B. f={,,} C. f={,,,} D. f={,} 5. 图1哈斯图所示的偏序集为格的是（ ）。

6. 设有无向图如图2，则（ ）是一条哈密顿回路。

A．gabcdefg B．abcdefg C．cfabcdeg D．efgabcd

7. 哪个顶点可成为图3的割点？（ ）

A. a B. b C. c D. d

8. 图4中（ ）是欧拉图。

9. 下列（）是满2元树。

2

10．图6中（ ）是平面图。

得分 阅卷教师 二、填空题：（每空2分，共20分）在以下各小题中画有_______处填上答案。

11. 具有唯一________的陈述句称作命题。 12.令P、Q为如下命题：

P:气温在0度以下。Q:正在下雪。用P、Q和逻辑联结符写出下列命题：也许气温在0度以下，也许在下雪，同时如果在0度以下，就不在下雪_______________。

13. 设S(x):x是学生；L(x):x喜欢英语。则命题“有些学生喜欢英语”的符号化为：________。 14. 设B={ {φ},φ}，则B的幂集P(B)= ____________。 15. 设A={1,2},B={2,3},C={a,b,c}，则|(A∪B)×C|=______。

16．计算机1班的32名学生中，有10人在第一次考试中得A，11人在第2次考试中得A，已知有

19人两次考试均未得A，则两次考试都得A的学生人数为_____人。

17. 给定A={1,2,3,4}，A上的关系R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}满足的性质是_________________。

18. 设A={a,b,c}，F是A上的二元关系，F={,,}，则其自反闭包为r(F)= ______________。

19. 设A和B是有穷集合，|A|=m，|B|=n，A到B有_______多少个不同一对一映射。 20．完全偶图Km,n的边数是_______。 得分 阅卷教师 三 、综合题（60分）

21. 从音乐排行榜前10张不同光碟，选3张，有多少种选法？如果排列第一名的光碟至少选1

张，总共选3张，有多少种选法？

22. 求解下述递推关系an=7an-1-12an-2，a0?0,a1?1

23. 使用Warshall算法求解在集合{1，2，3，4}上的关系{(1,2), (2,1), (2,3), (3,4), (4,1)}

的传递闭包。

24. 对偏序集（{2，4，5，10，12，20，25}，|）上的整除关系，画出哈斯图并回答下列问

3

题：

（1）求极大、极小元素； （2）求最大、最小元素；

（3）找出{2，5}的所有上界，如果存在的话求出最小上界； （3）找出{12，10}的所有下界，如果存在的话求出最大下界。

25. 在整数集合Z上代数系统（Z，*），定义：a*b?a?b?2ab,a,b?Z 其中右边是一般的整数加、减乘法运算。判断： （1）是否满足交换律、结合律。

（2）指出零元、幺元和每个元素的逆元。 （3）该代数系统是否为群？为什么？

26.证明(P(S),?,?,?)是布尔代数。其中P(S)是集合S的幂集。

4