離散數(shù)學(xué)模擬題開卷

...wd......wd......wd...《離散數(shù)學(xué)》模擬題〔補〕單項選擇題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、07.給定推理① 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ù)集。設(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.當(dāng)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,*>中的每個元素在右逆元必定也是左逆元?！?〕每個元素的逆元是唯一的。5.證明任一環(huán)的同態(tài)象也是一環(huán)。四.中國郵遞員問題求帶權(quán)圖G中的最優(yōu)投遞路線。郵局在v1點。五.應(yīng)用題某年級共有9門選修課程，期末考試前必須提前將這9門課程考完，每人每天只在下午考一門課，假設(shè)以課程表示結(jié)點，有一人同時選兩門課程，則這兩點間有邊〔其圖如右〕，問至少需幾天參考答案：單項選擇題題目123456789答案BCBBCCCCA題目10111213答案ABDD二．填空題1.2.奇數(shù)3.54.n5.LCM〔x,y〕6.乘法7.群8.三．證明題1、反證法：假設(shè)G不連通，不妨設(shè)G可分成兩個連通分支G1、G2，假設(shè)G1和G2的頂點數(shù)分別為n1和n2，顯然。與假設(shè)矛盾。所以G連通。2、設(shè)G=〔V，E〕，對完全二部圖有當(dāng)時，完全二部圖的邊數(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的左逆元?！?〕設(shè)元素a有兩個逆元b、c，那么a的逆元是唯一的。5.證明:設(shè)是一環(huán),且是關(guān)于同態(tài)映射f的同態(tài)象。由是Abel群，易證也是Abel群。是半群，易證也是半群?，F(xiàn)只需證：對是可分配的。于是同理可證因此也是環(huán)。四．中國郵遞員問題解：圖中有4個奇數(shù)結(jié)點，求任兩結(jié)點的最短路再找兩條道路使得它們沒有一樣的起點和終點，且長度總和最短：在原圖中復(fù)制出，設(shè)圖G‘，則圖G‘中每個結(jié)點度數(shù)均為偶數(shù)的圖G‘