(完整word版)離散數(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(P(x) yR(y) Q(x)中的 x

2、()。A只是約束變元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. x(A(x) B(x) xA(x) xB(x)B. x(A(x) B(x)xA(x) xB(x)C. x(A(x) B)xA(x) BD. x(A B(x) A xB(x)6下列關(guān)于集合的勢的敘述中，( )是錯(cuò)誤的。A. 實(shí)數(shù)集比自然數(shù)集優(yōu)勢；B. 任一無限集合都存在與自己等勢的真子集；C. 集合之間的優(yōu)勢關(guān)系是偏序

3、關(guān)系；D. 有理數(shù)集比整數(shù)集優(yōu)勢。7設(shè) A,B,C 是集合， F是關(guān)系， G :A B, D A ，則下列式子中不正確的是( )。A A BA B B B.G 1(G(D) DC. FA B FA FBD.(A B) C A (B C)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. 下列敘述中錯(cuò)誤的是 ( ) 。A n(n 2)階競賽圖都具有哈密頓通路； B非平凡樹不是歐拉圖，也不是哈密頓圖；Cn(n 3且為奇數(shù) )階的二部圖一定不是哈密頓圖； D歐拉回路包

4、含圖的所有頂點(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題，每題 3分，共 24分) 1令 F(x) ：x 是汽車， G(y) ：y 是火車， H(x,y) ： x 比 y 快。則命題“不存在比所有火車都快的汽車”符號化形式為 _ x(F(x) ( y(G(y) H(x,y) 。2公式 (p q) r 的主析取范式為 m1 m3 m7 。

5、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è)命題的符號化分別為 _ p q, p q, p q_ , 和 。(請按順序填寫)三、應(yīng)用、計(jì)算和證明題(共 6 題，46分) 1(6 分) 在命題邏輯的自然推理系統(tǒng)中構(gòu)造下面推理的證明。前提： (P Q)

6、， QR，R 結(jié)論： P2(8 分)設(shè)集合 A=a，b，c，d ，A上的關(guān)系 R=, 求：( 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 分） 判斷左圖是否為歐拉圖， 若是，請給出一歐拉回路 （用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可） ； 若不是，請說明原因；（ 4 分） 判斷右圖是否為哈密頓圖，若

7、是，請給出一哈密頓回路（用阿拉伯?dāng)?shù)字在頂點(diǎn)上標(biāo)明順 序即可）；若不是，請說明原因（ 4 分）；5（ 8分） 設(shè) G是無向簡單圖且 （G） k 2，試證明 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 DCADD1.x(F(x)y(G(y) H (x,y)或者 x(F(x)y(G(y) H(x,y) 2. m1 m3 m73. 154. m=2n-25. 2t-16. , , , , 7. 268.p q

8、,p q,p q ( 該小題每空1 （ 1）QR前提引入（2）R前提引入（3）Q（1）（2）析取三段論（4）(P Q)前提引入（5）PQ置換(6)P（3）（5）析取三段論若未注明推理規(guī)則,或標(biāo)注有錯(cuò) ,扣 1 分 .2 （ 1）如圖 12)r(R) R R0 R I A a,a , a,b , b,a , c,d , b,c I A1s(R) R R 1 a,a , a,b , b,a , c,d , b,c , d,c , c,b 2t(R) R R a,a , a,b , a,c , a,d , b,b , b,d b,a , c,d , b,c 該題要求畫出三個(gè)閉包的關(guān)系圖 . 每個(gè)關(guān)系

9、圖 2 分 ,共 6 分 . 邊少畫或多畫一律判錯(cuò)3 (1) 如圖 2（2）A 的極大元有： 7，8， 9，10，11，12A 的極小元有： 1（3）B 的上界是 6,12, 最小上界是 6B 的下界是 1 ，最小下界是 1 哈斯圖中若出現(xiàn)水平的邊 ,扣 1 分 .4（分） （）判斷下圖是否為歐拉圖，若是，請給出一歐拉回路（用阿拉伯?dāng)?shù)字在邊上標(biāo)明順序即可）；若不是， 請說明原因；（ 4 分）答：因?yàn)樵搱D是連通圖且圖中沒有奇度頂點(diǎn)，所以該圖是歐拉圖（只要判斷正確給 2 分 ）。歐拉回路標(biāo)序如圖：找的歐拉回路正確再 2 分 （2）判斷下圖是否為哈密頓圖，若是，請給出一哈密頓回路（用阿拉伯?dāng)?shù)字在頂點(diǎn)

10、上標(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è)圈 ,矛盾 .( 8分)設(shè) G是無向簡單圖且 (G) k 2，試證明 G中存在長度大于等于 k+1 的初級回路(圈)。 證明：不妨設(shè)是連通圖，若 G不連通，因?yàn)榈母鬟B通分支的最小度也都大等于k ，因而可對它的某個(gè)連通分支進(jìn)行討論。設(shè) u,v 為 G 中任意兩

11、個(gè)頂點(diǎn)，由 G 是連通圖，因而 u,v 之間存在路徑，用“擴(kuò)大路徑 法”擴(kuò)大這條路徑， 設(shè)最后得到的“極大路徑”為t=v0v1vt,則 t k，事實(shí)上若存在“極大路徑” s=v0v1vs 且 sk，則 v0只能與 s中的頂點(diǎn)相鄰，因?yàn)?G為簡單圖，所以與 v0相鄰的頂點(diǎn)最多為 s 個(gè)，而 sk，這與 (G)k 矛盾，所以“極大路徑”長度大等于k。在t上構(gòu)造圈，由于 (v0)(G)k2，因而 v0除與t上的 v1相鄰?fù)猓€存在 t上的 k-1 個(gè) 頂點(diǎn) vi1,vi2, ,vik1(1 i1 i2ik 1 t) 與v0相鄰，則v0v1.vi1.vi2 vik1v0為一個(gè)圈且長度大等于 k+1。注意:也可直接設(shè) 是 G的最長路徑 .( 8分)在一棵有 3個(gè) 2度頂點(diǎn)， 2個(gè) 4度頂點(diǎn)，其余頂點(diǎn)都是樹葉的無向樹中，應(yīng)該有幾片樹葉？ ( 2 分)請畫出所有這樣的非同構(gòu)的無向樹。( 6 分)