中國地質(zhì)大學(xué)（北京）繼續(xù)教育學(xué)院 2016年03課程考試 《離散數(shù)學(xué)》模擬題（補） 1． 單項選擇題 1．下面四組數(shù)能構(gòu)成無向圖的度數(shù)列的有( )。 　 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 2．圖 的鄰接矩陣為( )。 A、；B、；C、；D、。 3.設(shè)S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}， S5={3，5}，在條件下X與（ ）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X與S1，…，S5中任何集合都不等。 4．下列圖中是歐拉圖的有( )。 5.下述命題公式中，是重言式的為（ ）。 A、； B、； C、； D、。 6.的主析取范式中含極小項的個數(shù)為（ ）。 A 、2； B、 3； C、5； D、0 7.給定推理 ① P ② US① ③ P ④ ES③ ⑤ T②④I ⑥ UG⑤ 推理過程中錯在（ ）。 A、①->②; B、②->③; C、③->④; D、④->⑤ 8.設(shè)S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}， S5={3，5}，在條件下X與（ ）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X與S1，…，S5中任何集合都不等。 9.設(shè)R和S是P上的關(guān)系，P是所有人的集合，，則表示關(guān)系 （ ）。 A、； B、； C、 ； D、。 10.下面函數(shù)（ ）是單射而非滿射。 A、； B、； C、； D、。 11.其中R為實數(shù)集，Z為整數(shù)集，R+，Z+分別表示正實數(shù)與正整數(shù)集。 1、 設(shè)S={1，2，3}，R為S上的關(guān)系，其關(guān)系圖為 則R具有（ ）的性質(zhì)。 A、自反、對稱、傳遞； B、什么性質(zhì)也沒有； C、反自反、反對稱、傳遞； D、自反、對稱、反對稱、傳遞。 12.設(shè)，則有（ ）。 A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。 13.設(shè)A={1 ,2 ,3 }，則A上有（ ）個二元關(guān)系。 A、23 ； B、32 ； C、； D、 二．填空題 1.任何(n,m) 圖G = (V,E) , 邊與頂點數(shù)的關(guān)系是 。 2.當n為 時,非平凡無向完全圖Kn是歐拉圖。 3.已知一棵無向樹T有三個3頂點,一個2度頂點,其余的都是1度頂點, 則T中有 個1度頂點。 4.n階完全圖Kn的點色數(shù)X(KN)= 。 5.設(shè)集合A={1，2，3，4，5，6，7，8，9，10}，定義A上的二元關(guān)系“≤”為 x ≤ y = x|y , 則= 。 6.設(shè)，定義A上的二元運算為普通乘法、除法和加法，則代數(shù)系統(tǒng)<A,*>中運算*關(guān)于 運算具有封閉性。 7.在群坯、半群、獨異點、群中 滿足消去律。 8.設(shè)<G,*>是由元素生成的循環(huán)群，且|G|=n，則G = 。 三.證明題 1. 設(shè)G為具有n個結(jié)點的簡單圖，且則G是連通圖。 2. 設(shè)G是（n,m）簡單二部圖，則。 3.證明：在6個結(jié)點12條邊的連通平面簡單圖中，每個面的面度都是3。 4.對代數(shù)系統(tǒng)<A,*>，*是A上二元運算，e為A中幺元，如果*是可結(jié)合的且每個元素都有右逆元，則（1）<A,*>中的每個元素在右逆元必定也是左逆元。 （2）每個元素的逆元是唯一的。 5.證明任一環(huán)的同態(tài)象也是一環(huán)。 四.中國郵遞員問題 求帶權(quán)圖G中的最優(yōu)投遞路線。郵局在v1點。 五.應(yīng)用題 某年級共有9門選修課程，期末考試前必 須提前將這9門課程考完，每人每天只在下午考一門課，若以課程表示結(jié)點，有一人同時選兩門課程，則這兩點間有邊（其圖如右），問至少需幾天？ 參考答案： 一、 單項選擇題 題目 1 2 3 4 5 6 7 8 9 答案 B C B B C C C C A 題目 10 11 12 13 答案 A B D D 二．填空題 1.2.奇數(shù) 3.5 4.n 5.LCM（x,y） 6.乘法 7.群 8. 三．證明題 1、反證法：若G不連通，不妨設(shè)G可分成兩個連通分支G1、G2，假設(shè)G1和G2的頂點數(shù)分別為n1和n2，顯然。 與假設(shè)矛盾。所以G連通。 2、設(shè)G=（V，E）， 對完全二部圖有 當時，完全二部圖的邊數(shù)m有最大值。 故對任意簡單二部圖有。 3、證：n=6,m=12 歐拉公式n-m+f=2知 f=2-n+m=2-6-12=8 由圖論基本定理知：，而，所以必有，即每個面用3條邊圍成。 4.證明： （1）設(shè)，b是a的右逆元，c是b的右逆元，由于， 所以b是a的左逆元。 （2）設(shè)元素a有兩個逆元b、c，那么 a的逆元是唯一的。 5.證明: 設(shè)是一環(huán),且是關(guān)于同態(tài)映射f的同態(tài)象。 由是Abel群，易證也是Abel群。 是半群，易證也是半群。 現(xiàn)只需證：對是可分配的。 于是 同理可證 因此也是環(huán)。 四．中國郵遞員問題 解：圖中有4個奇數(shù)結(jié)點， （1） 求任兩結(jié)點的最短路 再找兩條道路使得它們沒有相同的起點和終點，且長度總和最短： （2） 在原圖中復(fù)制出，設(shè)圖G‘，則圖G‘中每個結(jié)點度數(shù)均為偶數(shù)的圖G‘存在歐拉回路，歐拉回路C權(quán)長為43。 五.應(yīng)用題 解：即為最少考試天數(shù)。 用Welch-Powell方法對G著色： 第一種顏色的點 ，剩余點 第二種顏色的點 ，剩余點 第三種顏色的點 所以≤3 任構(gòu)成一圈，所以≥3 故=3 所以三天下午即可考完全部九門課程。 第7頁(共7頁)