离散结构复习题2021年

《离散结构》复习题

一.单项选择题

1.设5=伯力},则S上可定义的二元运算的个数是（）

A.4；B.8;C.16；D.32。

2.下列数学结构中是代数系统的是（）

A.＜N-{0},x,­?＞；B.＜R-{0},+,x＞；C.＜N,+,一＞;D.＜N,+,x＞；

3.A={x[x＜100且为质数},在A上定义运算“*”和“#"如下:Vx.ySA,x*y=max{x,y},

x#y=lcm（x,y）,,其中lcm（x,y）表示x与y的最小公倍数。以下说法正确的是（）

A.＜A,*＞是代数系统，＜A,#＞不是代数系统；

B.＜A,*＞不是代数系统，＜A,#＞是代数系统；

C.＜A,*＞是代数系统，＜A,#＞也是代数系统；

D.＜A,*＞与＜A,#＞都不是代数系统。

4.设Z为整数集合，下列集合关于数的加法运算不能构成＜Z,+＞的子代数系统的是（）

A.N（自然数集合）；B.{2k|kez）;

C.{2k+1|€Z}；D.{3m+2n|m,nez}。

5.在自然数集合N上，下列哪个运算是可交换的（）

A.a*b=a-b；B.a*b=max{a,b}；C.a*b=a+2b；D.a*b=a。

6.在自然数集合N上，下列哪个运算是可结合的（）

A.a*b=a-b；B.a*b=max{a,b}；C.a*b=a+2b；D.a*b=|a-b|»

7.在自然数集合N上，下列哪个运算满足基等律（）

A.a*b=a-b；B.a*b=max{a,b}；C.a*b=a+2b；D.a*b=|a-b|＜,

8.在自然数集合N上，下列哪个运算满足消去律（）

A.a*b=b；B.a*b=max{a,b}；C.a*b=a+2b；D.a*b=|a-b|o

10.在代数系统＜N"③6＞中关于运算“＜8＞6”，下列元素中不是等基元的是（）。

A.1；B.2；C.3；D.4。

11.集合A={a,b,c,d}上的代数运算“*”如下表所示，则关于运算“*”的幺元为

*abcd

aaaaa

babcd

cbcab

dbdcd

A.a；B.b；C.c；D.do

12.设＜{a,b,c},*＞为代数系统，“*”运算如;，则零元为（）

*abc

aabc

bbac

cccc

A.aI3.bC.cD.没有

13.集合A={a,b,c,d}上的代数运算“*”如下表所示，则元素c的逆元为

*abcd

aaaaa

babcd

cacdb

dadbc

A.a；B.b；C.c；D.do

14.代数系统<Ns,<85〉中元素4的逆元是（）。

A.l；B.2；C.3；D.4o

15.设8={2,4,6,8},代数系统<B,⑼o>中关于运算“⑼o”的幺元是（）

A.2；B.4；C.6；D.8o

16.设$={14,2」,3」,4},“*”为普通乘法，则<S,*>是（）

A.代数系统，之不疑篦B.半群，不是群；C.群；D.都不是。

17.设Z为整数集合，以下代数系统中哪个不是独异点（）

A.<Z,x>；B.<{2k|keZ},x>；C.<{2k+l|keZ},x>；D.<{3m+5n|m,neZ},x>o

18.设R+为正实数集，<R+,x>是一个群，则下列集合关于数的乘法运算构成群<R+,x>的子

群的是（）

A.{R+中的有理数};B.{R+中的无理数};C.{R+中的自然数};D.{1,2,3}。

19.设Q为有理数集，Q上的二元运算“*”定义为：a*b=a+b-ab,则在代数系统<Q,*>中，

单位元是（）。

A.a；B.b；C.1；D.0。

20.设Q为有理数集，Q上的二元运算*定义为：a*b=a+b-ab,则在代数系统<Q,*>中，

零元是（）o

A.a；B.b；C.1；D.0。

21.下列几个代数系统中，不是群的是（）

A.<Z,+>；B.<Q,+>；C.<R,+>；D.<N,+>。

22.设a,b,x,yeG,在群<G,*>中方程ax=b,ya=b都有解，这个解是（）

A.不是唯一的；B.不一定唯一；C.唯一的；D.两个方程的解相同。

'0101'

23.设有向图G=<V,E>,V={q,V2,V3,V4},其邻接矩阵A=:[]]，则（）

1000

A.结点V3可达结点V4，但V4不可达V3；B.结点V3不可达结点V4,但V4可达V3；

C.结点V3不可达结点V4，V4也不可达V3；D.结点V3可达结点V4，V4也可达V3。

24.设有向图D=<V,E>,V={a,b,c,d,e,f},E={<a,b>,<b,c>,<a,e>,<c,d>,<d,f>,<e,d>,<f,e>},

则图D是（）。

A.非连通图；B.弱连通图，不是单向连通图；

C.单向连通图，不是强连通图；D,强连通图。

25.下图中，哪个是强连通图（)

(A)(B)(C)(D)

26.奇数个结点的无向完全图K”(n＞2)()

A.是欧拉图，不是哈密顿图；B.不是欧拉图，是哈密顿图；

C.是欧拉图，也是哈密顿图；D.不是欧拉图，也不是哈密顿图。

27.设G是5个顶点的无向完全图，则从G中删去()条边可以得到树。

A.10；B.6；C.5；D.4o

28.一个含4个顶点的无向图中有3个顶点的度数分别为1,2,3,则第4个顶点的度数不可能

是()

A.0；B.1；C.2；D.4。

29.若供选择答案中的数值表示一个简单图中各顶点的度数，能画出图的是()

A.(1,223,4,5)；B.(1,2,3,4,5,6)；C.(1,1,2,2,3,3)；D.(1,3,34,5,6)。

30.哈密顿回路是()

A,是基本回路，不一定是简单回路；B,是简单回路，不一定是基本回路；

C.既是基本回路也是简单回路；D.既不是基本回路也不是简单回路。

31.欧拉回路是()

A.是基本回路，不一定是简单回路；B.是简单回路，不一定是基本回路；

C.既是基本回路也是简单回路D.既不是基本回路也不是简单回路。

32.设G为连通的无向图，若G仅有2个结点的度数是奇数，则G一定具有()

A.欧拉通路；B.欧拉回路;C.哈密顿通路；D.哈密顿回路。

'o11r

1010

33.设图G的邻接矩阵为，则G的结点数与边数分别为()

1101

1010_

A.4,5；B.4,10；C.5,6；D.5,8o

34.图T是一棵根树，则(

A.T一定是连通的；B.T一定是强连通的；

C.T只有一个结点的出度为0；D.T只有一个结点的入度为1,

二、填空题

1.群＜N5-{0},®5＞中元素2的阶数分别为。

2.设＜S,*＞是群，则S中除外，不可能有别的等哥元。

3.在模10加法群＜NK),㊉io＞中，元素5的阶为,元素6的阶为。

4.在群＜N7-{O},©o＞中，元素5的阶为—,元素6的阶为o

5.设Z为整数集，Va,be乙a*b=a+b+l,关于运算“*”的幺元是一，a的逆元at

6.在模7加群＜N7，㊉7＞中，2-4=。

7.在群＜N7-{O},8）IO＞中，2-4=。

8.设集合A={1,3,5},运算“＜8＞6”为模6乘法，在代数系统＜A,③6＞中关于运算'电6”的零元

是。

9.设集合A={0,2,4},运算为模6乘法，在代数系统＜A,a＞中关于运算出小的单位元

是o

10.设集合A={2,4,6},A上的二元运算“*”定义为：Va,beA,a*b=max{a,b},则代数系统

＜A,*＞中，零元是。

H.设集合A={a,b},则代数系统＜P（A）,U,n＞中关于运算“u”的幺元是，关于运算“rr

的幺元是o

12.设＜G,*＞是群，若a,b,xeG,解方程a*x=b,得x=。

13.4阶3条边的所有非同构的无向简单图共有个。

14.n阶有向完全图的顶点v的度数deg（v）=。

15.n阶无向简单图的顶点的度数最多为。

16.无向图G是由k（k"）棵树组成的森林，至少要添加条边才能使G成为一棵树。

17.4阶无向连通图至多有棵不同构的生成树。

18.设G是具有7个结点的树，则G中增加条边才能把G变成完全图。

'0101'

_1011

19.设有向图G=＜V,E＞,V={v”V2,V%vj,邻接矩阵人=]]°0，则％的入度=,

1000

V,的出度=。

20.树T有8片树叶，2个3度分支点，其余的分支点都是4度，T有个4度分支点。

21.已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则图G的

边数是o

22.在一颗根数中，仅有一个结点的入度为—，称为树根，其余结点的入度均为o

三、判断题

1.设A是非空集合，则＜P（A）,U＞是独异点。（）

2.群中存在唯一的零元。（）

3.代数系统中一个元素若有左逆元，则该元素一定有右逆元。（）

4.如果集合A上存在关于运算“*”的幺元，则此幺元必为关于运算“*”的等基元。（）

5.如果集合A上存在关于运算“*”的零元，则此零元必为关于运算“*”的等幕元。（）

6.设集合A={0,2}=N4，则＜A,㊉4＞是半群＜N4,㊉4＞的子半群。（）

7.n阶有限群＜G,*＞中，幺元的阶是1,其它所有元素的阶都大于1且不超过n。（）

8.设集合A={0,2,4}qN6，则＜A,＜8）6＞是独异点＜用,③6＞的子独异点。（）

9.已知代数系统＜S,*＞有多于一个以上的等基元，则＜S,*＞一定不是群。（）

10.如果一个有向图D是欧拉图，则D是强连通的。（）

11.若无向图G的一个生成子图是连通图，则G必为连通图。（）

12.无向树T中的每对结点之间存在唯一的一条通路。()

13.若图G为含有n(n＞2)个结点的树，则G中至少有两个叶结点。()

14.若n阶图G是连通图，则图G中的边数mNn-1。()

15.若两图结点数相同，边数相等，度数相同的结点数相等，则两图是同构的。()

16.无平行边的图是简单图。()

17.设G是具有5个顶点，11条边的无向图，则G是简单图。()

四、计算证明题：

1.对于整数集Z,定义运算“*”：x*y=x+y-2.证明＜Z,*＞是群。

2.设集合G={25eZ},运算“x”表示普通数的乘法。证明＜G,x＞是群。

3.已知整数加法群＜Z,+＞,定义集合H={2n+3m|n,meZ},证明＜H,+＞是＜Z,+＞的子群。

4.设集合A={1,2,345,6,7,8,9},定义A上运算“*”：x*y=min{x,y}.证明运算“*”满足结合

律，交换律，鬲等律。

5.已知代数系统＜Z,*＞,其中对于乙a*b=ab+a+b。证明运算“*”满足结合律，交换律。

求关于运算“*”的等基元。

6.设集合G={2,4,6,8},*是定义在G上的模10乘法，即Va,b&G,a*b=(ab)(mod10)«已

知＜G,*＞是半群。

(1)构造＜G,*＞的运算表。

(2)证明＜G,*＞是有限群。

(3)求出＜G,*＞的所有子群。

7.设集合A={a,b},“㊉”为集合对称差运算，即对任意集合S,T,S㊉T=(S-T)U(T-S)。已知

＜P(A),㊉〉是半群。

(1)歹岫＜P(A),㊉〉的运算表。

(2)证明＜P(A),㊉〉是群。

(3)写出＜P(A),㊉〉的所有子群。

8.给定代数系统＜A,*＞,其中A={0,60,120,180,240,300},*是定义在A上的模360

加法，即Ta,beA,a*b=(a+b)(mod360)»已知＜A,*＞是半群。

(1)列出＜A,*＞的运算表。

(2)证明＜A,*＞是群。

(3)写出＜A,*＞的所有子群。

9.设群＜5,⑼i＞,其中S={1,3,4,5,9},“⑼J是定义在S上的模11乘法。

(1)列出＜S,*＞的运算表。

(2)指出＜S,*＞的幺元。

(3)求出＜S,*＞中每个元素的逆元和阶，填入下表。

X13459

r1

(4)求出＜S,*＞的所有子群。

10.给出无向图G如下：

(1)画出图G的一棵生成树。

(2)写出图G的邻接矩阵，顶点次序为A