離散數(shù)學(xué)習(xí)題（十五套）-答案解析

1、 離散數(shù)學(xué)試題與答案試卷一一、填空 20% （每小題2分）A B C1設(shè)（N：自然數(shù)集，E+正偶數(shù)）則。2A，B，C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為。3設(shè)P，Q 的真值為0，R，S的真值為1，則的真值= 。4公式的主合取式為。5若解釋I的論域D僅包含一個(gè)元素，則在I下真值為。6設(shè)A=1，2，3，4，A上關(guān)系圖為則 R2 = 。7設(shè)A=a，b，c，d，其上偏序關(guān)系R的哈斯圖為則 R= 。8圖的補(bǔ)圖為。9設(shè)A=a，b，c，d ，A上二元運(yùn)算如下：*a b c dabcda b c db c d ac d a bd a b c那么代數(shù)系統(tǒng)<A，*>的幺元是，有逆元的元素為，它們

2、的逆元分別為。10下圖所示的偏序集中，是格的為。二、選擇 20% （每小題 2分）1、下列是真命題的有（）A； B；C； D。2、下列集合中相等的有（） A4，3；B，3，4；C4，3，3；D 3，4。3、設(shè)A=1，2，3，則A上的二元關(guān)系有（）個(gè)。 A 23 ；B 32 ；C； D。4、設(shè)R，S是集合A上的關(guān)系，則下列說(shuō)確的是（） A若R，S 是自反的，則是自反的； B若R，S 是反自反的，則是反自反的； C若R，S 是對(duì)稱的，則是對(duì)稱的； D若R，S 是傳遞的，則是傳遞的。5、設(shè)A=1，2，3，4，P（A）（A的冪集）上規(guī)定二元系如下則P（A）/ R=（）AA ；BP(A) ；C1，1，2

3、，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、設(shè)A=，1，1，3，1，2，3則A上包含關(guān)系“”的哈斯圖為（）7、下列函數(shù)是雙射的為（）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = <n , n+1> ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。（注：I整數(shù)集，E偶數(shù)集， N自然數(shù)集，R實(shí)數(shù)集）8、圖中從v1到v3長(zhǎng)度為3 的通路有（）條。A 0；B 1；C 2；D 3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（）10、在一棵樹(shù)中有7片樹(shù)葉，3個(gè)3度結(jié)點(diǎn)，其余都是

4、4度結(jié)點(diǎn)則該樹(shù)有（）個(gè)4度結(jié)點(diǎn)。A1；B2；C3；D4 。三、證明 26%、 R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng)< a, b> 和<a , c>在R中有<.b , c>在R中。（8分）、 f和g都是群<G1 ,>到< G2, *>的同態(tài)映射，證明<C ,>是<G1,>的一個(gè)子群。其中C= (8分)、 G=<V, E> (|V| = v，|E|=e ) 是每一個(gè)面至少由k（k3）條邊圍成的連通平面圖，則，由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演

5、 16%用CP規(guī)則證明下題（每小題 8分）1、2、五、計(jì)算 18%1、設(shè)集合A=a，b，c，d上的關(guān)系R=<a , b > ,< b , a > ,< b, c > , < c , d >用矩陣運(yùn)算求出R的傳遞閉包t (R)。（9分）2、如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（分）試卷二試題與答案一、填空 20% （每小題2分）1、 P：你努力，Q：你失敗。“除非你努力，否則你將失敗”的翻譯為；“雖然你努力了，但還是失敗了”的翻譯為。2、論域D=1，2，

6、指定謂詞PP (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式真值為。2、 設(shè)S=a1 ，a2 ，a8，Bi是S的子集，則由B31所表達(dá)的子集是。3、 設(shè)A=2，3，4，5，6上的二元關(guān)系，則R= （列舉法）。R的關(guān)系矩陣MR=。5、設(shè)A=1，2，3，則A上既不是對(duì)稱的又不是反對(duì)稱的關(guān)系R= ；A上既是對(duì)稱的又是反對(duì)稱的關(guān)系R= 。*a b cabca b cb b cc c b6、設(shè)代數(shù)系統(tǒng)<A，*>，其中A=a，b，c,則幺元是；是否有冪等性；是否有對(duì)稱性。7、4階群必是群或群。8、下面偏序格是分配格的是。9、n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為，歐拉圖的充要條件

7、是。10、公式的根樹(shù)表示為。二、選擇 20% （每小題2分）1、在下述公式中是重言式為（）A；B；C； D。2、命題公式中極小項(xiàng)的個(gè)數(shù)為（），成真賦值的個(gè)數(shù)為（）。A0； B1； C2； D3 。3、設(shè)，則有（）個(gè)元素。A3； B6； C7； D8 。4、 設(shè)，定義上的等價(jià)關(guān)系則由 R產(chǎn)生的上一個(gè)劃分共有（）個(gè)分塊。A4； B5； C6； D9 。5、設(shè)，S上關(guān)系R的關(guān)系圖為則R具有（）性質(zhì)。A自反性、對(duì)稱性、傳遞性； B反自反性、反對(duì)稱性；C反自反性、反對(duì)稱性、傳遞性； D自反性。6、設(shè)為普通加法和乘法，則（）是域。A BCD= N 。7、下面偏序集（）能構(gòu)成格。8、在如下的有向圖中，從V1

8、到V4長(zhǎng)度為3 的道路有（）條。A1； B2； C3； D4 。9、在如下各圖中（）歐拉圖。10、設(shè)R是實(shí)數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)<R ，×> 是（）。A群； B獨(dú)異點(diǎn)； C半群。三、證明 46%1、 設(shè)R是A上一個(gè)二元關(guān)系，試證明若R是A上一個(gè)等價(jià)關(guān)系，則S也是A上的一個(gè)等價(jià)關(guān)系。（9分）2、 用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。（11分）3、 若是從A到B的函數(shù)，定義一個(gè)函數(shù)對(duì)任意有，證明：若f是A到B的滿射，則g是從B到的單射。（10分）4、 若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定連通。（8分）

9、5、 設(shè)G是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，其邊數(shù)，則G是Hamilton圖（8分）四、計(jì)算 14%1、 設(shè)<Z6,+6>是一個(gè)群，這里+6是模6加法，Z6=0 ，1，2，3，4，5，試求出<Z6,+6>的所有子群及其相應(yīng)左陪集。（7分）2、 權(quán)數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹(shù)。（7分）試卷二答案：試卷三試題與答案一、 填空 20% （每空 2分）1、 設(shè) f，g是自然數(shù)集N上的函數(shù)，則。2、 設(shè)A=a，b，c，A上二元關(guān)系R=< a, a > , < a, b >,< a, c >, < c

10、, c> , 則s（R）= 。3、 A=1，2，3，4，5，6，A上二元關(guān)系，則用列舉法 T= ；T的關(guān)系圖為；T具有性質(zhì)。4、 集合的冪集= 。5、 P，Q真值為0 ；R，S真值為1。則的真值為。6、 的主合取式為。7、 設(shè) P（x）：x是素?cái)?shù)， E(x)：x 是偶數(shù)，O(x)：x是奇數(shù) N (x,y)：x可以整數(shù)y。則謂詞的自然語(yǔ)言是。8、 謂詞的前束式為。二、 選擇 20% （每小題 2分）1、 下述命題公式中，是重言式的為（）。A、； B、；C、； D、。2、 的主析取式中含極小項(xiàng)的個(gè)數(shù)為（）。A 、2； B、 3； C、5； D、0； E、 8 。3、 給定推理PUSPESTI

11、UG推理過(guò)程中錯(cuò)在（）。A、-> B、-> C、-> D、-> E、->4、 設(shè)S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在條件下X與（）集合相等。A、 X=S2或S5 ； B、X=S4或S5；C、X=S1，S2或S4； D、X與S1，S5中任何集合都不等。5、 設(shè)R和S是P上的關(guān)系，P是所有人的集合，則表示關(guān)系（）。A、；B、；C、； D、。6、 下面函數(shù)（）是單射而非滿射。A、；B、；C、；D、。其中R為實(shí)數(shù)集，Z為整數(shù)集，R+，Z+分別表示正實(shí)數(shù)與正整數(shù)集。7、 設(shè)S=1，2，3，R為S上的關(guān)系，其

12、關(guān)系圖為則R具有（）的性質(zhì)。A、 自反、對(duì)稱、傳遞； B、什么性質(zhì)也沒(méi)有；C、反自反、反對(duì)稱、傳遞； D、自反、對(duì)稱、反對(duì)稱、傳遞。8、 設(shè)，則有（）。A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 設(shè)A=1 ,2 ,3 ，則A上有（）個(gè)二元關(guān)系。A、23； B、32； C、； D、。10、全體小項(xiàng)合取式為（）。A、可滿足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。三、 用CP規(guī)則證明 16% （每小題 8分）1、2、四、（14%） 集合X=<1,2>, <3,4>, <5,6>, ，R=<<x1,y1>,<

13、x2,y2>>|x1+y2 = x2+y1 。1、 證明R是X上的等價(jià)關(guān)系。（10分）2、 求出X關(guān)于R的商集。（4分）五、（10%）設(shè)集合A= a ,b , c , d 上關(guān)系R=< a, b > , < b , a > , < b , c > , < c , d > 要求 1、寫(xiě)出R的關(guān)系矩陣和關(guān)系圖。（4分） 2、用矩陣運(yùn)算求出R的傳遞閉包。（6分）六、（20%）1、（10分）設(shè)f和g是函數(shù)，證明也是函數(shù)。2、（10分）設(shè)函數(shù)，證明有一左逆函數(shù)當(dāng)且僅當(dāng)f是入射函數(shù)。答案：一、 填空 20%（每空2分）1、2(x+1)；2、；3、

14、；4、反對(duì)稱性、反自反性；4、；5、1；6、；7、任意x，如果x是素?cái)?shù)則存在一個(gè)y，y是奇數(shù)且y整除x ；8、。二、 選擇 20%（每小題 2分）題目12345678910答案CCCCABDADC三、 證明 16%(每小題8分)1、P（附加前提）TIPTITITIPTICP2、P（附加前提）TEESPUSTIEGCP四、 14%（1） 證明：1、 自反性：2、 對(duì)稱性：3、 傳遞性：即由（1）（2）（3）知：R是X上的先等價(jià)關(guān)系。2、X/R=五、 10%1、；關(guān)系圖2、t (R)=<a , a> , <a , b> , < a , c> , <a ,

15、d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > 。六、 20%1、（1）（2）。2、證明：。試卷四試題與答案一、 填空 10% （每小題 2分）1、 若P，Q，為二命題，真值為0 當(dāng)且僅當(dāng)。2、 命題“對(duì)于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F(x)：x為實(shí)數(shù)，則命題的邏輯謂詞公式為。3、 謂詞合式公式的前束式為。4、 將量詞轄域中出現(xiàn)的和指導(dǎo)變?cè)粨Q為另一變?cè)?hào)，公式其余的部分不變，這種方法稱為換名規(guī)則。5、 設(shè)x是謂詞合式公式A的一個(gè)客體變

16、元，A的論域?yàn)镈，A(x)關(guān)于y是自由的，則被稱為存在量詞消去規(guī)則，記為ES。二、 選擇 25% （每小題 2.5分）1、 下列語(yǔ)句是命題的有（）。A、 明年中秋節(jié)的晚上是晴天； B、；C、當(dāng)且僅當(dāng)x和y都大于0； D、我正在說(shuō)謊。2、 下列各命題中真值為真的命題有（）。A、 2+2=4當(dāng)且僅當(dāng)3是奇數(shù)；B、2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)；C、2+24當(dāng)且僅當(dāng)3是奇數(shù)； D、2+24當(dāng)且僅當(dāng)3不是奇數(shù)；3、 下列符號(hào)串是合式公式的有（）A、；B、；C、；D、。4、 下列等價(jià)式成立的有（）。A、；B、；C、； D、。5、 若和B為wff，且則（）。A、稱為B的前件； B、稱B為的有效結(jié)論C、當(dāng)且僅

17、當(dāng)；D、當(dāng)且僅當(dāng)。6、 A，B為二合式公式，且，則（）。A、為重言式； B、；C、； D、； E、為重言式。7、 “人總是要死的”謂詞公式表示為（）。（論域?yàn)槿倐€(gè)體域）M(x)：x是人；Mortal(x)：x是要死的。A、； B、C、；D、8、 公式的解釋I為：個(gè)體域D=2，P(x)：x>3, Q(x)：x=4則A的真值為（）。A、1； B、0； C、可滿足式； D、無(wú)法判定。9、 下列等價(jià)關(guān)系正確的是（）。A、；B、；C、；D、。10、 下列推理步驟錯(cuò)在（）。PUSPESTIEGA、；B、；C、；D、三、 邏輯判斷30% 1、 用等值演算法和真值表法判斷公式的類型。（10分）2、 下

18、列問(wèn)題，若成立請(qǐng)證明，若不成立請(qǐng)舉出反例：（10分）（1） 已知，問(wèn)成立嗎？（2） 已知，問(wèn)成立嗎？3、 如果廠方拒絕增加工資，那么罷工就不會(huì)停止，除非罷工超過(guò)一年并且工廠撤換了廠長(zhǎng)。問(wèn)：若廠方拒絕增加工資，面罷工剛開(kāi)始，罷工是否能夠停止。（10分）四、計(jì)算10%1、 設(shè)命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。（5分）2、 利用主析取式，求公式的類型。（5分）五、謂詞邏輯推理 15%符號(hào)化語(yǔ)句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。六、證明：（10%）設(shè)論域D=a , b , c，求證：。答案：六、 填空 10%（每小題2分）1、P真值為

19、1，Q的真值為0；2、；3、；4、約束變?cè)?、，y為D的某些元素。七、 選擇 25%（每小題2.5分）題目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)八、 邏輯判斷 30%1、（1）等值演算法（2）真值表法P QA1 1111111 0010010 1100010 011111所以A為重言式。2、（1）不成立。若取但A與B不一定等價(jià)，可為任意不等價(jià)的公式。（2）成立。證明：即：所以故。3、解：設(shè)P：廠方拒絕增加工資；Q：罷工停止；R罷工超壺過(guò)一年；R：撤換廠長(zhǎng)前提：結(jié)論：PPTIPTITETI罷工不會(huì)停止是有效結(jié)論。四、計(jì)算 10%（1） 解：（2）

20、它無(wú)成真賦值，所以為矛盾式。五、謂詞邏輯推理 15%解：證明：PESTITIPUSTITEUSUSTIUG九、 證明10%試卷五試題與答案一、填空15%（每空3分）1、設(shè)G為9階無(wú)向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6，則G中至少有個(gè)5度結(jié)點(diǎn)。2、n階完全圖，Kn的點(diǎn)數(shù)X (Kn) = 。3、有向圖中從v1到v2長(zhǎng)度為2的通路有條。4、設(shè)R，+，·是代數(shù)系統(tǒng)，如果R，+是交換群R，·是半群則稱R，+，·為環(huán)。5、設(shè)是代數(shù)系統(tǒng)，則滿足冪等律，即對(duì)有。二、選擇15%（每小題3分）1、 下面四組數(shù)能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列的有（）。A、（2，2，2，2，2）； B、（1，1，2，

21、2，3）；C、（1，1，2，2，2）； D、（0，1，3，3，3）。2、 下圖中是哈密頓圖的為（）。3、 如果一個(gè)有向圖D是強(qiáng)連通圖，則D是歐拉圖，這個(gè)命題的真值為（）A、真； B、假。4、 下列偏序集（）能構(gòu)成格。5、 設(shè)，*為普通乘法，則S，*是（）。A、代數(shù)系統(tǒng)； B、半群； C、群； D、都不是。三、證明 48%1、（10%）在至少有2個(gè)人的人群中，至少有2 個(gè)人，他們有相同的朋友數(shù)。2、（8%）若圖G中恰有兩個(gè)奇數(shù)度頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。3、（8%）證明在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中，每個(gè)面的面數(shù)都是3。4、（10%）證明循環(huán)群的同態(tài)像必是循環(huán)群。5、（12%）設(shè)是布爾代

22、數(shù)，定義運(yùn)算*為，求證B，*是阿貝爾群。四、計(jì)算22%1、在二叉樹(shù)中1） 求帶權(quán)為2，3，5，7，8的最優(yōu)二叉樹(shù)T。（5分）2） 求T對(duì)應(yīng)的二元前綴碼。（5分）2、 下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長(zhǎng)度（郵局在D點(diǎn)）。答案：一、填空（15%）每空3 分1、 6；2、n；3、2；4、+對(duì)·分配且·對(duì)+分配均成立；5、。二、選擇（15%）每小題3分題目12345答案A,BB,DBCD三、證明（48%）1、（10分）證明：用n個(gè)頂點(diǎn)v1，vn表示n個(gè)人，構(gòu)成頂點(diǎn)集V=v1，vn，設(shè)，無(wú)向圖G=（V，E）現(xiàn)證G中至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同。事實(shí)上，（1）若G中孤立點(diǎn)個(gè)數(shù)大于等

23、于2，結(jié)論成立。（2）若G中有一個(gè)孤立點(diǎn)，則G中的至少有3個(gè)頂點(diǎn)，既不考慮孤立點(diǎn)。設(shè)G中每個(gè)結(jié)點(diǎn)度數(shù)均大于等于1，又因?yàn)镚為簡(jiǎn)單圖，所以每個(gè)頂點(diǎn)度數(shù)都小于等于n-1，由于G中n頂點(diǎn)其度數(shù)取值只能是1，2，n-1，由鴿巢原理，必然至少有兩個(gè)結(jié)點(diǎn)度數(shù)是相同的。2、（8分）證：設(shè)G中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u，v。若 u，v不連通則至少有兩個(gè)連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個(gè)奇數(shù)度結(jié)點(diǎn)，與握手定理矛盾。因而u，v必連通。3（8分）證：n=6,m=12 歐拉公式n-m+f=2知 f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個(gè)面用3條邊圍成

24、。4（10分）證：設(shè)循環(huán)群A，·的生成元為a，同態(tài)映射為f，同態(tài)像為f（A），*，于是都有對(duì)n=1有n=2, 有若n=k-1時(shí)有對(duì)n=k時(shí)，這表明，f(A)中每一個(gè)元素均可表示為，所以f(A),*為f(a) 生成的循環(huán)群。5、證：（1） 交換律：有（2） 結(jié)合律：有而：（3） 幺：有（4） 逆：綜上所述：B，*是阿貝爾群。四、計(jì)算（22%）1、（10分）（1）（5分）由Huffman方法,得最佳二叉樹(shù)為：（2）（5分）最佳前綴碼為：000，001，01，10，112、（12分）圖中奇數(shù)點(diǎn)為E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF復(fù)制道路EG、GF，得圖G，

25、則G是歐拉圖。由D開(kāi)始找一條歐拉回路：DEGFGEBACBDCFD。道路長(zhǎng)度為：35+8+20+20+8+40+30+50+19+6+12+10+23=281。試卷六試題與答案一、 填空 15% （每小題 3分）1、 n階完全圖結(jié)點(diǎn)v的度數(shù)d(v) = 。2、 設(shè)n階圖G中有m條邊，每個(gè)結(jié)點(diǎn)的度數(shù)不是k的是k+1，若G中有Nk個(gè)k度頂點(diǎn)，Nk+1個(gè)k+1度頂點(diǎn)，則N k = 。3、 算式的二叉樹(shù)表示為。4、 如圖給出格L，則e的補(bǔ)元是。5、 一組學(xué)生，用二二扳腕子比賽法來(lái)測(cè)定臂力的大小，則幺元是。二、選擇 15% （每小題 3分）1、設(shè)S=0,1,2,3,為小于等于關(guān)系，則S，是（）。A、群；

26、B、環(huán)；C、域；D、格。2、設(shè)a , b , c，*為代數(shù)系統(tǒng)，*運(yùn)算如下：*abcaabcbbaccccc則零元為（）。A、a； B、b； C、c； D、沒(méi)有。3、如右圖相對(duì)于完全圖K5的補(bǔ)圖為（）。4、一棵無(wú)向樹(shù)T有7片樹(shù)葉，3個(gè)3度頂點(diǎn)，其余頂點(diǎn)均為4度。則T有（）4度結(jié)點(diǎn)。A、1； B、2； C、3； D、4。5、設(shè)A，+，·是代數(shù)系統(tǒng)，其中+，·為普通加法和乘法，則A=（）時(shí)，A，+，·是整環(huán)。A、； B、；C、； D、。三、證明 50%1、設(shè)G是（n,m）簡(jiǎn)單二部圖，則。（10分）2、設(shè)G為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，且，則G是連通圖。（10分）3、記“開(kāi)”

27、為1，“關(guān)”為0，反映電路規(guī)律的代數(shù)系統(tǒng)0，1，+，·的加法運(yùn)算和乘法運(yùn)算。如下：+01·01001000110101證明它是一個(gè)環(huán)，并且是一個(gè)域。（14分）4、 是一代數(shù)格，“”為自然偏序，則L，是偏序格。（16分）四、10%設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式，試寫(xiě)出的析取式和合取式（10分）五、10%如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信成路造價(jià)（單位：萬(wàn)元），試給出一個(gè)設(shè)計(jì)方案，使得各城市之間既能夠通信又使總造價(jià)最小。答案：一、填空 15%（每小題3分）1、n-1；2、n(k+1)-2m；3、如右圖；4、0 ；5、臂力小者二、選擇 15%（每小題

28、 3分）題目12345答案DCAAD三、證明 50%（1） 證：設(shè)G=（V，E）對(duì)完全二部圖有當(dāng)時(shí)，完全二部圖的邊數(shù)m有最大值故對(duì)任意簡(jiǎn)單二部圖有。（2） 證：反證法：若G不連通，不妨設(shè)G可分成兩個(gè)連通分支G1、G2，假設(shè)G1和G2的頂點(diǎn)數(shù)分別為n1和n2，顯然與假設(shè)矛盾。所以G連通。（3） （1）0，1，+，·是環(huán)0，1，+是交換群乘：由“+”運(yùn)算表知其封閉性。由于運(yùn)算表的對(duì)稱性知：+運(yùn)算可交換。群：（0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1 ；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0

29、結(jié)合律成立。幺：幺元為0。逆：0，1逆元均為其本身。0，1，·是半群乘：由“·”運(yùn)算表知封閉群：（0·0）·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）= 0；（0·1）·0=0·（1·0）=0 ；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0 。·對(duì)+的分配律 0·（x+y）=0=0+0=(0·x)+(0

30、83;y)； 1·（x+y）當(dāng)x=y (x+y)=0 則；當(dāng)（）則所以均有同理可證：所以·對(duì)+ 是可分配的。由得，0，1，+，·是環(huán)。（2）0，1，+，·是域因?yàn)?，1，+，·是有限環(huán)，故只需證明是整環(huán)即可。乘交環(huán)：由乘法運(yùn)算表的對(duì)稱性知，乘法可交換。含幺環(huán)：乘法的幺元是1無(wú)零因子：1·1=10因此0，1，+，·是整環(huán)，故它是域。4、證：（1 ）“”是偏序關(guān)系，自然偏序反自反性：由代數(shù)格冪等關(guān)系：。反對(duì)稱性：若即：，則傳遞性：則：（2）在L中存在x,y的下（上）確界設(shè)則：事實(shí)上：若x , y 有另一下界c，則是x , y 最

31、大下界，即同理可證上確界情況。四、14%解：函數(shù)表為：00000011010001111000101111011111析取式：合取式：五、10%解：用庫(kù)斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹(shù)。算法為：結(jié)果如圖：樹(shù)權(quán)C(T)=23+1+4+9+3+17=57（萬(wàn)元）即為總造價(jià)試卷七試題與答案一、 填空 15% （每小題 3分）1. 任何(n,m) 圖G = (V,E) , 邊與頂點(diǎn)數(shù)的關(guān)系是 。2. 當(dāng)n為 時(shí),非平凡無(wú)向完全圖Kn是歐拉圖。3. 已知一棵無(wú)向樹(shù)T有三個(gè)3頂點(diǎn),一個(gè)2度頂點(diǎn),其余的都是1度頂點(diǎn),則T中有個(gè)1度頂點(diǎn)。4. n階完全圖Kn的點(diǎn)色數(shù)X(KN)= 。5. 一組學(xué)生,用兩

32、兩扳腕子比賽來(lái)測(cè)定臂力大小,則幺元是 。二、 選擇 15% （每小題 3分）1、下面四組數(shù)能構(gòu)成無(wú)向圖的度數(shù)列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。2、圖 的鄰接矩陣為( )。A、；B、；C、；D、。3、下列幾個(gè)圖是簡(jiǎn)單圖的有( )。A. G1=(V1,E1), 其中 V1=a,b,c,d,e,E1=ab,be,eb,ae,de；B. G2=(V2,E2)其中V2=V1,E2=<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d

33、,e>；C. G=(V3,E3), 其中V3=V1,E3=ab,be,ed,cc；D. G=(V4,E4),其中V4=V1,E4=（a,a）,（a,b）,（b,c）,（e,c）,（e,d）。4、下列圖中是歐拉圖的有( )。5、，其中，為集合對(duì)稱差運(yùn)算，則方程的解為（）。A、； B、； C、； D、。三、 證明 34% 1、 證明：在至少有2 個(gè)人的人群中，至少有2 個(gè)人，他的有相同的朋友數(shù)。（8分）2、 若圖G中恰有兩個(gè)奇數(shù)頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。（8分）3、 證明：在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中，每個(gè)面的面度都是3。（8分）4、 證明循環(huán)群的同態(tài)像必是循環(huán)群。（10分）四、

34、中國(guó)郵遞員問(wèn)題13%求帶權(quán)圖G中的最優(yōu)投遞路線。郵局在v1點(diǎn)。五、 根樹(shù)的應(yīng)用 13%在通訊中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%求傳輸它們最佳前綴碼（寫(xiě)出求解過(guò)程）。六、 10%設(shè)B4=e , a , b , ab ，運(yùn)算*如下表，*則<B4,*>是一個(gè)群（稱作Klein四元群答案：十、 填空 15%（每小題3分）1、；2、奇數(shù)；3、5；4、n；5、臂力小者十一、 選擇 15%（每小題 3分）題目12345答案BCBBA十二、 證明 34%1、（10分）證明：用n個(gè)頂點(diǎn)v1，vn表示n個(gè)人，構(gòu)成頂點(diǎn)

35、集V=v1，vn，設(shè)，無(wú)向圖G=（V，E）現(xiàn)證G中至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同。事實(shí)上，（1）若G中孤立點(diǎn)個(gè)數(shù)大于等于2，結(jié)論成立。（2）若G中有一個(gè)孤立點(diǎn)，則G中的至少有3個(gè)頂點(diǎn)，現(xiàn)不考慮孤立點(diǎn)。設(shè)G中每個(gè)結(jié)點(diǎn)度數(shù)均大于等于1，又因?yàn)镚為簡(jiǎn)單圖，所以每個(gè)頂點(diǎn)度數(shù)都小于等于n-1，由于G中頂點(diǎn)數(shù)到值只能是1，2，n-1這n-1個(gè)數(shù)，因而取n-1個(gè)值的n個(gè)頂點(diǎn)的度數(shù)至少有兩個(gè)結(jié)點(diǎn)度數(shù)是相同的。2、（8分）證：設(shè)G中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u，v。若 u，v不連通，即它們中無(wú)任何通路，則至少有兩個(gè)連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個(gè)奇數(shù)度結(jié)點(diǎn)，與握手定理矛盾。因而u，

36、v必連通。3、（8分）證：n=6,m=12 歐拉公式n-m+f=2知 f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個(gè)面用3條邊圍成。4、（10分）證：設(shè)循環(huán)群A，·的生成元為a，同態(tài)映射為f，同態(tài)像為<f（A），*>，于是都有對(duì)n=1有n=2, 有若n=k-1時(shí)有對(duì)n=k時(shí)，這表明，f(A)中每一個(gè)元素均可表示為，所以<f(A),*>是以f(a) 生成元的循環(huán)群。十三、 中國(guó)郵遞員問(wèn)題 14%解：圖中有4個(gè)奇數(shù)結(jié)點(diǎn)，（1） 求任兩結(jié)點(diǎn)的最短路再找兩條道路使得它們沒(méi)有相同的起點(diǎn)和終點(diǎn)，且長(zhǎng)度總和最短：（2） 在原圖中復(fù)制出，設(shè)圖G，則圖

37、G中每個(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù)的圖G存在歐拉回路，歐拉回路C權(quán)長(zhǎng)為43。十四、 根樹(shù)的應(yīng)用13%解：用100乘各頻率并由小到大排列得權(quán)數(shù)（1） 用Huffman算法求最優(yōu)二叉樹(shù)：（2） 前綴碼用 00000傳送 5；00001傳送 6；0001傳送 7；100傳送 3；101傳送 4；001傳送 2；11傳送 1；01傳送 0 （頻率越高傳送的前綴碼越短）。十五、 10%證明：（1） 乘：由運(yùn)算表可知運(yùn)算*是封閉的。（2） 群：即要證明，這里有43=64個(gè)等式需要驗(yàn)證但： e是幺元，含e的等式一定成立。ab=a*b=b*a，如果對(duì)含a，b的等式成立，則對(duì)含a、b、ab的等式也都成立。剩下只需驗(yàn)證含a

38、、b等式，共有23=8個(gè)等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b； (a*b)*b=ab*b=a=a*(b*b)=a*e=a；(a*a)*a=e*a=a=a*(a*a)=a*e=a ； (a*a)*b=e*b=b=a*(a*b)=a*ab=b；(b*b)*a=e*a=a=b*(b*a)=b*ab=a； (b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b ； (b*a)*b=ab*b=a=b*(a*b)=b*ab=a 。（3） 幺： e為幺元（4） 逆：e -1=e ；a -1=a ；b -1=b ； (a

39、b) -1=ab 。所以<B4,*>為群。試卷八試題與答案一、 填空 15% （每小題 3分）1、 n階完全圖Kn的邊數(shù)為。2、 右圖的鄰接矩陣A= 。3、 圖的對(duì)偶圖為。4、 完全二叉樹(shù)中，葉數(shù)為nt，則邊數(shù)m= 。5、 設(shè)< a,b,c, * >為代數(shù)系統(tǒng)，* 運(yùn)算如下：*abcaabcbbaccccc則它的幺元為；零元為；a、b、c的逆元分別為。二、 選擇 15% （每小題 3分）1、 圖相對(duì)于完全圖的補(bǔ)圖為（）。2、 對(duì)圖G 則分別為（）。A、2、2、2； B、1、1、2； C、2、1、2； D、1、2、2 。3、 一棵無(wú)向樹(shù)T有8個(gè)頂點(diǎn)，4度、3度、2度的分枝

40、點(diǎn)各1個(gè)，其余頂點(diǎn)均為樹(shù)葉，則T中有（）片樹(shù)葉。A、3； B、4； C、5； D、64、 設(shè)<A，+，·>是代數(shù)系統(tǒng)，其中+，·為普通的加法和乘法，則A=（）時(shí)<A，+，·>是整環(huán)。A、； B、；C、； D、。5、 設(shè)A=1，2，10 ，則下面定義的運(yùn)算*關(guān)于A封閉的有（）。A、 x*y=max(x ,y)； B、x*y=質(zhì)數(shù)p的個(gè)數(shù)使得；C、x*y=gcd(x , y)； (gcd (x ,y)表示x和y的最大公約數(shù))；D、x*y=lcm(x ,y) （lcm(x ,y) 表示x和y的最小公倍數(shù)）。三、 證明 45% 1、設(shè)G是（n,m）

41、簡(jiǎn)單二部圖，則。（8分）2、設(shè)G為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，且則G是連通圖。（8分）3、設(shè)G是階數(shù)不小于11的簡(jiǎn)單圖，則G或中至少有一個(gè)是非平圖。（14分）4、記“開(kāi)”為1，“關(guān)”為0，反映電路規(guī)律的代數(shù)系統(tǒng)0，1，+，·的加法運(yùn)算和乘法運(yùn)算。如下：+01·01001000110101證明它是一個(gè)環(huán)，并且是一個(gè)域。（15分）四、 生成樹(shù)及應(yīng)用 10%1、（10分）如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先測(cè)算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間既能夠通信而且總造價(jià)最小。2、（10分）構(gòu)造H、A、P、N、E、W、R、對(duì)應(yīng)的前綴碼，并畫(huà)出與該前綴碼對(duì)應(yīng)的

42、二叉樹(shù)，寫(xiě)出英文短語(yǔ)HAPPY NEW YEAR的編碼信息。五、 5%對(duì)于實(shí)數(shù)集合R，在下表所列的二元遠(yuǎn)算是否具有左邊一列中的性質(zhì)，請(qǐng)?jiān)谙鄳?yīng)位上填寫(xiě)“Y”或“N”。MaxMin+可結(jié)合性可交換性存在幺元存在零元答案：十六、 填空 15%（每小題3分）1、；2、；3、；4、；5、a，c，a、b、沒(méi)有十七、 選擇 15%（每小題 3分）題目12345答案AACDA，C十八、 證明 45%1、 （8分）：設(shè)G=（V，E），對(duì)完全二部圖有當(dāng)時(shí)，完全二部圖的邊數(shù)m有最大值。故對(duì)任意簡(jiǎn)單二部圖有。2、 （8分）反證法：若G不連通，不妨設(shè)G可分成兩個(gè)連通分支G1、G2，假設(shè)G1和G2的頂點(diǎn)數(shù)分別為n1和n2

43、，顯然。與假設(shè)矛盾。所以G連通。3、（14分）（1）當(dāng)n=11時(shí)，邊數(shù)條，因而必有或的邊數(shù)大于等于28，不妨設(shè)G的邊數(shù)，設(shè)G有k個(gè)連通分支，則G中必有回路。（否則G為k棵樹(shù)構(gòu)成的森林，每棵樹(shù)的頂點(diǎn)數(shù)為ni，邊數(shù)mi，則,矛盾）下面用反證法證明G為非平面圖。假設(shè)G為平面圖，由于G中有回路且G為簡(jiǎn)單圖，因而回路長(zhǎng)大于等于3 。于是G的每個(gè)面至少由g ()條邊圍成，由點(diǎn)、邊、面數(shù)的關(guān)系，得：而矛盾，所以G為非平面圖。（2）當(dāng)n>11時(shí)，考慮G的具有11個(gè)頂點(diǎn)的子圖，則或必為非平面圖。如果為非平面圖，則為非平面圖。如果為非平面圖，則為非平面圖。4、 （15分）1）0，1，+，·是環(huán)0，

44、1，+是交換群乘：由“+”運(yùn)算表知其封閉性。由于運(yùn)算表的對(duì)稱性知：+運(yùn)算可交換。群：（0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1 ；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0 結(jié)合律成立。幺：幺元為0。逆：0，1逆元均為其本身。所以，<0，1，+>是Abel群。<0，1，·>是半群乘：由“·”運(yùn)算表知封閉群： (0·0)·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）=1

45、；（0·1）·0=0·（1·0）=1 ；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0 ；·對(duì)+的分配律對(duì) 0·（x+y）=0=0+0=(0·x)+(0·y) 1·（x+y）當(dāng)x=y (x+y)=0 則當(dāng)（）則所以均有同理可證：所以·對(duì)+ 是可分配的。由得，<0，1，+，·>是環(huán)。（2）<0，1，+，·>是域因?yàn)?lt;0，1，+，·>

46、;是有限環(huán)，故只需證明是整環(huán)即可。乘交環(huán)：由乘法運(yùn)算表的對(duì)稱性知，乘法可交換。含幺環(huán)：乘法的幺元是1無(wú)零因子：1·1=10因此0，1，+，·是整環(huán)，故它是域。十九、 樹(shù)的應(yīng)用 20%1、（10分）解：用庫(kù)斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹(shù)。算法略。結(jié)果如圖：樹(shù)權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)五、（10分）由二叉樹(shù)知H、A、P、Y、N、E、W、R對(duì)應(yīng)的編碼分別為000、001、010、011、100、101、110、111。顯然000，001，010，011，100，101，110，111為前綴碼。英文短語(yǔ)HAPPY NEW YEAR 的編碼信息為

47、000 001 010 010 011 100 101 001 001 101 001 111六、5%MaxMin+可結(jié)合性YYY可交換性YYY存在幺元NNY存在零元NNN試卷九試題與答案一、 填空 30% （每空 3分）1、 選擇合適的論域和謂詞表達(dá)集合A=“直角坐標(biāo)系中，單位元（不包括單位圓周）的點(diǎn)集”則A= 。2、 集合A=,的冪集P(A) = 。3、 設(shè)A=1，2，3，4，A上二元關(guān)系R=<1，2>，<2，1>，<2，3>，<3，4>畫(huà)出R的關(guān)系圖。4、 設(shè)A=<1,2>,<2 , 4 >,<3 , 3 &g

48、t; , B=<1,3>,<2,4>,<4,2>,則= 。= 。5、 設(shè)|A|=3，則A上有個(gè)二元關(guān)系。6、 A=1，2，3上關(guān)系R= 時(shí)，R既是對(duì)稱的又是反對(duì)稱的。7、 偏序集的哈斯圖為，則= 。8、 設(shè)|X|=n，|Y|=m則（1）從X到Y(jié)有個(gè)不同的函數(shù)。（2）當(dāng)n , m滿足時(shí)，存在雙射有個(gè)不同的雙射。9、 是有理數(shù)的真值為。10、 Q：我將去，R：我有時(shí)間，公式的自然語(yǔ)言為。11、 公式的主合取式是。12、 若是集合A的一個(gè)分劃，則它應(yīng)滿足。二、 選擇 20% （每小題 2分）1、 設(shè)全集為I，下列相等的集合是（）。A、； B、；C、； D、。2、

49、設(shè)S=N，Q，R，下列命題正確的是（）。A、； B、；C、； D、。3、 設(shè)C=a,b,a,b，則分別為（）。A、C和a,b；B、a,b與；C、a,b與a,b；D、C與C4、 下列語(yǔ)句不是命題的有（）。A、 x=13； B、離散數(shù)學(xué)是計(jì)算機(jī)系的一門必修課； C、雞有三只腳；D、太陽(yáng)系以外的星球上有生物； E、你打算考碩士研究生嗎？5、 的合取式為（）。A、；B、；C、 D、。6、 設(shè)|A|=n，則A上有（）二元關(guān)系。A、2n ； B、n2 ； C、； D、nn； E、。7、 設(shè)r為集合A上的相容關(guān)系，其簡(jiǎn)化關(guān)系圖（如圖），則 I r產(chǎn)生的最大相容類為（）；A、； B、； C、； D、II A的

50、完全覆蓋為（）。A、； B、；C、； D、。8、 集合A=1，2，3，4上的偏序關(guān)系圖為則它的哈斯圖為（）。9、 下列關(guān)系中能構(gòu)成函數(shù)的是（）。A、；B、；C、； D、。10、N是自然數(shù)集，定義（即x除以3的余數(shù)），則f是（）。A、滿射不是單射；B、單射不是滿射；C、雙射；D、不是單射也不是滿射。三、 簡(jiǎn)答題 15% 1、(10分)設(shè)S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”為S上整除關(guān)系，問(wèn)：（1）偏序集的Hass圖如何？（2）偏序集的極小元、最小元、極大元、最大元是什么?2、（5分）設(shè)解釋R如下：DR是實(shí)數(shù)集，DR中特定元素a=0，DR中特定函數(shù)，特定謂詞，問(wèn)公

51、式的涵義如何？真值如何？四、 邏輯推理 10%或者邏輯難學(xué)，或者有少數(shù)學(xué)生不喜歡它；如果數(shù)學(xué)容易學(xué)，那么邏輯并不難學(xué)。因此，如果許多學(xué)生喜歡邏輯，那么數(shù)學(xué)并不難學(xué)。五、10%設(shè)X=1,2,3,4,5，X上的關(guān)系R=<1,1> , < 1 , 2 > , <2 , 4 > , < 3 , 5 > , < 4 , 2 > ，用Warshall方法，求R的傳遞閉包t (R)。六、證明 15%1、 每一有限全序集必是良序集。（7分）2、 設(shè)是復(fù)合函數(shù)，如果滿射，則也是滿射。（8分）答案二十、 填空 20%（每小題2分）1、；2、；3、見(jiàn)右圖；

52、4、< 1 , 2 > , < 2 , 4 > , <3 , 3 > , < 1，3 >，<2,4> ,<4,2>、< 1 , 4 > , < 2 , 2 > ；5、29； 6、< 1 , 1 > , < 2 , 2 > , <3 , 3 > ；7、<a,b>,<a,d>,<a,e>,<b,d>,<b,e>,<a,c>,<a,f>,<a,g>,<c,f>,<c,g>；8、mn、n=m、n!；9、假；10、我將去當(dāng)且僅當(dāng)我有空；11、；12、。二十一、 選擇 20%（每小題 2分）題目12345678910答案A、DCBA、EB、DCB、D；CABD二十二、 簡(jiǎn)