滄州交通學(xué)院《離散數(shù)學(xué)》2017-2018學(xué)年期末試卷

1一、選擇題A．矛盾式B．重言式C．可滿足式D．無法判斷2、不是最小聯(lián)結(jié)詞組的有。3、下列關(guān)于圖論說法正確的是。A.若兩圖結(jié)點(diǎn)數(shù)目相同，邊數(shù)相等，且度數(shù)相同的結(jié)點(diǎn)數(shù)目相等，則兩圖同構(gòu)。B.通路都是跡，跡不都是通路。C．對(duì)于任何一個(gè)圖G，都有點(diǎn)連通度大于等于邊連通度。D．多于3個(gè)結(jié)點(diǎn)有向完全圖Kn不一定是漢密爾頓圖。4、設(shè)圖G=（V，E|V|=8，若G有3個(gè)度數(shù)為3的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，其余的結(jié)點(diǎn)度數(shù)為1，則G有條邊。5、設(shè)有21臺(tái)電腦，公用一個(gè)電源，若要21臺(tái)電腦同時(shí)工作，則需要三插頭的接線板數(shù)為。二、填空題1、若P與Q為二命題，則PΦQ真值為F當(dāng)且僅當(dāng)。2、命題公式(P^Q)量T的對(duì)偶式為。3、論域D={1，2}，指定謂詞PP(2,2)TTFF則公式Vx二yP(y,x)真值為。2對(duì)該謂詞公式中的自由變?cè)M(jìn)行代入為。5、下圖相對(duì)于完全圖的補(bǔ)圖為。A6、下面有向圖的強(qiáng)分圖為由導(dǎo)出的子圖。三、計(jì)算題1、已知命題公式P((PQ)^(QP))，利用等價(jià)公式法求該命題公式的主析取范式，并求其成真賦值。2、某景區(qū)有6個(gè)景點(diǎn)A,B,C,D,E,F，景點(diǎn)之間道路的長(zhǎng)度分別是d(A,B)=1,d(A,C)=11,d(A,D)=6,d(A,F)=2,d(B,C)=9,d(B,D)=3,d(C,E)=8,d(C,F)=7,d(D,E)=10,d(D,F)=4,d(E,F)=5。景點(diǎn)間的關(guān)系圖如下：A69F1）寫出此圖的鄰接矩陣A與可達(dá)性矩陣P。2）判斷此圖是否為歐拉圖，是否為漢密爾頓圖。要求給出判斷依據(jù)。3）判斷此圖是否為平面圖。若是，則畫出平面圖形并求其對(duì)偶圖；否則，說明原因。4）以道路的長(zhǎng)度為權(quán)值，利用Kruskal算法求其最小生成樹，并給出相應(yīng)樹權(quán)。5）利用韋爾奇法對(duì)該圖著色，求著色數(shù)。3對(duì)應(yīng)的前綴碼。1、利用謂詞推理理論構(gòu)造下面推理