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

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請聯(lián)系刪除，謝謝！沈陽師范大學(xué)離散考試預(yù)測題一、選擇題（共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)yR(yQ(x)中的x()。A．只是約束變元B．只是自由變元C．既非約束變元又非自由變元D．既是約束變元又是自由變元4.下列關(guān)系中，（）不是等價關(guān)系。A.非空集合的冪集的元素間包含關(guān)系；B.集合之間的等勢關(guān)系；C.公式之間的等值關(guān)系；D.圖之間的同構(gòu)關(guān)系。5.下面等值式中，（）是不正確的。A.x((x)B(x(x)xB(x)B.x((x)B(x(x)xB(x)C.x((x)B)(x)BD.x(AB(xAxB(x)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(xiàn)是關(guān)系，G:AB,DA，則下列式子中不正確的是（）。A．ABABBB.G(G(D))D1C.F[AB]F[]F[B]D.(AB)CA(BC)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．非平凡樹不是歐拉圖，也不是哈密頓圖；C．n(n≥3且為奇數(shù))階的二部圖一定不是哈密頓圖；D．歐拉回路包含圖的所有頂點，哈密頓回路包含圖的所有邊。10．下列關(guān)于圖的連通性的敘述中正確的是()。A.有向圖是連通的是指它是強連通的；B.任一無向圖的點連通度都不超過它的邊連通度；C.在一n階圈Cn(n≥4)上任意去掉兩個頂點得到得圖都有2個連通分支；D.n階無向完全圖的點連通度為n；二、填空題（共8題，每題3分，共24分）1．令F(x)：x是汽車，G(y)：y是火車，H(x,y)：x比y快。則命題“不存在比所有火車都快的汽車”符號化形式為___(()(()(,______________。xFxyGyHxy2．公式(pq)r的主析取范式為_______mmm_______。1373．集合A={a,b,c,d}上的等價關(guān)系共有___15___個。4．自對偶圖的頂點數(shù)n和邊數(shù)m之間滿足關(guān)系式為m=_______m=2n-2________。5．設(shè)T是有t片樹葉的2叉正則樹，則T應(yīng)該有_______個頂點。6．P({Φ,{Φ}})=_{Φ,{Φ},{Φ,Φ}},{{Φ}}}____。{7．在1到100之間（包含1和100）即不能被2，也不能被3，還不能被5整除的自然數(shù)有_______個。8．“p僅當q”，“只有q才p”，“除非q才p”這三個命題的符號化分別為___pq,pq,pq__,____和_____。（請按順序填寫）三、應(yīng)用、計算和證明題（共6題，46分）1．(6分)在命題邏輯的自然推理系統(tǒng)中構(gòu)造下面推理的證明。RRP分）設(shè)集合上的關(guān)系求：（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分）若不是，請說明原因；（4分）判斷右圖是否為哈密頓圖，若是，請給出一哈密頓回路（用阿拉伯數(shù)字在頂點上標明順序即可）；若不是，請說明原因（4分）；5．（8分）設(shè)G是無向簡單圖且G中存在長度大于等于k+1的初級回路（圈）。6．（8分）在一棵有3個2度頂點，2個4度頂點，其余頂點都是樹葉的無向樹中，應(yīng)該有幾片樹葉？（2分）請畫出所有這樣的非同構(gòu)的無向樹。（6分）一二137,{},{{{,{三(PQ)(R)RRRIa,a,a,b,b,a,c,d,b,c}I0AAt(R)RR2a,a,a,b,a,c,a,d,b,b,b,db,a,c,d,b,c}32A1扣1.2１８９２３４５１１６５７５７８４９９２３２３GGG為GGvvt01ts01s且v