《《离散数学》测试题答案》由会员分享，可在线阅读，更多相关《《离散数学》测试题答案（50页珍藏版）》请在金锄头文库上搜索。
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、有些
2、无限集合没有可数子集 D、有理数集合是不可数集合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.1A B.4,5A C. 1,2,3A D.A8、在有界格中，若一个元素有补元，则补元( )。A、必惟一 B、不惟一 C、不一定惟一 D、可能惟一9、设集合A=1,2,3,10，下面定义的哪种运算关于集合A是不封闭的？（ ） A、 x*y=maxx,y
3、B、 x*y=minx,y C、 x*y=GCD(x,y)，即x,y的最大公约数 D、 x*y=LCM(x,y)，即x,y的最小公倍数1 / 42如果您需要使用本文档，请点击下载按钮下载!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. 设为
4、自然数，且则分别是（ ）。A.0，0 B.0，0C.0，0 D.0，014. 下列命题公式中是矛盾式的有（ ）。A. B.C. D. 15. 下列各Hasse图中，是格的有（ ）。A. B. C. D.2 / 42如果您需要使用本文档，请点击下载按钮下载!16 下列命题公式中是永假式的有（ ）。A. B.C. D.17. 设命题公式(P(QP)，记作G，则使G的真值指派为0的P，Q的取值是( )。 A.(0,0) B.(0,1) C.(1,0) D. (1,1)18. 与命题公式P（QR）等值的公式是( )。 A.(PQ)R B.(PQ)R C.(PQ)R D. P(QR)19. 命题公式(P
5、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规则 B.UG规则 C.ES规则 D.EG规则25. 在图G中，结点总度数与边数的关系是( )。A.deg(vi)=
6、2E 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)/23 / 42如果您需要使用本文档，请点击下载按钮下载!27. 仅有一个孤立结点的图称为( )。A.零图 B.平凡图 C.补图 D.子图28. 设G为无向简单图，V=n，D(G)为G的最大度，则有（ ）。A. D(G)n D. D(G)n29. 图G与G的结点和边分别存在一一对应关系，是GG(同构)的( )。A.充分条件 B.必要条件 C.充分必要条件 D.既非
7、充分也非必要条件30. 设，则与V能构成强连通图的边集合是( )。A.B.C.D.31. 相邻矩阵具有对称性的图一定是( )。A.有向图 B.无向图 C.混合图 D.简单图32. 无向图G是欧拉图，当且仅当( )。A.G的所有结点的度数全为偶数 B.G的所有结点的度数全为奇数C.G连通且所有结点的度数全为偶数 D.G连通且所有结点的度数全为奇数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最
8、多为( )。A.2 B.3 C.5 D. 436. 下图是( ) 。A.完全图 B. 哈密顿图 C.欧拉图 D.平面图h h h h h h 图 37. 设集合A1,2,3,10,在集合A上定义的运算，不是封闭的为( )。4 / 42如果您需要使用本文档，请点击下载按钮下载!A.a,bA, a*b=lcma,b(最小公倍数) B.a,bA, a*b=gcda,b(最大公约数)C.a,bA, a*b=maxa,b D.a,bA, a*b=mina,b38. 在自然数N上定义的二元运算，满足结合律的是( )。A.ab=ab B. ab=a+2b C. ab=maxa,b D. ab=ab39. 下
9、列代数系统(G,*)中，其中*是加法运算. ( )不是群。A.G为整数集合 B.G为偶数集合 C.G为有理数集合 D.G为自然数集合40. 设s1，s2，s3是三个置换，其中 s1(1 2)(2 3)(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(BC)( )。A., B.,
10、C., D.,45. 设A0,a,B=1,a,3,则AB的恒等关系是( )。A. , B.,5 / 42如果您需要使用本文档，请点击下载按钮下载! C., D. ,46. 设A=a，b，c，R=，则R具有性质（ ）。A.自反的 B.反自反的 C.反对称的 D.等价的47. 设集合是从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 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
