中央電大離散數(shù)學(xué)(本科)考試試題小抄

1、專業(yè)好文檔中央電大離散數(shù)學(xué)（本科）考試試題一、單項選擇題（每小題3分，本題共15分）1若集合a=1，2，b=1，2，1，2，則下列表述正確的是( a ) aab，且ab bba，且abcab，且ab dab，且ab 2設(shè)有向圖（a）、（b）、（c）與（d）如圖一所示，則下列結(jié)論成立的是 ( d ) 圖一 a（a）是強連通的 b（b）是強連通的c（c）是強連通的 d（d）是強連通的3設(shè)圖g的鄰接矩陣為則g的邊數(shù)為( b )a6 b5 c4 d34無向簡單圖g是棵樹，當(dāng)且僅當(dāng)( a )ag連通且邊數(shù)比結(jié)點數(shù)少1 bg連通且結(jié)點數(shù)比邊數(shù)少1cg的邊數(shù)比結(jié)點數(shù)少1 dg中沒有回路5下列公式 ( c )

2、為重言式apqpq b(q(pq) (q(pq) c(p(qp)(p(pq) d(p(pq) q1若集合a=a，b，b= a，b， a，b ，則（ a ） aab，且ab bab，但ab cab，但ab dab，且ab2集合a=1, 2, 3, 4, 5, 6, 7, 8上的關(guān)系r=|x+y=10且x, ya，則r的性質(zhì)為（ b ） a自反的 b對稱的 c傳遞且對稱的 d反自反且傳遞的3如果r1和r2是a上的自反關(guān)系，則r1r2，r1r2，r1-r2中自反關(guān)系有（ b ）個 a0 b2 c1 d34如圖一所示，以下說法正確的是 ( d ) a(a, e)是割邊 b(a, e)是邊割集c(a,

3、e) ,(b, c)是邊割集 d(d, e)是邊割集 圖一5設(shè)a（x）：x是人，b（x）：x是學(xué)生，則命題“不是所有人都是學(xué)生”可符號化為（ c ）a(x)(a(x)b(x) b(x)(a(x)b(x) c(x)(a(x) b(x) d(x)(a(x)b(x)1設(shè)a=a, b，b=1, 2，r1，r2，r3是a到b的二元關(guān)系，且r1=, ，r2=, , ，r3=, ，則（ b ）不是從a到b的函數(shù) ar1和r2 br2 cr3 dr1和r32設(shè)a=1, 2, 3, 4, 5, 6, 7, 8，r是a上的整除關(guān)系，b=2, 4, 6，則集合b的最大元、最小元、上界、下界依次為 ( b ) a8、

4、2、8、2 b無、2、無、2 c6、2、6、2 d8、1、6、13若集合a的元素個數(shù)為10，則其冪集的元素個數(shù)為（ a ） a1024 b10 c100 d14設(shè)完全圖k有n個結(jié)點(n2)，m條邊，當(dāng)（ c ）時，k中存在歐拉回路am為奇數(shù) bn為偶數(shù) cn為奇數(shù) dm為偶數(shù)5已知圖g的鄰接矩陣為 ，則g有（ d ） a5點，8邊 b6點，7邊 c6點，8邊 d5點，7邊1若集合a a，a，1，2，則下列表述正確的是( c ) aa，aa b2acaa da 2設(shè)圖g，vv，則下列結(jié)論成立的是 ( c ) adeg(v)=2e b deg(v)=e c d3命題公式（pq）r的析取范式是 (

5、d ) a（pq）r b（pq）r c（pq）r d（pq）r4如圖一所示，以下說法正確的是 ( a )ae是割點 ba, e是點割集cb, e是點割集 dd是點割集5下列等價公式成立的為( b )apqpq bp(qp) p(pq) cq(pq) q(pq) dp(pq) q1若g是一個漢密爾頓圖，則g一定是( d ) a平面圖 b對偶圖c歐拉圖 d連通圖2集合a=1, 2, 3, 4上的關(guān)系r=|x=y且x, ya，則r的性質(zhì)為（ c ） a不是自反的 b不是對稱的 c傳遞的 d反自反3設(shè)集合a=1，2，3，4，5，偏序關(guān)系是a上的整除關(guān)系，則偏序集上的元素5是集合a的（ b ） a最大元

6、 b極大元 c最小元 d極小元4圖g如圖一所示，以下說法正確的是 ( c ) a(a, d)是割邊 b(a, d)是邊割集c(a, d) ,(b, d)是邊割集 d(b, d)是邊割集 圖一5設(shè)a（x）：x是人，b（x）：x是工人，則命題“有人是工人”可符號化為（ a ）a(x)(a(x)b(x) b(x)(a(x)b(x) c(x)(a(x) b(x) d(x)(a(x)b(x)1若集合a a，a，則下列表述正確的是( a ) aaa baaca，aa da2命題公式（pq）的合取范式是 ( c ) a（pq） b（pq）（pq） c（pq） d（pq）3無向樹t有8個結(jié)點，則t的邊數(shù)為(

7、b )a6 b7 c8 d9 4圖g如圖一所示，以下說法正確的是 ( b )aa是割點 bb, c是點割集cb, d是點割集 dc是點割集 圖一5下列公式成立的為( d )apq pq bpq pq cqp p dp(pq)q1“小于5的非負(fù)整數(shù)集合”采用描述法表示為_a_ axxn, x5 bxxr, x5 cxxz, x5 dxxq, x5 2設(shè)r1，r2是集合a=a,b,c,d上的兩個關(guān)系，其中r1=(a,a),(b,b),(b,c), (d,d)，r2=(a,a),(b,b),(b,c),(c,b),(d,d)，則r2是r1的_b_閉包 a自反 b對稱 c傳遞 d以上答案都不對 3設(shè)函

8、數(shù)f：rr，f(a)=2a+1；g：rr，g(a)=a2，則_c_有反函數(shù) afg bgf cf dg 4已知圖g的鄰接矩陣為，則圖g有_d_ a5點，8邊 b6點，7邊 c6點，8邊 d5點7邊 5無向完全圖k4是_a_ a漢密爾頓圖 b歐拉圖 c非平面圖 d樹 6在5個結(jié)點的完全二叉樹中，若有4條邊，則有_b_片樹葉 a2 b3 c4 d5 7無向樹t有7片樹葉，3個3度結(jié)點，其余的都是4度結(jié)點，則t有_c_個4度結(jié)點 a3 b2 c1 d0 8與命題公式p（qr）等值的公式是_a_ a(pq)r b(pq)r c(pq)r dp(qr) 9謂詞公式中量詞x的轄域是_b_ a b cp(x

9、) d 10謂詞公式的類型是_c_ a蘊涵式 b永假式 c永真式 d非永真的可滿足式1設(shè)a=1,2,3,4，b=1,3，c=-1,0,1,2，則_a_ a b c d 2若集合a的元素個數(shù)為10，則其冪集的元素個數(shù)為_b_ a1000 b1024 c1 d10 3設(shè)集合a=1,2，b=a,b，c=，則_c_ a, b1,1,2,2, c, d1,2,a,b, 4設(shè)a=1, 2, 3, 4, 5, 6, 7, 8，r是a上的整除關(guān)系，b=2, 4, 6，則集合b的最大元、最小元、上界、下界依次為_d_ a8、1、6、1 b 8、2、8、2 c6、2、6、2 d無、2、無、2 5有5個結(jié)點的無向完

10、全圖k5的邊數(shù)為_a_ a10 b20 c5 d25 6設(shè)完全圖k有n個結(jié)點(n2)，m條邊，當(dāng)_b_時，k中存在歐拉回路 an為偶數(shù) bn為奇數(shù) cm為偶數(shù) dm為奇數(shù) 7一棵無向樹t有5片樹葉，3個2度分支點，其余的分支點都是3度頂點，則t有_c_個頂點 a3 b8 c11 d13 8命題公式（pq）r的析取范式是_b_ a（pq）r b （pq）r c（pq）r d（pq）r 9下列等價公式成立的是_b_ apqpq b p(qp) p(pq) cp(pq) q dq(pq) q(pq) 10謂詞公式的類型是_c_ a蘊涵式 b永假式 c永真式 d非永真的可滿足式二、填空題（每小題3分，

11、本題共15分）6命題公式的真值是 t （或1） 7若圖g=中具有一條漢密爾頓回路，則對于結(jié)點集v的每個非空子集s，在g中刪除s中的所有結(jié)點得到的連通分支數(shù)為w，則s中結(jié)點數(shù)|s|與w滿足的關(guān)系式為 w|s| 8給定一個序列集合000，001，01，10，0，若去掉其中的元素 0 ，則該序列集合構(gòu)成前綴碼9已知一棵無向樹t中有8個結(jié)點，4度，3度，2度的分支點各一個，t的樹葉數(shù)為 5 10(x)(p(x)q(x)r(x，y)中的自由變元為r(x，y )中的y6若集合a的元素個數(shù)為10，則其冪集的元素個數(shù)為 1024 7設(shè)a=a，b，c，b=1，2，作f：ab，則不同的函數(shù)個數(shù)為 8 8若a=1,

12、2，r=|xa, ya, x+y=10，則r的自反閉包為, 9結(jié)點數(shù)v與邊數(shù)e滿足 e=v-1 關(guān)系的無向連通圖就是樹6設(shè)集合aa，b，那么集合a的冪集是,a,b,a,b 7如果r1和r2是a上的自反關(guān)系，則r1r2，r1r2，r1-r2中自反關(guān)系有 2 個 8設(shè)圖g是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從g中刪去 4 條邊后使之變成樹9設(shè)連通平面圖g的結(jié)點數(shù)為5，邊數(shù)為6，則面數(shù)為 3 10設(shè)個體域da, b，則謂詞公式(x)a(x)（$x）b（x）消去量詞后的等值式為(a (a)a (b)(b（a）b（b）) 6設(shè)集合a=0, 1, 2, 3，b=2, 3, 4, 5，r是a到b的

13、二元關(guān)系，則r的有序?qū)蠟椋?設(shè)g是連通平面圖，v, e, r分別表示g的結(jié)點數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關(guān)系式v-e+r=2 8設(shè)g是有6個結(jié)點，8條邊的連通圖，則從g中刪去 3 條邊，可以確定圖g的一棵生成樹9無向圖g存在歐拉回路，當(dāng)且僅當(dāng)g連通且所有結(jié)點的度數(shù)全為偶數(shù)10設(shè)個體域d1,2，則謂詞公式消去量詞后的等值式為a(1)a(2)6命題公式的真值是 t （或1） 7若圖g=中具有一條漢密爾頓回路，則對于結(jié)點集v的每個非空子集s，在g中刪除s中的所有結(jié)點得到的連通分支數(shù)為w，則s中結(jié)點數(shù)|s|與w滿足的關(guān)系式為 w|s| 8給定一個序列集合000，001，01，10，0，若去掉

14、其中的元素 0 ，則該序列集合構(gòu)成前綴碼9已知一棵無向樹t中有8個結(jié)點，4度，3度，2度的分支點各一個，t的樹葉數(shù)為 5 10(x)(p(x)q(x)r(x，y)中的自由變元為r(x，y )中的y6若集合a的元素個數(shù)為10，則其冪集的元素個數(shù)為 1024 7設(shè)a=a，b，c，b=1，2，作f：ab，則不同的函數(shù)個數(shù)為 8 8若a=1,2，r=|xa, ya, x+y=10，則r的自反閉包為, 9結(jié)點數(shù)v與邊數(shù)e滿足 e=v-1 關(guān)系的無向連通圖就是樹10設(shè)個體域da, b, c，則謂詞公式(x)a(x)消去量詞后的等值式為a (a) a (b)a（c）6若集合a=1，3，5，7，b=2，4，6

15、，8，則ab=空集（或） 7設(shè)集合a=1，2，3上的函數(shù)分別為：f=,，g=,，則復(fù)合函數(shù)gf =, , ,8設(shè)g是一個圖，結(jié)點集合為v，邊集合為e，則g的結(jié)點度數(shù)之和為2|e|（或“邊數(shù)的兩倍”） 9無向連通圖g的結(jié)點數(shù)為v，邊數(shù)為e，則g當(dāng)v與e滿足 e=v-1 關(guān)系時是樹 10設(shè)個體域d1, 2, 3， p(x)為“x小于2”，則謂詞公式(x)p(x) 的真值為假（或f，或0） 6設(shè)集合a=2, 3, 4，b=1, 2, 3, 4，r是a到b的二元關(guān)系， 則r的有序?qū)蠟椋?如果r是非空集合a上的等價關(guān)系，a a，ba，則可推知r中至少包含，等元素8設(shè)g是有4個結(jié)點，8條邊的無向連通圖

16、，則從g中刪去 5 條邊，可以確定圖g的一棵生成樹9設(shè)g是具有n個結(jié)點m條邊k個面的連通平面圖，則m等于n+k-210設(shè)個體域d1, 2，a(x)為“x大于1”，則謂詞公式的真值為真（或t，或1）11設(shè)集合a=1,2,3，用列舉法寫出a上的恒等關(guān)系ia，全關(guān)系ea： ia = _ ia =,； ea =, 12設(shè)集合aa，b，那么集合a的冪集是,a,b,a,b 13設(shè)集合a=1,2,3，b=a,b，從a到b的兩個二元關(guān)系r=,，s=,，則r-s=_ r-s= 14設(shè)g是連通平面圖，v, e, r分別表示g的結(jié)點數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關(guān)系式v-e+r=2 15無向連通圖g是歐拉圖的充

17、分必要條件是結(jié)點度數(shù)均為偶數(shù) 16設(shè)g是有6個結(jié)點，8條邊的連通圖，則從g中刪去 3 條邊，可以確定圖g的一棵生成樹 17設(shè)g是完全二叉樹，g有15個結(jié)點，其中有8個是樹葉，則g有_14_條邊，g的總度數(shù)是_28_，g的分支點數(shù)是_7_ 18設(shè)p，q的真值為1，r，s的真值為0，則命題公式的真值為_0_ 19命題公式的合取范式為析取范式為 20設(shè)個體域為整數(shù)集，公式真值為_1_11設(shè)集合a=1,2,3,4，b=3,4,5,6，則： _3,4_，_1,2,3,4,5,6_ 12設(shè)集合a有n個元素，那么a的冪集合p(a)的元素個數(shù)為 13設(shè)集合a=a,b,c,d，b=x,y,z，r=,則關(guān)系矩陣m

18、r 14設(shè)集合a=a,b,c,d,e，a上的二元關(guān)系r=,，s=,，則rs=, 15無向圖g存在歐拉回路，當(dāng)且僅當(dāng)g連通且_所有結(jié)點的度數(shù)全為偶數(shù) 16設(shè)連通平面圖g的結(jié)點數(shù)為5，邊數(shù)為6，則面數(shù)為 3 17設(shè)正則二叉樹有n個分支點，且內(nèi)部通路長度總和為i，外部通路長度總和為e，則有e=_ i+2n 18設(shè)p，q的真值為0，r，s的真值為1，則命題公式的真值為_1_ 19已知命題公式為g(pq)r，則命題公式g的析取范式是(pq)r 20謂詞命題公式(x)(p(x)q(x)r(x，y)中的約束變元為_x_三、邏輯公式翻譯（每小題4分，本題共12分）11將語句“如果所有人今天都去參加活動，則明天

19、的會議取消”翻譯成命題公式設(shè)p：所有人今天都去參加活動，q：明天的會議取消， （1分） p q （4分）12將語句“今天沒有人來” 翻譯成命題公式設(shè) p：今天有人來， （1分） p （4分）13將語句“有人去上課” 翻譯成謂詞公式設(shè)p(x)：x是人，q(x)：x去上課， （1分）($x)(p(x) q(x) （4分）11將語句“如果你去了，那么他就不去”翻譯成命題公式設(shè)p：你去，q：他去， （1分）pq （4分）12將語句“小王去旅游，小李也去旅游”翻譯成命題公式設(shè)p：小王去旅游，q：小李去旅游， （1分）pq （4分）13將語句“所有人都去工作”翻譯成謂詞公式設(shè)p(x)：x是人，q(x)：x

20、去工作， （1分）(x)(p(x)q(x) （4分）11將語句“他不去學(xué)?！狈g成命題公式設(shè)p：他去學(xué)校， （1分） p （4分）12將語句“他去旅游，僅當(dāng)他有時間”翻譯成命題公式設(shè) p：他去旅游，q：他有時間， （1分）p q （4分）13將語句“所有的人都學(xué)習(xí)努力”翻譯成命題公式設(shè)p(x)：x是人，q(x)：x學(xué)習(xí)努力， （1分）（x）(p(x)q(x) （3分）11將語句“盡管他接受了這個任務(wù)，但他沒有完成好”翻譯成命題公式設(shè)p：他接受了這個任務(wù)，q：他完成好了這個任務(wù)， （2分） p q （6分）12將語句“今天沒有下雨”翻譯成命題公式設(shè)p：今天下雨， （2分） p （6分）11將語句

21、“他是學(xué)生”翻譯成命題公式設(shè)p：他是學(xué)生， （2分） 則命題公式為： p （6分）12將語句“如果明天不下雨，我們就去郊游”翻譯成命題公式設(shè)p：明天下雨，q：我們就去郊游， （2分） 則命題公式為： p q （6分）11將語句“今天考試，明天放假”翻譯成命題公式設(shè)p：今天考試，q：明天放假 （2分） 則命題公式為：pq （6分） 12將語句“我去旅游，僅當(dāng)我有時間”翻譯成命題公式 設(shè)p：我去旅游，q：我有時間， （2分）則命題公式為：pq （6分） 將語句“如果明天不下雨，我們就去春游”翻譯成命題公式 將語句“有人去上課” 翻譯成謂詞公式設(shè)命題p表示“明天下雨”，命題q表示“我們就去春游”.

22、則原語句可以表示成命題公式 pq. （5分） 設(shè)p(x)：x是人，q(x)：x去上課 則原語句可以表示成謂詞公式 ($x)(p(x) q(x) 四、判斷說明題（每小題7分，本題共14分）14p（pq）p為永真式正確 （3分）p（pq）p是由p（pq）與p組成的析取式，如果p的值為真，則p（pq）p為真， （5分）如果p的值為假，則p與pq為真，即p（pq）為真，也即p（pq）p為真，所以p（pq）p是永真式 （7分）15若偏序集的哈斯圖如圖一所示，則集合a的最大元為a，最小元不存在 正確 （3分）對于集合a的任意元素x，均有r（或xra），所以a是集合a中的最大元（5分）14如果r1和r2是a

23、上的自反關(guān)系，則r1r2是自反的正確 （3分）r1和r2是自反的，x a， r1， r2， 則 r1r2， 所以r1r2是自反的 （7分）v1v2v3v5v4dbacefghn圖二15如圖二所示的圖g存在一條歐拉回路 正確 （3分）因為圖g為連通的，且其中每個頂點的度數(shù)為偶數(shù) （7分）14設(shè)n、r分別為自然數(shù)集與實數(shù)集，f：nr，f (x)=x+6，則f是單射正確 （3分）設(shè)x1，x2為自然數(shù)且x1x2，則有f(x1)= x1+6 x2+6= f(x2)，故f為單射 （7分）15設(shè)g是一個有6個結(jié)點14條邊的連通圖，則g為平面圖錯誤 （3分）不滿足“設(shè)g是一個有v個結(jié)點e條邊的連通簡單平面圖，

24、若v3，則e3v-6” 13下面的推理是否正確，試予以說明 (1) （x）f（x）g（x） 前提引入 (2) f（y）g（y） us（1）錯誤 （3分）（2）應(yīng)為f（y）g（x），換名時，約束變元與自由變元不能混淆 （7分）14若偏序集的哈斯圖如圖二所示，則集合a的最大元為a，最小元不存在 錯誤 （3分）集合a的最大元不存在，a是極大元 （7分）13下面的推理是否正確，試予以說明 (1) （x）f（x）g（x） 前提引入 (2) f（y）g（y） us（1）錯誤 （3分）（2）應(yīng)為f（y）g（x），換名時，約束變元與自由變元不能混淆 （7分）14如圖二所示的圖g存在一條歐拉回路錯誤 （3分）因

25、為圖g為中包含度數(shù)為奇數(shù)的結(jié)點 （7分）13如果圖g是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖g是歐拉圖錯誤 （3分）當(dāng)圖g不連通時圖g不為歐拉圖 （7分）14若偏序集的哈斯圖如圖二所示，則集合a的最大元為a，最小元是f 圖二錯誤 （3分）集合a的最大元與最小元不存在，a是極大元，f是極小元， 五計算題（每小題12分，本題共36分）16設(shè)集合a=1，2，3，4，r=|x, ya；|x-y|=1或x-y=0，試（1）寫出r的有序?qū)Ρ硎荆?（2）畫出r的關(guān)系圖；（3）說明r滿足自反性，不滿足傳遞性（1）r=, （3分）1234（2）關(guān)系圖為 （6分）（3）因為,均屬于r，即a的每個元素構(gòu)成的有序?qū)趓

26、中，故r在a上是自反的。 （9分）因有與屬于r，但不屬于r，所以r在a上不是傳遞的。 17求pqr的析取范式，合取范式、主析取范式，主合取范式p（rq）p(rq) pqr （析取、合取、主合取范式） （9分） (pqr)(pqr) (pqr) (pqr) (pqr) (pqr) (pqr) （主析取范式） （12分）18設(shè)圖g=，v= v1，v2，v3，v4，v5，e= (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) ，試 畫出g的圖形表示； 寫出其鄰接矩陣；(3) 求出每個結(jié)點的度數(shù)；v1v2v3v4v5ooooo

27、(4) 畫出圖g的補圖的圖形（1）關(guān)系圖 （3分）（2）鄰接矩陣 （6分）（3）deg(v1)=2deg(v2)=3v1v2v3v4v5ooooodeg(v3)=4deg(v4)=3deg(v5)=2 （9分） （4）補圖16設(shè)謂詞公式，試（1）寫出量詞的轄域； （2）指出該公式的自由變元和約束變元（1）$x量詞的轄域為， （2分）z量詞的轄域為, （4分） y量詞的轄域為 （6分）（2）自由變元為與中的y，以及中的z約束變元為x與中的z，以及中的y （12分）17設(shè)a=1,2,1,2，b=1,2,1,2，試計算（1）（a-b）； （2）（ab）； （3）ab（1）a-b =1,2 （4分）（

28、2）ab =1,2 （8分）（3）ab=，, 18設(shè)g=，v= v1，v2，v3，v4，v5，e= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試（1）給出g的圖形表示； （2）寫出其鄰接矩陣；（3）求出每個結(jié)點的度數(shù)； （4）畫出其補圖的圖形1）g的圖形表示為： （3分）（2）鄰接矩陣： （6分）（3）v1，v2，v3，v4，v5結(jié)點的度數(shù)依次為1，2，4，3，2 （9分）（4）補圖如下：16試求出（pq）r的析取范式，合取范式，主合取范式（pq）r(pq)r (pq)r（析取范式） （3分） (pr) (qr)（合取范式） （6分） (pr)(qq) (qr)(pp) (prq)(prq) (qrp)(qrp) (pqr)(pqr) (pqr) （主合取范式） （12分）17設(shè)a=a, b, 1, 2，b= a, b, 1, 1，試計算（1）（a-b） （2）（ab） （3）（ab）-（ab）（1）（a-b）=a, b, 2 （4分）（2）（ab）=