《离散数学》测试习题答案

1、测 试 题离散数学一、选择题1、G是一棵根树，则（ ）。A、G一定是连通的 B、G一定是强连通的C、G只有一个顶点的出度为0 D、G只有一个顶点的入度为12、下面哪个语句不是命题（ ）。A、中国将成功举办2008年奥运会 B、一亿年前地球发生了大灾难C、我说的不是真话 D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算*：a，bR，a*b=a+b-ab，则下面的论断中正确的是（ ）。A、0是*的零元 B、1是*的幺元C、0是*的幺元 D、*没有等幂元4、下面说法中正确的是（ ）。A、所有可数集合都是等势的 B、任何集合都有与其等势的真子集C、有些无限集合没有可数子集 D、有理数集合是不可

2、数集合5、无向完全图K3的不同构的生成子图有（ ）个。A. 6 B.5 C. 4 D. 36、下面哪一种图不一定是无向树?A、无回路的连通图B、有n个顶点n-1条边的连通图C、每对顶点间都有通路的图D、连通但删去一条边则不连通的图7、设集合A1,2,3,4,5,6,7,8，则下列各式为真的是( )。A.1ÎA B.4,5ÌA C. 1,2,3ÍA D.ÆÎA8、在有界格中，若一个元素有补元，则补元( )。A、必惟一 B、不惟一 C、不一定惟一 D、可能惟一9、设集合A=1,2,3,10，下面定义的哪种运算关于集合A是不封闭的（ ） A、 x*y

3、=maxx,y B、 x*y=minx,y C、 x*y=GCD(x,y)，即x,y的最大公约数 D、 x*y=LCM(x,y)，即x,y的最小公倍数10、集合X中的关系R，其矩阵是 ，则关于R的论述中正确的是（ ）。A、R是对称的 B、R是反对称的C、R是反自反的 D、R中有7个元素11. 下列各组数中，哪个可以构成无向图的度数列（ ）。A.1，1，1，2，2 B.2，2，2，2，3C.1，2，2，4，6 D.2，3，3，312. 是定义在Z上的二元运算，则的幺元和零元分别是（ ）。A.不存在，0 B.0，1C.1，不存在 D.不存在，不存在13. 设为自然数，且则分别是（ ）。A.0，0

4、B.0，0C.0，0 D.0，014. 下列命题公式中是矛盾式的有（ ）。A. B.C. D. 15. 下列各Hasse图中，是格的有（ ）。A. B. C. D.16 下列命题公式中是永假式的有（ ）。A. B.C. D.17. 设命题公式Ø(PÙ(Q®ØP)，记作G，则使G的真值指派为0的P，Q的取值是( )。 A.(0,0) B.(0,1) C.(1,0) D. (1,1)18. 与命题公式P®（Q®R）等值的公式是( )。 A.(PÚQ)®R B.(PÙQ)®R C.(P®Q)

5、®R D. P®(QÚR)19. 命题公式(PÙQ)®P是( )。 A.永真式 B.永假式 C.可满足式 D.合取范式20. 设命题公式，则G与H的关系是( ) 。A. B. C. D.21谓词公式中量词"x的辖域是( )。A B. P(x) C. D.22设个体域为整数集，下列公式中其值为1的是( )。A. B.C. D.23设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )。A. B. C. D.24在谓词演算中，P(a)是的有效结论，根据是 ( )。 A.US规则

6、 B.UG规则 C.ES规则 D.EG规则25. 在图G<V,E>中，结点总度数与边数的关系是( )。A.deg(vi)=2½E½ B. deg(vi)=½E½ C. D. 26. 设G是有n个结点的无向完全图，则图G的边数为( )；设D是有n个结点的有向完全图，则图D的边数为( )。A. n(n1) B. n(n+1) C. n(n1)/2 D. n(n+1)/227. 仅有一个孤立结点的图称为( )。A.零图 B.平凡图 C.补图 D.子图28. 设G<V,E>为无向简单图，½V½=n，D(G)为G的最大度

7、，则有（ ）。A. D(G)<n B.D(G)£n C. D(G)>n D. D(G)³n29. 图G与G¢的结点和边分别存在一一对应关系，是GG¢(同构)的( )。A.充分条件 B.必要条件 C.充分必要条件 D.既非充分也非必要条件30. 设，则与V能构成强连通图的边集合是( )。A.B.C.D.31. 相邻矩阵具有对称性的图一定是( )。A.有向图 B.无向图 C.混合图 D.简单图32. 无向图G是欧拉图，当且仅当( )。A.G的所有结点的度数全为偶数 B.G的所有结点的度数全为奇数C.G连通且所有结点的度数全为偶数 D.G连通且所有

8、结点的度数全为奇数33. 设为连通平面图且有r个面，则r( )。A. mn+2 B.nm2 C.n+m-2 D.m+n+234. 设G是由5个结点组成的完全图，则从G中删去( )条边可以得到树。 A.4 B.5 C.6 D.1035. 由5个结点可构成的根树中，其叉数m最多为( )。A.2 B.3 C.5 D. 436. 下图是( ) 。A.完全图 B. 哈密顿图 C.欧拉图 D.平面图h h h h h h 图 37. 设集合A1,2,3,10,在集合A上定义的运算，不是封闭的为( )。A."a,bÎA, a*b=lcma,b(最小公倍数) B."a,b

9、6;A, a*b=gcda,b(最大公约数)C."a,bÎA, a*b=maxa,b D."a,bÎA, a*b=mina,b38. 在自然数N上定义的二元运算·，满足结合律的是( )。A.a·b=ab B. a·b=a+2b C. a·b=maxa,b D. a·b=½ab½39. 下列代数系统(G,*)中，其中*是加法运算. ( )不是群。A.G为整数集合 B.G为偶数集合 C.G为有理数集合 D.G为自然数集合40. 设s1，s2，s3是三个置换，其中 s1(1 2)(2 3)(

10、1 3),s2=(2 4)(1 4),s3=(1 3 2 4)则s3可以表成( )。A. B.s1s2 C. D.s2s141. 下列图表示的偏序集中，是格的为( )。A. B.C. D. 42. 设是布尔代数，则下式不成立的是( )。A. B. C. D.43. 布尔代数式=( )。A. B. C. D.44. 设集合A1,2，B=a,b,c,C=c,d, 则A×(BÇC)( )。A.<c,1>,<2,c> B.<1,c>,<2,c> C.<c,1>,<c,2> D.<1,c>,<c

11、,2>45. 设A0,a,B=1,a,3,则AÈB的恒等关系是( )。A. <0,0><1,1>,<3,3>,<a,a> B.<0,0>,<1,1>,<3,3> C.<1,1>,<a,a>,<3,3> D. <0,1>,<1,a>,<a,3>,<3,0>46. 设A=a，b，c，R=<a，a>，<b，b>，则R具有性质（ ）。A.自反的 B.反自反的 C.反对称的 D.等价的47. 设集合

12、是从A到B的函数， ，则s是( )。A.双射 B.满射但不是单射 C.单射但不是满射 D.非单射也非满射48.下列式子中正确的是（ ）。A.Æ=0 B.ÆÎÆ C.ÆÎa,b D.ÆÎÆ49.有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的( ) 。A.度数 B. 出度 C.最大度数 D.入度50. 给定无向图如下所示，下面给出的顶点集子集中，不是点割集的是（ ）。 a· f · b· · · ·g c · &#

13、183;h 图d e A.b,d B.d C.e D.f,h 51 谓词公式xA(x)ØxA(x)的类型是（ ）。A.永真式 B.矛盾式C.非永真式的可满足式 D.不属于(A),(B),(C)任何类型52. 谓词公式取真值为1的充分必要条件是( )。A.对任意y，使P(y)都取真值1 B.存在一个y0，使P(y0)取真值1 C.存在某些y，使P(y)都取真值1 D.存在y0，使P(y0)取真值053. 设G是群，当G有（ ）个元素时，不能肯定G是交换群。A.4 B.5 C.6 D.754若集合Aa,b,c,Æ为空集合，则下列表示正确的是( )。A.aÎAB.a&#

14、204;AC.aÌAD.ÆÎA55. 设A, B, C都是集合，如果AÇCBÇC，则有( ) 。 A.AB B.A¹B C.当ACBC时,有A=B D.当C=U时, 有A¹B 56. 设S1Æ，S2Æ, S3P(Æ), S4P(Æ)，以下命题为假的是( )。A.S2ÎS4 B.S1 Í S3， C.S4 Í S2 D.S4Î S357.设G是有6个元素的循环群，a是生成元素，则G的子集（ ）是子群。A.a B.a,e C.e,a3 D.e,a,

15、a258.设集合A=a,b,c,d,e,半序关系R的哈斯图如下，假设A的子集B=c,d,e,则元素c为B的（ ）。A.下界 B.最大下界C.最小上界 D.以上答案都不对59. 设GÛ"x$yP(x,y)®Q(z,w)，下面三个命题为真的是( )。A.G是前束范式 B.G不是前束范式 C.G不是一阶公式 D.G是永真式60对任意集合S，SÈÆS，满足( )。A.幂等律 B.零一律 C.同一律 D.互补律61设命题公式，则使公式G取真值为1的P，Q，R赋值分别是( )。 A. 0，0，0 B. 0，0，1 C.0，1，0 D.1，0，062设a是集

16、合A的元素，则以下正确的是( )。 A. B. C. D.63设集合A1，2，3，4，B：2，4，6，9，那么集合A，B的对称差AB( )。 A.1，3 B.2，4，6 C.1，3，6，9 D.1，2，3，4，6，964. 有向完全图D<，>，则图D的边数是( )。 A.(E1)2 B.(一1)2 C.() D.()65设G是有n个结点，m条边的连通阻，必须删去G的( )条边，才能确定G的一棵生成树。 A.m一n1 B.n一m C.mn1D.nm166. 设N为自然数集合，<N，>在下面4种运算下不构成代数系统的是（ ）。A. xy = x+y2xy B.xy = x+

17、y C. xy = xy D.xy = |x|+|y|67.已知图G的相邻矩阵为，则G有（ ）。A.6个点，度为4 B.5个点，度为6 C.4个点，度为3 D.4个点，度为668. 设集合A=1，2，3，10，半序关系£是A上的整除关系，则半序集（A，£）上的元素10是集合A的（ ）。A.最大元 B.最小元 C.极大元 D.极小元二、填空题1. 代数格（L，´，Ä）中的运算´和Ä满足的算律有_、_、_。2、A是含有3个元素的集合，在A上可以定义_个不同的等价关系。3、R是实数集合，R中的关系g=<x2，x> _ 从R到R的

18、函数（填“是”或“不是”）。4、<G，*>是群，|G|>1，则G中的零元_。5、当n是_值时，无向完全图Kn是欧拉图。6、I是整数集合，代数系统<I，×>（×是通常乘法）的幺元是_, -1的逆元是_。7、元素数目不超过_的格一定是链。8、公式的主合取范式为_。9、的有效结论是_。10、已知公式A(p，q，r)的主合取范式为MMM，它的主析取范式为(写成编码形式)_。11、设A=a,b，B=0,1,2，那么可定义_种不同的从A到B的单射。12. 已知集合A=Æ，1，2，则A的幂集合r (A)=_。13、设<A，>是分配格，若

19、对任意的a，c，cA，如果有ab=ac，ab=ac成立，则a_b。14、仅当n_时，Kn为平面图。15. pq 的主合取范式是_ 。 16. 语句“我在说谎”_命题。（填“是”或“不是”）。17. 设A=a,b,c,d，R是定义在A上的关系，R=<a, b>,<c, d>,<a, d> ，则r(R)= _。 18一个树林G有三棵树，G的顶点数是20，则G的边数为_ 。 19P(P(Ø)=_ 。 20整数加法群<Z, +>中1的阶是_ 。 21设有向图D<V,E>的邻接矩阵为A(D)=，那么½E½ 。 22

20、. 语句“这句话是错的” 命题。（填“是”或“不是”）。23设命题公式GPÙ(ØQÚR)，则使G取真值为1的指派是 ， ，_。24. 已知命题公式为G(ØPÙQ)®R,则命题公式G的析取范式是 。25. 公式的自由变元是 , 约束变元是 。26. 谓词逻辑公式的前束范式是 。27. 设个体域Da,b,消去公式中的量词，则 。28. 换名规则施于 变元，代入规则施于 变元。29. 设图G<V，E>和G¢<V¢,E¢>,若 ，则G¢是G的真子图，若 ，则G¢是G的生

21、成子图。30. 在无向图中，结点间的连通关系具有 性， 性， 性，是 关系. 。31. 无环有向图D的关联矩阵M(D)中，第i行值为1的元素个数为结点vi的 ，第j列值为1的元素个数为结点vj的 .。32. 设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有 条边，G的总度数是 ，G的分支点数是 ，G中度数为3的结点数是 . 。33. 连通有向图D含有欧拉回路的充分必要条件是 。34. 设G是有n个结点的简单图，若G中每对结点的度数之和 ，则G一定是哈密顿图. 。35. 设G是有n个结点，m条边的连通图，要确定G的一颗生成树，必须删去G的 条边. 。36. 一个有向树T称为根树，若 ，

22、其中 ，称为树根， 称为树叶. 。37. 在代数系统(N,+)中，其单位元是 ， 有逆元. 。38. 设A是非空集合，集合代数(P(A)，È，Ç)中，P(A)对运算È的单位元是 ， P(A)对运算Ç的单位元是 。39. 把置换表成轮换的乘积是 ，表成对换的乘积是 。40. 设G是由6个元素构成的循环群，a是G的一个生成元素，则G有 个子群，G的生成元是 。41. 非空集合L，其上定义二元运算¡和·，如果 是交换群，(L,·)是 ，而且 满足分配律，则L对二元运算¡和·构成环。 42. 设L是一个集合，&#

23、183;和¡是L上两个二元运算，如果这两个二元运算满足 律， 律和 律，则(L,·,¡)是格。43. 在布尔代数中，有成立. 则该式的对偶式 也一定成立。44. 设R1，R2是集合A1,2,3,4上的二元关系,其中 R1<1,1>,<1,2>,<2,4>, R2=<1,4>,<2,3>,<2,4>,<3,2>,则R1×R2 。45. 设R，S都是集合A上的等价关系，则对称闭包s(RÇS)= 。46. 图的通路中边的数目称为 . 结点不重复的通路是 通路. 边不重

24、复的通路是 通路。47. 将谓词公式中的约束变元换名_。48. 写出下列集合的子集：B=Æ ;C=Æ_。49设全集合E1,2,3,4,5,A=1,2,3,B=2,5,AÇB= ,B= 。AÈB= 。50. 设A, B代表集合，命题A-B=ÆÛA=B的真值为 。51. 设集合Aa,b,c,B=a,b,那么P(A)P(B)= ，P(B)P(A)= 。52设A=,Î,Ï,Ì, É选择适当的符号填在各小题的横线上.（1）(1,2,3,4) N; (2) 。53关于格的命题P：a(bc)，求P的对偶命题P

25、*=_。54计算Z6的所有理想_。55求的真值_。56判定公式(P®Q)Ù(R®Q)«(PÚ R)®Q)的类型_。57. 将命题公式化为只含Ú和Ø的尽可能简单的等值式_。58. 设n(A)=m,则A上有_个不同的自反关系。59. 设集合A=a,b,c,d，A上的关系R=(a,a),(a,c),(b,d) ，则关系R2=_。60. 设集合A中有4个元素,则A上的不同的等价关系的个数为_个。三、判断题1. 空间中的平行六面体是平面图。（ ）2、每个顶点的度都是偶数的无向图一定是欧拉图。（ ）3、顶点数目相同，边数也相同

26、的两个无向图一定同构。（ ）4、函数的逆关系还是函数。（ ）5、A，B，C都是集合，如果AB=AC，则B=C。（ ）6、设R是环，A,B是R的两个理想，且B包含于A,则A/B是R/B的理想，并且R/B /(A/B)同构于 R/A。（ ）7. 的对偶是 。（ ）8. 设G是有r个面的连通平面图，顶点数和边数分别是n和m，则n-m+r=2 。（ ）9. n阶有向完全图有n（n-1）条边。（ ）10. 在代数系统中，若，则 。（ ）11. 设无向图T是树，则T中一定没有简单回路。（ ） 12. 能够画在一张平面上的图是平面图。13. 设是代数系统，B是S的非空子集，则是的子代数。（ ）14. 循环群

27、的子群仍然是循环群。（ ）15. 格不一定是布尔代数。（ ）161+101=110是命题 。（ ）17“全体立正是命题” 。（ ）18“明天是否开大会？”是命题 。（ ）19“如果天气好，那么我去散步”是命题。（ ）20. 判断(Z,£)是否为格？其中£是数的小于或等于关系。（ ）21设 R是实数集，“”为数的加法，“×”定义为. 试问R对二元运算和×是否构成环。（ ）22. 设集合A18的正整数因子，£为整除关系，说明<A, £>是否是偏序关系。（ ）23是对的。（ ）24Æ是Æ的子集。（ ） 25如

28、果SÈTSÈM，则TM。（ ）26. 已知S2,a,3,4,R=a,3,4,1,则aÎS。（ ）27. 整数集合Z和普通的减法运算是封闭的。（ ）28在R中定义二元运算：* ,a*b=a+b+ab,对于任意a,b 属于 R，则<R,*>是独异点。（ ）29整数集合1,2,3,4,6,12关于整除关系构成了偏序集，并且该偏序集是格。（ ）四、证明题1. 设<G，*>是群，具有幺元e，如果对G的任意元素a，都有a²=e, 则<G，*>是交换群2. 形式证明3. 证明：P®(Q®R)ÛP

29、7;Q®R.4试证明：5试证明：6. 证明：Þ7设G是图，无回路，但若外加任意一条边于G后，就形成一回路. 试证明G必为树. 8. 设B是任意集合，试验证(P(B),Å)是群. P(B)是集合B的幂集，Å是集合的对称差运算， 9给定代数系统(G,+,*), 二元运算见表一，表二. 表一 表二 +abcD *abcDAabcDaaaaaBbadCbabcdCcDaBcacdbDdCbAdadbc证明(G,+,*)是域. 10. 证明如果非空集合A上的二元关系R和S是偏序关系，则也是A上的偏序关系11试证A(BC)(AB)È(AÇC)12

30、设非空集合A，验证()是布尔代数，13. 试证明属于关系不满足传递性，即对于任意的集合A,B,C若AB且BC 不一定有AC14设 A,B为两个集合，证明 AB=A当且仅当AB= ø15. 设R,S都是非空集合A上的二元关系，且他们是对称的，证明：RoS具有对称性当且仅当 RoS=SoR.16. 已知g：A->B,f：B->C 1） 已知fog是单射的且g是满射的，证明f是单射的 2） 已知fog 是满射的且f是单射的，证明g是满射的17设A是传递集，证明A+也是传递集。18设G是n阶无向简单图，其直径为d(G)=2, (G)=n-2，证明G的边数m2n-419V=<

31、S,*>是可交换半群,若a,b S是V中得幂等元，证明a*b也是V中的幂等元20设 L是格，证明对于任意a,b,c,dL有：( ab)(cd)(ac)(bd)五、计算题 1. 无向树T有2个2度顶点，1个3度顶点，3个4度顶点，其他的都是树叶，问T中有多少片树叶？2. 设公式 ，其中P(x)：x>2，Q(x)：x=0，F是永假式，个体域是1，2，求公式A(x)的真值3. 设集合X=1，2，3, 4，X中的关系为F=<1，1>，<1，2>，<1，4>，<2，1>，<2，2>，<3，3>，<4，1>，&

32、lt;4，4>写出F的关系矩阵及其关系图，F有哪些性质？4. (1) n(n1)阶无向完全图与有向完全图各有多少条边为什么(2)完全二部图K中共有多少条边为什么(3) 每个顶点的度都为k的无向图称为k正则图，问：n阶k正则图中共有多少条边为什么5. 设集合L=a，b，在L中规定 + 和·如下：a+a=a，a+b=b+a=b，b+b=ba·a=a，a·b=b·a=a，b·b=b问<L，+，·>能构成代数系统吗若可以，写出该代数系统的运算表。该代数系统有什么特性6. 设多重集A=，1，1，1， B=，1，1.计算AB，A

33、B，A-B7. 设集合M=1，2，3，4，5，s 和t 是M上的两个置换，s =，t =（1 4 5）（2 3），用轮换的形式写出s t，ts，t1is 1。8. 对集合L，规定对于x，yL，xy当且仅当x是y的因子。问下面哪几个偏序集是格为什么(1)L=1, 2, 3, 4, 6, 12(2)L=1, 2 , 3, 48, 12, 14(3)L=1, 2, 3, 4, 5, 6, 7, 8, 9, 109 在全总个体域中符号化下列命题。（1）是金子总是要发光的。（2）并非所有微笑的人都是高兴的。（3）平面图的色数不超过410 若无向图G是欧拉图，G中是否存在割边为什么11. 设集合，R是定义

34、在A上的二元关系，写出R的关系矩阵并求R的对称闭包。 12. 设集合A=2，3，4，6，8，12，24，R为A上的整除关系。（1）画出半序集（A，R）的哈斯图；（2）写出集合A中的最大元、最小元、极大元、极小元；（3）写出A的子集B=2，3，6，12的上界、下界、最小上界，最大下界。13. 令X=,Y=,。问有多少个不同的由X到Y的关系？有多少个不同的由X到Y的函数？当n,m满足什么条件时，存在单射，且有多少个不同的单射？ 14在全总个体域中符号化下列命题。（1）在中国工作的人并非都是中国人。（2）有的人在微笑但内心不高兴。（3）每种金属都可以溶解在某种液体种。15. 将下列命题符号化：(1)

35、 虽然交通堵塞，但是老王还是准时到达火车站； (2) 张力是三好学生或优秀共青团员(3) 老李或小刁中有一个人去广州出差16. 判定公式P®Q与ØPÚQ是否等值.17 用等值演算法判定公式PÚ(QÙR)®PÚQÚR是永真式永假式18求公式的主合取范式和主析取范式.19. 化简下式： (AÙBÙC)Ú(ØAÙBÙC)20 设命题P,Q的真值为0，命题R,S的真值为1，求命题公式的真值.21 将下列命题符号化：（1）每个母亲都爱自己的孩子；(2) 所有的人都呼

36、吸；(3) 有某些实数是有理数. 22指出下列公式 中量词的每次出现辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元. 23给定解释I： D2,3; D中特定元素a=2； 函数为 谓词F(x)为F(2)=0,F(3)=1G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0求在解释I下各公式的真值. (1) ;(2) ；24讨论公式的类型.25将公式F 化为前束范式.26. 判定下面二图是否同构 27. 设G(V,E)是一个无向图， (1) 画出G的图解；(2) 指

37、出与v3邻接的结点，以及与v3关联的边；(3) 指出与e1关联的结点；(4) 该图是否有孤立结点和孤立边？(5) 求出各结点的度数，并判断是不是完全图？(6) G<V,E>的½V½，½E½各是多少？28. 给定下列六个图(如图)，G1<V1,E1>,其中V1=a,b,c,d,e,E1=(a,b）,(b,c),(c,d),(a,e)G2<V2,E2>,其中V2=V1,E2=(a,b),(b,e),(e,b),(a,e),(d,e)G3<V3,E3>,其中V3=V1,E3=(a,b),(b,e),(e,d),(

38、c,c)G4<V4,E4>,其中V4=V1,E4=<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>G5<V5,E5>,其中V5=V1,E5=<a,b>,<b,a>,<b,c>,<c,d>,<d,e>,<e,a>G6<V6,E6>,其中V6=V1,E6=<a,a>,<a,b>,<b,c>,<e,c>,<e,d> al a l a l a

39、l a l a l bl le bl le bl l e b l l e b l l e bl l e cl ld cl ld cl l d cl ld cl ld cl ld (G1) (G2) (G3) (G4) (G5) (G6) 图试问：(1) 哪些图是有向图哪些图是无向图 (2) 哪些是简单图？(3) 哪些是强连通图哪些是单侧连通图哪些是弱连通图29. 求图G的点割集、割点、边割集和割边. 30. 已知有关人员a,b,c,d,e,f,g的有关信息： a：说英语；b：说英语或西班牙语；c；说英语，意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法

40、语和德语. 试问上述7人中是否任意两人都能交谈(如果必要，可由其余5人中组成的译员链帮助)31. 在具有n个结点的完全图Kn中，需要删去多少条边才能得到树. 32画出具有下列条件的有 5个结点的图. (1) 没有哈密顿回路，也不能适当指定各边的方向，使其具有欧拉回路；(2) 有哈密顿回路，但是不能适当指定各边的方向，使其具有欧拉回路；(3) 没有哈密顿回路，但是能适当指定各边的方向，使其具有欧拉回路； (4) 有哈密顿回路，也能适当指定各边的方向，使其具有欧拉回路. 33. 通常数的加法运算可看作正整数N上的二元运算. 下列集合是N的子集，加法运算在这些子集上封闭吗为什么(1) (2) (3)

41、 34. ；运算*是否有单位元和幂等元若有单位元的话，哪些元素有逆元 35. 是布尔代数，化简. 36. 设是定义在Z5(0,1,2,3,4)上的多项式(即系数是Z5的元素的多项式)，试计算P(x)+Q(x)，P(x)Q(x).37. 回答下列代数系统是环吗是交换环吗(1) (Zm,，*),其中Zm0,1,2,m1，和*是模m加法和乘法. (2) (Mn(R)，°), 其中Mn(R)是n阶实矩阵全体，°分别是矩阵的加法和乘法.38. 设集合Aa,b,R是P(A)上的包含关系，写出R的表达式和关系矩阵.39. 设A1,2,3,用列举法给出A上的恒等关系IA，全关系EA，A上的

42、小于关系 及其逆关系和关系矩阵. 40. 设A1,2,3,4, R是A上的二元关系，其关系矩阵为试求 (1) R的关系表达式； (2) Dom(R)和Ran(R)；(3) R·R中有多少个有序对 (4) R1的关系图中有多少条自回路?41. 设集合判定下列关系，哪些是自反的，对称的，反对称的，传递的？ 42. 设A1,2,3,4,5,6,定义A上的二元关系 R<1,1>,<1,4>,<2,2>,<2,3>,<2,6>,<3,2>,<3,3>,<3,6>, <4,1>,<4

43、,4>,<5,5>,<6,2>,<6,3>,<6,6>(1) 判定R是否为等价关系 (2) 若是等价关系，写出A的关于R的等价类.43. 设集合Aa,b,c,d,定义R<a,b>,<b,a>,<b,c>,<c,d>,求r(R),s(R),t(R). 44求谓词公式的真值其中P：4>3，Q（x）：x>1，R（x）：x£2f（-3）=1，f（1）=5，f（5）= -3a：5个体域D=（-3，1，5）45化简46设集合 A=a,b,B=1,2,3,C=d,求(A×B)

44、×C，A×B×C，B×A. 47用列举法表示以下集合：(1) ； (2) ;(3) 48. 列出下列集合的各元子集，并求幂集（1）A=a,b,c (2) A=1,2,3 (3)A=ø, ø 49. A=a,b,c,B=1,2,令a1=P(A),a2=A->B, 构造一个a1到a2的双射函数，再构造一个a2到a1的双射函数 50. 由f:A->B导出A上的等价关系定义为： R=<x,y>|xA yA f(x)=f(y) 设f1,f2,f3,f4NàN且 f1(n)=n f2(n)= 1 n为奇数 f3(

45、n)=0 n为偶数 f3(n)=j,n=3k+j,j=0,1,2,kN f4(n)=j,n=6k+j,j=0,1,5,kN Rk为fk导出的N上的等价关系,k=1,2,3,4 1) 求商集N/Rk k=1,2,3,4 2) 求H=10k|kN 在f1,f2,f3,f4 下的象！ 51对图给出的二叉树分别进行先根遍历、中根遍历和后根遍历。 更多课程资料请到大学课程网www.0206.cc学习测 试 题 答 案离散数学一、选择题 1. A 2. C 3. C 4. A. 5. D 6. C 7. D 8. C 9. D 10. D 11.B 12. D 13. B 14. B 15. B 16.B

46、 17.C 18.B 19.A 20.D 21.C 22.A 23.D 24.A 25.C 26.C,A 27.B 28.A 29.B 30.A 31.B 32.C 33.A 34.C 35.D 36.B 37.A 38.C 39.D 40.D 41.C 42.D 43.B 44.B 45.C 46.A 47.B 48.D 49.B,D 50.A 51.B 52.A 53.D 54.B 55.C 56.A 57.C 58.C 59.B 60.C 61.D 62.B 63.C 64.D 65.A 66.A 67.D 68.C 二、填空题1. 交换律、结合律、吸收律 2. 5 3. 不是4. 不存

47、在5. 奇数6. 1, -17. 38. 9. R 10. m1m2m4m6m711. 612、r(A)=Æ，Æ，1，2，Æ，1，Æ，2，1，2，A13、= 14、奇数15. 16. 不是17、<a,b>,<c,d>,<a,d>,<a,a>,<b,b>,<c,c>,<d,d>18、1719、，20、无限21、722. 不是23. (1,0,0,) (1,0,1) (1,1,1)24. PÚØQÚR25. y,x x,z26. 27. 28.

48、约束 自由29. 30. 自反性 对称性 传递性 等价. 31. 出度 入度32. 14 28 7 6 33. D中每个结点的入度出度.34. 大于或等于n35. m+1n36. 若有向图T恰有一个结点的入度为0，其余结点入度为1 入度为0的结点 入度为1的结点.37. 0 仅有单位元0.38. Æ A.39. (1 2 3)(5 6) (1 3)(1 2)(5 6)(不唯一)40. 4 a，a541. (L,¡) 半群 二元运算·对运算¡42. 交换律 结合律 吸收律43. 44. <1,4>,<1,3>45. RÇS46. 通路出度 初级 简单.47.48.