離散數(shù)學(xué)期末考試及答案

1、沈陽師范大學(xué)離散考試預(yù)測題一、 選擇題（共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、B只是自由變元C既非約束變元又非自由變元D既是約束變元又是自由變元4. 下列關(guān)系中，（ ）不是等價(jià)關(guān)系。A. 非空集合的冪集的元素間包含關(guān)系；B. 集合之間的等勢關(guān)系；C. 公式之間的等值關(guān)系；D. 圖之間的同構(gòu)關(guān)系。5. 下面等值式中，（ ）是不正確的。A. B.C. D.6下列關(guān)于集合的勢的敘述中，（ ）是錯(cuò)誤的。A. 實(shí)數(shù)集比自然數(shù)集優(yōu)勢；B. 任一無限集合都存在與自己等勢的真子集； C. 集合之間的優(yōu)勢關(guān)系是偏序關(guān)系；D. 有理數(shù)集比整數(shù)集優(yōu)勢。7設(shè)A,B,C是集合，F(xiàn)是關(guān)系，則下列式子中不正確的是（ ）。A B. C. D. 8. 以下序列中，（ ）是簡單可圖的。A. (4,4,3,

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)階競賽圖都具有哈密頓通路；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；二、填空題（共8題，每題

4、3分，共24分）1 令F(x)：x是汽車，G(y)：y是火車，H(x,y)：x比y快。則命題“不存在比所有火車都快的汽車”符號化形式為_。2 公式的主析取范式為_。3 集合A=a,b,c,d上的等價(jià)關(guān)系共有_15_個(gè)。4 自對偶圖的頂點(diǎn)數(shù)n和邊數(shù)m之間滿足關(guān)系式為m =_ m=2n-2_。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è)命題的符號化分別為_ _ , _ 和 _ 。（請按順序填寫） 三、應(yīng)用、計(jì)算和證明題（共6題

5、，46分）1(6分) 在命題邏輯的自然推理系統(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

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

7、. (該小題每空1分)三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（分）（）判斷下圖是否為歐拉圖，若是，請給出一歐拉回路（用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可）；若不是，請說明原因；（

8、4分）答：因?yàn)樵搱D是連通圖且圖中沒有奇度頂點(diǎn)，所以該圖是歐拉圖(只要判斷正確給2分)。歐拉回路標(biāo)序如下圖：10111213314找的歐拉回路正確再2分（2）判斷下圖是否為哈密頓圖，若是，請給出一哈密頓回路（用阿拉伯?dāng)?shù)字在頂點(diǎn)上標(biāo)明順序即可）；若不是，請說明原因（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是無向簡單圖且(G)k2，試證明G中存在長

9、度大于等于k+1的初級回路（圈）。證明：不妨設(shè)是連通圖，若G不連通，因?yàn)榈母鬟B通分支的最小度也都大等于k，因而可對它的某個(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)镚為簡單圖，所以與v0相鄰的頂點(diǎn)最多為s個(gè)，而s<k，這與(G)k矛盾，所以“極大路徑”長度大等于k。在t上構(gòu)造圈，由于(v0)(G)k2，因而v0除與t上的v1相鄰?fù)?，還存在t上的k-1個(gè)頂點(diǎn)與v0相鄰，則為一個(gè)圈且長度大等于k+1。注意:也可直接設(shè)是G的最長路徑.（8分）在一棵有3個(gè)2度頂點(diǎn)，2個(gè)4度頂點(diǎn)，其余頂點(diǎn)都是樹葉的無向樹中，應(yīng)該有幾片樹葉？（2分）請畫出所有這樣的非同構(gòu)的無向樹。（6分）答：設(shè)樹葉有x片，則邊數(shù)m=3+2+x-