最新廈大離散數(shù)學(xué)期末試卷2015試題+完整答案

1、1廈門大學(xué)離散數(shù)學(xué)課程試卷一、選擇題(共 10 題，每題 3 分，共 30 分)1. 下列語句為命題的是()。A. 勿踏草地；。B. 你去圖書館嗎？；C. 月球上有水；D. 本命題為假。2. 下列推理中，()是錯誤的。A. 如果 x 是有理數(shù)，則它為整數(shù)。1/2 是有理數(shù)。所以 1/2 是整數(shù)。B. 若周末氣溫超過 30 度，小紅就去游泳。小紅周末沒去游泳。所以周末氣溫沒超過30 度。C. 下午小明或者去看電影，或者去打籃球。下午小明沒去打籃球。因此下午小明去看電影了。D. 若 a 能被 4 整除，則 a 能被 2 整除。a 能被 2 整除。因此 a 能被 4 整除。3. 謂詞公式x(P(x)

2、 -yR(y) Q(x)中的 x()。A. 只是約束變元B. 只是自由變元2C. 既非約束變元又非自由變元D. 既是約束變元又是自由變元4.下列關(guān)系中，()不是等價關(guān)系。A. 非空集合的幕集的元素間包含關(guān)系;B. 集合之間的等勢關(guān)系；C. 公式之間的等值關(guān)系；D. 圖之間的同構(gòu)關(guān)系。5.下面等值式中，()是不正確的。A.- x(A(x) B(x)：= - xA(x) - xB(x)B.-1x( A(x) B(x) xA(x) TxB(x)C.x(A(x) B)= xA(x) BD._x(A B(x)= A、-xB(x)6.下列關(guān)于集合的勢的敘述中，()是錯誤的A.實數(shù)集比自然數(shù)集優(yōu)勢；B.任一

3、無限集合都存在與自己等勢的真子集;3C.集合之間的優(yōu)勢關(guān)系是偏序關(guān)系;D.有理數(shù)集比整數(shù)集優(yōu)勢。7設(shè) A,B,C 是集合，F(xiàn) 是關(guān)系，G : A B, D A，則下列式子中不正確的是()A. A-B=：=A_. B=BB.G (G(D)二 DC.FA - B =FA - FBD.(A二B)二C = A二(B二C)8. 以下序列中，()是簡單可圖的。A. (4,4,3,3,2,2); B. (3,3,3,1); C. (5,4,3,2,2); D. (6,6,3,2,2,2,1)。9. 下列敘述中錯誤的是()。A. n(n 2)階競賽圖都具有哈密頓通路；B. 非平凡樹不是歐拉圖，也不是哈密頓圖；

4、C. n(n 3 且為奇數(shù))階的二部圖一定不是哈密頓圖；D. 歐拉回路包含圖的所有頂點，哈密頓回路包含圖的所有邊。10.下列關(guān)于圖的連通性的敘述中正確的是 ()。A. 有向圖是連通的是指它是強連通的；B. 任一無向圖的點連通度都不超過它的邊連通度；4C. 在一 n 階圈 Cn(n4)上任意去掉兩個頂點得到得圖都有2 個連通分支；D. n 階無向完全圖的點連通度為 n；二、填空題(共 8 題，每題 3 分，共 24 分)1 令 F(x) : x 是汽車，G(y) : y 是火車，H(x,y) : x 比 y 快。則命題“不存在比所有火車都快的汽車”符號化形式為Px(F(x)a(Wy(G(y)T

5、H(x,y)_。2._ 公式(p T q)小的主析取范式為mO M m4 “ m6_。3.集合 A=a,b,c,d上的等價關(guān)系共有 _ 。4.自對偶圖的頂點數(shù) n 和邊數(shù) m 之間滿足關(guān)系式為 m =_。5.設(shè) T 是有 t 片樹葉的 2 叉正則樹，則 T 應(yīng)該有_ 頂點。6.P(,) = _,。7.在 1 到 1OO 之間(包含 1 和 1OO)即不能被 2,也不能被 3,還不能被 5 整除的自然數(shù)有_ 。8._ “p僅當(dāng) q”，“只有 q 才 p”，“除非 q 才 p”這三個命題的符號化分別為 _ , _和_ 。(請按順序填寫)三、應(yīng)用、計算和證明題(共 6 題，46 分)51.(6 分)

6、在命題邏輯的自然推理系統(tǒng)中構(gòu)造下面推理的證明6前提：r (PAnQ),n QV R，門 R結(jié)論P2.（ 8 分）設(shè)集合 A=a, b, c, d, A 上的關(guān)系 R=,b ,求：（1）畫出 R 的關(guān)系圖。（2 分）（2） R 的自反閉包、對稱閉包和傳遞閉包的關(guān)系圖。（2 分，2 分和 2 分）3.（ 8 分）設(shè)為一偏序集，其中 A=1, 2，,，12，R 是 A 上的整除關(guān)系。（1）畫出的哈斯圖；（4 分）（2）求 A 的所有極大元和極小元（2 分）（3）求 B=2,3,6 的最小上界和最大下界（ 2 分）。4.（8 分）判斷左圖是否為歐拉圖， 若是，請給出一歐拉回路（用阿拉伯?dāng)?shù)字在邊上標(biāo)明順

7、序即可）若不是，請說明原因；（ 4 分）判斷右圖是否為哈密頓圖，若是，請給出一哈密頓回路（用阿拉伯?dāng)?shù)字在頂點上標(biāo)明順序即可）；若不是，請說明原因（ 4 分）；c75.（ 8 分）設(shè) G 是無向簡單圖且S（G） k 2,試證明 G 中存在長度大于等于 k+1 的初級回 路（圈）。6.（ 8 分）在一棵有 3 個 2 度頂點，2 個 4 度頂點，其余頂點都是樹葉的無向樹中，應(yīng)該有 幾片樹葉？ （ 2 分）請畫出所有這樣的非同構(gòu)的無向樹。（6 分）答案及評分標(biāo)準(zhǔn)一選擇題CDDAC DCADD1.- x(F(x) -y(G(y) H (x, y)8或者-x(F(x)；_.y(G(y)一H (x, y)

8、2. mim3m793. 154. m=2 n-25. 2t-16. , , , 7. 268.p；q,p；q,p；q(該小題每空 1 分)2( 1) 如圖 11(1) 一Q R(2)-R(3)-Q(4)(P Q)(5)_P Qp前提引入前提引入(1) (2)析取三段論前提引入置換(3)(5)析取三段論若未注明推理規(guī)則，或標(biāo)注有錯，扣 110(2)r(R) = R _R= R _ IA=：a,a ，: a,b，: b,a，: c,d，: b,c _ IAs(R) = R _ R =：a,a ,：a,b，: b,a，: c,d，: b,c，: d,c ， : c,b 2 _t(R)=R_ R 珂

9、：a,a，: a,b ，:：a,c ，:：a,d，:：b,b，: b,d：b,a，: c,d，: b,c 該題要求畫出三個閉包的關(guān)系圖每個關(guān)系圖 2 分，共 6 分.邊少畫或多畫一律判錯.3 (1)如圖 2J0圖 2!（2） A 的極大元有：7, 8，9，10，11，12A 的極小元有：1（3）B 的上界是6,12,最小上界是 6 B 的下界是 1，最小下界是 1哈斯圖中若出現(xiàn)水平的邊，扣 1 分.114.(8 分)(1)判斷下圖是否為歐拉圖，若是，請給出一歐拉回路(用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可)；若不是,請說明原因；(4 分)答：因為該圖是連通圖且圖中沒有奇度頂點，所以該圖是歐拉圖(只要判

10、斷正確給 2 分)。歐拉回路標(biāo)序如下圖：找的歐拉回路正確再 2 分(2)判斷下圖是否為哈密頓圖，若是，請給出一哈密頓回路(用阿拉伯?dāng)?shù)字在頂點上標(biāo)明順序即可)；若不是，請說明原因(4 分)23457612答：該圖不是哈密頓圖(2 分)。取 V=4,6,8,從圖中刪除 V,得五個連通分支，如下圖所示, 所以該圖不是哈密頓圖。(2 分)另一證明：反證若有哈密頓圈，由于點 5,7,9 都是二度點，因此該哈密頓圈必包含邊(4,5)(5,6)(6,7)(7,8)(8,9)(9,4),這 6 條邊構(gòu)成一個圈,矛盾135.( 8 分)設(shè) G 是無向簡單圖且 S (G) k 2,試證明 G 中存在長度大于等于

11、k+1 的初級回路(圈)。證明：不妨設(shè) G是連通圖，若G 不連通，因為 G的各連通分支的最小度也都大等于k，因而可對它的某個連通分支進(jìn)行討論。設(shè)u,v 為 G 中任意兩個頂點，由 G 是連通圖，因而 u,v 之間存在路徑，用“擴(kuò)大路徑法”擴(kuò)大這條路徑，設(shè)最后得到的“極大路徑”為 rt=voVi, Vt,則 t k，事實上若存在“極大路徑” rs=voVi, Vs且 sk，則 vo只能與 r沖的頂點相鄰，因為 G 為簡單圖，所以與 vo相鄰的頂點最多為 s 個，而 s k 矛盾，所以“極大路徑”長度大等于k。在 rt上構(gòu)造圈，由于S(vo) S(G) k2，因而 vo除與 rt上的 vi相鄰?fù)?，還存在 rt上的 k-i 個頂點 VjV-,亠(1 vh vi2*ikt)與 V。相鄰，則VOVL.VJ.U 人。為一個圈且長度大等于 k+1。6 74914注意：也可直接設(shè) r 是 G 的最長路徑.6.（ 8 分）在一棵有 3 個 2 度頂點，2 個 4 度頂點，其余頂點都是樹葉的無向樹中，應(yīng)該有幾片樹葉？（2 分）請畫出所有這樣的非同構(gòu)的無向樹。（6 分）答：設(shè)樹葉有 x 片