北郵離散數(shù)學(xué)期末復(fù)習(xí)題

1、學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考北郵離散數(shù)學(xué)期末復(fù)習(xí)題第一章集合論一、判斷題(1)空集是任何集合的真子集.(錯)(2)他是空集.(錯)(3)awa,a(對)(4)設(shè)集合A=42,l,28則1,212A.(對)(5)如果a正A=B,則a更A或a更B.(錯)解a是A=B則awA.B=AcB,即awA且awB,所以a是A且a叁B(6)如果AUB=B,則A=B.(對)設(shè)集合A=ai,a2,a3,B=6也笛3,則A父B=<a1,b1A,<a2,b2A<a3,b3a(錯)(8)設(shè)集合A=0,1,則P=<®,0a,(電1>,<0,0>,<0,1>是

2、2A到A的關(guān)系.(對)解2A=*0,1,a,2AA=：,0,：,1j0,0”0,1J1,01,1-：A,0jA,1(9)關(guān)系的復(fù)合運(yùn)算滿足交換律.(錯)(10)PoP=P是集合A上的關(guān)系P具有傳遞性的充分必要條件.(錯)(11)設(shè)P是集合A上的傳遞關(guān)系，則也是A上的傳遞關(guān)系.(對)(12)集合A上的對稱關(guān)系必不是反對稱的.(錯)(13)設(shè)P1，P2為集合A上的等彳關(guān)系，則PcP2也是集合A上的等彳關(guān)系(對)(14)設(shè)P是集合A上的等價關(guān)系，則當(dāng)<a,bwP時，ap=bp(對)P0戶0=P。(15)設(shè)%p2為集合A上的等價關(guān)系，則(錯)二、單項(xiàng)選擇題(1)設(shè)R為實(shí)數(shù)集合，下列集合中哪一個不

3、是空集(A)A.&|x2-1=0，且xwrB.&|x2+9=0，且xwr)C.4|x=x+1，且xwR)d.x|x2=-1，且xwR)學(xué)習(xí)資料(2)設(shè)A,B為集合，若AB=4，則一定有A. B= B .B#4 C.(3)下列各式中不正確的是A. B B .C.A B D. A = B(C )；.，二。 D. 。三<', )(4)設(shè)A = a,a,則下列各式中錯誤的是A.右< 2A B . a=2A C. 4aw 2A D.'a：'2A設(shè)A = 2,B=a,b,c, C=L,d,則 Am(BPIC)為A. <c,1>, <2,

4、c> B . <1,0, < 2, c>C. L1,c ，:二 c,2 襄 D. 1； c,1 ., ： c,2(6)設(shè)慶=0, b, B =l, b, 3,則AU B的恒等關(guān)系為(A )A. <0,0 >, <1,1 >,<b,b >, <3,3 U B . <0,0 >,<1,1 >,<3,3 UC. L0,0 , ：b,b ,：二3,3 .) D.L 0,1 ,：二 1,b .,:二 b,3 ,：二 3,0 j(7)設(shè)A=Qb,c上的二元關(guān)系如下，則具有傳遞性的為(D)A. P1=匚二a,c,

5、:二c,a,:二a,b,：b,aJB. 72-1；a,c,:二c,aC. P3-：a,b,：c,c，:b,a，:：b,cD. ：'4-I；a,aJ(8)設(shè)P為集合A上的等價關(guān)系，對任意awA,其等價類a】p為(b)A.空集； B .非空集；C.(9)映射的復(fù)合運(yùn)算滿足A.交換律 B .結(jié)合律 C.(10)設(shè)A, B是集合，則下列說法中(A. A至ij B的關(guān)系都是A至ij B的映射B. A到B的映射都是可逆的C. A到B的雙射都是可逆的D. A二B時必不存在 A到B的雙射是否為空集不能確定； D.x|x A.(B )嘉等律 D.分配律C )是正確的.（11）設(shè)A是集合，則（B）成立.A

6、#2a=2#aAB.Xw2A修X工AC.你k2AD.bk2A（12）設(shè)A是有限集（#A=n）,則A上既是E又是的關(guān)系共有（B）A. 0個B. 1個C. 2個D. n個三、填空題1 .設(shè)A=1,2,1,2,則2A=.填2A=,1,2,1,2,1,2,1,1,2,2,1,2,A2 .設(shè)A=電螫,則2A=.填2A=*,*,*,A3 .設(shè)集合A,B中元素的個數(shù)分別為#A=5,#B=7,且#(AuB)=9,則集合AcB中元素的個數(shù)#(AcB)=.34 .設(shè)集合A=x|1ExW100,x是4的倍數(shù),xwZ,B=x|1ExE100,x是5的倍數(shù)，xwZ,則AUB中元素的個數(shù)為.405 .設(shè)A=a,b,P是2

7、A上的包含于關(guān)系，則有P=.：，:二，a,:二，b,二，A，：a,a,二a,A,二b,b,：二b,A,:二A,A6 .設(shè)耳，2為集合A上的二元關(guān)系，則巳迅=P2°P17 .集合A上的二元關(guān)系P為傳遞的充分必要條件是.P口P1P8 .設(shè)集合A=6,1,2汪的關(guān)系R=<0,2>,<2,0'及集合A到集合B=0,2,4的關(guān)系P2=<a,b>|<a,b>wAmB且a,bAnB）則P1。P2=填：二0,0,<0,2,:二2,0,:二2,2四、解答題1 .設(shè)A=a,b,c,d,A上的關(guān)系P=二a,a，二b,b，二c,c，二d,d',

8、:a,b,：:：b,a，二c,d，二d,c(1)寫出P的關(guān)系矩陣；(2)驗(yàn)證P是A上的等價關(guān)系；(3)求出A的各元素的等價類。解(1)P的關(guān)系矩陣為(2)從p的關(guān)系矩陣可知: 又由于P是自反的和對稱的。<0或p。p = p滿足 所以P是傳遞的。1010因?yàn)镻是自反的、對稱的和傳遞的，所以(3) a=b=a,b, c=d=c,dP是A上的等價關(guān)系。2.設(shè)集合A =1,2,3,6,8,12,24,36 , 2是A上的整除關(guān)系,(1) 寫出P的關(guān)系矩陣M p；(2) 畫出偏序集< A, P A的哈斯圖;(3) 求出A的子集B =2,3,6的最小上界和最大下界。解：(1)00M p =01

9、111110 1110 110 10 0 10 10 0 0 1 01111111110(2)<0 0 0 0 0 00 1J(3)lubB=6,glbB=1五、證明題1.設(shè)R,p2為集合A上的等價關(guān)系，試證Pqp2也是集合A上的等價關(guān)系。證明：由于P1，P2是自反的，所以對任意awA,ca,aP，<a,a>wP2,因而<a,ap1cp2,即P1cP2是自反的。若<a,b*PcP2,則<a,b*P1，<a,b*p?，由于P1，P2是對稱的，所以<b,a4,<b,aP2,從而<b,aPqP2,即PqP2是對稱的。若<a,ba,cb

10、,cRcP2,則<a,ba,<b,cP，<a,ba,<b,c*P2,由于P1，P2是傳遞的，所以<a,c>P1,<a,c>£P2,從而<a,cP1cp2,即P1cP2是傳遞的。由于RcP2是自反的、對稱的和傳遞的，所以P2是等價關(guān)系。第二章代數(shù)系統(tǒng)一、判斷題（1）集合A上的任一運(yùn)算對A是封閉的.（對）（2）代數(shù)系統(tǒng)的零元是可逆元.（錯）（3）設(shè)A是集合，:AMATA,a°b=b，則。是可結(jié)合的.（對）（4）設(shè)a,b是代數(shù)系統(tǒng)A,的元素，如果a°b=b'a=e（e是該代數(shù)系統(tǒng)的單位元），則4a=b.（對）

11、設(shè)a,b是群彳G,：的元素，則（a匕尸=a匕.（錯）222（6）設(shè)<G>是群.如果又于任意a,b=G,有（ab）=ab，則<G,0是阿貝爾群.（對）（7）設(shè)L,ha>是格，則運(yùn)算¥滿足曷等律.（對）（8）設(shè)集合A=a,b,則<4,a,b,A,5cA是格.（對）（9）設(shè)<B,¥,a,a是布爾代數(shù)，則<B,ha>是格.二、單項(xiàng)選擇題（1）在整數(shù)集Z上，下列哪種運(yùn)算是可結(jié)合的（B）A.a°b=a-bB.ab=maxa,bC.ab=a2bD.ab=|a-b|（2）下列定義的實(shí)數(shù)集R上的運(yùn)算*中可結(jié)合的是.（C）A. a*b=

12、a+abB. a*b=a+2abC. ab=bD. a*b=|a+b其中，+,II分別為實(shí)數(shù)的加法、乘法和取絕對值運(yùn)算.（3）設(shè)集合A=/2,3,4,，10,下面定義的哪種運(yùn)算關(guān)于集合A不是封閉的（D）A. xy=maxx,yB. xy=minx,yC. x©y=GCDx,y,即x,y的最大公約數(shù)D. x°y=LCMx,y,即x,y的最小公倍數(shù)（4）下列哪個集關(guān)于減法運(yùn)算是封閉的（B）A.N（自然數(shù)集）；B.2x|xwZ（整數(shù)集）；C.2x+1|xWZ；D.x|x是質(zhì)數(shù).（5）設(shè)Q是有理數(shù)集，在Q定義運(yùn)算*為2*b=a+bab,則（Qj）的單位元為（D）A.a;B.b;C.

13、1;D.0（6）設(shè)代數(shù)系統(tǒng)A,工則下面結(jié)論成立的是.（C）A.如果（A,）是群，則A,，是阿貝爾群B.如果（A,是阿貝爾群，則A,）是循環(huán)群C.如果（A,）是循環(huán)群，則A,）是阿貝爾群D.如果（A,）是阿貝爾群，則A,）必不是循環(huán)群循環(huán)群億,十）的所有生成元為（D）A.1,0B,-1,2C.1,2D.1,-1三、填空題1 .設(shè)A為非空有限集，代數(shù)系統(tǒng)2A,Ua中，2A對運(yùn)算U的單位元為,零元為.填電A2 .代數(shù)系統(tǒng)Z,+中(其中Z為整數(shù)集合，+為普通加法)，對任意的xwI,其X=.填-x3 .在整數(shù)集合Z上定義。運(yùn)算為a©b=a+2+b,則Z,的單位元為解設(shè)單位元為e,a0e=a+2

14、+e=a，所以e=2,又a。(-2)=a+2+(2)=a,(-2)-a=(2)+2+a=a,所以單位元為e=-24 .在整數(shù)集合Z上定義。運(yùn)算為a©b=a+bab,則Z,©a的單位元為.解設(shè)單位元為e,aoe=a+e-ae=a,(1一a)e=0,所以e=05 .設(shè)(G,)是群，又任意a,b,cwG，如果ab=ac,則.填b=c6 .設(shè)(G,，是群，e為單位元，若G元素a滿足a2=a,則a=填e四、解答題1 .設(shè)'為實(shí)數(shù)集R上的二元運(yùn)算，其定義為2:RtR,a”b=a+b+2ab,對于任意a,b二R求運(yùn)算*的單位元和零元。解：設(shè)單位元為e,則對任意awR,有a'

15、;e=a+e+2ae=a,即e(1+2a)=0,由a的任意性知e=0,又對任意awR,a0=a+0+0=a;0'a=0+a+0=a所以單位元為0設(shè)零元為6,則對任意awR,有a©e=a+6+2a9=日，1即a(1+26)=0,由a的任意性知6=2111111又對任息a=R,a°()=aa=,(-)°a=-+a-a=-222222一一.1所以零兀為一122 .設(shè)'為集合I5=0,1,2,3,4上的二元運(yùn)算，其定義為,2:15TI5,ab=(ab)mod5,對于任意a,b匚15(1) 寫出運(yùn)算的運(yùn)算表；(2) 說明運(yùn)算。是否滿足交換律、結(jié)合律，是否有單

16、位元和零元、如果有請指出;(3)寫出所有可逆元的逆元解：(1)運(yùn)算表為Q01234000000101234202413303142404321(2)運(yùn)算二滿足交換律、結(jié)合律，有單位元，單位元為1,有零元，零元為0;(3)1的逆元為1,2的逆元為3,3的逆元為2,4的逆元4,0沒有逆元五、證明題1 .設(shè)G,：是一個群，試證G是交換群當(dāng)且僅當(dāng)對任意的a,bwG，有a2b2=(ab)2.證明：充分性若在群G,中，對任意的a,bwG,有a2*2=(a*)2.則(aa)(bb)=(ab)(ab)a(ab)b=a(ba)bab=ba從而G,：是一個交換群。必要性若G,。是一個交換群，對任意的a,bG,有a

17、+bnba,則a(ab)b=a(ba)b(aa)(bb)=(ab)(ab)即a2b2=(ab)2.2 .證明代數(shù)系統(tǒng)Z,0是群，其中二元運(yùn)算'定義如下：。：Z2tZ,x0y=x+y-3(這里，+,-分別是整數(shù)的加法與減法運(yùn)算.)證明(1)運(yùn)算滿足交換律對任意x,y,zwZ,由(xy)z=(xy-3)z=xyz-6,x(yz)=x(yz-3)=xyz-6得(x*y)*z=x*(y*z),即“滿足結(jié)合律;(2)有單位元3是單位元；(3)任意元素有逆元對任意xwZ,x*=6x.所以，(Z,是群.第三章圖論、判斷題(1)n階完全圖的任意兩個不同結(jié)點(diǎn)的距離都為1.(對)(2)圖G的兩個不同結(jié)點(diǎn)v

18、i,vj連接時一定鄰接.(錯)圖G中連接結(jié)點(diǎn)vi,vj的初級通路為vi,vj之間的短程.(錯)(4)在有向圖中，結(jié)點(diǎn)Vi到結(jié)點(diǎn)Vj的有向短程即為Vj到v的有向短程.(錯)(5)強(qiáng)連通有向圖一定是單向連通的.(對)(6)不論無向圖或有向圖，初級回路一定是簡單回路.(對)(7)設(shè)圖G是連通的，則任意指定G的各邊方向后所得的有向圖是弱連通的.(對)(8)有生成樹的無向圖是連通的.(對)(9)下圖所示的圖是歐拉圖.(錯)(10)下圖所示的圖有哈密爾頓回路(A)(B)(B)(C)二、單項(xiàng)選擇題(1)僅由孤立點(diǎn)組成的圖稱為A.零圖；B.平凡圖；C.完全圖；D.多重圖.(2)僅由一個孤立點(diǎn)組成的圖稱為A.零

19、圖；B.平凡圖；C.多重圖；D.子圖.(3)在任何圖G中必有偶數(shù)個A.度數(shù)為偶數(shù)的結(jié)點(diǎn)；B.度數(shù)為奇數(shù)的結(jié)點(diǎn)；C.入度為奇數(shù)的結(jié)點(diǎn)；D.出度為奇數(shù)的結(jié)點(diǎn).(4)設(shè)G為有n個結(jié)點(diǎn)的無向完全圖，則G的邊數(shù)為n(n -1). 2D. (n -1). 2A. n(n-1)B,n(n+1)C.A.最多n -1條;.至少n -1條;(5)在有n個結(jié)點(diǎn)的連通圖G中，其邊數(shù)C.最多n條；D.至少n條.(6)任何無向圖G中結(jié)點(diǎn)間的連通關(guān)系是(B)A.偏序關(guān)系；B.等價關(guān)系；C.既是偏序關(guān)系又是等價關(guān)系；D.既不是偏序關(guān)系也不是等價關(guān)系.(7)對于無向圖，下列說法中正確的是.(B)A.不含平行邊及環(huán)的圖稱為完全圖

20、B.任何兩個不同結(jié)點(diǎn)都有邊相連且無平行邊及環(huán)的圖稱為完全圖C.具有經(jīng)過每條邊一次且僅一次回路的圖稱為哈密爾頓圖D.具有經(jīng)過每個結(jié)點(diǎn)一次且僅一次回路的圖稱為歐拉圖(8)設(shè)D是有向圖，則D強(qiáng)連通的充分必要條件為.(C)A.略去D中各邊方向后所得到的無向圖是連通的B. D是單向連通圖，且改變它的各邊方向后所得到的有向圖也是單向連通圖C. D的任意兩個不同的結(jié)點(diǎn)都可以相互到達(dá)D. D是完全圖(9)對于無向圖G,以下結(jié)論中不正確的是.(A)A.如果G的兩個不同結(jié)點(diǎn)是連接的，則這兩個結(jié)點(diǎn)之間有初級回路B.如果G的兩個不同結(jié)點(diǎn)是連接的，則這兩個結(jié)點(diǎn)之間至少有一條短程C.如果G是樹，則任何兩個不同結(jié)點(diǎn)之間有且

21、僅有一條初級通路D.如果G是歐拉圖，則G有歐拉回路三、填空題1 .設(shè)機(jī)T中有7片樹葉，3個3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)，則T中有個4度結(jié)點(diǎn).解用握手定理和樹的性質(zhì)列出方程求解，設(shè)有X個4度結(jié)點(diǎn)，7+9+4x=2(7+3+x-1),X=12 .設(shè)T=<V,E>為樹，T中有4度，3度，2度分支點(diǎn)各1個，問T中有一片樹葉。解與上題解法相同，設(shè)有x片樹葉，4+3+2+x=2(3+x1),x=53 .n階完全圖的任意兩個不同結(jié)點(diǎn)的距離都為.14 .圖G為n階無向完全圖，則G共有條邊。n(n1)/25 .設(shè)G為(n,m)圖，則圖中結(jié)點(diǎn)度數(shù)的總和為。2m6 .圖G為歐拉圖的充分必要條件是.G為無奇

22、度結(jié)點(diǎn)的連通圖四、解答題1.對下圖所示的圖G,求(1) G的鄰接矩陣A;(2) G的結(jié)點(diǎn)Vi,V3之間長度為3的通路;(3) G的連接矩陣C；(4) G的關(guān)聯(lián)矩陣M。解(1)(2)因?yàn)?v2v3v4v5v101110Av2A=10101v311011v410100v5<0110031212、僅M7M13221XXXXXa322411,A=MMMMM12121XXXXX、21112,.x：XXXX<JA2=3的通路共有7條，它們是所以，結(jié)點(diǎn)必”3之間長度為V1V3V1V3,VlV2v5v3,V1V2V1V3,V1V4V1V3,v1v3v5v3,v1v3v2v3,v1v3v4v3.v1

23、v2v3v4v11111v21111C=v31111v41111v5J111(4)e1e2e3e4v1p011v21100M=v30110v40001v590002.在卜面的有向圖D中回答t、夕U問題(3)由于圖G是連通的，所以v5r11.11e5e6e000、001110100011,(1)寫出圖D的鄰接矩陣A;(2)寫出結(jié)點(diǎn)vi到結(jié)點(diǎn)V3的長度為3的所有有向通路;(3)寫出結(jié)點(diǎn)V5到自身的長度為3的所有有向回路;0 0 11 0 01 1 00 0 10 1 0,0010解：(1)A=0000101101 01、01121A3 = 011 2110101:0112 1,0022 2)A2=

24、00I1010'0111011110100101,v5v2v1v5所以結(jié)點(diǎn)V1到結(jié)點(diǎn)V3的長度為3的所有有向通路只有一條：v1v5v2v3(3)結(jié)點(diǎn)V5到自身的長度為3的所有有向回路只有一條:3 .在下面的無向圖G中，回答下列問題(1)寫出a,d之間的所有初級通路；(2)寫出a,d之間的所有短程，并求d(a,d)；(3)判斷無向圖G是否為歐拉圖并說明理由。解(1)a,d之間的所有初級通路共有7條，分別為aed,aecd,aebcd,abed,abcd,abecd,abced(2) a,d之間的長度最短的通路只有1條，即aed,因而它是a,d之間唯一的短程，d(a,d)=2(3)由于無向圖G中有兩個奇度頂點(diǎn)deg(b)=3,deg(c)=3,所以無向圖G沒有歐拉回路，因而不是歐拉圖。第四章數(shù)理邏輯一、判斷題（1） “如果8+7>