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

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

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

3、B.等價(jià)關(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.自反，對(duì)稱(chēng)，傳遞B.反自反，非對(duì)稱(chēng)C.反自反，對(duì)稱(chēng)，非傳遞D.反自反，對(duì)稱(chēng)，反對(duì)稱(chēng)，傳遞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(chóng)的冪集，下列論斷不正確的是( )A. P(), P()B.P（），P（）C. P（P（），P（P（）D.P（P（）,P（P（）11.利用謂詞的約束變?cè)拿?guī)則和自由變?cè)胍?guī)則，可將如下公式：改寫(xiě)成( )A. B. C. D. 12.設(shè)論域?yàn)檎麛?shù)集，下列謂詞公式中真值為假的是( )A.B. C. D. 13.在命題演算中，語(yǔ)句為真為假的一種性質(zhì)稱(chēng)為( )A.真值B.陳述句C.命題D.謂詞14.設(shè)P：明天天晴；q：我去爬山；那么“除非明天天晴，否則我不去爬山?！笨煞?hào)化為( )A.B. C. D. 15.下列命題公式是永真

5、式的是( )A. qB.C. D.二、填空題(本大題共10小題，每空1分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16.一棵有6個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，有_個(gè)內(nèi)點(diǎn)；而若一棵樹(shù)有2個(gè)結(jié)點(diǎn)度數(shù)為2，一個(gè)結(jié)點(diǎn)度數(shù)為3，3個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，則該樹(shù)有_個(gè)葉結(jié)點(diǎn)。17.在一棵根樹(shù)中，有且只有一個(gè)結(jié)點(diǎn)的入度為_(kāi)，其余所有結(jié)點(diǎn)的入度均為_(kāi)。18.設(shè)<S,>是格，其中一個(gè)命題P是a(ab) (ac),則P的對(duì)偶命題是a_(ab)_(ac)。19.設(shè)Z是整數(shù)集，+是整數(shù)加法運(yùn)算，則<Z,+>是群，其幺元是_，對(duì)任一整數(shù)i,其逆元是_。20.當(dāng)f:XY是_函數(shù)時(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.由命題變?cè)捌浞穸ㄋM成的有限個(gè)析取式的合取式稱(chēng)為_(kāi)，由命題變?cè)捌浞穸ㄋM成的有限個(gè)合取式的析取式稱(chēng)為_(kāi)。25.不包含_的命題叫做原子命題，包含_的命題稱(chēng)為復(fù)合命題。三、計(jì)算題(本大題共7小題，第26、28小題每小題5分，第27、31小題每小題7分，第29、30

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