離散數(shù)學(xué)復(fù)習(xí)題及答案

1、總復(fù)習(xí)題（一）一單選題1 (C)。一連通的平面圖，5個(gè)頂點(diǎn)3個(gè)面，則邊數(shù)為（）。、4 、5 、6 、72、 (A)。如果一個(gè)簡(jiǎn)單圖，則稱(chēng)為自補(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)單圖，則稱(chēng)為自補(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)。有向圖的通路包

2、括。、簡(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ù)

3、為（）。A、 B、 C、 D、14、 (C)。任意平面圖最多是（）色的。A、3 B、4 C、5 D、615、 (A)。對(duì)與10個(gè)結(jié)點(diǎn)的完全圖，對(duì)其著色時(shí)，需要的最少顏色數(shù)為（）。A、10 B、9 C、11 D、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)。彼

4、得森圖不是哈密爾頓圖。（）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)。余樹(shù)一定是樹(shù)。（）13、 (A)。為無(wú)向連通圖，是的生成子圖，并且是樹(shù)，則是的生成樹(shù)。（）14、 (A)。是非平凡的無(wú)向樹(shù)，則至少有兩片樹(shù)葉（）15、 (B)。無(wú)向樹(shù)有3個(gè)3度、2個(gè)2度頂點(diǎn)，其余頂點(diǎn)都是樹(shù)葉，共有4片樹(shù)葉。 ( )16、 (A)。無(wú)向樹(shù)有3個(gè)3度、2個(gè)2度頂點(diǎn)，其余頂點(diǎn)都是樹(shù)葉，共有5片樹(shù)葉。

5、( )17、 (B)。已知n(n=2)階無(wú)向簡(jiǎn)單樹(shù)具有n-1條邊，他一定是樹(shù)。( )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)于樹(shù)的定義是每一對(duì)結(jié)點(diǎn)之間有且僅有一條路。（）21、 (A)。完全叉樹(shù)是每一個(gè)結(jié)點(diǎn)的出度等于或0的根樹(shù)。（）22、 (A)。在正則叉樹(shù)中，所有的樹(shù)葉層次相同。（）23、 (B)。樹(shù)中分支點(diǎn)的通路長(zhǎng)度為外部通路長(zhǎng)度。（）24、 (B)。樹(shù)中樹(shù)葉的通路長(zhǎng)度為內(nèi)部通路長(zhǎng)度。（）25、 (A)。任何一棵二叉樹(shù)的樹(shù)

6、葉可對(duì)應(yīng)一個(gè)前綴碼。（）26、(A)。任何一個(gè)前綴碼都對(duì)應(yīng)一棵二叉樹(shù)。（）三綜合題1.證明:若圖是自對(duì)偶的，則.2.T是一棵樹(shù),有兩個(gè)2度結(jié)點(diǎn)，一個(gè)3度結(jié)點(diǎn)，三個(gè)4度結(jié)點(diǎn)，T有幾片樹(shù)葉？解：設(shè)樹(shù)T有x片樹(shù)葉，則T的結(jié)點(diǎn)數(shù) n=2+1+3+x T的邊數(shù)m=n-1=5+x又由得 2 （5+x）=22+31+43+x所以x=9，即樹(shù)T有9片樹(shù)葉。3.圖所示的賦權(quán)圖G表示七個(gè)城市a,b,c,d,e,f,g及架起城市間直接通訊線路的預(yù)測(cè)造價(jià)。試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小,并計(jì)算出最小造價(jià)。解：最小生成樹(shù)為因此如圖TG架線使各城市間能夠通訊，且總造價(jià)最小，最小造價(jià)為：()23484.

7、求出下所示圖的鄰接矩陣和可達(dá)性矩陣，并找出。解：鄰接矩陣答案錯(cuò)誤5.求下圖的一棵最小生成樹(shù).解：因?yàn)閳D中n8，所以按算法要執(zhí)行n17次，其過(guò)程見(jiàn)下圖中(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)算，則稱(chēng)為。、半群、可交換半群、可交換群、域2、 (D)。設(shè)是代數(shù)系統(tǒng)，其中為非空集合，如果,+是上的二元運(yùn)算，則稱(chēng)環(huán)、為半群、為阿貝爾群、乘法對(duì)加法適合分配律、滿足A、B、C三條3、 (D)。設(shè)是環(huán)，如果乘法適合交換律

8、，則稱(chēng)環(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è)元素有逆元

9、判斷題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)算，(1) 指出運(yùn)算的性質(zhì).(2) 求 運(yùn)算的單位元、零元和所有可逆元.解：(1) 運(yùn)算可交換，可結(jié)合. 任取 x, yQ,xy = x+y+2xy = y+x+2yx = y x,任取 x, y, zQ, (xy)z = (x+y+2xy)+z+2(x+y+2xy)z = x+y+z+2xy+2xz+2yz+4xyz x(yz) = x+

10、(y+z+2yz)+2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz(2) 設(shè)運(yùn)算的單位元和零元分別為 e 和 q，則對(duì)于任意 x 有 xe = x 成立，即 x+e+2xe = x e = 0 由于運(yùn)算可交換，所以 0 是幺元.對(duì)于任意 x 有xq= q成立，即x+q+2xq =qx+2xq= 0 q = -1/2 給定 x，設(shè) x 的逆元為 y, 則有 xy = 0 成立，即 x+y+2xy = 0 (x -1/2 )因此當(dāng)x-1/2時(shí)， 是x的逆元. 2.S = P(1, 2), 為對(duì)稱(chēng)差運(yùn)算，寫(xiě)出 的運(yùn)算表，并判斷此代數(shù)系統(tǒng)是一個(gè)群。解：1 2 1,2121,2

11、1 2 1,21 1.2 22 1,2 11,2 2 1 3.證明關(guān)于gcd, lcm運(yùn)算構(gòu)成的布爾代數(shù). 解(1) 不難驗(yàn)證S110關(guān)于gcd和lcm 運(yùn)算構(gòu)成格. (略)(2) 驗(yàn)證分配律x, y, zS110有g(shù)cd(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ǔ)元, 從而證明了為布爾代數(shù).總復(fù)習(xí)題三一證明下列公式等值二（1）求(pq)r公式的析取范式與合取范式以及成真賦值成假賦值。解 (pq)r (pq

12、)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，并知道它的成真賦值為0

13、01, 010, 111, 求A的主析取范式和主合取范式，及A對(duì)應(yīng)的真值函數(shù).解：A的主析取范式為m1 m2m7A的主合取范式為M0M3M4 M5M6 pq r F pq r F0 0 0 0 1 0 0 00 0 1 1 1 0 1 00 1 0 1 1 1 0 00 1 1 0 1 1 1 1三構(gòu)造下面推理的證明：（1）若明天是星期一或星期三，我明天就有課. 若我明天有課，今天必備課. 我今天沒(méi)備課. 所以，明天不是星期一、也不是星期三. 解(1) 設(shè)命題并符號(hào)化 設(shè) p：明天是星期一，q：明天是星期三，r：我明天有課，s：我今天備課(2) 寫(xiě)出證明的形式結(jié)構(gòu) 前提：(pq)r, rs,

14、s結(jié)論：pq(3) 證明 rs前提引入 s前提引入 r 拒取式 (pq)r前提引入 (pq) 拒取式 pq 置換（2）2是素?cái)?shù)或合數(shù). 若2是素?cái)?shù)，則 是無(wú)理數(shù). 若 是無(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： 是無(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前提引入

15、 s前提引入 r 拒取式 (pq)r前提引入 (pq) 析取三段論 pq 置換 p 析取三段論 p前提引入pp 合?。?） (P（QR)(SQ)(PS)R.證：（1） PS P（2） P T（1） I1（3） S T（1） I1（4） P（QR) P（5） QR T (2)，(4) I11（6） SQ P（7） Q T(3)，(6) I11（8） R T(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)著黑頭

16、發(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

17、(2)=0, F(3)=1在I下求下列各式的真值。 (1) x(F(x)G(x,a);(2) $x(F(f(x)G(x,f(x);(3) x$y L(x,y); (4) $yx L(x,y)A (F(2)G(2,2)(F(3)G(3,2)解：設(shè)公式（1）為A, 則 (01)(11) 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) (11)(01) 1(3) C (L(2, 2) L(2,3)(L(3,2)L(3,3) (10)(01) 1(4) D (L(2,2) L(2,3)(L(3,2)L(3,3) (10)(01)

18、0七求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個(gè)？S = x | xZ1x1000 A = x | xSx可被5整除B = x | xSx可被6整除C = x | xSx可被8整除解：|A| = int(1000/5) = 200|B| = int(1000/6) = 166|C| = int(1000/8) = 125|AB| = int(1000/lcm(5,6) = 33|AC| = int(1000/lcm(5,8) = 25|BC| = int(1000/lcm(6,8) = 41|ABC| = int(1000/lcm(5,6,8) = 81000-(200+100+33+67)=600八A=1,2,3,4, R=,求關(guān)系的定義域、值域與域并求 R的關(guān)系矩陣MR和關(guān)系圖GR解：關(guān)系圖為domR=1, 2, 4 ranR=1，2, 3, 4 fldR=1, 2, 3, 4九設(shè)A=a,b,c,d, R=,求R和r(R), s(R), t(R)的關(guān)系圖Rr(R)s(R)t(R)十給出 A1,2,3上所有的等價(jià)關(guān)系解：先求出A的所有劃分：p1=1