资源描述：
《离散数学期末考试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、--------------------------------------------------------------------------------------装订线------------------------------------------------------------------------------------上海海事大学试卷2010—2011学年第一学期期末考试《离散数学》（A卷）班级学号姓名总分题目得分阅卷人1.(5’)2.(6’)在150位学生中，有109位同学在PASCAL,BASIC,C++中至少学习一门
2、。假设45人学BASIC，61人学PASCAL，53人学C++，18人学BASIC和PASCAL，15人学BASIC和C++，23人学PASCAL和C++。(a)多少人三门语言都学？(b)多少人只学BASIC?(c)多少人一门都不学？3.(5’)已知前提为：结论为：给出逻辑推理的过程。4.(6’)设B={1,2,3,4,5}，A=B×B,定义A上的关系R如下：(u,v)R(x,y)当且仅当u-v=x-y.(a)证明R是等价关系。(b)找出[(2,3)].（c）计算A/R.5.(6’)设定义f:S→T如下：(a)证明f是单射的。(b)证明f是满射的。
3、(c)f有反函数吗？若有的话，求出反函数。8(a)写出的表达式和他的定义域和值域。(b)是单射的吗？说明原因。6.(5’)设A={a,b,c,d}且A上的关系R的矩阵如下(a)证明R是偏序关系。(b)画出R的哈斯图。7.(6’)设D105代表正整数105的所有正约数的集合上由整除关系构成的格。(a)画出此格的哈斯图。(b)写出每个元素的补元素(c)此格是否布尔代数？写出它的原子集合。8.(6’)布尔函数的真值表如下：xyzf(x,y,z)00000010010101101001101111011110写出f对应的析取范式并尽量化简。9.(5’)完成
4、下表使得二元运算满足交换律和幂等率。*abcacbcb10.(5’)设G是一个群，幺元是e.证明若G中存在x使得x2=x，则x=e.11.(5’)设f是G1到G2的满同态，G2是阿贝尔群。证明ker(f)包含了G1中所有形式为的元素，其中a,b是G1中的任意元素。12.(6’)设S={1,-1,i,-i},且G=(S,普通复数乘法)(a)证明H={1，-1}是G的子群。(b)确定H的所有左陪集。(c)证明G和Z4同构813.(6’)有8个元素的群G的乘法表如下：eijkmnopeeijkmnopiijkepomnjjkeinmpokkeijopnm
5、mmonpejiknnpmojekioonpmkiejppmonikje(a)写出G中阶数是2的元素。(b)写出G中具有4个元素的子循环群及其生成元。(c)写出一个G中具有4个元素的非循环子群。(d)列出G的所有3阶子群。如果没有的话说明理由。14.(6’)已知简单有向图G=如下图所示：v1v5v3v2v4(a)用矩阵运算的方法找出所有长度为2的路。(b)用Warshall方法求出可达矩阵，再根据可达矩阵求图G的强分图。15.(6’)一个艺术展览安排在如下图所示的5个房间中（图中已标注）。是否有一条路恰好经过每个门一次看完展览？如果有的话
6、，在下图上描出路径。1234516.(5’)画出K5中的没有公共边的两个汉密尔顿回路，817.(6’)一颗根树(T,v0)如下图所示：v0v1v3v2v4v5v10v6v7v8v9(a)T的高度是多少？(b)列出T的树叶。(c)包含v4的子树有多少？(d)列出v7的兄弟节点。(e)把T转化成二叉树。18.(5’)用Kruskal算法求出下图的最小生成树。按照选择次序列出生成树的各条边。ACEDGBF4654423347528参考答案1.(a){1,2,3,4,…}.(b){…,-3,-2,-1,0}∪B.(c){2,4}(d){A}(e)(2,6,
7、10,14,…)2(a)6.(b)18.(c)41.3.4.(a)∵u-v=u-v,∴(u,v)R(u,v),即R是自反的。如果(u,v)R(x,y),则u-v=x-y,即x-y=u-v,故(x,y)R(u,v),所以R是对称的。如果(u,v)R(x,y)且(x,y)R(w,z),则u-v=x-y=w-z,故(u,v)R(w,z),所以R是传递的。(b)[(2,3)]={(2,3),(1,2),(3,4),(4,5)}.(c)A/R={[(2,3)],[(2,4)],[(2,5)],[(2,2)],[(2,1)],[(3,1)],[(4,1)],[
8、(5,1)],[(1,5)]}【注：代表元素不必相同，但须写够9个等价类】5.(a)设f(x1)=f(x2),则，∴x1+
