华东理工大学离散结构(新)作业及期末复习题

一、判断（共计50分，每题2.5分）

1、连通且不含圈的图称为树。

A.正确

B.错误

参考答案：【A】

2、在格〈L,V,A）中，如果交运算对并运算是可分配的，则并运算对交运算

也是可分配的。

A.正确

B.错误

参考答案：【A】

3、一个代数系统的单位元、零元、逆元如存在，则必唯一。

A.正确

B.错误

参考答案：【A】

4、设，则的募集是。

A.正确

B.错误

参考答案：【A】

5、设A、B为谓词公式，若A<->B是逻辑有效式，则称A和B是等值的，记作

A=>Bo

A.正确

B.错误

参考答案：【B】

6、不同的生成树的基本割集可能不一样，但基本割集的个数是固定的。

A.正确

B.错误

参考答案：【A】

7、强连通图一定是单向连通图。

A.正确

B.错误

参考答案：【A】

8、不含有任何元素的集合，称为空集，记作F。

A.正确

B.错误

参考答案：【A】

9、图中度为零的结点称为孤立结点。

A.正确

B.错误

参考答案：【A】

10、大于100的整数集合可以表示为｛101,102,103,…｝。

A.正确

B.错误

参考答案：【A】

11、在有补分配格〈L,V,A）中，任一元素adL的补元素是唯一的。

A.正确

B.错误

参考答案：【A】

12、域是整环。

A.正确

B.错误

参考答案：【A】

13、在任何图中，奇数度的结点数必是偶数。

A.正确

B.错误

参考答案：【A】

14、克鲁斯卡尔（Kruskal）算法可以求最小生成树。

A.正确

B.错误

参考答案：【A】

15、任何连通图G至少存在一棵生成树。

A.正确

B.错误

参考答案：【A】

16、完全图Kn没有割集，它的连通性能是最好的。

A.正确

B.错误

参考答案：【A】

17、两个代数系统同构则两个集合元素间存在双射。

A.正确

B.错误

参考答案：【A】

18、一个从A到B的二元关系是有序偶的集合R,在每一个有序偶中，第一个

元素取自A,第二个元素取自Bo

A.正确

B.错误

参考答案：【A】

19、树T的每一对结点之间有且仅有一条道路可通。

A.正确

B.错误

参考答案：【A】

20、若关系R是对称的，则其关系图中若两个结点之间有弧线，就一定是有双向

两条弧。

A.正确

B.错误

参考答案：【A】

二、单选（共计50分，每题2.5分）

21、设，则有（）

A.B.C.D.参考答案：【C】

22、设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为

()

A.-1PA-|Q

B.-]PV-)Q

C.-|(PQ)

D.-](-|PV-|Q)

参考答案：【B】

23、下列等价式不正确的是()

A.B.C.D.参考答案：【A】

24、从真值角度看，命题公式的全部类型是()

A.永真式

B.永假式

C.永真式，永假式

D.永真式，永假式，可满足式

参考答案：【D】

25、下列四个格，是分配格的是()

A.B.C.D.参考答案：【C】

26、下列语句中是真命题的是()

A.我正在说谎

B.严禁吸烟

C.如果1+2=3,那么雪是黑的

D.如果1+2=5,那么雪是黑的

参考答案：【D】

27、在下列代数系统中，不是环的只有()

A.<Z,+,*),其中Z为整数集，+,*分别为整数加法和乘法。

B.(Q,+,*),其中Q为有理数集，+,*分别为有理数加法和乘法。

C.<R,+,*>,其中R为实数集，+为实数加法，a*b=a+2b。

D.<Mn(R),+,*>,其中Mn(R)为实数集nXn阶矩阵结合，+,*是矩阵加法和

乘法。

参考答案：【C】

28、在公式()F(x,y)—(y)G(x,y)中变元x是()

A.自由变元

B.约束变元

C.既是自由变元，又是约束变元

D.既不是自由变元，又不是约束变元

参考答案：【C】

29、下列命题联结词集合中，是最小联结词组的是()

A.，)

B.{-j,V,A)

c.{-)，A}

D.{A,f}

参考答案：【c】

30、设人={1,2,3,4,5},B={6,7,8,9,10),以下关系是从A到B的入射

函数的是()

A.f={<l,8>,<3,9>,<4,10>,<2,6>,<5,7>}

B.f={<1,7>,<2,6>,<4,8>,<1,9>,<5,1O>}

C.f={<1,6>,<2,7>,<4,9>,<3,8>}

D.f={<l,10>/<5,9>,<3,6>,<4,6>,<2,8>}

参考答案：【A】

31、在实数集合R上，下列定义的运算中不可结合的是()

A.a*b=a+b+2ab

B.a*b=a+b

C.a*b=a+b+ab

D.a*b=a-b

参考答案：【D】

32、下面关于关系R的传递闭包t(R)的描述最确切的是()

A.t(R)是包含R的二元关系

B.t(R)是包含R的最小传递关系

C.t(R)是包含R的一个传递关系

D.t(R)是任何包含R的传递关系

参考答案：【B】

33、下列集合关于所给定的运算成为群的是()

A.已给实数a的正整数次幕的全体，且a{0,1,；},关于数的乘法

B.所有非负整数的集合，关于数的加法

C.所有正有理数的集合，关于数的乘法

D.实数集，关于数的除法

参考答案：

34、下列等价式正确的是()

A.11A

B.C.nA

D.参考答案：【C】

35、设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2,

则该图的顶点数是()

A.3

B.4

C.5

D.6

参考答案：【B】

36、集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,xWA,yWA},则R的

性质是()

A.自反的

B.对称的

C.传递的、对称的

D.反自反的、传递的

参考答案：【B】

37、设A(x):x是人，B(X)：x犯错误，命题“没有不犯错误的人”符号化为

()

A.B.B(x))

c.n

D.n-iB(x))

参考答案：【D】

38、下列语句中不是命题的只有()

A.鸡毛也能飞上天？

B.或重于泰山，或轻于鸿毛。

C.不经一事，不长一智。

D.牙好，胃口就好。

参考答案：【A】

39、下列式子正确的是()

A.(A-B)-C=A-(BUC)

B.A-(BUC)=(A-B)UC

C.-(A-B)=~(B-A)

D.参考答案：【A】

40、下列集合对所给的运算是封闭的只有()

A,非零整数集合Z*上的除法运算

B.全体nXn实可逆矩阵集合Mn(R)上的矩阵加法和乘法运算

C.全体nXn实矩阵集合Mn(R)上的矩阵加法和乘法运算

D.A={1,2,…，10},x*y=LCM(x,y),即x,y最小公倍数

参考答案：【C】

一、判断(共计50分，每题2.5分)

1、设〈G,。)是一个群.若存在从〈G,。〉至U〈H,*〉的满同态，则〈H,*〉

也构成群。

A.正确

B.错误

参考答案：【A】

2、完全图Kn没有割集，它的连通性能是最好的。

A.正确

B.错误

参考答案：【A】

3、一个从A到B的二元关系是有序偶的集合R,在每一个有序偶中，第一个元

素取自A,第二个元素取自Bo

A.正确

B.错误

参考答案：【A】

4、克鲁斯卡尔(Kruskal)算法可以求最小生成树。

A.正确

B.错误

参考答案：【A】

5、不同的生成树的基本割集可能不一样，但基本割集的个数是固定的。

A.正确

B.错误

参考答案：【A】

6、域是整环。

A.正确

B.错误

参考答案：【A】

7、大于100的整数集合可以表示为｛101,102,103,…｝。

A.正确

B.错误

参考答案：【A】

、不含有任何元素的集合，称为空集，记作

8Fo

A.正确

B.错误

参考答案：【A】

9、任何连通图G至少存在一棵生成树。

A.正确

B.错误

参考答案：【A】

10、强连通图一定是单向连通图。

A.正确

B.错误

参考答案：【A】

11、若关系R是对称的，则其关系图中若两个结点之间有弧线，就一定是有双向

两条弧。

A.正确

B.错误

参考答案：【A】

12、两个代数系统同构则两个集合元素间存在双射。

A.正确

B.错误

参考答案：【A】

13、图中度为零的结点称为孤立结点。

A.正确

B.错误

参考答案：【A】

14、一个代数系统的单位元、零元、逆元如存在，则必唯一。

A.正确

B.错误

参考答案：【A】

15、设，则的幕集是。

A.正确

B.错误

参考答案：【A】

16、具有条边的连通图最多具有个结点。

A.正确

B.错误

参考答案：【A】

17、树T的每一对结点之间有且仅有一条道路可通。

A.正确

B.错误

参考答案：【A】

18、设A、B为谓词公式，若A<->B是逻辑有效式，则称A和B是等值的，记作

A=>Bo

A.正确

B.错误

参考答案：【B】

19、只由一个孤立结点构成的图称为平凡图。

A.正确

B.错误

参考答案：【A】

20、上的普遍关系的关系矩阵是全1矩阵，而恒等关系的关系矩阵是单位矩

阵。

A.正确

B.错误

参考答案：【A】

二、单选（共计50分，每题2.5分）

21、下列整数集对于整除关系都构成偏序集，而能构成格的是（）

A.{I,2,3,4,5}

B.{1,2,3,6,12}

C.{2,3,7}

D.{I,2,3,7}

参考答案：【B】

22、从真值角度看，命题公式的全部类型是（）

A.永真式

B.永假式

C.永真式，永假式

D.永真式，永假式，可满足式

参考答案：【D】

23、下列集合关于所给定的运算成为群的是（）

A.已给实数a的正整数次毒的全体，且a{0,1,-1},关于数的乘法

B.所有非负整数的集合，关于数的加法

C.所有正有理数的集合，关于数的乘法

D.实数集，关于数的除法

参考答案：【C】

24、下列不一定是树的是（）

A.无回路的连通图

B.有n个结点，n-1条边的连通图

C.每对结点之间都有通路的图

D.连通但删去一条边则不连通的图

参考答案：【C】

25、下列函数中为双射的是（）

A.f：Z-*Z,f(j)=j(mod)

B.f：N-N,f(j)=

C.f：Z-*N,f(j)=|2j|+l

D.f：RfR,f(r)=2r-15

参考答案：【D】

26、设人={1,2,3,4,5},B={6,7,8,9,10},以下关系是从A到B的入射

函数的是()

A.f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}

B.f={<1,7>,<2,6>,<4,8>,<1,9>,<5Z1O>}

C.f={<lz6>,<2,7>,<4,9>,<3,8>}

D.f={<l,10>,<5,9>,<3,6>,<4,6>,<2,8>}

参考答案：【A】

27、设A(x):x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为

()

A.B.-1B(x))

C.-)

D.1-]B(x))

参考答案：【D】

28、设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2,

则该图的顶点数是()

A.3

B.4

C.5

D.6

参考答案：【B】

29、A,B是集合，P(A),P(B)为其基集，且，则P(A)CP⑻为()

A.B.C.D.参考答案：【B】

30、设M={x|fl(x)=0},N={x|f2(x)=0},则方程fl(x)•f2(x)=0的解为()

A.MON

B.MUN

C.MN

D.M-N

参考答案：【B】

31、设G是具有n个结点的无向简单图，若在G中存在一条汉密尔顿路，则G中

每一对结点的度数之和与n-1的关系为()

A.大于

B.大于等于

C.等于

D.小于

参考答案：【B】

32、在公式()F(x,y)—(y)G(x,y)中变元x是()

A.自由变元

B.约束变元

C.既是自由变元，又是约束变元

D.既不是自由变元，又不是约束变元

参考答案：【C】

33、下列集合对所给的运算是封闭的只有()

A.非零整数集合Z*上的除法运算

B.全体nXn实可逆矩阵集合Mn(R)上的矩阵加法和乘法运算

C.全体nXn实矩阵集合Mn(R)上的矩阵加法和乘法运算

D.A={1,2,…，10},x*y=LCM(x,y),即x,y最小公倍数

参考答案：【C】

34、设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是

()

A.-1PAQ

B.PA-]Q

C.P->-IQ

D.PV-)Q

参考答案：【B】

35、下列等价式正确的是()

A.11A

B.C.~|nA

D.参考答案：【C】

36、设H,K是群(G,)的子群，下面代数系统是(G,)的子群的是()

A.(HAK,)

B.(HUK,)

C.(K-H,)

D.(H-K,)

参考答案：【A】

37、在实数集合R上，下列定义的运算中不可结合的是()

A.a*b=a+b+2ab

B.a*b=a+b

C.a*b=a+b+ab

D.a*b=a-b

参考答案：【D】

38、命题公式(PA(P—Q))-Q是()

A.矛盾式

B.蕴含式

C.重言式

D.等价式

参考答案：【C】

39、下列命题公式为重言式的是()

A.pf(pVq)

B.(pVqpLq

C.qAnq

D.pf1q

参考答案：【A】

40、下列语句中不是命题的只有()

A.鸡毛也能飞上天？

B.或重于泰山，或轻于鸿毛。

C.不经一事，不长一智。

D.牙好，胃口就好。

参考答案：【A】

一、判断（共计50分，每题2.5分）

1、域是整环。

A.正确

B.错误

参考答案：【A】

2、大于100的整数集合可以表示为｛101,102,103,…｝。

A.正确

B.错误

参考答案：【A】

3、图中度为零的结点称为孤立结点。

A.正确

B.错误

参考答案：【A】

4、设,则的幕集是。

A.正确

B.错误

参考答案：【A】

5、若关系R是对称的，则其关系图中若两个结点之间有弧线，就一定是有双向

两条弧。

A.正确

B.错误

参考答案：【A】

6、两个代数系统同构则两个集合元素间存在双射。

A.正确

B.错误

参考答案：【A】

7、在格〈L,V,A）中，如果交运算对并运算是可分配的，则并运算对交运算

也是可分配的。

A.正确

B.错误

参考答案：【A】

8、一个从A到B的二元关系是有序偶的集合R,在每一个有序偶中，第一个元

素取自A,第二个元素取自Bo

A.正确

B.错误

参考答案：【A】

9、强连通图一定是单向连通图。

A.正确

B.错误

参考答案：【A】

10、克鲁斯卡尔(Kruskal)算法可以求最小生成树。

A.正确

B.错误

参考答案：【A】

11、在有补分配格〈L,V,A)中，任一元素ad[.的补元素是唯一的。

A.正确

B.错误

参考答案：【A】

12、设〈G,。)是一个群.若存在从〈G,。〉至I」<H,*)的满同态，则<H,*)

也构成群。

A.正确

B.错误

参考答案：【A】

13、不含有任何元素的集合，称为空集，记作F。

A.正确

B.错误

参考答案：【A】

14、设A、B为谓词公式，若A<->B是逻辑有效式，则称A和B是等值的，记作

A=>Bo

A.正确

B.错误

参考答案：【B】

15、连通且不含圈的图称为树。

A.正确

B.错误

参考答案：【A】

16、完全图Kn没有割集，它的连通性能是最好的。

A.正确

B.错误

参考答案：【A】

17、具有条边的连通图最多具有个结点。

A.正确

B.错误

参考答案：【A】

18、不同的生成树的基本割集可能不一样，但基本割集的个数是固定的。

A.正确

B.错误

参考答案：【A】

19、任何连通图G至少存在一棵生成树。

A.正确

B.错误

参考答案：【A】

20、只由一个孤立结点构成的图称为平凡图。

A.正确

B.错误

参考答案：【A】

二、单选(共计50分，每题2.5分)

21、具有4个结点的非同构的无向树的数目是()

A.2

B.3

C.4

D.5

参考答案：【A】

22、下面关于关系R的传递闭包t(R)的描述最确切的是()

A.t(R)是包含R的二元关系

B.t(R)是包含R的最小传递关系

C.t(R)是包含R的一个传递关系

D.t(R)是任何包含R的传递关系

参考答案：【B】

23、下列命题公式为重言式的是()

A.p—(pVq)

B.(pVqp)fq

C.qA-)q

D.p-*1q

参考答案：【A】

24、设人={1,2,3,4,5},B={6,7,8,9,10},以下关系是从A到B的入射

函数的是()

A.f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}

B.f={<lz7>,<2,6>,<4,8>z<l,9>,<5,10>}

C.f={<1,6>,<2,7>,<4,9>,<3,8>}

D.f={<l,10>,<5,9>,<3,6>,<4,6>,<2,8>}

参考答案：【A】

25、设，则有()

A.B.C.D.参考答案：【C】

26、下列式子正确的是()

A.(A-B)-C=A-(BUC)

B.A-(BUC)=(A-B)UC

C.-(A-B)=~(B-A)

D.参考答案：【A】

27、从真值角度看，命题公式的全部类型是()

A.永真式

B.永假式

C.永真式，永假式

D.永真式，永假式，可满足式

参考答案：【D】

28、下列语句中不是命题的只有()

A.鸡毛也能飞上天？

B.或重于泰山，或轻于鸿毛。

C.不经一事，不长一智。

D.牙好，胃口就好。

参考答案：【A】

29、下列等价式不正确的是（）

A.B.C.D.参考答案：【A】

30、下列等价式正确的是（）

A.1-|A

B.C.-]nA

D.参考答案：【C】

31、命题公式（PA（PfQ））fQ是（）

A.矛盾式

B.蕴含式

C.重言式

D.等价式

参考答案：【C】

32、设G是具有n个结点的无向简单图，若在G中存在一条汉密尔顿路，则G中

每一对结点的度数之和与n-1的关系为（）

A.大于

B.大于等于

C.等于

D.小于

参考答案：【B】

33、下列公式是前束范式的是（）

A.B.C.D.参考答案：【A】

34、在实数集合R上，下列定义的运算中不可结合的是（）

A.a*b=a+b+2ab

B.a*b=a+b

C.a*b=a+b+ab

D.a*b=a-b

参考答案：【D】

35、在公式（）F（x,y）—（y）G（x,y）中变元x是（）

A.自由变元

B.约束变元

C.既是自由变元，又是约束变元

D.既不是自由变元，又不是约束变元

参考答案：【C】

36、R={<1,4>,<2,3>,<3,1>,<4,3>},则下列不是t（R）中元素的是（）

A.<1,1>

B.<1,2>

C.<1,3>

D.<1,4>

参考答案：【B】

37、设H,K是群（G.）的子群，下面代数系统是（G,）的子群的是（）

A.(HAK,)

B.(HUK,)

C.(K-H,)

D.(H-K,)

参考答案：【A】

38、设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2,

则该图的顶点数是()

A.3

B.4

C.5

D.6

参考答案：【B】

39、A,B是集合，P(A),P(B)为其毒集，且，则P(A)np(B)为()

A.B.C.D.参考答案：【B】

40、下列整数集对于整除关系都构成偏序集，而能构成格的是()

A,{I,2,3,4,5}

B.{1,2,3,6,12}

C.{2,3,7}

D.{I,2,3,7}

参考答案：【B】

一、判断(共计50分，每题2.5分)

1、若关系R是对称的，则其关系图中若两个结点之间有弧线，就一定是有双向

两条弧。

A,正确

B.错误

参考答案：【A】

2、树T的每一对结点之间有且仅有一条道路可通。

A.正确

B.错误

参考答案：【A】

3、在有补分配格〈L,V,A)中，任一元素aGL的补元素是唯一的。

A.正确

B.错误

参考答案：【A】

4、两个代数系统同构则两个集合元素间存在双射。

A.正确

B.错误

参考答案：【A】

5、设〈G,。)是一个群.若存在从〈G,。〉至U〈H,*〉的满同态，则＜H,*)

也构成群。

A.正确

B.错误

参考答案：【A】

6、连通且不含圈的图称为树。

A.正确

B.错误

参考答案：【A】

7、设,则的累集是。

A.正确

B.错误

参考答案：【A】

8、域是整环。

A.正确

B.错误

参考答案：【A】

9、只由一个孤立结点构成的图称为平凡图。

A.正确

B.错误

参考答案：【A】

10、在格〈L,V,A）中，如果交运算对并运算是可分配的，则并运算对交运

算也是可分配的。

A.正确

B.错误

参考答案：【A】

11、图中度为零的结点称为孤立结点。

A.正确

B.错误

参考答案：【A】

12、不含有任何元素的集合，称为空集，记作F。

A.正确

B.错误

参考答案：【A】

13、一个代数系统的单位元、零元、逆元如存在，则必唯一。

A.正确

B.错误

参考答案：【A】

14、大于100的整数集合可以表示为｛101,102,103,…｝。

A.正确

B.错误

参考答案：【A】

15、设A、B为谓词公式，若A<->B是逻辑有效式，则称A和B是等值的，记作

A=>Bo

A.正确

B.错误

参考答案：【B】

16、任何连通图G至少存在一棵生成树。

A.正确

B.错误

参考答案：【A】

17、克鲁斯卡尔(Kruskal)算法可以求最小生成树。

A.正确

B.错误

参考答案：【A】

18、上的普遍关系的关系矩阵是全1矩阵，而恒等关系的关系矩阵是单位矩

阵。

A,正确

B.错误

参考答案：【A】

19、强连通图一定是单向连通图。

A.正确

B.错误

参考答案：【A】

20、不同的生成树的基本割集可能不一样，但基本割集的个数是固定的。

A.正确

B.错误

参考答案：【A】

二、单选(共计50分，每题2.5分)

21、设A(x):x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为

()

A.B.~|nB(x))

C.~|

D.n1B(x))

参考答案：【D】

22、设H,K是群(G,)的子群，下面代数系统是(G,)的子群的是()

A.(HAK,)

B.(HUK,)

C.(K-H,)

D.(H-K,)

参考答案：【A】

23、下列函数中为双射的是()

A.f：Z-*Z,f(j)=j(mod)

B.f：N-N,f(j)=

C.f：Z-*N,f(j)=|2j|+l

D.f：RfR,f(r)=2r-15

参考答案：【D】

24、设M={x|fl(x)=0},N={x|f2(x)=0},则方程fl(x)•f2(x)=0的解为()

A.MON

B.MUN

C.MN

D.M-N

参考答案：【B】

25、下列四个格，是分配格的是()

A.B.C.D.参考答案：【C】

26、设无向图中有6条边，有一个3度顶点和一