1、沈陽(yáng)師范大學(xué)離散考試預(yù)測(cè)題一、 選擇題（共10題，每題3分，共30分）1、下列語(yǔ)句為命題的是（ ）。A勿踏草地；。B你去圖書(shū)館嗎？；C月球上有水；D本命題為假。2 下列推理中，（ ）是錯(cuò)誤的。A. 如果x是有理數(shù)，則它為整數(shù)。1/2是有理數(shù)。所以1/2是整數(shù)。B. 若周末氣溫超過(guò)30度，小紅就去游泳。小紅周末沒(méi)去游泳。所以周末氣溫沒(méi)超過(guò)30度。C. 下午小明或者去看電影，或者去打籃球。下午小明沒(méi)去打籃球。因此下午小明去看電影了。D. 若a能被4整除，則a能被2整除。a能被2整除。因此a能被4整除。3謂詞公式中的x(      )。A只是約束變?cè)?/p>

2、B只是自由變?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. 任一無(wú)限集合都存在與自己等勢(shì)的真子集； C. 集合之間的優(yōu)勢(shì)關(guān)系是偏序關(guān)系；D. 有理數(shù)集比整數(shù)集優(yōu)勢(shì)。7設(shè)A,B,C是集合，F(xiàn)是關(guān)系，則下列式子中不正確的是（ ）。A B. C. D. 8. 以下序列中，（ ）是簡(jiǎn)單可圖的。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)階競(jìng)賽圖都具有哈密頓通路；B 非平凡樹(shù)不是歐拉圖，也不是哈密頓圖；C n(n3且為奇數(shù))階的二部圖一定不是哈密頓圖；D 歐拉回路包含圖的所有頂點(diǎn)，哈密頓回路包含圖的所有邊。10下列關(guān)于圖的連通性的敘述中正確的是( )。A. 有向圖是連通的是指它是強(qiáng)連通的； B. 任一無(wú)向圖的點(diǎn)連通度都不超過(guò)它的邊連通度；C. 在一n階圈Cn(n4)上任意去掉兩個(gè)頂點(diǎn)得到得圖都有2個(gè)連通分支； D. n階無(wú)向完全圖的點(diǎn)連通度為n；二、填空題（共8題，每題

4、3分，共24分）1 令F(x)：x是汽車(chē)，G(y)：y是火車(chē)，H(x,y)：x比y快。則命題“不存在比所有火車(chē)都快的汽車(chē)”符號(hào)化形式為_(kāi)。2 公式的主析取范式為_(kāi)。3 集合A=a,b,c,d上的等價(jià)關(guān)系共有_15_個(gè)。4 自對(duì)偶圖的頂點(diǎn)數(shù)n和邊數(shù)m之間滿足關(guān)系式為m =_ m=2n-2_。5設(shè)T是有t片樹(shù)葉的2叉正則樹(shù)，則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)化分別為_(kāi) _ , _ 和 _ 。（請(qǐng)按順序填寫(xiě)） 三、應(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）畫(huà)出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）畫(huà)出<A,R>的哈斯圖；（4分）（2）求A的所有極大元和極小元（2分）（3）求B=2,3,6的最小上界和最大下界（2

6、分）。4.（8分）判斷左圖是否為歐拉圖，若是，請(qǐng)給出一歐拉回路（用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可）；若不是，請(qǐng)說(shuō)明原因；（4分）判斷右圖是否為哈密頓圖，若是，請(qǐng)給出一哈密頓回路（用阿拉伯?dāng)?shù)字在頂點(diǎn)上標(biāo)明順序即可）；若不是，請(qǐng)說(shuō)明原因（4分）； 5 （8分） 設(shè)G是無(wú)向簡(jiǎn)單圖且(G)k2，試證明G中存在長(zhǎng)度大于等于k+1的初級(jí)回路（圈）。6 （8分）在一棵有3個(gè)2度頂點(diǎn)，2個(gè)4度頂點(diǎn)，其余頂點(diǎn)都是樹(shù)葉的無(wú)向樹(shù)中，應(yīng)該有幾片樹(shù)葉？（2分）請(qǐng)畫(huà)出所有這樣的非同構(gòu)的無(wú)向樹(shù)。（6分）答案及評(píng)分標(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） 該題要求畫(huà)出三個(gè)閉包的關(guān)系圖. 每個(gè)關(guān)系圖2分,共6分. 邊少畫(huà)或多畫(huà)一律判錯(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)說(shuō)明原因；（

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

9、度大于等于k+1的初級(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)都是樹(shù)葉的無(wú)向樹(shù)中，應(yīng)該有幾片樹(shù)葉？（2分）請(qǐng)畫(huà)出所有這樣的非同構(gòu)的無(wú)向樹(shù)。（6分）答：設(shè)樹(shù)葉有x片，則邊數(shù)m=3+2+x-