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

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(      )。a只

2、是約束變元b只是自由變元c既非約束變元又非自由變元d既是約束變元又是自由變元4. 下列關(guān)系中，（ ）不是等價關(guān)系。a. 非空集合的冪集的元素間包含關(guān)系；b. 集合之間的等勢關(guān)系；c. 公式之間的等值關(guān)系；d. 圖之間的同構(gòu)關(guān)系。5. 下面等值式中，（ ）是不正確的。a. b.c. d.6下列關(guān)于集合的勢的敘述中，（ ）是錯誤的。a. 實數(shù)集比自然數(shù)集優(yōu)勢；b. 任一無限集合都存在與自己等勢的真子集； c. 集合之間的優(yōu)勢關(guān)系是偏序關(guān)系；d. 有理數(shù)集比整數(shù)集優(yōu)勢。7設(shè)a,b,c是集合，f是關(guān)系，則下列式子中不正確的是（ ）。a b. c. d. 8. 以下序列中，（ ）是簡單可圖的。a. (4

3、,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(n2)階競賽圖都具有哈密頓通路；b 非平凡樹不是歐拉圖，也不是哈密頓圖；c n(n3且為奇數(shù))階的二部圖一定不是哈密頓圖；d 歐拉回路包含圖的所有頂點，哈密頓回路包含圖的所有邊。10下列關(guān)于圖的連通性的敘述中正確的是( )。a. 有向圖是連通的是指它是強(qiáng)連通的； b. 任一無向圖的點連通度都不超過它的邊連通度；c. 在一n階圈cn(n4)上任意去掉兩個頂點得到得圖都有2個連通分支； d. n階無向完全圖的點連通度為n；二、填空題（共

4、8題，每題3分，共24分）1 令f(x)：x是汽車，g(y)：y是火車，h(x,y)：x比y快。則命題“不存在比所有火車都快的汽車”符號化形式為_。2 公式的主析取范式為_。3 集合a=a,b,c,d上的等價關(guān)系共有_個。4 自對偶圖的頂點數(shù)n和邊數(shù)m之間滿足關(guān)系式為m =_。5設(shè)t是有t片樹葉的2叉正則樹，則t應(yīng)該有_個頂點。6p(,) = _,_。7在1到100之間（包含1和100）即不能被2，也不能被3，還不能被5整除的自然數(shù)有_個。8“p僅當(dāng)q”，“只有q才p”，“除非q才p”這三個命題的符號化分別為_ , _ 和 _ 。（請按順序填寫） 三、應(yīng)用、計算和證明題（共6題，46分）1(6

5、分) 在命題邏輯的自然推理系統(tǒng)中構(gòu)造下面推理的證明。前提：(pq)，qr，r結(jié)論：p 2（8分）設(shè)集合a=a，b，c，d，a上的關(guān)系r=<a，a>,<a，b>,<b，a>,<c，d>,<b，c> 求：（1）畫出r的關(guān)系圖。(2分) （2）r的自反閉包、對稱閉包和傳遞閉包的關(guān)系圖。（2分，2分和2分）3（8分）設(shè)<a,r>為一偏序集，其中a=1，2，12，r是a上的整除關(guān)系。（1）畫出<a,r>的哈斯圖；（4分）（2）求a的所有極大元和極小元（2分）（3）求b=2,3,6的最小上界和最大下界（2分）。4.（8分）

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

7、分)三1 （1） 前提引入 （2） 前提引入 （3） （1）（2）析取三段論 （4） 前提引入 （5） 置換(6) (3)(5)析取三段論若未注明推理規(guī)則,或標(biāo)注有錯,扣1分.2 （1） 如圖1 （2） 該題要求畫出三個閉包的關(guān)系圖. 每個關(guān)系圖2分,共6分. 邊少畫或多畫一律判錯.3 (1)如圖2 （2）a的極大元有：7，8，9，10，11，12 a的極小元有：1 （3）b的上界是6,12,最小上界是6 b的下界是1，最小下界是1哈斯圖中若出現(xiàn)水平的邊,扣1分.4（分）（）判斷下圖是否為歐拉圖，若是，請給出一歐拉回路（用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可）；若不是，請說明原因；（4分）答：因為該圖

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

9、初級回路（圈）。證明：不妨設(shè)是連通圖，若g不連通，因為的各連通分支的最小度也都大等于k，因而可對它的某個連通分支進(jìn)行討論。設(shè)u,v為g中任意兩個頂點，由g是連通圖，因而u,v之間存在路徑，用“擴(kuò)大路徑法”擴(kuò)大這條路徑，設(shè)最后得到的“極大路徑”為t=v0v1vt,則tk，事實上若存在“極大路徑” s=v0v1vs且s<k，則v0只能與s中的頂點相鄰，因為g為簡單圖，所以與v0相鄰的頂點最多為s個，而s<k，這與(g)k矛盾，所以“極大路徑”長度大等于k。在t上構(gòu)造圈，由于(v0)(g)k2，因而v0除與t上的v1相鄰?fù)猓€存在t上的k-1個頂點與v0相鄰，則為一個圈且長度大等于k+1。注意:也可直接設(shè)是g的最長路徑.（8分）在一棵有3個2度頂點，2個4度頂點，其余頂點都是樹葉的無向樹中，應(yīng)該有幾片樹葉？（2分）請畫出所有這樣的非同構(gòu)的無向樹。（6分）答：設(shè)樹葉有x片，則邊數(shù)m=3+2+x-1=4+x，由