離散數(shù)學(xué)有大題

總復(fù)習(xí)題（一）一．單選題1(C)。一連通的平面圖，5個(gè)頂點(diǎn)3個(gè)面，則邊數(shù)為（）。、4、5、6、72、(A)。如果一個(gè)簡(jiǎn)單圖，則稱為自補(bǔ)圖，非同構(gòu)的無(wú)向4階自補(bǔ)圖有（）個(gè)。、1、2、3、43、(D)。為無(wú)環(huán)有向圖，為的關(guān)聯(lián)矩陣，則（）。、是的終點(diǎn)、與不關(guān)聯(lián)、與關(guān)聯(lián)、是的始點(diǎn)4、(B)。一連通的平面圖，8個(gè)頂點(diǎn)4個(gè)面，則邊數(shù)為。、9、10、11、125、(D)。如果一個(gè)簡(jiǎn)單圖，則稱為自補(bǔ)圖，非同構(gòu)的3階有向完全圖的子圖中自補(bǔ)圖有個(gè)。、1、2、3、46、21條邊，3個(gè)4度頂點(diǎn)，其余頂點(diǎn)為3度的無(wú)向圖共有個(gè)頂點(diǎn)。、13、12、11、107、(D)。有向圖的通路包括。、簡(jiǎn)單通路、初級(jí)通路、復(fù)雜通路、簡(jiǎn)單通路、初級(jí)通路和復(fù)雜通路8、(D)。一連通的平面圖，9個(gè)頂點(diǎn)5個(gè)面，則邊數(shù)為。、9、10、11、129、21條邊，3個(gè)4度頂點(diǎn)，其余頂點(diǎn)為3度的無(wú)向圖共有個(gè)頂點(diǎn)。、13、12、11、1010、(D)。有向圖的通路包括。、簡(jiǎn)單通路、初級(jí)通路、復(fù)雜通路、簡(jiǎn)單通路、初級(jí)通路和復(fù)雜通路11、(D)。一連通的平面圖，9個(gè)頂點(diǎn)5個(gè)面，則邊數(shù)為。、9、10、11、1212、(B)。為有向圖，為的鄰接矩陣，則。、鄰接到的邊的條數(shù)是５、接到的長(zhǎng)度為４的通路數(shù)是５、長(zhǎng)度為４的通路總數(shù)是５、長(zhǎng)度為４的回路總數(shù)是５13、(C)。在無(wú)向完全圖中有個(gè)結(jié)點(diǎn)，則該圖的邊數(shù)為（）。A、B、C、D、14、(C)。任意平面圖最多是（）色的。A、3B、4C、5D、615、(A)。對(duì)與10個(gè)結(jié)點(diǎn)的完全圖，對(duì)其著色時(shí)，需要的最少顏色數(shù)為（）。A、10B、9C、11D、1216、(C)。對(duì)于任意的連通的平面圖，且每個(gè)面的次數(shù)至少為有，其中，分別為的階數(shù)、邊數(shù)。、、、、二．判斷題1、(A)。有向圖的關(guān)聯(lián)矩陣要求圖是無(wú)環(huán)圖。（）2、(A)。是某圖的度數(shù)序列。（）3、(A)。無(wú)向連通圖的點(diǎn)的連通關(guān)系是等價(jià)關(guān)系（）4、(B)。是某圖的度數(shù)序列。（）5、(A)。V和E分別為無(wú)向連通圖G1的點(diǎn)割集和邊割集.G1-E的連通分支個(gè)數(shù)為2。()6、(A)。彼得森圖不是哈密爾頓圖。（）7、(B)。是平面圖。（）8、(B)。設(shè)是平面圖，若，則它們的對(duì)偶圖。（）9、(A)。是平面圖。（）10、(A)。一個(gè)簡(jiǎn)單圖的閉包是漢密爾頓圖時(shí)，這個(gè)簡(jiǎn)單圖是漢密爾頓圖。（）11、(B)。平面圖中，任何兩條邊除端點(diǎn)外可以有其他交點(diǎn)。（）12、(B)。余樹一定是樹。（）13、(A)。為無(wú)向連通圖，是的生成子圖，并且是樹，則是的生成樹。（）14、(A)。是非平凡的無(wú)向樹，則至少有兩片樹葉（）15、(B)。無(wú)向樹有3個(gè)3度、2個(gè)2度頂點(diǎn)，其余頂點(diǎn)都是樹葉，共有4片樹葉。()16、(A)。無(wú)向樹有3個(gè)3度、2個(gè)2度頂點(diǎn)，其余頂點(diǎn)都是樹葉，共有5片樹葉。()17、(B)。已知n(n>=2)階無(wú)向簡(jiǎn)單樹具有n-1條邊，他一定是樹。()18、(A)。一個(gè)連通無(wú)向圖中，存在兩個(gè)結(jié)點(diǎn)和，如果結(jié)點(diǎn)和的每一條路都通過(guò)結(jié)點(diǎn)，則結(jié)點(diǎn)比為割點(diǎn)。（）19、(A)。一個(gè)有向圖，如果中有一個(gè)回路，至少包含每個(gè)結(jié)點(diǎn)一次，則是強(qiáng)連通。20、(A)。給定圖，則關(guān)于樹的定義是每一對(duì)結(jié)點(diǎn)之間有且僅有一條路。（）21、(A)。完全叉樹是每一個(gè)結(jié)點(diǎn)的出度等于或0的根樹。（）22、(A)。在正則叉樹中，所有的樹葉層次相同。（）23、(B)。樹中分支點(diǎn)的通路長(zhǎng)度為外部通路長(zhǎng)度。（）24、(B)。樹中樹葉的通路長(zhǎng)度為內(nèi)部通路長(zhǎng)度。（）25、(A)。任何一棵二叉樹的樹葉可對(duì)應(yīng)一個(gè)前綴碼。（）26、(A)。任何一個(gè)前綴碼都對(duì)應(yīng)一棵二叉樹。（）三．綜合題1.證明:若圖是自對(duì)偶的，則e=2v-2.2.T是一棵樹,有兩個(gè)2度結(jié)點(diǎn)，一個(gè)3度結(jié)點(diǎn)，三個(gè)4度結(jié)點(diǎn)，T有幾片樹葉？解：設(shè)樹T有x片樹葉，則T的結(jié)點(diǎn)數(shù)n=2+1+3+xT的邊數(shù)m=n-1=5+x又由得2·（5+x）=2·2+3·1+4·3+x

所以x=9，即樹T有9片樹葉。3.圖所示的賦權(quán)圖G表示七個(gè)城市a,b,c,d,e,f,g及架起城市間直接通訊線路的預(yù)測(cè)造價(jià)。試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小,并計(jì)算出最小造價(jià)。解：最小生成樹為因此如圖TG架線使各城市間能夠通訊，且總造價(jià)最小，最小造價(jià)為：Ｗ(Ｔ)＝１＋３＋４＋８＋９＋23＝484.求出下所示圖的鄰接矩陣和可達(dá)性矩陣，并找出v1解：鄰接矩陣v5.求下圖的一棵最小生成樹.解：因?yàn)閳D中n＝8，所以按算法要執(zhí)行n－1＝7次，其過(guò)程見下圖中(1)~(7)。6.v1到v4,v4到v1長(zhǎng)為3的通路各有多少條?求出下所示圖的鄰接矩陣和可達(dá)性矩陣v1到v4長(zhǎng)為3的通路0條，v4到v1長(zhǎng)為3的通路3條?？倧?fù)習(xí)題二1、(B)。設(shè)是半群，其中為非空集合，如果是上滿足交換律的二元運(yùn)算，則稱為。、半群、可交換半群、可交換群、域2、(D)。設(shè)是代數(shù)系統(tǒng)，其中為非空集合，如果,+是上的二元運(yùn)算，則稱環(huán)、為半群、為阿貝爾群、乘法對(duì)加法適合分配律、滿足A、B、C三條3、(D)。設(shè)是環(huán)，如果乘法適合交換律，則稱環(huán)。、整環(huán)、除環(huán)、域、交換環(huán)4、(B)。設(shè)代數(shù)系統(tǒng)是個(gè)獨(dú)異點(diǎn)，對(duì)任意，且均有逆元，則為（）。A、B、C、D、5、(D)。設(shè)代數(shù)系統(tǒng)是個(gè)獨(dú)異點(diǎn)，則還需滿足（）條件，代數(shù)系統(tǒng)為群。A、運(yùn)算封閉B、運(yùn)算可結(jié)合C、運(yùn)算可交換D、每個(gè)元素有逆元6、(B)。代數(shù)系統(tǒng)中，如果存在為等冪元，則（）。A、B、C、D、7、(B)。設(shè)是個(gè)群，是的平凡子群，則=（）。A、B、C、D、8、(D)。在群中，對(duì)于，必存在，使得，則為（）。A、B、C、D、9、(C)。設(shè)代數(shù)系統(tǒng)是群，則運(yùn)算滿足（）條件，是阿貝爾群。A、運(yùn)算封閉B、運(yùn)算可結(jié)合C、運(yùn)算可交換D、每個(gè)元素有逆元判斷題1、(A)。為獨(dú)異點(diǎn)，且中任意元素都存在逆元，則為一個(gè)群。（）2、(A)。為代數(shù)系統(tǒng)，為二元運(yùn)算，如果是可結(jié)合的，且中任意元素都存在逆元，則為一個(gè)群。（）3、(B)。為獨(dú)異點(diǎn)，且中任意元素都存在逆元，則為一個(gè)半群。（）三．綜合題1.設(shè)°運(yùn)算為Q上的二元運(yùn)算，?x,y∈Q,x°y=x+y+2x?y(1)指出°運(yùn)算的性質(zhì).(2)求°運(yùn)算的單位元、零元和所有可逆元.解：(1)°運(yùn)算可交換，可結(jié)合.任取x,yQ,x°y=x+y+2xy=y+x+2yx=y°x,任取x,y,zQ,(x°y)°z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyzx°(y°z)=x+(y+z+2yz)+2x(y+z+2yz=x+y+z+2xy+2xz+2yz+4xyz(2)設(shè)°運(yùn)算的單位元和零元分別為e和，則對(duì)于任意x有x°e=x成立，即x+e+2xe=xe=0由于°運(yùn)算可交換，所以0是幺元.對(duì)于任意x有x°=成立，即x++2x=x+2x=0=1/2給定x，設(shè)x的逆元為y,則有x°y=0成立，即x+y+2xy=0(x≠1/2)因此當(dāng)x1/2時(shí)，是x的逆元.2.S=P({1,2}),為對(duì)稱差運(yùn)算，寫出<s,>的運(yùn)算表，并判斷此代數(shù)系統(tǒng)是一個(gè)群。解：{1}{2}{1,2}{1}{2}{1,2}{1}{2}{1,2}{1}{1.2}{2}{2}{1,2}{1}{1,2}{2}{1}3.證明S110=1,2,5,10,11,22,55,110關(guān)于解解(1)不難驗(yàn)證S110關(guān)于gcd和lcm運(yùn)算構(gòu)成格.(略)(2)驗(yàn)證分配律x,y,z∈S110有

gcd(x,lcm(y,z))=lcm(gcd(x,y),gcd(x,z))

(3)驗(yàn)證它是有補(bǔ)格,1作為S110中的全下界,110為全上界,1和110互為補(bǔ)元,2和55互為補(bǔ)元,5和22互為補(bǔ)元,10和11互為補(bǔ)元,從而證明了<S110,gcd,lcm>為布爾代數(shù).總復(fù)習(xí)題三一．證明下列公式等值（1）┐(p∨q)?┐p∧┐q（2）p→(q→r)?(p∧q)→r（3）(p∨q)→r?(p→r)∧(q→r)（4）（p→q)∧p→q?1二．（1）求(pq)r公式的析取范式與合取范式以及成真賦值成假賦值。解(pq)r(pq)r（析取范式）①(pq)(pq)(rr)(pqr)(pqr)m6m7②r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7③②,③代入①并排序，得(pq)rm1m3m5m6m7（主析取范式）(pq)r(pr)(qr)（合取范式）④prp(qq)r(pqr)(pqr)M0M2⑤qr(pp)qr(pqr)(pqr)M0M4⑥⑤,⑥代入④并排序，得(pq)rM0M2M4（主合取范式）成真賦值為001,011,101,110,111，成假賦值為000,010,100.（2）已知命題公式A中含3個(gè)命題變項(xiàng)p,q,r，并知道它的成真賦值為001,010,111,求A的主析取范式和主合取范式，及A對(duì)應(yīng)的真值函數(shù).解：A的主析取范式為m1m2m7A的主合取范式為M0M3M4M5M6pqpqrFpqrF00001000001110100101110001101111三．構(gòu)造下面推理的證明：（1）若明天是星期一或星期三，我明天就有課.若我明天有課，今天必備課.我今天沒(méi)備課.所以，明天不是星期一、也不是星期三.解(1)設(shè)命題并符號(hào)化設(shè)p：明天是星期一，q：明天是星期三，r：我明天有課，s：我今天備課(2)寫出證明的形式結(jié)構(gòu)前提：(pq)r,rs,s結(jié)論：pq(3)證明①rs前提引入②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置換（2）2是素?cái)?shù)或合數(shù).若2是素?cái)?shù)，則2是無(wú)理數(shù).若2是無(wú)理數(shù)，則4不是素?cái)?shù).所以，如果4是素?cái)?shù)，則2是合數(shù).解用附加前提證明法構(gòu)造證明(1)設(shè)p：2是素?cái)?shù)，q：2是合數(shù)，r：2是無(wú)理數(shù)，s：4是素?cái)?shù)(2)推理的形式結(jié)構(gòu)前提：pq,pr,rs結(jié)論：sq(3)證明①s附加前提引入②pr前提引入③rs前提引入④ps②③假言三段論⑤p①④拒取式⑥pq前提引入⑦q⑤⑥析取三段論（3）前提：(pq)r,rs,s,p結(jié)論：q證明用歸繆法①q結(jié)論否定引入②rs前提引入③s前提引入④r②③拒取式⑤(pq)r前提引入⑥(pq)④⑤析取三段論⑦pq⑥置換⑧p①⑦析取三段論⑨p前提引入pp⑧⑨合?。?）(P（Q∨R))∧(┐S┐Q)∧(P∧┐S)R.證：（1）P∧┐SP（2）PT（1）I1（3）┐ST（1）I1（4）P（Q∨R)P（5）Q∨RT(2)，(4)I11（6）┐S┐QP（7）┐QT(3)，(6)I11（8）RT(5)，(7)I11四．求下列公式的前束范式。解：五．將下列命題符號(hào)化。(1)所有的人都長(zhǎng)著黑頭發(fā)；(2)有的人登上過(guò)月球；(3)沒(méi)有人登上過(guò)木星；(4)在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。解：令解：令M(x)：x為人。(1)

令F(x)：x長(zhǎng)著黑頭發(fā)。則x(M(x)→F(x))。(2)

令G(x)：x登上過(guò)月球。則x(M(x)∧G(x))。(3)

令H(x)：x登上過(guò)木星。則┐x(M(x)∧H(x))。(4)

令F(x)：x是在美國(guó)留學(xué)的學(xué)生;G(x)：x是亞洲人。則┐x(F(x)→G(x))。六．給定解釋I如下：（a）

個(gè)體域D={2,3};（b）

D中特定元素，a=2;（c）

D上特定函數(shù)f(x)為：f(2)=3,f(3)=2。（d）

D上特定謂詞：G(x,y):G(2,2)=G(2,3)=G(3,2)=1,G(3,3)=0;L(x,y):L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;F(x)：F(2)=0,F(3)=1在I下求下列各式的真值。(1)x(F(x)∧G(x,a));(2)x(F(f(x)∧G(x,f(x)));(3)xyL(x,y);(4)yxL(x,y)A(F(2)∧G(2,2))∧A(F(2)∧G(2,2))∧(F(3)∧G(3,2))(0∧1)∧(1∧1)0(2)B(F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3)))(F(3)∧G(2,3))∨(F(2)∧G(3,2))(1∧1)∨(0∧1)1(3)C(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))(1∨0)∧(0∨1)1(4)D(L(2,2)∧L(2,3))∨(L(3,2)∧L(3,3))(1∧0)∨(0∧1)0七．求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個(gè)？S={x|xS={x|xZ∧1x1000}A={x|xS∧x可被5整除}B={x|xS∧x可被6整除}C={x|xS∧x可被8整除}|A|=|A|=int(1000/5)=200|B|=int(1000/6)=166|C|=int(1000/8)=125|A∩B|=int(1000/lcm(5,6))=33|A∩C|=int(1000/lcm(5,8))=25|B∩C|=in