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

中國(guó)地質(zhì)大學(xué)（北京）繼續(xù)教育學(xué)院 2016年03課程考試離散數(shù)學(xué)模擬題（補(bǔ)）1 單項(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.給定推理PUSPESTIUG推理過(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ù)集。1、 設(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ú)向樹(shù)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è)元素在右逆元必定也是左逆元。（2）每個(gè)元素的逆元是唯一的。5.證明任一環(huán)的同態(tài)象也是一環(huán)。四.中國(guó)郵遞員問(wèn)題求帶權(quán)圖G中的最優(yōu)投遞路線。郵局在v1點(diǎn)。五.應(yīng)用題某年級(jí)共有9門選修課程，期末考試前必 須提前將這9門課程考完，每人每天只在下午考一門課，若以課程表示結(jié)點(diǎn)，有一人同時(shí)選兩門課程，則這兩點(diǎn)間有邊（其圖如右），問(wèn)至少需幾天？參考答案：一、 單項(xiàng)選擇題題目123456789答案BCBBCCCCA題目10111213答案ABDD二填空題1.2.奇數(shù) 3.5 4.n 5.LCM（x,y） 6.乘法 7.群 8.三證明題1、反證法：若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的左逆元。（2）設(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)，（1） 求任兩結(jié)點(diǎn)的最短路再找兩條道路使得它們沒(méi)有相同的起點(diǎn)和終點(diǎn)，且長(zhǎng)度總和最短：（2） 在原圖中復(fù)制出，設(shè)圖G，則圖G中每個(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù)的圖G存在歐拉回路，歐拉回路C權(quán)長(zhǎng)為43。 五.應(yīng)用題解：即為最少考試天數(shù)。用Welch-Powell方法對(duì)G著色：第一種顏色的點(diǎn) ，剩余點(diǎn)第二種顏色的點(diǎn) ，剩余點(diǎn)第三種顏色的點(diǎn) 所以3任構(gòu)成一圈，所以3故=3所以三天下午即可考完全部九門課程。 第7頁(yè)(共7頁(yè))