2008《离散数学（2）》期末考试卷.docVIP

A

班号学号姓名成绩

《离散数学（2）》期末考试卷

注意事项：1、请大家仔细审题

2、千万不能违反考场纪律

题目：

一、判断题（每小题2分，共20分）

（）1.若A?B=A?C，则B=C。

（）2.若AíC且BíC，则A∪BíC。

（）3.设A、B为任意两个集合，则ρ(A)?ρ(B)=ρ(A?B)。

（）4.设R为集合A上的等价关系，则R2也为A上的等价关系。

（）5.若R是集合A上的二元关系，则str(R)是A上的等价关系。

（）6.设Q+为正有理数集合，则Q+，?是良序结构。

（）7.设N为自然数集合，则N?N与N?N?N等势。

（）8.设f：X→Y和g：Y→Z，若gof是满射，则f是满射。

（）9.若G中任意结点v的度数dG(v)?2，则G中必存在回路。

（）10.n阶二叉树有(n?1)/2个分支结点。

二、设A={a，b，c，d}上的二元关系和定义如下：（20分）

={a,b,a,d,c,b,c,d}

R2={a,b,b,a,b,c,c,d,d,ad,c}

1）试分别指出和所具有的性质（即是否具有自反性、反自反性、对称性、反对称性和传递性这五种性质）。

2）试求出R12，和R2+。

三、设集合A上的二元关系R是自反的。证明：（10分）

R为等价关系的充要条件是：若a,b,a,c?R，则b,c?R。

四、任给52个整数，证明其中必有两数之和或两数之差能被100整除。（12分）

五、试求叶的权分别为1，4，9，16，25，36，49的最优叶加权二叉树及其叶加权

路径长度。（12分）

六、设n阶连通无向图G为非循环的，直接用归纳法证明：G有n–1条边。（10分）

七、设R为集合A上的二元关系，证明t(R)=R+。（8分）

其中，t(R)为R的传递闭包，R+=。

八、设函数f:X→Y且g:Y→X，若令（8分）

A={a?X?g(f(a))=a}且B={b?Y?f(g(b))=b}

则f[A]=B。