計科普本2005級《離散數(shù)學(xué)》期末試題B及答案

1、第 1 頁 共 9 頁湖北教育學(xué)院 2005 2006 學(xué)年度第2 學(xué)期課程考試試卷( 本科卷 b ) 課程名稱： 離散數(shù)學(xué)考試方式：閉卷系（部）：專業(yè)年級：學(xué)生姓名：學(xué)號：題號一二三四總分分?jǐn)?shù)一選擇題（每小題2 分，共 30 分）1設(shè) a= a , b , c 上的關(guān)系如下，有傳遞性的是（）a.r1 = , , , b.r2 = , c.r3 = , d.r4 = , , , 2 設(shè) r 和 s是集合 a 上的等價關(guān)系，則rs 的對稱性（）a不可能成立b一定不成立c不一定成立d一定成立3 設(shè) r 是集合 a 上的偏序關(guān)系，r-1是 r 的逆關(guān)系，則rr-1是（）a偏序關(guān)系b相容關(guān)系c等價關(guān)系

2、d都不是4 設(shè)集合 a 中有 3 個元素，則a 上的不同的等價關(guān)系的個數(shù)有（）a 5 個b6 個c7 個d4 個5 設(shè) a= a , b , c ,d , b= 0 , 1 , f : ab ，則不同函數(shù)個數(shù)有（）分?jǐn)?shù)評卷人第 2 頁 共 9 頁a 15 個b8 個c 6 個d16 個6 若 g f 是滿射，則（）a f 必是滿射bf 必是單射cg 必是滿射dg 必是單射7 z 是正整數(shù)集，函數(shù)定義為：z z ，f（x）= x+1 ，則f 是（）a單射b滿射c雙射d非單射非滿射8 設(shè) g =為無向圖，則有（）a e v v be v vc e vv de = v v 9 含 5 個頂點 3 條

3、邊的不同構(gòu)的無向簡單圖有（）a 2 個b3 個c4 個d5 個10任何無向圖中頂點間的連通關(guān)系是（）a偏序關(guān)系b相容關(guān)系c等價關(guān)系d自反關(guān)系11設(shè) d=為有向圖， v= a , b , c , d , e= , , , , 則圖 d 是（）a強連通圖b單向連通圖c弱連通圖d不連通圖12給定無向圖如下圖所示，下面給出的頂點集子集中，不是點割集的為（）a. b, d b. d c. a , c d. g, e 13連通圖g 是一棵樹，當(dāng)且僅當(dāng)g 中（）a每條邊都是割邊b有些邊不是割邊c無割邊集d每條邊都不是割邊14具有 4 個頂點的非同構(gòu)的根樹的棵數(shù)有（）a 3 棵b4 棵c5 棵d 6 棵a g

4、bdfce 第 12題 圖第 3 頁 共 9 頁15哈密爾頓回路是（）a路徑b簡單回路c既是初級回路也是簡單回路d既非初級回路也非簡單回路二、填空題（每空2 分，共 20 分）1. 設(shè) r 是集合 a 上的偏序關(guān)系，則r 所具有的關(guān)系的三個特性是：_. 2關(guān)系 r 是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中。在關(guān)系圖中。3設(shè) a= 1, 2, 3 , 4 上的關(guān)系r= , , , ，則 r（r）= 。s（ r） = 。4集合 a = a , b , c , d , e 上的一個劃分= a, b , c ,d ,e ，那么對應(yīng)的等價關(guān)系r 應(yīng)該有個有序?qū)Α?設(shè) r 是 a= 3, 4, 5, 6, 8, 1

5、0, 12, 24, 36 上的整除關(guān)系，那么a 的極大元有，極小元有。6. 畫出以下無向圖的鄰接矩陣并畫出其補圖。分?jǐn)?shù)評卷人a b c d e 第 4 頁 共 9 頁三、判斷題（對的打，錯的打，每小題 2 分，共 20 分）1. 設(shè)有二元關(guān)系f1 = , , ，則 f1是函數(shù)。（）2. 函數(shù) f(x) = (x2-1)/(x+1) 和 g(x) = x-1 是相等的。（）3若 r 和 s 是集合 a 上的任意兩個對稱關(guān)系，r s 也是對稱的。（）4集合 a=a, b, c 上的關(guān)系r= , , 不滿足傳遞性。（）5 （1, 1, 1, 2, 3）能夠成為無向簡單圖的度數(shù)序列（）6在有向圖中結(jié)

6、點間的可達(dá)關(guān)系不是等價關(guān)系。（）7. 集合 a 上的恒等關(guān)系ia是等價關(guān)系并且|a / ia | = |a| （）8若 n 階無向連通圖g 有 m 條邊，那么m n1 。（）9如果一個無向圖g 是歐拉圖，則g 必是一個二部圖。（）10含 4 個頂點的，非同構(gòu)的無向樹有3 棵。（）四、解析題（每小題5 分，共 30 分）1. 設(shè) n 表示自然數(shù)集（含0） ，r ：n n 。r= | x , y n 2x+y=10 ，試求 dom（r） 、ran （r）2.對集合 s= 0 , 1 , 2 , 3 上的關(guān)系r = | x , y s x y( mod2 ) ，寫出它的元素，作出對應(yīng)的關(guān)系圖及關(guān)系矩

7、陣。分?jǐn)?shù)評卷人分?jǐn)?shù)評卷人第 5 頁 共 9 頁3.畫出如下圖所示關(guān)系r 對應(yīng)的自反閉包及傳遞閉包。4.如下圖所示的兩個圖g1， g2 是否同構(gòu)， 若兩圖同構(gòu)， 寫出頂點之間的對應(yīng)關(guān)系，若不同構(gòu)，則說明理由。g1g2 5. 今有 a, b, c, d, e, f, g 7 個人，已知下列事實：a 會講英語b會講英語、漢語c會講英語、意大利語、德語d會講日語、漢語e會講德語、意大利語f會講法語、日語、俄語g會講法語、德語試問這 7 個人應(yīng)該如何排座位（圓桌），才能使每個人都能和他身邊的人交談？這是一個什么回路？a b c d a 1 bc d2 3 4 e f 5 6 第 6 頁 共 9 頁6.

8、試判斷以下各無向圖分別對應(yīng)以下哪一條性質(zhì)？(a) “具有歐拉回路而沒有哈密爾頓回路”的圖號是。(b) “具有歐拉回路和哈密爾頓回路”的圖號是。(c) “既沒有歐拉回路，也沒有哈密爾頓回路”的圖號是。(d) “具有哈密爾頓回路而沒有歐拉回路”的圖號是。第 7 頁 共 9 頁湖北教育學(xué)院2005 2006 學(xué)年度第 2 學(xué)期課程考試試題參考答案（本科卷 b）課程名稱： 離散數(shù)學(xué)學(xué)生人數(shù) : _59_ 考試方式：閉卷（開卷、 閉卷）任課教師：阮宏一系（部）：專業(yè)年級：一. 選擇題（每題 2 分，共 30 分）1. 5. c c c a d 6. 10. c a c c c 11. 15 b a a

9、b c 二. 填空題（每空 2 分，共 20 分）1.自反性、反對稱性、傳遞性2.主對角線元素全為1每個頂點是都有環(huán)3. , , ia , , , , , , 4.13 5.8, 10, 24, 36 3, 4, 5 6. 鄰接矩陣為：其補圖為：三. 判斷題（每題 2 分，共 20 分）1. 5. 2. 10. a b c d e 0110010110110010100100110第 8 頁 共 9 頁四. 解析題（每小題 5 分，共 30 分）1.domr = 0, 1, 2, 3, 4, 5 3 分ranr = 10, 8, 6, 4, 2, 0 2 分2.r = , , , is2 分3.a b a b c d c d r(r) 2 分t(r)3 分4.不同構(gòu) 2 分圖 g2 中有 3 個頂點分別不相鄰，如2，3，4 但圖 g1 中沒有 3 個不相鄰的頂點。即圖 g1 與圖 g2 結(jié)構(gòu)不一樣。3 分5.排法為： a b d f g e c a4 分是哈密爾頓回路 1 分6.解：各圖具有的性質(zhì)分別如下：(a) “具有歐拉回路而沒有哈密爾頓回路”的圖號是( 2 ) 。(b) “具有歐