离散数学试卷07-08(A)

合肥学院2007至2008学年第二学期

《离散数学》课程考试（ B ）卷

计算机 系 06 级 网络工程 专业 学号 姓名

题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 总 分

一、选择题：(每小题3分，共24分) 1、下面语句是真命题的是（ ）。

得分 A、我正在说谎。 B、如果1?1?2,则雪是黑色的。 C、如果1?1?3,则雪是黑色的。 D、吃饭了吗？

装订线 2、合式公式p?(q?p)是（ ）。

A、重言式 B、可满足式 C、矛盾式 D、等价式

3、设A????，B?P(P(A))，则以下不正确的式子是（ ）。 A、????,???B C、

B、??????B

??????B D、???????,????B4、设f是实数集R到R的函数，则f(x)为双射函数的是（ ）。

?1,??1,3 A、f(x)??x?0x?0 B、f(x)?lnx,x?0

3 C、f(x)?1(x?8),x??2 D、f(x)?x?8

5、设S?{0,1}，*为普通乘法，则?S,*?是（ ）。

A、半群，但不是独异点 B、只是独异点，但不是群

命题教师 共 页，第 页 C、群 D、环，但不是群 6、下图给出一个格L，则L是（ ）。

A、分配格 B、有补格 C、布尔格 D、A,B,C都不对 7、给定下列各序列，哪些可以构成无向简单图的度数序列（ ）。 （1）、（2，2，2，2，2） （2）、（1，1，2，2，3） （3）、（1，1，2，2，2） （4）、（0，1，3，3，3） （5）、（1，3，4，4，5）

A、（1）、（3）、（4） B、（1）、（2） C、（3）、（4）、（5） D、（1）、（3） 8、下列哪个是2元正则树（ ）。

二、填空题：（每题3分，共18分）

1、在公式?x(F(x)??yH(x,y))中，?x的辖域是_________________，?y的辖域是 _________________。

共 页，第 页 得分 2、公式?xF(x)???xG(x)的前束范式为________________________。

3、设R是集合A??1,2,?,10?上模3的同余关系，则[2]R=_________________。 4、代数系统?P(S),??的幺元为_________________，零元为_________________。

5、设一棵树有3个3度的结点，2个2度的结点，其余结点都是树叶，则有

_________________片树叶。 6、设有（a）、（b）两个有向图，从连通性判断图（a）是_________________图，图（b）

是_________________图。

装订线三、计算题：（第1-4题每题8分，第5、6每题6分，共44分）

得分 1、设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x2?x3)是布尔代数?{0,1},?,?,-?上的一个布尔表达式。试写出E(x1,x2,x3)的析取范式和合取范式。

共 页，第 页 2、设A?{1,2,3,4},A上二元关系R?{?1,1?,?2,3?,?2,4?,?3,2?,?3,4?}，求其自反闭包、对称闭包、传递闭包。

3、设A??1,2,3,5,6,9,15,27,36,45?上的整除关系

R??a1,a2a1,a2?A,a1整除a2?，

则(1)证明R为A上的偏序关系； (2)画出R的哈斯图； (3)求?2,9?的最小上界，最大下界。

共 页，第 页 4、对于正整数k，Nk?{0,1,2,?,k?1}，设*k是Nk的一个二元运算，使得a*kb?用k除a?b所得的余数，这里a,b?Nk。 (1)当k=4时，试造出*k的运算表；

(2)对于任意正整数k，证明?Nk,*k?是一个半群。

装订线

5、求下图D的邻接矩阵和可达矩阵，并找出v2到v4长度为2的通路。

共 页，第 页 6、求带权为2，3，5，7，8，9的最优2叉树，并计算它的权。

四、应用题：（第1题8分，第2题6分，共14分） 1、构造下面推理的证明（个体域：所有人的集合）：

2、设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英语、汉语；c会讲英、俄语；d会讲日、汉语；e会讲德语、俄语；f会讲法语、日语；g会讲法语、德语。试用图论的方法安排圆桌座位，使每人都能与其身边的人交谈。

共 页，第 页 得分 所有主持人都很有风度，李明是个学生且是个节目主持人。因此，有些学生很有风度。

本文来源：https://www.bwwdw.com/article/jsp2.html