离散数学选择题

离散数学选择题

Prepared on 22 November 2020

单项选择题

第一章 命题逻辑

1．下列语句，哪一个是真命题：（ B ）

A．我正在说谎 B．如果1+1=0，那么雪是黑的 C．9+5＞18 D．存在最大的质数 2．下面哪一个命题是假命题（ A ）

A．如果2是偶数，那么一个公式的析取范式唯一 B．如果2是偶数，那么一个公式的析取范式不唯一 C．如果2是奇数，那么一个公式的析取范式唯一 D．如果2是奇数，那么一个公式的析取范式不唯一 3．下面哪个联结词运算不可交换（ B ） A． ； B． C． D．

4．设P：天下大雨，Q：他乘公共汽车上班。命题“只有天下大雨，他才乘公共汽车上

班”符号化为（ B ）

A．PQ B．QP C．PQ D． PQ

5．设P：天下钉子，Q：我去B城 。命题“除非天下钉子，否则我去B城”符号化为：（ C ）

A．P Q B．Q P C．P Q D．Q ┐P

6．设P：我们划船，Q：我们跳舞，命题“我们不能既划船又跳舞”符号化为（ B ） A．PVQ 2）┐（P∧Q） C．┐P∧┐Q D．┐P∧Q

7．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为

（ D ）

A．P┐Q B．P∨┐Q C．P∧Q D．P∧┐Q

8．设P：我将去镇上，Q：我有时间，命题“我将去镇上，仅当我有时间”，符号化为（ A ）。

A．P Q B、Q P C、PQ D、┐P∨┐Q 9．下面哪一个命题公式是重言式（ D ） A．（P∨R）∧（P Q） B．P（Q∨R）

C．（P∨Q）（Q∨R） D．（P（Q R））（P Q）（PR） 10．下面哪一组命题公式不是等价的（ C ）

A．（PQ）（QP），PQ B． （PQ），（P∧┐Q）∨（┐P∧Q） C．P（Q∨R），┐P∧（Q∨R） D． P（Q∨R），（P∧┐Q） R 11．下面哪个命题公式是重言式（ B ）

A．（P Q）（QP） B．（PQ）P C．（┐P∨Q）∧┐（┐P∧Q） D．（PQ）P 12．下列公式哪一个是两个命题变元P，Q的小项（ C ）

A．P∧┐P∧Q B．┐P∨Q C．┐P∧Q D．┐P∨P∨Q 13．一个公式在等价意义下，下面哪个写法是唯一的。（ C ）

A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不对 14．命题公式(PQ)的主析取范式编码为 ( D )

A．m00m01m11 B．m00∨m11 C．m01 D．m10 15.命题公式(PQ)的主合取范为 ( a )

A．M01M10 B.M00M11 C.M00M01 D.M10M11 16.命题公式的任意两个不同极小项的合取式一定为( b )

A.永真式 B.永假式 C.可满足式 D.不可确定

17．下面联结词集中，哪一个不是联结词的极小全功能集（ d ）

A．{，} B．{↓} C．{} D．{，，} 第二章 一阶逻辑

1．设S(x): x是三好学生, a:张三, b: 李四, 命题“张三是三好学生而李四不是”符号化为（ ） D

A．S（a）， S（b） B．S（a）∨S（b） C．S（a）∨S（b） D．S（a）∧S（b）

2.令F(x):x是有理数，G(x):x是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为 （ ） B (F(x)∧G(x))∧x(G(x)F(x)) (F(x)G(x))∧x(G(x)∧F(x)) (F(x)∧G(x))∧x(G(x)∧F(x)) (F(x)G(x))∧x(G(x)F(x))

3．设F(x)：x是火车，G(x)：x是汽车，H(x,y)：x比y快。“每列火车都比某些汽车快”符号化为（ ） C

A．(x)(y)(F(x)G(y)H(x,y))； B．(x)(y)(F(x)G(y)H(x,y))； C．(x)(F(x)(y)(G(y)H(x,y)))； D．(x)F(x)H(x,y) 4．设C(x)：x是国家选手，G(x)：x是健壮的。命题“没有一个国家选手不是健壮的”可符号化为（ ） C

A．(x)(C(x)G(x))； B．(x)(C(x)G(x))； C．(x)(C(x)G(x))； D．(x)(C(x)G(x))；

5．设个体域A={a、b}，公式(x)P(x)xS(x)在A上消去量词应为（ ） D

A．P(x)∧S(x) B．P(a)∧P(b)∧S(a)∨S(b)

C．P(a)∧S(b) D．P(a)∧P(b)∧(S(a)∨S(b)) 6．一阶公式x(P(x)∨yR(y))→Q(x)中量词x的辖域是 ( ) A

A. (P(x)∨yR(y)) B. P(x)

C. x(P(x)∨yR(y)) D. (P(x)∨yR(y))→Q(x) 7、设论域为整数集，下列公式中哪个值为真（ ） A A．xy(xy0) B.yx(xy0) C. xy(xy0) D．xy(xy0)

8．下面给出的一阶逻辑等价式中，哪一个是错的。（ ） B

A．AxB（x）x（AB（x））

B．x（A（x）B（x））xA（x）xB（x） C．x（A（x）B（x））xA（x）xB（x） D．xA（x）x（A（x））

9．在谓词演算中，下列各式中，哪式是正确的（ ）。B

A．xyA(x,y)yxA(x,y) B．xyA(x,y)yxA(x,y) C．xyA(x,y)xyA(x,y) D．xyA(x,y)yxB(x,y) 10．设论域为整数集，下列公式中哪个值为假 （ ） D A．y(xy0) B．yx(xy2) C．xyz(xyz) D．xy((xy)1) 11．设I是如下一个解释：D＝{a,b},

P(a,a) P(a,b) P(b,a) P(b,b)

1 0 1 0则在解释I下取真值为1的公式是( ).D

A xyP(x,y) B xyP(x,y) C xP(x,x)

D xyP(x,y).

12．谓词公式(x)P(x,y)∧(x)(Q(x,z)(x)(y)R(x,y,z))中量词x的辖域是（ ）A

A．（Q(x,z)(x)(y)R(x,y,z)） B．Q(x,z)，R(x,y,z) C．Q(x,z)(y)R(x,y,z) D．Q(x,z) 13.谓词公式x(p(x)yR(y)Q(x)中变元χ是 ( ) D A．自由变元 B．既不是自由变元也不是约束变元 C．约束变元 D．既是自由变元又是约束变元 14.一阶逻辑公式x(F(x,y)∧G(y,z))→zF(z,y)是 （ ） C A.前束范式 B.封闭公式 C.永真式 D.永假式 15．一阶逻辑公式xP(x)xP(x)是( ) A

A.永真的 B.永假的 C.可满足的 D.前束范式.

16.一阶逻辑公式xP(x)yQ(y)的前束范式是（ d ） (P(x)Q(y)) (x)∨yQ(y) (x)∨Q(y) (P(x)Q(y))

第三章 集合的基本概念和运算 1．下列式子中正确的是（ ）． D

A．＝0； B．；C．＝{}； D．｛｝ 2．下列各式中哪个是错的（ B ）

A、 ； B、； C、 ｛｝； D、{} 。 3．下列命题正确的是（ ）。 A

A．{}= B．{}= C．{a}{a，b，c} D．{a，b，c} 4．下列各命题哪一个是假命题（ ） B

A．{a,b}{a,b,c,{a,b,c}} B．{a,b}{a,b,c,{a,b,c}} C．{a,b}{a,b,{a,b}} D．{a,b}{{a,b}}

5．设A={{1,2,3}, {4,5}, {6,7,8}}，下列哪个式子为真（ ） C

A．1∈A B．{1,2,3}A C．{{4,5}}A D．A 6．设A＝{}，B=P（P（A）），下式中错的是（ ） D

A．B； B．{}B； C．{{}}B； D．{，{}}P（A）。 7．设A=，B={, {}}，则B－A是（ ） C

A．{{}}； B．{}； C．{, {}}； D． 8．集合{0}的所有子集是（ ） B

A．； B．, {0}； C．{}； D．{, {0}} 9．设A＝{a,b}，则A的幂集P（A）为（ ） D

A．{a,b} B．{,{a},{b}} C．{,{a,}} D．{,{a},{b},{a,b}} 10．设X，Y，Z是集合，“一”是集合相对补运算，下列等式不正确的是（ ）Ａ

A．(X－Y)－Z＝X－(Y∩Z) B．(X－Y)－Z＝(X－Z)－Y C．(X－Y)－Z＝(X－Z)－(Y－Z) D．(X－Y)－Z＝X－(Y∪Z)

11.设集合A={2,{a},3,4}，B={1,{a},3,4}，E为全集，则下列命题正确的是( ) C

A {2}A B {a} A C {{a}} B D {{a},1,3,4} B. 12.设A,B为集合,A∩B=A∪B成立的充分必要条件是( D )

A. A=B= B. A= C. B= D. A=B 第四章 二元关系与函数

1．设A＝{1，2}，B＝{a,b,c}，C＝{c,d}，则A×（B∩C）为（ B ） A．c,1,2,c B．1,c,2,c C．c,1,c,2 D．1,c,c,2

2．设集合A={1，2，3}，A上的关系R={<1，1>，<1，2>，<2，2>，<3，3>，<3，2>}，

则R不具备( ) B

A．传递性 B．对称性 C．自反性 D．反对称性 3．设R是集合A={a,b,c,d}上的二元关系，

R={,,,,,,}，则R具有关系的哪些性质（ ） D

A.自反性、反对称性 B.反自反性、传递性 C.自反性、对称性 D.反对称性、传递性

4．设集合A＝{1,2,3,4}，A上的关系R＝{<1,1>,<2,2>,<1,3>}，则R具有关系的哪些性质（ ）．A

A．传递性；B．自反性；C．对称性；D．以上答案都不对 5．设A={0, b}，B={1, b, 3}，则A∪B的恒等关系为（ ）A

A．{<0, 0>, <1, 1>, ,<3, 3>}； B．{<0, 0>, <1, 1>, <3, 3>}； C．{<1, 1>, , <3, 3>}； D．{<0, 1>, <1, b>, , <3, 0>} 6．设A＝{1，2，4，6，8},集合A上的二元关系Ra,bab2，则domR和ranR分别为（ ）B

1,4 B．1,4和1,2 C．1,4和2,1 D．1,1,4,2A．1,2和和2,1

7．若集合A上的关系R为等价关系，则R的必要条件是（ ）D

A．对称的和传递的 B．反自反的 C．反对称的 D．自反的，对称的和传递的 8．设集合A={a,b,c}，A上所有互不相同的等价关系的数目为( ) C

A. 3 B. 4 C. 5 D. 6

9．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ）D

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

10．P={a、b、c、d}的最大划分是（ ）（即集中元素数目最多的划分） C

A．{{a}，{b，c}{d}}； B．{a，{b，c}}； C．{{a}、{b}，{c}，{d}} D．{{a，b，c，d}} 11．集合A上的关系R是偏序关系的必要条件是（ ） A

A．自反的，反对称的和传递的； B．自反的和对称的； C．传递和和对称的； D．传递的和反对称的。

12．集合A＝{1,2,3，4，5，6，7，8，9，10}，A上的整除关系是一个偏序关系，则元

素10是集合A的（ ）． C

A．最大元； B．最小元； C．极大元； D．极小元 13.下列关系中哪一个是集合A={a,b,c,d,e,f}上偏序关系 （ ） B

A.{,,}∪IA B.{,,}∪IA

C.{,,}∪IA D.{,,,}∪IA

14.集合A=a,b,c,d，A上的一个划分1a,b,c,d，则对应的等价关系

R1（ A ）。

A．{a,b,b,a}IA B．{a,b,b,a,c,c,d,d} C．{a,a,b,b,c,c,d,d} D．{a,b,b,a}

15.设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ D）

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}} 16．设R为实数集，映射f：RR，f（x）＝-x2+2x-1，则f是（ ）。D

A．单射而非满射 B．满射而非单射 C．双射 D．既不是单射，也不是满射 17．设f和g都是A到A的双射函数，则（fog）-1为（ D ） A．f-1og-1 C.（gof）-1 o f-1

18.设集合A={a,b,c},B={β,ε,θ},则从A到B最多可以定义多少个双射函数( )D B. 9 第七章 图的基本概念

1．仅由一个孤立点组成的图称为（ ） B

A．零图 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．下面所给的数值序列，能成为简单图的度数序列的是（ ） C

A．(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＞中，顶点总度数和边数的关系为（ ）C

deg(v)2Edeg(v)Edeg(v)2Edeg(v)EA．vV B．vVC．vV D．vV 5．设G为有n个结点的无向完全图，则G的边数为（ ） A A．n(n1)2 B．(n1)2 C．n (n－1) D．n (n+1)

6．有向图G=，其中V={a,b,c,d,e,f}，E={,,,,}是( ) A

A．弱连通图 B．单向连通图 C．强连通图 D．不连通图 7．图G=如下图所示，从a到d有多少条简单通路（ ）C A．5 B．6 C．7 D．8 8．邻接矩阵具有对称性的图一定是（ ） B

A．有向图 B．无向图 C．混合图 D．简单图

9．G=是简单有向图，可达矩阵P（G）刻划下列哪种关系（ ）A

A．点与点 B．点与边 C．边与点 D．边与边

0111110．设图G的邻接矩阵为1010010111，则G的顶点数与边数分别为( ) D

1010110110A．4, 5 B．5, 6 C．4, 10 D．5, 8 11．在完全图K4的所有非同构的生成子图中，有几个是3条边的( ) B A. 1 B. 2 C. 3 D. 4

12．图G和G’的结点和边分别存在— —对应关系是GG'（同构）的（ ）

A．充分条件 B．充分必要条件 C．必要条件 D．既不充分也不必要条件 13.设图G=为无向图，|V|=6，|E|=22，则G一定是 D A.完全图 B.正则图 C.简单图 D.多重图

14．设A（G）是有向图G=（V，E）的邻接矩接，其中第i行中值为1的元素数目为

（ ） B

A．结点Vi的入度 B.结点Vi的出度 C．结点Vi的度数 D.结点Vj的度数

15.有3条边的互不同构的4阶无向简单图的个数为 （ ）A

16.有向图G是强连通图，当且仅当 D

A.图G中至少有一条通路 B.图G中有通过每个顶点至少一次的通路 C.图G中至少有一条回路 D.图G中有通过每个顶点至少一次的回路 17.有向图G是单向连通图，当且仅当( ) B A.图G中至少有一条通路 B.图G中有通过每个顶点至少一次的通路 C.图G的连通分枝数为一. D.图G中有通过每个顶点至少一次的回路. 第八章 一些特殊的图

1．一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) BA．哈密尔顿回路 B．欧拉回路 C．哈密尔顿通路 D．初级回路 2．无向图G是欧拉图，当且仅当（ ） D

A．G的所有结点的度数全为偶数。 B．G中所有结点的度数全为奇数。 C．G连通且所有结点度数全为奇数。 D．G连通且所有结点度数全为偶数。 3．设G是连通平面图，有5个顶点，6个面，则G的边数是( ) A A．9条 B．5条 C．6条 D．11条

4．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） C A．2个面 B．3个面 C．4个面 D．5个面 5．二部图K3,3是( ) B

A.欧拉图 B. 哈密顿图 C. 平面图 D.完全图 6.下列图形哪一个可以一笔画出 （ ） D

7．在下面的无向图中，哪一个是哈密顿图。（ ） B 8．下图属于什么图（ ） D

A．二部图 B．欧拉图 C．哈密尔顿图 D．是二部图也是哈密尔顿图 9.下图的最大匹配是( )a

A.{e1,e2,e5,e7,e11} B.{e2,e4,e6,e9,e11} C.{e1,e5,e7,e9,e11} D.{e1,e2,e4,e7,e11}

10.、给定平面G如下所示，则G中所有面的总次数为（ B） （1）28 （2）22 （3）26 （4）24 第九章 树

1．下面哪一种图不一定是树。（ D ）

A．有n个顶点n—1条边的连通图 B．无回路的连通图 C．连通但删去一条边则不连通的图 D．每对结点间都有路的图 2．设G是有5个顶点的完全图，则从G中删去多少条边可以得到树( A ) A．6 B．5 C．10 D．4.

3．在具有n个顶点的完全图Kn中删去多少条边才能得到树（ A ）

n(n1)A．2(n1)； B．n(n1)m； C．mn1； D．mn1。

4．设G=为（n, m）连通图，则要确定G的一棵生成树必删去G中边数为（ C

A．n－m+1 B．n－m－1 C．m－n+1 D．m－n－1

5.设图G是有6个顶点的连通图，总度数为20，则从G中删去多少条边使之变成树（ ） B

A．10 B．5 C．3 D．2

6．下面给出的符号串集合中，哪一个是前缀码（ ） A A．{1, 01, 001, 000} B．{1, 11, 101, 001, 0011} C．{b, c, aa, bc, aba} D．{b, c, a, aa, ac, abb} 7．下面给出的符号串集合中，哪一个不是前缀码（ ） B

A．0,10,110,1111； B．1101,1001,101,110,； C．01,001,000,10； D．b,c,aa,ac,aba,abc。

）

8．设T是有n个结点的二元正则树，则树T的叶子数为（ ）。C A．n－1 B．2n－1 C．(n+1)/2 D．(n+2)/3 为二元正则树，有t片叶子，e条边，则有（ c ）

A．e > 2(t－1) B. e < 2(t－1) C. e＝ 2(t－1) D. e＝2(t+1)