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

1、最新精品推薦廈門大學(xué)離散數(shù)學(xué)課程試卷一、 選擇題（共10題，每題3分，共30分）1、下列語句為命題的是（ ）。a勿踏草地；。b你去圖書館嗎？；c月球上有水；d本命題為假。2 下列推理中，（ ）是錯(cuò)誤的。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、是約束變?cè)猙只是自由變?cè)猚既非約束變?cè)址亲杂勺冊(cè)猟既是約束變?cè)质亲杂勺冊(cè)?. 下列關(guān)系中，（ ）不是等價(jià)關(guān)系。a. 非空集合的冪集的元素間包含關(guān)系；b. 集合之間的等勢(shì)關(guān)系；c. 公式之間的等值關(guān)系；d. 圖之間的同構(gòu)關(guān)系。5. 下面等值式中，（ ）是不正確的。a. b.c. d.6下列關(guān)于集合的勢(shì)的敘述中，（ ）是錯(cuò)誤的。a. 實(shí)數(shù)集比自然數(shù)集優(yōu)勢(shì)；b. 任一無限集合都存在與自己等勢(shì)的真子集； c. 集合之間的優(yōu)勢(shì)關(guān)系是偏序關(guān)系；d. 有理數(shù)集比整數(shù)集優(yōu)勢(shì)。7設(shè)a,b,c是集合，f是關(guān)系，則下列式子中不正確的是（ ）。a b. c. d. 8. 以下序列中，（ ）是簡(jiǎn)單可圖的。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. 下列敘述中錯(cuò)誤的是( )。a n(n2)階競(jìng)賽圖都具有哈密頓通路；b 非平凡樹不是歐拉圖，也不是哈密頓圖；c n(n3且為奇數(shù))階的二部圖一定不是哈密頓圖；d 歐拉回路包含圖的所有頂點(diǎn)，哈密頓回路包含圖的所有邊。10下列關(guān)于圖的連通性的敘述中正確的是( )。a. 有向圖是連通的是指它是強(qiáng)連通的； b. 任一無向圖的點(diǎn)連通度都不超過它的邊連通度；c. 在一n階圈cn(n4)上任意去掉兩個(gè)頂點(diǎn)得到得圖都有2個(gè)連通分支； d. n階無向完全圖的點(diǎn)連通度為n；二、填空題（共

4、8題，每題3分，共24分）1 令f(x)：x是汽車，g(y)：y是火車，h(x,y)：x比y快。則命題“不存在比所有火車都快的汽車”符號(hào)化形式為_。2 公式的主析取范式為_。3 集合a=a,b,c,d上的等價(jià)關(guān)系共有_個(gè)。4 自對(duì)偶圖的頂點(diǎn)數(shù)n和邊數(shù)m之間滿足關(guān)系式為m =_。5設(shè)t是有t片樹葉的2叉正則樹，則t應(yīng)該有_個(gè)頂點(diǎn)。6p(,) = _,_。7在1到100之間（包含1和100）即不能被2，也不能被3，還不能被5整除的自然數(shù)有_個(gè)。8“p僅當(dāng)q”，“只有q才p”，“除非q才p”這三個(gè)命題的符號(hào)化分別為_ , _ 和 _ 。（請(qǐng)按順序填寫） 三、應(yīng)用、計(jì)算和證明題（共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的自反閉包、對(duì)稱閉包和傳遞閉包的關(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、判斷左圖是否為歐拉圖，若是，請(qǐng)給出一歐拉回路（用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可）；若不是，請(qǐng)說明原因；（4分）判斷右圖是否為哈密頓圖，若是，請(qǐng)給出一哈密頓回路（用阿拉伯?dāng)?shù)字在頂點(diǎn)上標(biāo)明順序即可）；若不是，請(qǐng)說明原因（4分）； 5 （8分） 設(shè)g是無向簡(jiǎn)單圖且(g)k2，試證明g中存在長(zhǎng)度大于等于k+1的初級(jí)回路（圈）。6 （8分）在一棵有3個(gè)2度頂點(diǎn)，2個(gè)4度頂點(diǎn)，其余頂點(diǎn)都是樹葉的無向樹中，應(yīng)該有幾片樹葉？（2分）請(qǐng)畫出所有這樣的非同構(gòu)的無向樹。（6分）答案及評(píng)分標(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)注有錯(cuò),扣1分.2 （1） 如圖1 （2） 該題要求畫出三個(gè)閉包的關(guān)系圖. 每個(gè)關(guān)系圖2分,共6分. 邊少畫或多畫一律判錯(cuò).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（分）（）判斷下圖是否為歐拉圖，若是，請(qǐng)給出一歐拉回路（用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可）；若不是，請(qǐng)說明原因；（4分）答：因?yàn)樵搱D

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

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