北邮离散数学期末复习题

文档北邮离散数学期末复习题第一章集合论一、判断题（1）空集是任何集合的真子集．（错）（2）是空集．（错）a{a},a（（3）对）A1,2,1,2,则1,22A.（4）设集合(对）aAaBaAB，则或．（5）如果（错）解aAB则aABAB，即aA且aB，所以且aAaB（6）如果A∪BB,则AB.（对）A{a,a,a}，B{b,b,b}，则（7）设集合123123AB{a,b,a,b,a,b}（错）112233（8）设集合A{0,1}，则{,0,,1,{0},0,{0},1}是2A到A的关系．（对）2{,{0},{1},A}，解A2AA{,0,,1,{0},0,{0},1,{1},0,{1},1,A,0,A,1}（9）关系的复合运算满足交换律．（错）是集合A上的关系具有传递性的充分必要条件.（10）（错）~是集合A上的传递关系,则也是A上的传递关系.（11）设(对)（12）集合A上的对称关系必不是反对称的12.（错）,（13）设为集合A上的等价关系,则也是集合A上的等价关系(对)12（14）设是集合时，A上的等价关系,则当a,b[a][b](对),（15）设为集合A上的等价关系,则(错)12二、单项选择题（1）设R为实数集合，下列集合中哪一个不是空集（A）|210,且x|x90,且xRA.xxxRB．2|1,且C.xxxxRD.x|x21,且xR文档A\B,AB为集合，若，则一定有（C）（2）设A.BB．BC.ABD.AB（3）下列各式中不正确的是（C）A.B．C.,{}D.Aa,{a}，则下列各式中错误的是（（4）设B）2A.aAB．a2AC.{a}2AD.{a}2AA1,2，Ba,b,c，Cc,d，则A(BC)为（B）（5）设c,1,2,cB．1,c,2,cA.C.1,c,c,2D.c,1,c,2A0,B1,b,3b，，则的恒等关系为AB（6）设（A）0,0,1,1,b,b,3,3B．0,0,1,1,3,3A.C.0,0,b,b,3,3D.0,1,1,b,b,3,3,0,,Aabc上的二元关系如下，则（7）设具有传递性的为（D）a,c,c,a,a,b,b,aA.B．C.D.123a,c,c,aa,b,c,c,b,a,b,ca,a4（8）设为集合A上的等价关系，对任意aA，其等价类a为（B）A.空集；B．非空集；C.是否为空集不能确定；D.{x|xA}.（9）映射的复合运算满足（B）A.交换律B．结合律C.幂等律D.分配律（10）设A，B是集合，则下列说法中（C）是正确的.A．A到B的关系都是A到B的映射B．A到B的映射都是可逆的C．A到B的双射都是可逆的D．AB时必不存在A到B的双射文档（11）设A是集合，则（B）成立.#22#AA．AX2AXAB．2C．AA2D．A#An（12）设A是有限集（），则A上既是又是～的关系共有（B）.A．0个B．1个C．2个nD．个三、填空题1.设A{1,2,{1,2}}2____________.，则A2{,{1},{2},{{1,2}},{1,2},{1,{1,2}},{2,{1,2}},A}填AA{,{}}22.设，则2{,{},{{}},A}A=.填AA,B#A5#B73.设集合中元素的个数分别为，，且#(AB)9，AB#(AB).3则集合中元素的个数4.设集合A{x|1x100,x是4的倍数，xZ}，B{x|1x100,x是5的倍数，xZ}AB，则中元素的个数为.40A{a,b}2A上的包含于关系，,则有5.设,是=.{,,,{a},,{b},,A,{a},{a},{a},A,{b},{b},{b},A,A,A}~~21,6.设为集合上的二元关系,则.A12127.集合上的二元关系为传递的充分必要条件是A．A到集合A0,1,2上的关系0,2,2,0B0,2,4的关8.设集合及集合1系｛|12a,ba,bAB且a,bA∩B,则___________________.2填{0,0,0,2,2,0,2,2}四、解答题1.设A{a,b,c,d},A上的关系{a,a,b,b,c,c,d,d,a,b,b,a,c,d,d,c}（1）写出的关系矩阵；A（2）验证是上的等价关系；A（3）求出的各元素的等价类。文档解（1）的关系矩阵为11001100M00110011（2）从的关系矩阵可知：是自反的和对称的。又由于110011001100110011001100MM001100110011M001100110011或满足所以是传递的。、对称的和传递的，所以是因为是自反的A上的等价关系。（3）[a][b]{a,b}，[c][d]{c,d}2.设集合A{1,2,3,6,8,12,24,36}，是A上的整除关系，（1）写出的关系矩阵M；A,的哈斯图；画出偏序集（2）（3）求出A的子集B{2,3,6}的最小上界和11111111最大下界。010111110011011100010111M解：（1）00001010000001110000001000000001（2）文档（3）lubB=6,glbB=1五、证明题1.设,为集合A上的等价关系,试证也是集合A上的等价关系。1证明：由于a,a若a,b以b,a,b,a,从而b,a2,1是自反的，所以对任意aA,2a,aa,a,,因而2，即是自反的。11212122，即,由于,是对称的，所a,b,a,b，则12112是对称的。121212a,b,b,c若a,b,b,c,a,b,b,c，则12,由于1,是传递的，所以21，即2是传递的。a,c,a,c,从而a,c121是自反的、对称的和传递的，所以21是等价关系。2由于1212第二章代数系统一、判断题（1）集合A上的任一运算对A是封闭的．（对）（2）代数系统的零元是可逆元.（错）（3）设A是集合，:AAA，abb，则是可结合的．（对）（4）设a,b是代数系统A,的元素，如果abbae(e是该代数系统的单位元），则1b.a(对)（5）设a,b是群G,的元素,则(ab)1a1b1.（6）设G,是群．如果对于任意a,bG，有(ab)2a2b2，则G,是阿贝尔（错）群．（对）（7）设L,,是格,则运算满足幂等律.（对）（8）设集合A{a,b}，则{,{a},{b},A},,是格．（对）（9）设B,,,是布尔代数，则B,,是格．（对）文档二、单项选择题（1）在整数集Z上，下列哪种运算是可结合的（B）A.ababB．abmax{a,b}C.aba2bD.ab|ab|（2）下列定义的实数集R上的运算*中可结合的是.（C）A．abaabB．aba2abC．abbD．abab其中，+，·，︱︱分别为实数的加法、乘法和取绝对值运算.A1,2,3,4,,10，下（3）设集合面定义的哪种运算关于集合A不是封闭的（D）A.xymax{x,y}B．xymin{x,y}C.xyGCD{x,y}，即x,y的最大公约数D.xyLCM{x,y}，即x,y的最小公倍数（4）下列哪个集关于减法运算是封闭的（B）A.N（自然数集）；B．{2x|xZ(整数集)}；C.{2x1|xZ}；D.{x|x是质数}.abababQ,的单位元，则（5）设Q是有理数集，在Q定义运算为为（D）A.a；B．b；C.1；D.0（6）设代数系统A，·，则下面结论成立的是.（C）A．如果A，·是群，则A，·是阿贝尔群B．如果A，·是阿贝尔群，则A，·是循环群C．如果A，·是循环群，则A，·是阿贝尔群D．如果A，·是阿贝尔群，则A，·必不是循环群（7）循环群Z,的所有生成元为（D）A.1，0B．-1，2C.1，2D.1，-1三、填空题文档2,1.设A为非空有限集，代数系统2中，对运算的单位元为，零元AA为.填,AZ,xI+为普通加法），对任意的，其2.代数系统中（其中为整数集合，Zx1.填x2Z,b，则的单位元为.3.在整数集合Z上定义运算为aba解设单位元为e，aea2又a(2)a2(2)a,(2)a(2)2aa，所以单位元为ea，所以，e2e2Z上定义运算为ababab，则Z,的单位元为.e，aeaeaea，(1a)e0G,是群，对任意,,abcG，如果4.在整数集合e0，所以解设单位元为abac,，则bc.填5.设G,是群，G元素e为单位元，若a满足eaa，则a.填26.设四、解答题1.设为实数集R上的二元运算，其定义为:R2R,abab2ab，对于任意a,bR求运算的单位元和零元。aR，有aeae2aea，解：设单位元为e，则对任意即e(12a)0，由a的任意性知e0，aR，a0a00a；0a0a0a又对任意所以单位元为0设零元为，则对任意，aR，有aa2a1a(12)0，由a的任意性知即211，22又对任意aR，a()a1a1()a1aa122221所以零元为2I{0,1,2,3,4}上的二元运算，其定义为2.设为集合5:I2I,ab(ab)mod5，对a,bI于任意555写出运算的运算表；（1）（2）说明运算是否满足交换律、结合律，是否有单位元和零元、如果有请指出；（3）写出所有解：（表为可逆元的逆元1）运算文档01234012303142400000000123424134321（2）运算满足交换律、结合律，有单位元，单位元为1，有零元，零元为0；（3）1的逆元为1，2的逆元为3，3的逆元为2，4的逆元4，0没有逆元五、证明题1.设G,是一个群，试证是交换a,bG,有G群当且仅当对任意的a2b2(ab)2.证明：充分性若在群G,中，对任意的a,bG,有a2b2(ab)2.则(aa)(bb)(ab)(ab)a(ab)ba(ba)babba从而G,是一个交换群。必要性若G,群，对任意的a,bG,有abba，则是一个交换a(ab)ba(ba)b(aa)(bb)(ab)(ab)即a2b2(ab)2.2.证明代数系统Z,是群，其中二元运算定义如下：：Z2Z，xyxy3（这里，+，－分别是整数的加法与减法运算.）证明（1）运算满足交换律对任意x,y,zZ，由(xy)z(xy3)zxyz6,x(yz)x(yz3)xyz6得(xy)zx(yz),即满足结合律；（2）有单位元3是单位元；（3）任意元素有逆元对任意xZ，x16x.所以,Z，是群.文档第三章图论一、判断题（1）n阶完全图的任意两个不同结点的距离都为1.（对）G的两个不同结点v,v连接时一定邻接.（2）图（错）（错）ijv,v的初级通路为v,v之间的短程.G中连接结点i（3）图jij（4）在有向图中，结点v到结点v的有向短程即为v到v的有向短程．jiji（错）（5）强连通有向图一定是单向连通的．（对）（6）不论无向图或有向图，初级回路一定是简单回路．（对）（7）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的．（对）（8）有生成树的无向图是连通的．（对）（9）下图所示的图是欧拉图.（错）（10）下图所示的图有哈密尔顿回路.（对）二、单项选择题（1）仅由孤立点组成的图称为（A）A.零图；B．平凡图；C.完全图；D.多重图.（2）仅由一个孤立点组成的图称为（B）A.零图；B．平凡图；C.多重图；D.子图.（3）在任何图G中必有偶数个（B）A.度数为偶数的结点；B．度数为奇数的结点；C.入度为奇数的结点；D.出度为奇数的结点.（4）设G为有n个结点的无向完全图，则G的边数为（C）A.n(n1)B．n(n1)C.n(n1)2D.(n1)2（5）在有n个结点的连通图G中，其边数（B）A.最多n1条；B．至少n1条；文档C.最多D.至少n条；n条.（6）任何无向图G中结点间的连通关系是（B）A.偏序关系；B．等价关系；C.既是偏序关系又是等价关系；D.既不是偏序关系也不是等价关系.（7）对于无向图，下列说法中正确的是.（B）A．不含平行边及环的图称为完全图B．任何两个不同结点都有边相连且无平行边及环的图称为完全图C．具有经过每条边一次且仅一次回路的图称为哈密尔顿图D．具有经过每个结点一次且仅一次回路的图称为欧拉图（8）设D是有向图，则D强连通的充分必要条件为.(C)A．略去D中各边方向后所得到的无向图是连通的B．D是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图C．D的任意两个不同的结点都可以相互到达D．D是完全图（9）对于无向图（A）A．如果G的两个不同结点是连接的，则这两个结点之间有初级回路B．如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程C．如果G是树，则任何两个不同结点之间有且仅有一条初级通路D．如果G是欧拉图，则G有欧拉回路G，以下结论中不正确的是.三、填空题1.设树T中有7片树解用握手定理和树的性质列出方程叶，3个3度结点，其余都是4度结点，则T中有个4度结点.求解，设有x个4度结点，794x2(73x1)，x12.设TV,E为树，T中有4度，3度，2度分支点各1个，问T中有片树叶。解与上题解法相同，设有x片树叶，432x2(3x1)，x53.n阶完全图的任意两个不同结点的距离都为．1G为n阶无向完全图，则G共有条边4.图。n(n1)/2(n,m)G为图，则图中结点度数的总和为。2m5.设6.图G为欧拉图的充分必要条件是_____________________.G为无奇度结点的连通图四、解答题1.对下图所示的图G，求（1）G的邻接矩阵A；v,v之间长度为3的通路；（2）G的结点13（3）G的连接矩阵C；（4）G的关联矩阵M。文档vvvvv4123501110v1v2v310101解（1）A=.11011v101004v011005（2）因为31212713221,,A2=2241112121A3=21112v,v之间长度为所以，结点3的通路共有7条，它们是13vvvv,vvvv,vvvv,131312531213vvvv,vvvv,vvvv,vvvv.1413135313231343（3）由于图G是连通的，所以vvvvv4123511111v1v2C=v3v41111111111.11111v111115（4）eeeeeee51234671011000v1v2M=v3v411000010110110.0001100v000001152.在下面的有向图D中，回答下列问题文档（1）写出图D的邻接矩阵A；（2）写出结点v到结点v的长度为3的所有有向通路；13v到自身的长度为3的所有有向回路；（3）写出结点50000110100A001101）00001解：（01010010101010100111001110112101121A3A（2）201010101011010101121所以结点v到结点v的长度为3的所有有向通路只有一条:vvvv152313（3）结点v到自身的长度为3的所有有向回路只有一条：vvvv521553.在下面的无向图G中，回答下列问题aedbcad之间的所有初级通路；,d(a,d)2）写出,（1）写出（ad之间的所有短程，并求；G是否为欧拉图并说明理由。解（1）a,d之间的所有初级通路7条，分别为aed，aecd，aebcd，abed，abcd，abecd，abced（3）判断无向图共有（2）a,d之间的长度最短的通路只有1条，即，因而它是之间aeda,d唯一的短程，d(a,d)2