2019年4月全國自考離散數(shù)學(xué)試題及答案解析

1、2019年4月全國自考離散數(shù)學(xué)試題及答案解析一、單選題(共4題，共8分)1. 下面四組數(shù)能構(gòu)成無向圖的度數(shù)列的有()。A.2,3,4,5,6,7B.1,2,2,3,4C.2,1,1,1,2D.3,3,5,6,02. 下列幾個圖是簡單圖的有()。A.G1=(V1,E1),其中V1=a,b,c,d,e,E1=ab,be,eb,ae,deB.G2=(V2,E2)其中V2=V1,E2=,C.G=(V3,E3),其中V3=V1,E3=ab,be,ed,ccD.G=(V4,E4),其中V4=V1,E4=(a,a),(a,b),(b,c),e,c),(e,d)。3. 下列圖中是歐拉圖的有()。A.B.C.D

2、.4.與命題公式6(Q-R)等價的公式是()A.B.C.D.二、判斷題（共10題，共20分）5 .命題公式（AA（A-B）-B是一個矛盾式。正確錯誤6 .任何循環(huán)群必定是阿貝爾群，反之亦真。正確錯誤7 .根樹中最長路徑的端點都是葉子。正確錯誤8 .若集合A上的關(guān)系R是對稱的，則RA-1也是對稱的正確錯誤9 .數(shù)集合上的不等關(guān)系（？）可確定A的一個劃分。正確錯誤10 .設(shè)集合AB、C為任意集合，若AXB=刖C,則B=G正確錯誤11 .函數(shù)的復(fù)合運算“?！睗M足結(jié)合律。正確錯誤12 .若G是歐拉圖，則其邊數(shù)e合結(jié)點數(shù)v的奇偶性不能相反。正確錯誤13 .圖G為(n,m)圖，G的生成樹TG必有n個結(jié)點。

3、正確錯誤14 .使命題公式6(QVR)的真值為F的真值指派的P、QR值分別是T、F、F。正確錯誤三、填空題(共10題，共20分)15 .任何(n,m)圖G=(V,E),邊數(shù)與頂點度數(shù)的關(guān)系是。16 .當(dāng)n為Bt非平凡無向完全圖Kn是歐拉圖。17 .已知一棵無向樹T有三個3頂點,一個2度頂點,其余的都是1度頂點,則T中有個1度頂點。18 .設(shè)X1,2,3,4,R1,2,2,4,3,3,則r(R)=;s(R)=;t(R)=。19 .任意兩個不同小項的合取為，全體小項的析取式為。20 .設(shè)Q(x):x為偶數(shù)，P(x):x為素數(shù)，則下列命題：(1)存在唯一偶素數(shù);(2)至多有一個偶素數(shù);分別形式化：(

4、1) (2)。21 .含5個結(jié)點，4條邊的無向連通圖(不同構(gòu))有個，它們22 .設(shè)T為根樹，若,則稱T為m元樹；若M稱T為完全m叉樹。23 .在代數(shù)系統(tǒng)（N，+）中，其單位元是0，僅有有逆元。24 .如果連通平面圖G有n個頂點，e條邊，則G有個面。四、問答題（共5題，共38分）25 .若圖G中恰有兩個奇數(shù)頂點，則這兩個頂點是連通的。26 .證明：在6個結(jié)點12條邊的連通平面簡單圖中，每個面的面度都是3。27 .某次會議有20人參加，其中每人至少有10個朋友，這20人擬圍一桌入席，用圖論知識說明是否可能每人鄰做的都是朋友?（理由）28 .試判斷（z,W）是否為格腿明理由29 .設(shè)R是實數(shù)集，f:

5、RxRR,f（a,b）a+b,g:RxRR,g（a,b尸ab。求證：f和g都是滿射，但不是單射。五、計算題（共10題，共20分）30 .在通訊中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求傳輸它們最佳前綴碼（寫出求解過程）。31 .求命題公式pAqVr的主合取范式與主析取范式。32 .無向圖G有12條邊，G中有6個3度結(jié)點，其余結(jié)點的度數(shù)均小于3,問G中至少有多少個結(jié)點？33 .無向圖G有9個結(jié)點，每個結(jié)點的度數(shù)不是5就是6，求證5個6度結(jié)點或6個5度結(jié)點。1、正確答案B2、正確答案B3、正確答案B4、正確答案B5、正確

6、答案錯誤6、正確答案錯誤7、正確答案錯誤8、正確答案正確9、正確答案錯誤11、正確答案：正確12、正確答案：錯誤13、正確答案：正確14、正確答案：正確15、正確答案：16、正確答案：奇數(shù)17、正確答案：518、正確答案：19、正確答案：永假式（矛盾式）、永真式（重言式）20、正確答案：21、正確答案：3、22、正確答案：每個結(jié)點的出度都小于等于m;除葉子外，每個結(jié)點的出度都等于mi23、正確答案：124、正確答案：e+2-n25、正確答案：證：設(shè)G中兩個奇數(shù)度結(jié)點分別為u,v若u,v不連通，即它們中無任何通路，則至少有兩個連通分支G1、G2,使得u,v分別屬于G1和G2于是G1與G2中各含有一個奇數(shù)度結(jié)點，與握手定理矛盾。因而u，v必連通。26、正確答案：證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8。由圖論基本定理知：所以必有，即每個面用3條邊圍成。27.某次會議有20人參加，其中每人至少有10個朋友，這20人擬圍一桌入席，用圖論知識說明是否可能每人鄰做的都是朋友?(理由)正確答案：解：可能。將人用結(jié)點表示，當(dāng)兩人是朋友時相應(yīng)結(jié)點間連一條邊，則得一個無向圖,，20人圍一桌，使每人鄰做都是朋友，即要找一個過每個點一次且僅一次得回路。由題已知，由判定定理，G中存在一條漢密爾頓回路。即所談情況可