離散結(jié)構(gòu)復習題2021年_第1頁
離散結(jié)構(gòu)復習題2021年_第2頁
離散結(jié)構(gòu)復習題2021年_第3頁
離散結(jié)構(gòu)復習題2021年_第4頁
離散結(jié)構(gòu)復習題2021年_第5頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

《離散結(jié)構(gòu)》復習題

一.單項選擇題

1.設(shè)5=伯力},則S上可定義的二元運算的個數(shù)是()

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

2.下列數(shù)學結(jié)構(gòu)中是代數(shù)系統(tǒng)的是()

A.<N-{0},x,-?>;B.<R-{0},+,x>;C.<N,+,一>;D.<N,+,x>;

3.A={x[x<100且為質(zhì)數(shù)},在A上定義運算“*”和“#"如下:Vx.ySA,x*y=max{x,y},

x#y=lcm(x,y),,其中l(wèi)cm(x,y)表示x與y的最小公倍數(shù)。以下說法正確的是()

A.<A,*>是代數(shù)系統(tǒng),<A,#>不是代數(shù)系統(tǒng);

B.<A,*>不是代數(shù)系統(tǒng),<A,#>是代數(shù)系統(tǒng);

C.<A,*>是代數(shù)系統(tǒng),<A,#>也是代數(shù)系統(tǒng);

D.<A,*>與<A,#>都不是代數(shù)系統(tǒng)。

4.設(shè)Z為整數(shù)集合,下列集合關(guān)于數(shù)的加法運算不能構(gòu)成<Z,+>的子代數(shù)系統(tǒng)的是()

A.N(自然數(shù)集合);B.{2k|kez);

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

5.在自然數(shù)集合N上,下列哪個運算是可交換的()

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

6.在自然數(shù)集合N上,下列哪個運算是可結(jié)合的()

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

7.在自然數(shù)集合N上,下列哪個運算滿足基等律()

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

8.在自然數(shù)集合N上,下列哪個運算滿足消去律()

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

10.在代數(shù)系統(tǒng)<N"③6>中關(guān)于運算“<8>6”,下列元素中不是等基元的是()。

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

11.集合A={a,b,c,d}上的代數(shù)運算“*”如下表所示,則關(guān)于運算“*”的幺元為

*abcd

aaaaa

babcd

cbcab

dbdcd

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

12.設(shè)<{a,b,c},*>為代數(shù)系統(tǒng),“*”運算如;,則零元為()

*abc

aabc

bbac

cccc

A.aI3.bC.cD.沒有

13.集合A={a,b,c,d}上的代數(shù)運算“*”如下表所示,則元素c的逆元為

*abcd

aaaaa

babcd

cacdb

dadbc

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

14.代數(shù)系統(tǒng)<Ns,<85〉中元素4的逆元是()。

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

15.設(shè)8={2,4,6,8},代數(shù)系統(tǒng)<B,⑼o>中關(guān)于運算“⑼o”的幺元是()

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

16.設(shè)$={14,2」,3」,4},“*”為普通乘法,則<S,*>是()

A.代數(shù)系統(tǒng),之不疑篦B.半群,不是群;C.群;D.都不是。

17.設(shè)Z為整數(shù)集合,以下代數(shù)系統(tǒng)中哪個不是獨異點()

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

18.設(shè)R+為正實數(shù)集,<R+,x>是一個群,則下列集合關(guān)于數(shù)的乘法運算構(gòu)成群<R+,x>的子

群的是()

A.{R+中的有理數(shù)};B.{R+中的無理數(shù)};C.{R+中的自然數(shù)};D.{1,2,3}。

19.設(shè)Q為有理數(shù)集,Q上的二元運算“*”定義為:a*b=a+b-ab,則在代數(shù)系統(tǒng)<Q,*>中,

單位元是()。

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

20.設(shè)Q為有理數(shù)集,Q上的二元運算*定義為:a*b=a+b-ab,則在代數(shù)系統(tǒng)<Q,*>中,

零元是()o

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

21.下列幾個代數(shù)系統(tǒng)中,不是群的是()

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

22.設(shè)a,b,x,yeG,在群<G,*>中方程ax=b,ya=b都有解,這個解是()

A.不是唯一的;B.不一定唯一;C.唯一的;D.兩個方程的解相同。

'0101'

23.設(shè)有向圖G=<V,E>,V={q,V2,V3,V4},其鄰接矩陣A=:[]],則()

1000

A.結(jié)點V3可達結(jié)點V4,但V4不可達V3;B.結(jié)點V3不可達結(jié)點V4,但V4可達V3;

C.結(jié)點V3不可達結(jié)點V4,V4也不可達V3;D.結(jié)點V3可達結(jié)點V4,V4也可達V3。

24.設(shè)有向圖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.奇數(shù)個結(jié)點的無向完全圖K”(n>2)()

A.是歐拉圖,不是哈密頓圖;B.不是歐拉圖,是哈密頓圖;

C.是歐拉圖,也是哈密頓圖;D.不是歐拉圖,也不是哈密頓圖。

27.設(shè)G是5個頂點的無向完全圖,則從G中刪去()條邊可以得到樹。

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

28.一個含4個頂點的無向圖中有3個頂點的度數(shù)分別為1,2,3,則第4個頂點的度數(shù)不可能

是()

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

29.若供選擇答案中的數(shù)值表示一個簡單圖中各頂點的度數(shù),能畫出圖的是()

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.設(shè)G為連通的無向圖,若G僅有2個結(jié)點的度數(shù)是奇數(shù),則G一定具有()

A.歐拉通路;B.歐拉回路;C.哈密頓通路;D.哈密頓回路。

'o11r

1010

33.設(shè)圖G的鄰接矩陣為,則G的結(jié)點數(shù)與邊數(shù)分別為()

1101

1010_

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

34.圖T是一棵根樹,則(

A.T一定是連通的;B.T一定是強連通的;

C.T只有一個結(jié)點的出度為0;D.T只有一個結(jié)點的入度為1,

二、填空題

1.群<N5-{0},?5>中元素2的階數(shù)分別為。

2.設(shè)<S,*>是群,則S中除外,不可能有別的等哥元。

3.在模10加法群<NK),十io>中,元素5的階為,元素6的階為。

4.在群<N7-{O},?o>中,元素5的階為—,元素6的階為o

5.設(shè)Z為整數(shù)集,Va,be乙a*b=a+b+l,關(guān)于運算“*”的幺元是一,a的逆元at

6.在模7加群<N7,十7>中,2-4=。

7.在群<N7-{O},8)IO>中,2-4=。

8.設(shè)集合A={1,3,5},運算“<8>6”為模6乘法,在代數(shù)系統(tǒng)<A,③6>中關(guān)于運算'電6”的零元

是。

9.設(shè)集合A={0,2,4},運算為模6乘法,在代數(shù)系統(tǒng)<A,a>中關(guān)于運算出小的單位元

是o

10.設(shè)集合A={2,4,6},A上的二元運算“*”定義為:Va,beA,a*b=max{a,b},則代數(shù)系統(tǒng)

<A,*>中,零元是。

H.設(shè)集合A={a,b},則代數(shù)系統(tǒng)<P(A),U,n>中關(guān)于運算“u”的幺元是,關(guān)于運算“rr

的幺元是o

12.設(shè)<G,*>是群,若a,b,xeG,解方程a*x=b,得x=。

13.4階3條邊的所有非同構(gòu)的無向簡單圖共有個。

14.n階有向完全圖的頂點v的度數(shù)deg(v)=。

15.n階無向簡單圖的頂點的度數(shù)最多為。

16.無向圖G是由k(k")棵樹組成的森林,至少要添加條邊才能使G成為一棵樹。

17.4階無向連通圖至多有棵不同構(gòu)的生成樹。

18.設(shè)G是具有7個結(jié)點的樹,則G中增加條邊才能把G變成完全圖。

'0101'

_1011

19.設(shè)有向圖G=<V,E>,V={v”V2,V%vj,鄰接矩陣人=]]°0,則%的入度=,

1000

V,的出度=。

20.樹T有8片樹葉,2個3度分支點,其余的分支點都是4度,T有個4度分支點。

21.已知圖G中有1個1度結(jié)點,2個2度結(jié)點,3個3度結(jié)點,4個4度結(jié)點,則圖G的

邊數(shù)是o

22.在一顆根數(shù)中,僅有一個結(jié)點的入度為—,稱為樹根,其余結(jié)點的入度均為o

三、判斷題

1.設(shè)A是非空集合,則<P(A),U>是獨異點。()

2.群中存在唯一的零元。()

3.代數(shù)系統(tǒng)中一個元素若有左逆元,則該元素一定有右逆元。()

4.如果集合A上存在關(guān)于運算“*”的幺元,則此幺元必為關(guān)于運算“*”的等基元。()

5.如果集合A上存在關(guān)于運算“*”的零元,則此零元必為關(guān)于運算“*”的等幕元。()

6.設(shè)集合A={0,2}=N4,則<A,十4>是半群<N4,十4>的子半群。()

7.n階有限群<G,*>中,幺元的階是1,其它所有元素的階都大于1且不超過n。()

8.設(shè)集合A={0,2,4}qN6,則<A,<8)6>是獨異點<用,③6>的子獨異點。()

9.已知代數(shù)系統(tǒng)<S,*>有多于一個以上的等基元,則<S,*>一定不是群。()

10.如果一個有向圖D是歐拉圖,則D是強連通的。()

11.若無向圖G的一個生成子圖是連通圖,則G必為連通圖。()

12.無向樹T中的每對結(jié)點之間存在唯一的一條通路。()

13.若圖G為含有n(n>2)個結(jié)點的樹,則G中至少有兩個葉結(jié)點。()

14.若n階圖G是連通圖,則圖G中的邊數(shù)mNn-1。()

15.若兩圖結(jié)點數(shù)相同,邊數(shù)相等,度數(shù)相同的結(jié)點數(shù)相等,則兩圖是同構(gòu)的。()

16.無平行邊的圖是簡單圖。()

17.設(shè)G是具有5個頂點,11條邊的無向圖,則G是簡單圖。()

四、計算證明題:

1.對于整數(shù)集Z,定義運算“*”:x*y=x+y-2.證明<Z,*>是群。

2.設(shè)集合G={25eZ},運算“x”表示普通數(shù)的乘法。證明<G,x>是群。

3.已知整數(shù)加法群<Z,+>,定義集合H={2n+3m|n,meZ},證明<H,+>是<Z,+>的子群。

4.設(shè)集合A={1,2,345,6,7,8,9},定義A上運算“*”:x*y=min{x,y}.證明運算“*”滿足結(jié)合

律,交換律,鬲等律。

5.已知代數(shù)系統(tǒng)<Z,*>,其中對于乙a*b=ab+a+b。證明運算“*”滿足結(jié)合律,交換律。

求關(guān)于運算“*”的等基元。

6.設(shè)集合G={2,4,6,8},*是定義在G上的模10乘法,即Va,b&G,a*b=(ab)(mod10)?已

知<G,*>是半群。

(1)構(gòu)造<G,*>的運算表。

(2)證明<G,*>是有限群。

(3)求出<G,*>的所有子群。

7.設(shè)集合A={a,b},“十”為集合對稱差運算,即對任意集合S,T,S十T=(S-T)U(T-S)。已知

<P(A),十〉是半群。

(1)歹岫<P(A),十〉的運算表。

(2)證明<P(A),十〉是群。

(3)寫出<P(A),十〉的所有子群。

8.給定代數(shù)系統(tǒng)<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.設(shè)群<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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論