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

1、沈陽師范大學離散考試預測題一、 選擇題（共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. 下列關系中，（ ）不是等價關系。A. 非空集合的冪集的元素間包含關系；B. 集合之間的等勢關系；C. 公式之間的等值關系；D. 圖之間的同構關系。5. 下面等值式中，（ ）是不正確的。A. B.C. D.6下列關于集合的勢的敘述中，（ ）是錯誤的。A. 實數(shù)集比自然數(shù)集優(yōu)勢；B. 任一無限集合都存在與自己等勢的真子集； C. 集合之間的優(yōu)勢關系是偏序關系；D. 有理數(shù)集比整數(shù)集優(yōu)勢。7設A,B,C是集合，F(xià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. 下列敘述中錯誤的是( )。A n(n2)階競賽圖都具有哈密頓通路；B 非平凡樹不是歐拉圖，也不是哈密頓圖；C n(n3且為奇數(shù))階的二部圖一定不是哈密頓圖；D 歐拉回路包含圖的所有頂點，哈密頓回路包含圖的所有邊。10下列關于圖的連通性的敘述中正確的是( )。A. 有向圖是連通的是指它是強連通的； B. 任一無向圖的點連通度都不超過它的邊連通度；C. 在一n階圈Cn(n4)上任意去掉兩個頂點得到得圖都有2個連通分支； D. 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上的等價關系共有_15_個。4 自對偶圖的頂點數(shù)n和邊數(shù)m之間滿足關系式為m =_ m=2n-2_。5設T是有t片樹葉的2叉正則樹，則T應該有_個頂點。6P(,) = _,_。7在1到100之間（包含1和100）即不能被2，也不能被3，還不能被5整除的自然數(shù)有_個。8“p僅當q”，“只有q才p”，“除非q才p”這三個命題的符號化分別為_ _ , _ 和 _ 。（請按順序填寫） 三、應用、計算和證明題（共6題

5、，46分）1(6分) 在命題邏輯的自然推理系統(tǒng)中構造下面推理的證明。前提：(PQ)，QR，R結論：P 2（8分）設集合A=a，b，c，d，A上的關系R=<a，a>,<a，b>,<b，a>,<c，d>,<b，c> 求：（1）畫出R的關系圖。(2分) （2）R的自反閉包、對稱閉包和傳遞閉包的關系圖。（2分，2分和2分） 3（8分）設<A,R>為一偏序集，其中A=1，2，12，R是A上的整除關系。（1）畫出<A,R>的哈斯圖；（4分）（2）求A的所有極大元和極小元（2分）（3）求B=2,3,6的最小上界和最大下界（2

6、分）。4.（8分）判斷左圖是否為歐拉圖，若是，請給出一歐拉回路（用阿拉伯數(shù)字在邊上標明順序即可）；若不是，請說明原因；（4分）判斷右圖是否為哈密頓圖，若是，請給出一哈密頓回路（用阿拉伯數(shù)字在頂點上標明順序即可）；若不是，請說明原因（4分）； 5 （8分） 設G是無向簡單圖且(G)k2，試證明G中存在長度大于等于k+1的初級回路（圈）。6 （8分）在一棵有3個2度頂點，2個4度頂點，其余頂點都是樹葉的無向樹中，應該有幾片樹葉？（2分）請畫出所有這樣的非同構的無向樹。（6分）答案及評分標準一 選擇題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ī)則,或標注有錯,扣1分.2 （1） 如圖1 （2） 該題要求畫出三個閉包的關系圖. 每個關系圖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（分）（）判斷下圖是否為歐拉圖，若是，請給出一歐拉回路（用阿拉伯數(shù)字在邊上標明順序即可）；若不是，請說明原因；（

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

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