离散数学选择题.doc

《离散数学选择题.doc》由会员分享，可在线阅读，更多相关《离散数学选择题.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流离散数学选择题.精品文档.单项选择题第一章 命题逻辑1下列语句，哪一个是真命题：（ B ）A我正在说谎 B如果1+1=0，那么雪是黑的C9+518 D存在最大的质数2下面哪一个命题是假命题（ A ）A如果2是偶数，那么一个公式的析取范式唯一B如果2是偶数，那么一个公式的析取范式不唯一C如果2是奇数，那么一个公式的析取范式唯一D如果2是奇数，那么一个公式的析取范式不唯一3下面哪个联结词运算不可交换（ B ）A ； B C D4设P：天下大雨，Q：他乘公共汽车上班。命题“只有天下大雨，他才乘公共汽车上班”符号化为（ B ）APQ BQP CPQ

2、D PQ5设P：天下钉子，Q：我去B城 。命题“除非天下钉子，否则我去B城”符号化为：（ C ）AP Q BQ P CP Q DQ P6设P：我们划船，Q：我们跳舞，命题“我们不能既划船又跳舞”符号化为（ B ）APQ 2）（PQ） CPQ DPQ7令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）APQ BPQ CPQ DPQ 8设P：我将去镇上，Q：我有时间，命题“我将去镇上，仅当我有时间”，符号化为（ A ）。AP Q B、Q P C、PQ D、PQ9下面哪一个命题公式是重言式（ D ）A（PR）（P Q） BP（QR）C（PQ）（QR） D（P（Q R

3、）（P Q）（PR）10下面哪一组命题公式不是等价的（ C ）A（PQ）（QP），PQ B （PQ），（PQ）（PQ）CP（QR），P（QR） D P（QR），（PQ） R11下面哪个命题公式是重言式（ B ）A（P Q）（QP） B（PQ）PC（PQ）（PQ） D（PQ）P12下列公式哪一个是两个命题变元P，Q的小项（ C ）APPQ BPQ CPQ DPPQ13一个公式在等价意义下，下面哪个写法是唯一的。（ C ）A析取范式 B合取范式 C主析取范式 D以上答案都不对14命题公式(PQ)的主析取范式编码为 ( D )A B C D15.命题公式(PQ)的主合取范为 ( a )A B. C.

4、 D.16.命题公式的任意两个不同极小项的合取式一定为( b )A.永真式 B.永假式 C.可满足式 D.不可确定17下面联结词集中，哪一个不是联结词的极小全功能集（ d ）A， B C D，第二章 一阶逻辑1设S(x): x是三好学生, a:张三, b: 李四, 命题“张三是三好学生而李四不是”符号化为（ ） DAS（a）， S（b） BS（a）S（b）CS（a）S（b） DS（a）S（b）2.令F(x):x是有理数，G(x):x是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为 （ ） BA.x(F(x)G(x)$x(G(x)F(x)B.x(F(x)G(x)$x(G(x

5、)F(x)C.x(F(x)G(x)$x(G(x)F(x)D.x(F(x)G(x)$x(G(x)F(x)3设F(x)：x是火车，G(x)：x是汽车，H(x,y)：x比y快。“每列火车都比某些汽车快”符号化为（ ） CA； B；C； D4设：是国家选手，：是健壮的。命题“没有一个国家选手不是健壮的”可符号化为（ ） CA； B；C； D；5设个体域A=a、b，公式在A上消去量词应为（ ） DAP(x)S(x) BP(a)P(b)S(a)S(b)CP(a)S(b) DP(a)P(b)(S(a)S(b)6一阶公式x(P(x)$yR(y)Q(x)中量词x的辖域是 ( ) AA. (P(x)$yR(y)

6、B. P(x)C. x(P(x)$yR(y) D. (P(x)$yR(y)Q(x)7、设论域为整数集，下列公式中哪个值为真（ ） AA B. C. D8下面给出的一阶逻辑等价式中，哪一个是错的。（ ） BAAxB（x）x（AB（x）Bx（A（x）B（x）xA（x）xB（x）C$x（A（x）B（x）$xA（x）$xB（x）DxA（x）$x（A（x）9在谓词演算中，下列各式中，哪式是正确的（ ）。BA BC D10设论域为整数集，下列公式中哪个值为假 （ ） DA BC D11设I是如下一个解释：Da,b, 则在解释I下取真值为1的公式是( ).DA $xyP(x,y) B xyP(x,y) C

7、xP(x,x) D x$yP(x,y).12谓词公式(x)P(x,y)($x)(Q(x,z)(x)(y)R(x,y,z)中量词$x的辖域是（ ）AA（Q(x,z)(x)(y)R(x,y,z)） BQ(x,z)，R(x,y,z)CQ(x,z)(y)R(x,y,z) DQ(x,z)13.谓词公式中变元是 ( ) DA自由变元 B既不是自由变元也不是约束变元C约束变元 D既是自由变元又是约束变元14.一阶逻辑公式x(F(x,y)G(y,z)zF(z,y)是 （ ） CA.前束范式 B.封闭公式 C.永真式 D.永假式15一阶逻辑公式xP(x)$xP(x)是( ) AA.永真的 B.永假的 C.可满足

8、的 D.前束范式.16.一阶逻辑公式xP(x)$yQ(y)的前束范式是（ d ）A.x$y(P(x)Q(y) B.xP(x)$yQ(y) C.x$yP(x)Q(y) D.$x$y(P(x)Q(y)第三章 集合的基本概念和运算1下列式子中正确的是（ ） DAF0； BFF；CFF； DFF2下列各式中哪个是错的（ B ） A、F F ； B、FF； C、F F； D、FF 。3下列命题正确的是（ ）。 AAFF=F BFF=F Caa，b，c DFa，b，c4下列各命题哪一个是假命题（ ） BAa,ba,b,c,a,b,c Ba,ba,b,c,a,b,cCa,ba,b,a,b Da,ba,b5设

9、A=1,2,3, 4,5, 6,7,8，下列哪个式子为真（ ） CA1A B1,2,3A C4,5A DFA6设AF，B=P（P（A），下式中错的是（ ） DAFB； BFB； CFB； DF，FP（A）。7设A=F，B=F, F，则BA是（ ） CAF； BF； CF, F； DF8集合0的所有子集是（ ） BAF； BF, 0； CF； DF, 09设Aa,b，则A的幂集P（A）为（ ） DAa,b BF,a,b CF,a, DF,a,b,a,b10设X，Y，Z是集合，“一”是集合相对补运算，下列等式不正确的是（ ）A(XY)ZX(YZ)B(XY)Z(XZ)YC(XY)Z(XZ)(YZ)D

10、(XY)ZX(YZ)11.设集合A=2,a,3,4，B=1,a,3,4，E为全集，则下列命题正确的是( ) CA 2A B a A C a B D a,1,3,4 B.12.设A,B为集合,AB=AB成立的充分必要条件是( D )A. A=B= B. A= C. B= D. A=B第四章 二元关系与函数1设A1，2，Ba,b,c，Cc,d，则A（BC）为（ B ）A B C D2设集合A=1，2，3，A上的关系R=，则R不具备( ) BA传递性 B对称性 C自反性 D反对称性3设R是集合A=a,b,c,d上的二元关系，R=,，则R具有关系的哪些性质（ ） DA.自反性、反对称性 B.反自反性、

11、传递性C.自反性、对称性 D.反对称性、传递性 4设集合A1,2,3,4，A上的关系R,，则R具有关系的哪些性质（ ）AA传递性；B自反性；C对称性；D以上答案都不对5设A=0, b，B=1, b, 3，则AB的恒等关系为（ ）AA, , ,； B, , ；C, , ； D, , , 6设A1，2，4，6，8,集合A上的二元关系，则和分别为（ ）BA和 B和 C和 D和7若集合A上的关系R为等价关系，则R的必要条件是（ ）DA对称的和传递的 B反自反的 C反对称的 D自反的，对称的和传递的8设集合A=a,b,c，A上所有互不相同的等价关系的数目为( ) CA. 3 B. 4 C. 5 D. 6

12、9设A=a,b,c,d，A上的等价关系R=,IA，则对应于R的A的划分是（ ）DAa,b,c,d Ba,b,c,dCa,b,c,d Da,b,c,d10P=a、b、c、d的最大划分是（ ）（即集中元素数目最多的划分） CAa，b，cd； Ba，b，c；Ca、b，c，d Da，b，c，d11集合A上的关系R是偏序关系的必要条件是（ ） AA自反的，反对称的和传递的； B自反的和对称的；C传递和和对称的； D传递的和反对称的。12集合A1,2,3，4，5，6，7，8，9，10，A上的整除关系是一个偏序关系，则元素10是集合的（ ） CA最大元； B最小元； C极大元； D极小元13.下列关系中哪一

13、个是集合A=a,b,c,d,e,f上偏序关系？ （ ） BA.,IA B.,IAC.,IA D.,IA14.集合A=，A上的一个划分，则对应的等价关系（ A ）。A BC D15.设A=a,b,c,d，A上的等价关系R=,IA，则对应于R的A的划分是（ D）Aa,b,c,d Ba,b,c,d Ca,b,c,d Da,b,c,d16设R为实数集，映射f：RR，f（x）-x2+2x-1，则f是（ ）。DA单射而非满射 B满射而非单射 C双射 D既不是单射，也不是满射17设f和g都是A到A的双射函数，则（fog）-1为（ D ）Af-1og-1 B.f-og-1 C.（gof）-1 D.g-1 o

14、f-118.设集合A=a,b,c,B=,则从A到B最多可以定义多少个双射函数( )D A.27 B. 9 C.8 D.6 第七章 图的基本概念1仅由一个孤立点组成的图称为（ ） BA零图 B平凡图 C多重图 D子图2给下列序列，哪一个可构成无向简单图的顶点度数序列（ B ）（1）（1，1，2，2，3） （2）（1，1，2，2，2） （3）（1，2，3，4，5） （4）（1，3，4，4，5） 3下面所给的数值序列，能成为简单图的度数序列的是（ ） CA(1,2,2,3,4,5) B(1,2,3,4,5,5) C(1,1,1,2,3) D(2,3,3,4,5,6)4在任何图G=V，E中，顶点总度数

15、和边数的关系为（ ）CA BC D5设G为有n个结点的无向完全图，则G的边数为（ ） AA B Cn (n1) Dn (n+1)6有向图G=，其中V=a,b,c,d,e,f，E=,是( ) AA弱连通图 B单向连通图 C强连通图 D不连通图7图G=如下图所示，从a到d有多少条简单通路（ ）CA5 B6 C7 D88邻接矩阵具有对称性的图一定是（ ） BA有向图 B无向图 C混合图 D简单图9G=是简单有向图，可达矩阵P（G）刻划下列哪种关系（ ）AA点与点 B点与边 C边与点 D边与边10设图G的邻接矩阵为，则G的顶点数与边数分别为( ) DA4, 5 B5, 6 C4, 10 D5, 811

16、在完全图的所有非同构的生成子图中，有几个是3条边的？( ) BA. 1 B. 2 C. 3 D. 412图G和G的结点和边分别存在 对应关系是（同构）的（ ）A充分条件 B充分必要条件 C必要条件 D既不充分也不必要条件13.设图G=为无向图，|V|=6，|E|=22，则G一定是 DA.完全图 B.正则图 C.简单图 D.多重图14设A（G）是有向图G=（V，E）的邻接矩接，其中第i行中值为1的元素数目为（ ） BA结点Vi的入度 B.结点Vi的出度 C结点Vi的度数 D.结点Vj的度数15.有3条边的互不同构的4阶无向简单图的个数为 （ ）AA.2 B.3 C.4 D.516.有向图G是强连

17、通图，当且仅当 DA.图G中至少有一条通路 B.图G中有通过每个顶点至少一次的通路C.图G中至少有一条回路 D.图G中有通过每个顶点至少一次的回路17.有向图G是单向连通图，当且仅当( ) BA.图G中至少有一条通路 B.图G中有通过每个顶点至少一次的通路C.图G的连通分枝数为一. D.图G中有通过每个顶点至少一次的回路.第八章 一些特殊的图1一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) BA哈密尔顿回路 B欧拉回路 C哈密尔顿通路 D初级回路2无向图G是欧拉图，当且仅当（ ） DAG的所有结点的度数全为偶数。 BG中所有结点的度数全为奇数。CG连通且所有结点度数全

18、为奇数。 DG连通且所有结点度数全为偶数。3设G是连通平面图，有5个顶点，6个面，则G的边数是( ) AA9条 B5条 C6条 D11条4设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） CA2个面 B3个面 C4个面 D5个面5二部图是( ) BA.欧拉图 B. 哈密顿图 C. 平面图 D.完全图6.下列图形哪一个可以一笔画出？ （ ） D7在下面的无向图中，哪一个是哈密顿图？。（ ） B8下图属于什么图？（ ） DA二部图 B欧拉图 C哈密尔顿图 D是二部图也是哈密尔顿图 9.下图的最大匹配是( )aA. B. C. D.10.、给定平面G如下所示，则G中所有面的总次数为（

19、B） （1）28 （2）22 （3）26 （4）24第九章 树1下面哪一种图不一定是树。（ D ）A有n个顶点n1条边的连通图 B无回路的连通图C连通但删去一条边则不连通的图 D每对结点间都有路的图2设G是有5个顶点的完全图，则从G中删去多少条边可以得到树？( A )A6 B5 C10 D4.3在具有n个顶点的完全图Kn中删去多少条边才能得到树？（ A ）A； B； C； D。4设G=为（n, m）连通图，则要确定G的一棵生成树必删去G中边数为（ ） CAnm+1 Bnm1 Cmn+1 Dmn15.设图G是有6个顶点的连通图，总度数为20，则从G中删去多少条边使之变成树？（ ） BA10 B5 C3 D2 6下面给出的符号串集合中，哪一个是前缀码？（ ） AA1, 01, 001, 000 B1, 11, 101, 001, 0011Cb, c, aa, bc, aba Db, c, a, aa, ac, abb7下面给出的符号串集合中，哪一个不是前缀码？（ ） BA； B；C； D。8设T是有n个结点的二元正则树，则树T的叶子数为（ ）。CAn1 B2n1 C(n+1)/2 D(n+2)/39.T为二元正则树，有t片叶子，e条边，则有（ c ）Ae 2(t1) B. e 2(t1) C. e 2(t1) D. e2(t+1)