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

...wd......wd......wd...《離散數(shù)學(xué)》模擬題〔補(bǔ)〕單項(xiàng)選擇題1．下面四組數(shù)能構(gòu)成無(wú)向圖的度數(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.的主析取范式中含極小項(xiàng)的個(gè)數(shù)為〔〕。A、2；B、3；C、5；D、07.給定推理① P② US①③ P④ ES③⑤ T②④I⑥ UG⑤推理過(guò)程中錯(cuò)在〔〕。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í)數(shù)集，Z為整數(shù)集，R+，Z+分別表示正實(shí)數(shù)與正整數(shù)集。設(shè)S={1，2，3}，R為S上的關(guān)系，其關(guān)系圖為則R具有〔〕的性質(zhì)。A、自反、對(duì)稱、傳遞；B、什么性質(zhì)也沒(méi)有；C、反自反、反對(duì)稱、傳遞；D、自反、對(duì)稱、反對(duì)稱、傳遞。12.設(shè)，則有〔〕。A、{{1,2}}；B、{1,2}；C、{1}；D、{2}。13.設(shè)A={1,2,3}，則A上有〔〕個(gè)二元關(guān)系。A、23；B、32；C、；D、二．填空題1.任何(n,m)圖G=(V,E),邊與頂點(diǎn)數(shù)的關(guān)系是。2.當(dāng)n為時(shí),非平凡無(wú)向完全圖Kn是歐拉圖。3.一棵無(wú)向樹T有三個(gè)3頂點(diǎn),一個(gè)2度頂點(diǎn),其余的都是1度頂點(diǎn),則T中有個(gè)1度頂點(diǎn)。4.n階完全圖Kn的點(diǎn)色數(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上的二元運(yùn)算為普通乘法、除法和加法，則代數(shù)系統(tǒng)<A,*>中運(yùn)算*關(guān)于運(yùn)算具有封閉性。7.在群坯、半群、獨(dú)異點(diǎn)、群中滿足消去律。8.設(shè)<G,*>是由元素生成的循環(huán)群，且|G|=n，則G=。三.證明題1.設(shè)G為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，且則G是連通圖。2.設(shè)G是〔n,m〕簡(jiǎn)單二部圖，則。3.證明：在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中，每個(gè)面的面度都是3。4.對(duì)代數(shù)系統(tǒng)<A,*>，*是A上二元運(yùn)算，e為A中幺元，如果*是可結(jié)合的且每個(gè)元素都有右逆元，則〔1〕<A,*>中的每個(gè)元素在右逆元必定也是左逆元?！?〕每個(gè)元素的逆元是唯一的。5.證明任一環(huán)的同態(tài)象也是一環(huán)。四.中國(guó)郵遞員問(wèn)題求帶權(quán)圖G中的最優(yōu)投遞路線。郵局在v1點(diǎn)。五.應(yīng)用題某年級(jí)共有9門選修課程，期末考試前必須提前將這9門課程考完，每人每天只在下午考一門課，假設(shè)以課程表示結(jié)點(diǎn)，有一人同時(shí)選兩門課程，則這兩點(diǎn)間有邊〔其圖如右〕，問(wèn)至少需幾天參考答案：?jiǎn)雾?xiàng)選擇題題目123456789答案BCBBCCCCA題目10111213答案ABDD二．填空題1.2.奇數(shù)3.54.n5.LCM〔x,y〕6.乘法7.群8.三．證明題1、反證法：假設(shè)G不連通，不妨設(shè)G可分成兩個(gè)連通分支G1、G2，假設(shè)G1和G2的頂點(diǎn)數(shù)分別為n1和n2，顯然。與假設(shè)矛盾。所以G連通。2、設(shè)G=〔V，E〕，對(duì)完全二部圖有當(dāng)時(shí)，完全二部圖的邊數(shù)m有最大值。故對(duì)任意簡(jiǎn)單二部圖有。3、證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個(gè)面用3條邊圍成。4.證明：〔1〕設(shè)，b是a的右逆元，c是b的右逆元，由于，所以b是a的左逆元?！?〕設(shè)元素a有兩個(gè)逆元b、c，那么a的逆元是唯一的。5.證明:設(shè)是一環(huán),且是關(guān)于同態(tài)映射f的同態(tài)象。由是Abel群，易證也是Abel群。是半群，易證也是半群?，F(xiàn)只需證：對(duì)是可分配的。于是同理可證因此也是環(huán)。四．中國(guó)郵遞員問(wèn)題解：圖中有4個(gè)奇數(shù)結(jié)點(diǎn)，求任兩結(jié)點(diǎn)的最短路再找兩條道路使得它們沒(méi)有一樣的起點(diǎn)和終點(diǎn)，且長(zhǎng)度總和最短：在原圖中復(fù)制出，設(shè)圖G‘，則圖G‘中每個(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù)的圖G‘