《《离散数学》测试题答案39页》由会员分享,可在线阅读,更多相关《《离散数学》测试题答案39页(39页珍藏版)》请在金锄头文库上搜索。
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.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 B、 x*y=minx,y C、 x*y=
3、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 B.0,0C.0,0 D.0,014. 下列命题公式中是矛
4、盾式的有( )。A. B.C. D. 15. 下列各Hasse图中,是格的有( )。A. B. C. D.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. 命题公式(PQ)P是( )。 A.永真式 B.永假式 C.可满足式 D.合取范式20. 设命题公式,则G与H的关系是( ) 。A. B. C. D.21谓词公式中
5、量词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)=2E B. deg(vi)=E C. D. 26. 设G是有n个结点的无向完全图,则图G的边数为( );设D是有n个结点的有向完全图,则图D的边数为(
6、 )。A. n(n1) B. n(n+1) C. n(n1)/2 D. n(n+1)/227. 仅有一个孤立结点的图称为( )。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.既非充分也非必要条件30. 设,则与V能构成强连通图的边集合是( )。A.B.C.D.31. 相邻矩阵具有对称性的图一定是( )。A.有向图 B.无向图 C.混合图 D.简单图32. 无向图G是欧拉图,当且仅
7、当( )。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最多为( )。A.2 B.3 C.5 D. 436. 下图是( ) 。A.完全图 B. 哈密顿图 C.欧拉图 D.平面图h h h h h h 图 37. 设集合A1,2,3,10,在集合A上定义的运算,不
8、是封闭的为( )。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. 下列代数系统(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
9、 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., C., D.,45. 设A0,a,B=1,a,3,则AB的恒等关系是( )。A. , B., C., D. ,46. 设A=a,b,c,R=,则R具有性质( )。A.自反的 B.反自反的 C.反对称的 D.等价的47. 设集合是从A到B的函数, ,则s是(
10、)。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 D.存在y0,使P(y0)取真值053. 设G是群,当G有( )个元素时,不能肯定G是交换群。A.4 B.5 C.6 D.754若集合Aa,b,c,为空集合,则下列表示正确的是( )。A.aAB.aAC.aAD.A55. 设A, B, C都是