2018年春季學期離散數(shù)學期末復習題VIP

1、2018年春季學期離散數(shù)學期末復習題第一章集合論一、判斷題（1）空集是任何集合的真子集.（錯）（2） 是空集.（錯）（3） aa,a（對）（4）設集合A1,2,1,2，則1,22A.（對）如果aAB,則aA或aB.（錯）解aAB則aABAB,即a入且aB,所以aA且aB（4） 如果AUBB,則AB.（對）設集合A匕色冏'B"也避,則ABaC,a2,b2,a3,b3（錯）(8)設集合A0,1,則,0,1,0,0,0,1是2A到A的關系.（對）A解2,0,1,A,A2A,0,1,0,0,0,1,1,0,1,1,A,0,A,1（5） 關系的復合運算滿足交換律.（錯）（10） 是集合

2、A上的關系具有傳遞性的充分必要條件.（錯）（11）設是集合A上的傳遞關系，則也是A上的傳遞關系.（對）（12）集合A上的對稱關系必不是反對稱的.（錯）（13）設1,2為集合A上的等彳關系，則12也是集合A上的等價關系（對）（14）設是集合A上的等價關系，則當a,b時，ab（對）戶1°P：°Pr（15）設1,2為集合A上的等價關系，則（錯）二、單項選擇題（1）設R為實數(shù)集合，下列集合中哪一個不是空集（A）.22A.x|x10,且xRB.x|x90,且xR2C.x|xx1,且xRD.x|x1,且xR2)設A,B為集合，若AB，則一定有A. BB BC. AD. A B3)下列各

3、式中不正確的是A.BC.D., 4)設a,a,則下列各式中錯誤的是A. a2ABa2C.a2AD. a2A5)1,2，a, b, cc, dA (BC)為A.c,1 ,2,cB1,c2, cC.1,cc,2D.c,1 , c,26)0, b ，1, b, 3B 的恒等關系為A.0,0 , 1,1 , b,b , 3,3B0,0 , 1,1, 3,3C.0,0 , b,b3,3D. 0,1 , 1,b, b,33,07)a,b,上的二元關系如下，則具有傳遞性的為則具有傳遞性的為A.a,cc,a , a,b ,b,aBa,cc, aC.a,b ,c,c , b,a ,b,cD.a,a8)為集合 A

4、 上的等價關系，對任意a A ，其等價類A. 空集；B.非空集;C. 是否為空集不能確定；D.x|xA.9)映射的復合運算滿足A. 交換律B.結合律C. 冪等律D.分配律10)設A，B是集合，則下列說法中(C)是正確的AA到B的關系都是A到B的映射BA到B的映射都是可逆的CA到B的雙射都是可逆的DAB時必不存在A到B的雙射（11）設A是集合，則（B）成立.A. #2A2#AAB. X2AXAC. 2AD. A2A（12）設A是有限集（#An）,則A上既是又是的關系共有（B）.A. 0個B. 1個C. 2個D. n個三、填空題1 .設A1,2,1,2,則2A.填2A,1,2,1,2,1,2,1,

5、1,2,2,1,2,A2 .設A,則2A=.填2A,A3 .設集合A,B中元素的個數(shù)分別為#A5,#B7,且#5B）9,則集合AB中元素的個數(shù)#（AB）.34 .設集合Ax|1x100,x是4的倍數(shù),xZ,Bx|1x100,x是5的倍數(shù)，xZ,則AB中元素的個數(shù)為.405 .設Aa,b,是2A上的包含于關系，則有=.,a,b,A,a,a,a,A,b,b,b,A,A,A6 .設1,2為集合A上的二元關系，則12.217 .集合A上的二元關系為傳遞的充分必要條件是.8.設集合A 0,1, 2上的關系10, 2 , 2, 0 及集合A到集合B 0,2,4的關系 2 a, b | a, bA B且a,

6、b A n B ,則 12填0,0,0,2,2,0,2,2四、解答題1.設集合A,1,2,B1,2,B求（1）AU2B;（2）2A解（1）AU2b,1,2,U,1,2,B,1,2,1,2,B.2)A2B，所以2A2B2,2.設Aa,b,c,d,A上的關系a,a,b,b,c,c,d,d（1）寫出的關系矩陣；（2）驗證是A上的等價關系；（3）求出A的各元素的等價類。解（1）的關系矩陣為a,b,b,a,c,d,d,c11001100M001100112）從的關系矩陣可知：是自反的和對稱的。又由于1100110011001100MM001100110011001111001100M00110011是

7、A 上的等價關系?；驖M足所以是傳遞的。因為是自反的、對稱的和傳遞的，所以3）aba,b，cdc,d3.設集合A1,2,3,5,6,15,30,是A上的整除關系,1）寫出的關系矩陣M；2）畫出偏序集A,的哈斯圖；（3）求出A的子集B（4）判斷其是否為格。111010001解：（1）M0000003,6,15 的最小上界和最大下界；111101010111101101010011000(3)lubB=30,glbB=3五、證明題1.設2為集合證明：由于A上的等價關系，試證是自反的，所以對任意2也是集合A上的等價關系。A,a,aa,a2,因而a,a若以b,a若a,b,1a,b2,即12是自反的。1b

8、,a2,則a,b2,從而1,b,aa,b22,即油于2是對稱的，所2是對稱的。b,ca,c由于a,ca,b,b,ca,b,b,c2,從而a,c2是自反的、對稱的和傳遞的,1所以、判斷題(1)(2)(3)(4)(5)(6)群.第二章代數(shù)系統(tǒng)集合A上的任一運算對A是封閉的.代數(shù)系統(tǒng)的零元是可逆元.A是集合，：AAa,b是代數(shù)系統(tǒng)A,a,b是群G,的元素的元素，如果，則（ab）1G,是群.如果又于任意a,bb,則G,L,是格，則運算滿足曷等律.傳遞的2是傳遞的。2是等價關系。是可結合的.（.2有(ab)e（e是該代數(shù)系統(tǒng)的單位元）G,是阿貝爾(8)設集合Aa,b,則,a,b,A,是格.(11) &l

9、t;0,1,2,3,4,max,min>是格.(對)(9)設B,是布爾代數(shù)，則B,是格.(對)(10)設B,/是布爾代數(shù)，則對任意a,bB,有abab.(對)二、單項選擇題(1)在整數(shù)集Z上，下列哪種運算是可結合的(B)A.ababB.abmaxa,bC.aba2bd.ab|ab|(2)下列定義的實數(shù)集R上的運算*中可結合的是.(C)A. abaabB. aba2abC. abbD. abab其中，+,II分別為實數(shù)的加法、乘法和取絕對值運算.(3)設集合A1,2,3,4,10,下面定義的哪種運算關于集合A不是封閉的(D)A. xymaxx,yB. xyminx,yC. xyGCDx,y

10、,即x,y的最大公約數(shù)D. xyLCMx,y,即x,y的最小公倍數(shù)(4)下列哪個集關于減法運算是封閉的(B)A. N (自然數(shù)集)；B. 2x|x Z(整數(shù)集);C. 2x 1|x Z；D. x|x是質數(shù).設Q是有理數(shù)集，在Q定義運算為ababab,則(Q,)的單位元為(D)A.a；B.b；C.1;D.0(6)設代數(shù)系統(tǒng)A,則下面結論成立的是.(C)A.如果A,是群，則A,是阿貝爾群B.如果A,是阿貝爾群，則A,是循環(huán)群C.如果A,是循環(huán)群，則A,是阿貝爾群D.如果A,是阿貝爾群，則A,必不是循環(huán)群循環(huán)群(Z,，的所有生成元為(D)A.1,0B.-1,2C.1,2D.1,-1三、填空題一AA1

11、 .設A為非空有限集，代數(shù)系統(tǒng)2,中，2對運算的單位元為,零元為.填,A2 .代數(shù)系統(tǒng)Z,中(其中Z為整數(shù)集合，+為普通加法)，對任意的xI,其x1填x3 .在整數(shù)集合Z上定義運算為aba2b,則Z,的單位元為.解設單位元為3,262262,所以32,又a(2)a2(2)a,(2)a(2)2aa,所以單位元為e24 .在整數(shù)集合Z上定義 解設單位元為e , a e運算為a b a b a e ae a, (1ab ,則 Z,的單位元為a)e 0 ,所以 e 05 .設G, 是群，又任意a, b,c.填 bc6 .設(G,)是群，e為單位元，若G元素a滿足a2a,則a填e四、解答題1 .設為實數(shù)

12、集R上的二元運算，其定義為_2_.一.、._:RR,abab2ab,對于任意a,bR求運算的單位元和零元。解：設單位元為e,則對任意aR,有aeae2aea,即e(12a)0,由a的任意性知e0,0 a 0 a 0 aa 2a ,12111一，(一)a 一222又對任意aR,a0a00a；所以單位元為0設零元為，則對任意aR,有a即a(12)0,由a的任意性知一_11又對任息aR,a(-)a-a22一一.1所以零兀為122.設為集合150,1,2,3,4上的二元運算，其定義為.2:15I5,ab(ab)mod5,對于任意a,b15(1)寫出運算的運算表；(2)說明運算是否滿足交換律、結合律，是

13、否有單位元和零元、如果有請指出;(3)寫出所有可逆元的逆元解：(1)運算表為01234000000101234202413303142404321(2)運算滿足交換律、結合律，有單位元，單位元為1,有零元，零元為0;(3)1的逆元為1,2的逆元為3,3的逆元為2,4的逆元4,0沒有逆元五、證明題1 .設G,是一個群，試證G是交換群當且僅當對任意的a,bG,有2 ,2,、2ab(ab).證明：充分性若在群G,中，對任意的a,bG，有a2b2(ab)2.則(aa)(bb)(ab)(ab)a(ab)ba(ba)babba從而G,是一個交換群。必要性若G,是一個交換群，對任意的a,bG,有abba,則

14、a(ab)ba(ba)b(aa)(bb)(ab)(ab)即a2b2(ab)2.2.證明代數(shù)系統(tǒng)Z,是群，其中二元運算定義如下：2：ZZ,xyxy3(這里，+,-分別是整數(shù)的加法與減法運算.)證明(1)運算滿足交換律對任意x,y,zZ,由(xy)z(xy3)zxyz6,x(yz)x(yz3)xyz6得(xy)zx(yz),即滿足結合律；（2）有單位元3是單位元；（3）任意元素有逆元對任意xZ,x16x.所以，Z,是群.第三章圖論一、判斷題（1）n階完全圖的任意兩個不同結點的距離都為1.（對）（2）圖G的兩個不同結點vi,vj連接時一定鄰接.（錯）圖G中連接結點viY的初級通路為via之間的短程.

15、（錯）（4）在有向圖中，結點vi到結點Vj的有向短程即為Vj到Vi的有向短程.（錯）（5）強連通有向圖一定是單向連通的.（對）（6）不論無向圖或有向圖，初級回路一定是簡單回路.（對）（7）設圖G是連通的，則任意指定G的各邊方向后所得的有向圖是弱連通的.（對）（8）設A是某個無向圖的鄰接矩陣，則AAT（AT是A的轉置矩陣）.(9)設有向圖D的可達矩陣為11110111P00110001（對 ）（對）（錯 ）則G是單向連通的.（10）有生成樹的無向圖是連通的.（11）下圖所示的圖是歐拉圖（12）下圖所示的圖有哈密爾頓回路(13)下圖中為歐拉圖的是( C )A.B.C.D.二、單項選擇題(1)僅由孤

16、立點組成的圖稱為A.零圖；B.平凡圖；(2)僅由一個孤立點組成的圖稱為A.零圖；B.平凡圖；(3)在任何圖G中必有偶數(shù)個A.度數(shù)為偶數(shù)的結點；C.入度為奇數(shù)的結點；C.完全圖；D.多重圖.C.多重圖；D.子圖.B.度數(shù)為奇數(shù)的結點；D.出度為奇數(shù)的結點.(4)設G為有n個結點的無向完全圖，則 G的邊數(shù)為(A )(B )(B )(C )A. n(n 1)B.n(n1)C.n(n1)2D.(n1),2(5)在有n個結點的連通圖G中，其邊數(shù)(B)A.最多n1條；B.至少n1條；C.最多n條；D.至少n條.(6)任何無向圖G中結點間的連通關系是(B)A.偏序關系；B.等價關系；C.既是偏序關系又是等價

17、關系；D.既不是偏序關系也不是等價關系.(7)對于無向圖，下列說法中正確的是.(B)A.不含平行邊及環(huán)的圖稱為完全圖B.任何兩個不同結點都有邊相連且無平行邊及環(huán)的圖稱為完全圖C.具有經過每條邊一次且僅一次回路的圖稱為哈密爾頓圖D.具有經過每個結點一次且僅一次回路的圖稱為歐拉圖(8)設D是有向圖，則D強連通的充分必要條件為.(C)A.略去D中各邊方向后所得到的無向圖是連通的B. D是單向連通圖，且改變它的各邊方向后所得到的有向圖也是單向連通圖C. D的任意兩個不同的結點都可以相互到達D. D是完全圖(9)對于無向圖G,以下結論中不正確的是.(A)A.如果G的兩個不同結點是連接的，則這兩個結點之間

18、有初級回路B.如果G的兩個不同結點是連接的，則這兩個結點之間至少有一條短程C.如果G是樹，則任何兩個不同結點之間有且僅有一條初級通路D.如果G是歐拉圖，則G有歐拉回路(10)設簡單無向圖G的鄰接矩陣為A(aij)nn,記Al(a;)nn(l1,2,)，則正確的是.A.當Vi,Vj是G的兩個不同結點時，a;為Vi,Vj之間長度為l的初級通路條數(shù)B.當Vi,Vj是G的兩個不同結點時，a：為v,vj之間長度為l的簡單通路條數(shù)C.當Vi,Vj是G的兩個不同結點時，a：為Vi,Vj之間長度為l的的通路條數(shù)D.當w是G的結點時，a(l)為通過vi的長度為l的初級回路條數(shù)(11) Mmijnm是無向圖GV,

19、E的關聯(lián)矩陣，ViV是G中的孤立點，則(A)A.Vi對應的一行元素全為0;B.Vi對應的一行元素全為1;C.Vi對應的一列元素全為0;D.Vi對應的一列元素全為1.三、填空題1 .設樹T中有7片樹葉，3個3度結點，其余都是4度結點，則T中有個4度結點.解用握手定理和樹的性質列出方程求解，設有X個4度結點，794x2(73x1),X12.設TV, E 為樹，T中有4度，3度，2度分支點各1個，問T中有片樹葉。解 與上題解法相同，設有 x片樹葉,4 3 2 x 2(3 x 1) , x 5階完全圖的任意兩個不同結點的距離都為.14 .圖G為n階無向完全圖，則G共有條邊。n(n1)/25 .設G為(

20、n,m)圖，則圖中結點度數(shù)的總和為6 .設圖G有6結點，若各結點的度數(shù)分別為：用握手定理222m,m=117 .圖G為歐拉圖的充分必要條件是四、解答題1 .對下圖所示的圖G,求(1) G的鄰接矩陣A;(2) G的結點v1,v3之間長度為3的通路；(3) G的連接矩陣C;(4) G的關聯(lián)矩陣M。2m1,4,4,3,5,5,貝UG共有條邊。.G為無奇度結點的連通圖v1v10v2v3v41v5011解（1）A=v210101v311011.v410100v501100（2）因為31212713221A2=22411,A3=1212121112所以，結點Vi,V3之間長度為3的通路共有7條，它們是v1

21、v3v1v3,v1v2v5v3,v1v2v1v3,v1v4v1v3,v1v3v5v3,v1v3v2v3,v1v3v4v3.3由于圖G是連通的，所以v1v2v3v4v5v111v211C=v311v411v5111111111111111114）e1e2e3e4e5e6e7000001110100011v11011v21100M=v30110v40001v500002 .在下面的有向圖D中，回答下列問題(1)寫出圖D的鄰接矩陣A;(2)寫出結點Vi到結點V3的長度為3的所有有向通路;(3)寫出結點V5到自身的長度為3的所有有向回路;0000110100解：(1)A0011001010A20 10

22、 100 0 1110 0 1110 10 1010 10 1所以結點V1到結點V3的長度為3的所有有向通路只有一條：V1V5v2v3(3)結點V5到自身的長度為3的所有有向回路只有一條:3.在下面的無向圖1010101121A3011211010101121v5v2v1v5(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中有兩個奇度頂點deg(b)3,deg(c)3,所以無向圖G沒有歐拉回路，因而不是歐拉圖。第四章數(shù)理邏輯一、判斷題1 1）“如果8+7>2,則三角形有四條邊”是命題.（對）2 ）設P,Q都是命