離散數(shù)學(xué)期末考試試題（配答案）模擬題(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上模擬題2廣東技術(shù)師范學(xué)院模擬試題 科 目：離散數(shù)學(xué) 考試形式：閉卷 考試時間: 120 分鐘系別、班級： 姓名： 學(xué)號： 一、填空20%（每空2分）：1若對命題P賦值1，Q賦值0，則命題（表示雙條件）的真值為 0 。2命題“如果你不看電影，那么我也不看電影”（P：你看電影，Q：我看電影）的符號化為 PQ3公式的對偶公式為_（PQ）（P（QS）_。4圖 的對偶圖為 5.若關(guān)系R是等價關(guān)系，則R滿足_自反性，對稱性，傳遞性_。 6代數(shù)系統(tǒng)是群，則它滿足_結(jié)合律，有幺元 ，每個元素都有遞元_。 7若連通平面圖共有r個面，其中，則它滿足的Euler公式為_v-e+r=2_。8

2、. n個結(jié)點(diǎn)的無向完全圖Kn的邊數(shù)為 n（n-1）/2 ，歐拉圖的充要條件是 頂點(diǎn)都是偶頂點(diǎn)且是連通的 。9. 設(shè)I為整數(shù)集合，R=| xy（mod3），則1=_ ，-2,1,4，_ 。10代數(shù)系統(tǒng)是環(huán)，若對運(yùn)算“ ”還滿足a，bR，使得ab0，可換，含幺元 則是整環(huán)。二、選擇10%（每小題2分）1集合對（ ）運(yùn)算封閉。A、加法； B、減法； C、乘法； D、 。2設(shè)I為整數(shù)集合，m是任意正整數(shù)，是由模m的同余類組成的同余類集合，在上定義運(yùn)算，則代數(shù)系統(tǒng)最確切的性質(zhì)是 ）。A、封閉的代數(shù)系統(tǒng)； B、半群； C、幺元； D、群。3設(shè)是偏序格，其中N是自然數(shù)集合，“”是普通的數(shù)間“小于等于” 關(guān)系

3、，則 有（ ）。A、a ； B、b ； C、max(a，b) ； D、min(a，b)。4連通非平凡的無向圖G有一條歐拉回路當(dāng)且僅當(dāng)圖G ( )。A、只有一個奇度結(jié)點(diǎn)； B、只有兩個奇度結(jié)點(diǎn)； C、只有三個奇度結(jié)點(diǎn)； D、沒有奇度結(jié)點(diǎn)。5設(shè)無向圖是連通的且 若（ ）則G是樹。 A、m=n+1 ； B、n=m+1 ； C、 ； D、 。三、12%符號化語句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結(jié)論。解: 設(shè)A(x):x是病人，B(x):x是醫(yī)生，C(x):x是騙子，D(x,y):x相信y前提：(x)(A(X)(y)(B(y)D(x,y)(x)(y)(A(

4、x)(y)D(x,y)結(jié)論：(x)(B(x)C(x)制表如下：編號公式依據(jù)（1）(x)(A(x)(y)(B(y)D(x,y)前提（2）A(a)(y)(B(y)D(a,y)(1),Es（3）A(a),(y)(B(y)D(a,y)(2)（4）(x)(y)(A(x)C(y)D(x,y)前提（5）(y)(A(a)C(y)D(a,y)(4),Us（6）A(a)(y)(C(y)D(a,y)(5)（7）(y)(C(y)D(a,y)(3)(6)（8）B(d)D(a,d)(3),Us（9）C(e)D(a,e)(7),Us（10）B(d)C(e)(8)(9)（11）(x)(B(x)C(x)(10),UG四、8%：

5、設(shè)，偏序集的Hass圖為求 A中最小元與最大元； 的上界和上確界，下界和下確界。解：（1）A中最小元：沒有；最大元： x1（2）上界x1 x3上確界 x3 下界無 下確界無（注：離散數(shù)學(xué)及應(yīng)用（溫武）127頁概念，自己去研究）五、8%：求集合的并與交。（注：寫這個還真麻煩，丑，呃）六、15% 已知某樹有2個2度結(jié)點(diǎn)、3個3度結(jié)點(diǎn)、4個4度結(jié)點(diǎn)，問有幾個葉子點(diǎn)（無其它度數(shù)點(diǎn)）解：設(shè)共有k個葉子點(diǎn)，總邊數(shù)為x，則2+3+4+k=x+1223344k=2x解得：k=13，x=21七、8% 若圖G不連通，則G的補(bǔ)圖是連通的。證明：G不連通，則G的連通分支有G1，G2，Gm,(m2)在補(bǔ)圖非G中找兩個頂

6、點(diǎn)，u，v有兩種情況：u，v落在G的不同連通分支中，uGi，vGj，ij；(u,v)是補(bǔ)圖非G的一條邊，故u，v連通。u，v都在Gi中，則找另一個連通分支Gj，在Gj找任意一個頂點(diǎn)w，(u,w),(w,v)是G的邊，則u，v在補(bǔ)圖非G邊連通。八、10% 求圖中的一棵最小生成樹。解：2九、9% 若集合（，），（，），（，），1、證明R是X上的等價關(guān)系。2、求出X關(guān)于R的商集。證明：1.自反性（x1，y1）x，由于x1+y1=y1+x1，所以（x1，y1），（x1，y1）R對稱性（x1，y1），（x2，y2）R,要證明（x2，y2），（x1，y1）R因?yàn)閤1+y2=x2+y1及自反性，可得:x2+y1=x1+y2所以具有對稱性。傳遞性 （x1，y1