【离散试卷】2010-2011-1

1上海海事大学试卷2010—2011学年第一学期期末考试《离散数学》（A卷）班级学号姓名总分1.(5’)CAeCAdBADAcAbZxxxxxDZnnxxCZnnxxBZnnxxA)()()()()()(BA(a)Z}.,0)86(|{},,4|{},,12|{},,2|{2：为全集，计算下列格式以设2.(6’)在150位学生中，有109位同学在PASCAL,BASIC,C++中至少学习一门。假设45人学BASIC，61人学PASCAL，53人学C++，18人学BASIC和PASCAL，15人学BASIC和C++，23人学PASCAL和C++。(a)多少人三门语言都学？(b)多少人只学BASIC?(c)多少人一门都不学？3.(5’)已知前提为：))()(()),()()((xQxCxxRxWxCx结论为：))()((xRxQx给出逻辑推理的过程。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’)设}0|{},1|{xRxTxRxS定义f:S→T如下：Sxxxf,1)((a)证明f是单射的。(b)证明f是满射的。(c)f有反函数吗？若有的话，求出反函数。题目得分阅卷人2(d)写出ff的表达式和他的定义域和值域。(e)ff是单射的吗？说明原因。6.(5’)设A={a,b,c,d}且A上的关系R的矩阵如下1000110011101101M(a)证明R是偏序关系。(b)画出R的哈斯图。7.(6’)设D105代表正整数105的所有正约数的集合上由整除关系构成的格。(a)画出此格的哈斯图。(b)写出每个元素的补元素(c)此格是否布尔代数？写出它的原子集合。8.(6’)布尔函数的真值表如下：xyzf(x,y,z)00000010010101101001101111011110写出f对应的析取范式并尽量化简。9.(5’)完成下表使得二元运算满足交换律和幂等率。*abcacbcb10.(5’)设G是一个群，幺元是e.证明若G中存在x使得x2=x，则x=e.11.(5’)设f是G1到G2的满同态，G2是阿贝尔群。证明ker(f)包含了G1中所有形式为11baba的元素，其中a,b是G1中的任意元素。12.(6’)设S={1,-1,i,-i},且G=(S,普通复数乘法)(a)证明H={1，-1}是G的子群。(b)确定H的所有左陪集。(c)证明G和Z4同构313.(6’)有8个元素的群G的乘法表如下：eijkmnopeeijkmnopiijkepomnjjkeinmpokkeijopnmmmonpejiknnpmojekioonpmkiejppmonikje(a)写出G中阶数是2的元素。(b)写出G中具有4个元素的子循环群及其生成元。(c)写出一个G中具有4个元素的非循环子群。(d)列出G的所有3阶子群。如果没有的话说明理由。14.(6’)已知简单有向图G=V,E如下图所示：(a)用矩阵运算的方法找出所有长度为2的路。(b)用Warshall方法求出可达矩阵，再根据可达矩阵求图G的强分图。15.(6’)一个艺术展览安排在如下图所示的5个房间中（图中已标注）。是否有一条路恰好经过每个门一次看完展览？如果有的话，在下图上描出路径。16.(5’)画出K5中的没有公共边的两个汉密尔顿回路，12345v1v5v3v2v4417.(6’)一颗根树(T,v0)如下图所示：(a)T的高度是多少？(b)列出T的树叶。(c)包含v4的子树有多少？(d)列出v7的兄弟节点。(e)把T转化成二叉树。18.(5’)用Kruskal算法求出下图的最小生成树。按照选择次序列出生成树的各条边。ACEDGBF465442334752v0v1v3v2v4v5v10v6v7v8v9