离散数学单项选择题习题(有答案)集.doc

单项选择题第一章第二章1. 下列表达式正确的有( )A. B.C.D.2. 下列推理步骤错在( )PUSPESTIEGA.B.C.D.3. 设P：22=5，Q：雪是黑的，R：24=8，S：太阳从东方升起，下列( )命题的真值为真。 A.B.C.D.4. 下列公式中哪些是永真式？( )A.(PQ)(QR)B.P(QQ) C.(PQ)P D.P(PQ)5. 下列等价关系正确的是( )A.B.C.D.6. 下列推导错在( )PUSESUGA.B. C. D.无7. 若公式的主析取范式为则它的主合取范式为( )A.B. ；C.D. 。8. 在下述公式中不是重言式为( )ABCD9. 下列各式中哪个不成立( )A.B.C.D.10. 命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x是聪明的，M(x)：x是人）( )A.B.C.D.11. 下述命题公式中，是重言式的为( )A.B.C.D.12. 谓词公式中的x是( )A.自由变元B.约束变元C.既是自由变元又是约束变元D.既不是自由变元又不是约束变元13. 命题“有的人喜欢所有的花”的逻辑符号化为( )设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢yA. B.C. D.14. 下列等价式成立的有( )A.B.C. D.15. 给定公式，当D=a,b时，解释( )使该公式真值为0。A.P(a)=0、P(b)=0B.P(a)=0、P(b)=1C.P(a)=1、P(b)=116. 设是人，犯错误,命题“没有不犯错误的人”符号化为( )A.B.C.D.17. 下列语句是命题的有( )A.明年中秋节的晚上是晴天B.C.当且仅当x和y都大于0 D.我正在说谎18. 下列公式是重言式的有( )A.B.C.D.19. 下列集合中哪个是最小联结词集( )A.B.,DC. ,DD.20. 设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为( )A.B.C.D.21. 下列各命题中真值为真的命题有( )A.2+2=4当且仅当3是奇数B.2+2=4当且仅当3不是奇数C.2+24当且仅当3是奇数D.2+2=4仅当3不是奇数22. 命题逻辑演绎的CP规则为( )A.在推演过程中可随便使用前提B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果C.如果要演绎出的公式为形式，那么将B作为前提，演绎出CD.设是含公式A的命题公式，则可用B替换中的A第三章23. 设A=1，2，3，4，P（A）（A的幂集）上规定二元系则P（A）/ R=( )AA BP(A)CR，1R，1，2R，1，2，3R，1，2，3，4R DR，2R，2，3R，2，3，4R，AR 24. 集合A=1,2,10上的关系R=|x+y=10,x,yA，则R 的性质为( )A.自反的B.对称的 C.传递的，对称的 D.传递的25. 集合A=1，2，3，4上的偏序关系为，则它的Hass图为( C )26. 设R，S是集合A上的关系，则下列说法正确的是( ) A若R，S 是自反的， 则是自反的B若R，S 是反自反的， 则是反自反的 C若R，S 是对称的， 则是对称的D若R，S 是传递的， 则是传递的27. ，是三个集合，则下列哪几个推理正确 ( )A.AB，BC则AC B.AB，BC则 AB C.AB，BC则 AC28. 设A=，1，1，3，1，2，3则A上包含关系“”的哈斯图为( C )29. 设f，g是函数，当( C )时，f=gA.B. C. D.30. 设，则BA是( )A. B. C. D.31. 集合A=1，2，3，4上的偏序关系图如下左，则它的哈斯图为( C )32. 设，定义上的等价关系,则由R产生的上一个划分共有( B )个分块。A4B5C6D933. 下列是真命题的有( )A BCD34. 设，下列各式中( B )是正确的domSB B.domSA C.ranSA D.domS ranS = S35. 设，S上关系R的关系图如下 ，则R具有( D )性质A自反性、对称性、传递性B反自反性、反对称性C反自反性、反对称性、传递性 D自反性36. 设,下列相等的集合是( D )A.A的BB.B和CC.C和DD.A和D37. 设，则P（A）A = ( C)A.A B.P（A）C.D.38. A是素数集合，B是奇数集合，则A-B=( D )A.素数集合B.奇数集合 C. D.239. 设R和S是P上的关系，P是所有人的集合，则表示关系 ( A )A.B.C.D.40. 在自然数集N上，（对任意）下列( B)运算是可结合的A.B.C.D.41. Q为有理数集N，Q上定义运算*为a*b = a + b ab ，则的幺元为( 0 ) A.aB.bC.1D.042. 公式换名( A )A.B.；C.D.。43. 下面蕴涵关系不成立的是( C )A.B.C.D.44. N是自然数集，定义（即x除以3的余数）,则f是(D)A.满射不是单射B.单射不是满射C.双射D.不是单射也不是满射45. 集合A=2，3，6，12，24，36上偏序关系R的Hass图为则集合B=2，3，6，12的上确界( )B=2，3，6，12的下界( )C=6，12，24，36的下确界( )D=6，12，24，36的上界( )A. 12,无,6,36B. 12,2,6,36 C. 12,2,12,36 D.12,无,6,无46. 下列哪个偏序集构成有界格( )A.（N，）B.（Z，） C.（2，3，4，6，12，|（整除关系）D.(P（A），)47. 六阶群的子群的阶数可以是( D)A.1，2，5B.2，4C.3，6，7D.2，348. 对右图，则分别为( C ) A.2、2、1B.1、1、2C.1、1、1D.1、2、2 49. 一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有( A )个4度结点A.1B.2C.3D.4 50. 具有6 个顶点，12条边的连通简单平面图中，每个面都是由( C )条边围成A.2B.4C.3D.551. 设G是有n个结点m条边的连通平面图，且有k个面，则k等于( A) A.m-n+2 B.n-m-2 C.n+m-2 D.m+n+252. 下列哪个公式为永真式？( C )A.Q=QPB.Q=PQ C.P=PQ D.P(PQ)=P53. “人总是要死的”谓词公式表示为( )（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的A. B. C. D.54. 设，则有( A )A.1,2 B.1,2 C.1 D.255. 判断下列命题哪个正确？( B )A.若ABAC，则BC B.a,b=b,aC.P(AB)P(A)P(B)（P(S)表示S的幂集） D.若A为非空集，则AAA成立56. 下列结果正确的是( )A.B.C.D.57. 集合对( )运算封闭A. 乘法B.减法C. 加法D.58. 设I为整数集合，m是任意正整数，是由模m的同余类组成的同余类集合，在上定义运算，则代数系统最确切的性质是( )A.封闭的代数系统B.半群C.独异点D.群59. 设是偏序格，其中N是自然数集合，“”是普通的数间“小于等于”关系，则 有( )A.a B.b C.min(a，b) D. max(a，b)60. 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有( )片树叶A.3B.4C.5D.661. 有向图D= ，则长度为2的通路有( )条A.0B.1C.2D.3 62. 设，则有向图是( )A.强连通的 B.单侧连通的 C.弱连通的 D.不连通的63. 设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点 A.10 B.4 C.8 D.1264. 下列命题正确的是( C )A.B.C.D.65. 设A=a,a，下列命题错误的是( B )A.aP(A)B.aP(A)C.aP(A)D.aP(A)66. 设A= ，B=(A) 下列( )表达式不成立 A. B. C. D. 67. 设R，S是集合A上的关系，则下列( )断言是正确的A.自反的，则是自反的B.若对称的，则是对称的C.若传递的，则是传递的D.若反对称的，则是反对称的68. 设P=x|(x+1)4且xR,Q=x|5x+16且xR,则下列命题哪个正确( ) A.QPB.QPC.PQD.P=Q代数系统69. ，其中，为集合对称差运算，则方程的解为( )A. B. C. D. 70. 在有理数集Q上定义的二元运算*，有，则Q中满足( )A. 时有逆元B.只有唯一逆元C. 所有元素都有逆元D.所有元素都无逆元71. 设S=0，1，*为普通乘法，则是( )A.半群，但不是独异点B.只是独异点，但不是群C.群D.环，但不是群72. 设A=1，2，10 ，则下面定义的运算*关于A封闭的有( )A.x*y=max(x ，y)B.x*y=质数p的个数使得C.x*y=gcd(x ， y)(gcd (x ，y)表示x和y的最大公约数)D.x*y=lcm(x ，y) （lcm(x ，y) 表示x和y的最小公倍数）73. 设a ， b ， c，*为代数系统，*运算如下：*abcaabcbbaccccc则零元为( C)A.aB.bC.cD.没有74. 设，其中表示模3加法，*表示模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是( B )A.B.C.D.75. 设R是实数集合，“”为普通乘法，则代数系统 不是( A )A群B独异点C半群76. 设是一个格，由格诱导的代数系统为，则( )成立A.B.C.D.77. 设，*为普通乘法，则是( )A.代数系统B.半群C.群D.都不是78. 设，*为普通乘法，则是( )A.代数系统B.半群C.群D.都不是79. 在自然数集N上，下列哪种运算是可结合的？( ) A.a*b=a-bB.a*b=maxa，bC.a*b=a+2bD.a*b=|a-b|80. 设是一个有界格，如果它也是有补格，只要满足( )A. 每个元素都至少有一个补元B. 每个元素都有多个补元C.每个元素都无补元D. 每个元素都有一个补元 81. 具有如下定义的代数系统，( )不构成群A.，*是模11乘B.，*是模11乘C.（有理数集），*是普通加法D.（有理数集），*是普通乘法82. 在( )中，补元是唯一的A.有界格B.有补格C.分配格D.有补分配格83. 在布尔代数中，当且仅当( )A.B.C.D.84. 设是偏序集，“”定义为：，则当A=( )时，是格A.1，2，3，4，6，12 B.1，2，3，4，6，8，12，14 C.1，2，3，12 D.1，2，3，485. 设是布尔代数，f是从An到A的函数，则( )A.f是布尔代数B.f能表示成析取范式，也能表示成合取范式C.若A=0，1，则f一定能表示成析取范式，也能表示成合取范式D.若f是布尔函数，它一定能表示成析（合）取范式图论86. 连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )A.只有一个奇度结点B.只有两个奇度结点C.只有三个奇度结点D.没有奇度结点87. 设为无向图，则G一定是( )A.完全图B.树C.简单图D.多重图88. 若一棵完全二元（叉）树有2n-1个顶点，则它( )片树叶A.nB.2n C.n-1 D.289. 图 给出一个格L，则L是( )A.分配格B.有补格C.布尔格D.A，B，C都不对90. 在Peterson图 中，至少填加( )条边才能构成Euler图A.1B.2C.4D.5 91. 在有n个顶点的连通图中，其边数( )A.最多有n-1条B.至少有n-1 条C.最多有n条 D.至少有n 条92. 图 中 从v1到v3长度为2的通路有( )条A 0B 3C 2D 193. 下面那一个图可一笔画出( A )94. 一个割边集与任何生成树之间( )A.没有关系B.割边集诱导子图是生成树C.有一条公共边D.至少有一条公共边95. 在任何图中必定有偶数个( )A.度数为偶数的结点 B.入度为奇数的结点 C.度数为奇数的结点 D.出度为奇数的结点 96. 一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为( )A.5B.7 C.8 D.997. 下列偏序集( C )能构成格98. 连通图G是一棵树当且仅当G中( )A.有些边是割边B.每条边都是割边C.所有边都不是割边D.图中存在一条欧拉路径99. 有n个结点，条边的连通简单图是平面图的必要条件( )A.B.C.D.100. 设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点A.10B.4C.8D.12101. 在有n个顶点的连通图中，其边数( )A.最多有n-1条B.至少有n-1条C.最多有n条D.至少有n条102. 给定无向图，如下图所示，下面哪个边集不是其边割集( )A.B.C.D.103. 如右图 相对于完全图K5的补图为( A )104. 下列哪一种图不一定是树( )A.无回路的简单连通图B.每对顶点间都有通路的图C.有n个顶点n-1条边的连通图 D.连通但删去任何一条边便不连通的图105. 下面偏序集( B )能构成格106. 6阶有限群的任何子群一定不是( )A.2阶B.3 阶C.4 阶D.6 阶107. 在如下的有向图中，从V1到V4长度为3 的道路有( )条A1B2C3D4108. n个结点的无向完全图的边数为( )A.B.C.D.109. 设G是一个哈密尔顿图，则G一定是( )A.欧拉图 B.树 C.平面图 D.连通图 110. 在如下各图中( B)是欧拉图111. 下列图中( )是根树A.B.C.D.112. 下面给出的集合中，哪一个是前缀码？( )A.0，10，110，101111B.1，11，101，001，0011C.b，c，aa，ab，aba D.01，001，000，1113. 左图0相对于完全图的补图为( A ) 114. 下列图中是欧拉图的有( A )115. 设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=( )A.nkB.n(k+1)C.n(k+1)-mD.n(k+1)-2m 116. 设G是简单有向图，可达矩阵P(G)刻画下列 ( C )关系A.点与边B.边与点C.点与点D.边与边117. 设G是一棵树，n,m分别表示顶点数和边数，则( )A.n=m B. n=m+1 C. m=n+1 D.不能确定 .13