離散數(shù)學(xué)試卷及答案三

1、一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.下列各圖是平面圖的是( ) 2.設(shè)G是n個頂點的無向簡單圖，則下列說法不正確的是 )A.若G是樹，則其邊數(shù)等于n-1B.若G是歐拉圖，則G中必有割邊C.若G中有歐拉路，則G是連通圖，且有零個或兩個奇度數(shù)頂點D.若G中任意一對頂點的度數(shù)之和大于等于n-1，則G中有漢密爾頓路3.格L是分配格的充要條件是L不含與下面哪一個選項同構(gòu)的子格( )A.鏈B.鉆石格C.五角格D.五角格與鉆石格4.設(shè)<G,*>是有限循環(huán)群，則下列說法

2、不正確的是( )A.<G,*>的生成元是唯一的B.有限循環(huán)群中的運算*適合交換律C.G中存在一元素a，使G中任一元素都由a的冪組成D.設(shè)a是<G,*>的生成元，則對任一正整數(shù)i，存在正整數(shù)j使a-i=aj5.在實數(shù)集合R上，下列定義的運算中是可結(jié)合的只有( )A.a*b=a+2bB.a*b=a+b-2abC.a*b=a-b+2abD.a*b=a-b-2ab6.設(shè)群G=<A,*>中,A的元素個數(shù)大于1，若元素aA的逆元素為bA，則a*b的運算結(jié)果是( )A.aB.bC.G中零元素D.G中幺元7.非空集合A上的二元關(guān)系R若是自反和對稱的，則R是( )A.偏序關(guān)系

3、B.等價關(guān)系C.相容關(guān)系D.擬序關(guān)系8.下面的圖是A=1,2,3上關(guān)系R的關(guān)系圖G(R),從G(R)可判斷R所具有的性質(zhì)是( )1。2。 3。A.自反，對稱，傳遞B.反自反，非對稱C.反自反，對稱，非傳遞D.反自反，對稱，反對稱，傳遞9.設(shè)A=1，2，3，B=a,b，下列二元關(guān)系R為A到B的函數(shù)的是( )A.R=<1,a>,<2,a>,<3,a>B.R=<1,a>,<2,b>C.R=<1,a>,<1,b>,<2,a>,<3,a>D.R=<1,b>,<2,a>,&l

4、t;3,b>,<1,a>10.設(shè)為空集，P(x)是集合x的冪集，下列論斷不正確的是( )A. P(), P()B.P（），P（）C. P（P（），P（P（）D.P（P（）,P（P（）11.利用謂詞的約束變元改名規(guī)則和自由變元代入規(guī)則，可將如下公式：改寫成( )A. B. C. D. 12.設(shè)論域為整數(shù)集，下列謂詞公式中真值為假的是( )A.B. C. D. 13.在命題演算中，語句為真為假的一種性質(zhì)稱為( )A.真值B.陳述句C.命題D.謂詞14.設(shè)P：明天天晴；q：我去爬山；那么“除非明天天晴，否則我不去爬山?！笨煞柣癁? )A.B. C. D. 15.下列命題公式是永真

5、式的是( )A. qB.C. D.二、填空題(本大題共10小題，每空1分，共20分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.一棵有6個葉結(jié)點的完全二叉樹，有_個內(nèi)點；而若一棵樹有2個結(jié)點度數(shù)為2，一個結(jié)點度數(shù)為3，3個結(jié)點度數(shù)為4，其余是葉結(jié)點，則該樹有_個葉結(jié)點。17.在一棵根樹中，有且只有一個結(jié)點的入度為_，其余所有結(jié)點的入度均為_。18.設(shè)<S,>是格，其中一個命題P是a(ab) (ac),則P的對偶命題是a_(ab)_(ac)。19.設(shè)Z是整數(shù)集，+是整數(shù)加法運算，則<Z,+>是群，其幺元是_，對任一整數(shù)i,其逆元是_。20.當f:XY是_函數(shù)時

6、，f有逆函數(shù)，且f -1。f=_。21.設(shè)E=1,2,3,4,5,6,A=1,4,B=1,2,3,C=2,4,則(AB)C=_,冪集P(AB)C)=_。22.設(shè)論域D=a,b,則(x)P(x)_,(x)(y)Q(x,y)_。23.使公式(x)(y)(A(x)B(y)(x)A(x)(y)B(y)成立的條件是_不含有y，_不含有x。24.由命題變元及其否定所組成的有限個析取式的合取式稱為_，由命題變元及其否定所組成的有限個合取式的析取式稱為_。25.不包含_的命題叫做原子命題，包含_的命題稱為復(fù)合命題。三、計算題(本大題共7小題，第26、28小題每小題5分，第27、31小題每小題7分，第29、30

7、小題每小題8分，第32小題9分，共49分)26.用等值演算法，求P(QR)的主析取范式，并按P，Q，R順序，寫成編碼形式。27.設(shè)A=1,2,3，給定A上二元關(guān)系R=<1,1>,<1,2>,<2,3>，求r(R),s(R)和t(R)。28.求公式的前束范式。29.對如下有向圖D，求D中長度為4的路有多少條?其中回路有多少條?30.設(shè)A=a,abc,bc,bcd,bd，定義A上二元關(guān)系R=<x,y>|x,yA且字符串x包含于字符串y中，即R=IA<a,abc>,<bc,abc>,<bc,bcd>，可以驗證R是A上偏序關(guān)系。作出R的哈斯圖向R中最少添加幾個序偶可使之成為等價關(guān)系?求出該等價關(guān)系所確定的集合A的劃分。31.某科研所要從3個項目A、B、C中選擇12個項目上馬，由于某種原因，立項時要滿足以下條件：(1)若A上，則C也要上；(2)若B上，則C不能上；(3)若C不上，則A或B可以上。請找出所有的立項方案32.設(shè)有6個城市V1，V2，V6，它們之間有輸油管連通，其布置如下圖(a),Si(數(shù)字)中Si為邊的編號，括號內(nèi)數(shù)字為邊的權(quán)，它是兩城市間的矩離，為了保衛(wèi)油管不受破壞，在每段油管間派一連士兵看守，為保證每個城市石油的正常供應(yīng)最少需多少連士兵看守?輸油管道總長度越短，士