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

1、總復(fù)習(xí)題（一）一單選題1 (C)。一連通的平面圖，5個(gè)頂點(diǎn)3個(gè)面，則邊數(shù)為（）。、4 、5 、6 、72、 (A)。如果一個(gè)簡單圖，則稱為自補(bǔ)圖，非同構(gòu)的無向4階自補(bǔ)圖有（）個(gè)。、1 、2 、3 、43、 (D)。為無環(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è)簡單圖，則稱為自補(bǔ)圖，非同構(gòu)的3階有向完全圖的子圖中自補(bǔ)圖有個(gè)。、1 、2 、3 、46、21條邊，3個(gè)4度頂點(diǎn)，其余頂點(diǎn)為3度的無向圖共有個(gè)頂點(diǎn)。、13 、12 、11 、107、 (D)。有向圖的通路包

2、括。、簡單通路、初級通路、復(fù)雜通路、簡單通路、初級通路和復(fù)雜通路8、 (D)。一連通的平面圖，9個(gè)頂點(diǎn)5個(gè)面，則邊數(shù)為。、9 、10 、11 、129、21條邊，3個(gè)4度頂點(diǎn)，其余頂點(diǎn)為3度的無向圖共有個(gè)頂點(diǎn)。、13 、12 、11 、1010、 (D)。有向圖的通路包括。、簡單通路、初級通路、復(fù)雜通路、簡單通路、初級通路和復(fù)雜通路11、 (D)。一連通的平面圖，9個(gè)頂點(diǎn)5個(gè)面，則邊數(shù)為。、9 、10 、11 、1212、 (B)。為有向圖，為的鄰接矩陣，則。、鄰接到的邊的條數(shù)是、接到的長度為的通路數(shù)是、長度為的通路總數(shù)是、長度為的回路總數(shù)是13、 (C)。在無向完全圖中有個(gè)結(jié)點(diǎn)，則該圖的邊數(shù)

3、為（）。A、 B、 C、 D、14、 (C)。任意平面圖最多是（）色的。A、3 B、4 C、5 D、615、 (A)。對與10個(gè)結(jié)點(diǎn)的完全圖，對其著色時(shí)，需要的最少顏色數(shù)為（）。A、10 B、9 C、11 D、1216、(C)。對于任意的連通的平面圖，且每個(gè)面的次數(shù)至少為有，其中，分別為的階數(shù)、邊數(shù)。、二判斷題1、 (A)。有向圖的關(guān)聯(lián)矩陣要求圖是無環(huán)圖。（）2、 (A)。是某圖的度數(shù)序列。（）3、 (A)。無向連通圖的點(diǎn)的連通關(guān)系是等價(jià)關(guān)系（）4、 (B)。是某圖的度數(shù)序列。（）5、 (A)。V和E分別為無向連通圖G1的點(diǎn)割集和邊割集. G1 -E的連通分支個(gè)數(shù)為2。 ( )6、 (A)。彼

4、得森圖不是哈密爾頓圖。（）7、 (B)。是平面圖。（）8、 (B)。設(shè)是平面圖，若，則它們的對偶圖。（）9、 (A)。是平面圖。（）10、 (A)。一個(gè)簡單圖的閉包是漢密爾頓圖時(shí)，這個(gè)簡單圖是漢密爾頓圖。（）11、 (B)。平面圖中，任何兩條邊除端點(diǎn)外可以有其他交點(diǎn)。（）12、 (B)。余樹一定是樹。（）13、 (A)。為無向連通圖，是的生成子圖，并且是樹，則是的生成樹。（）14、 (A)。是非平凡的無向樹，則至少有兩片樹葉（）15、 (B)。無向樹有3個(gè)3度、2個(gè)2度頂點(diǎn)，其余頂點(diǎn)都是樹葉，共有4片樹葉。 ( )16、 (A)。無向樹有3個(gè)3度、2個(gè)2度頂點(diǎn)，其余頂點(diǎn)都是樹葉，共有5片樹葉。

5、( )17、 (B)。已知n(n>=2)階無向簡單樹具有n-1條邊，他一定是樹。( )18、 (A)。一個(gè)連通無向圖中，存在兩個(gè)結(jié)點(diǎn)和，如果結(jié)點(diǎn)和的每一條路都通過結(jié)點(diǎn)，則結(jié)點(diǎn)比為割點(diǎn)。（）19、 (A)。一個(gè)有向圖，如果中有一個(gè)回路，至少包含每個(gè)結(jié)點(diǎn)一次，則是強(qiáng)連通。20、 (A)。給定圖，則關(guān)于樹的定義是每一對結(jié)點(diǎn)之間有且僅有一條路。（）21、 (A)。完全叉樹是每一個(gè)結(jié)點(diǎn)的出度等于或0的根樹。（）22、 (A)。在正則叉樹中，所有的樹葉層次相同。（）23、 (B)。樹中分支點(diǎn)的通路長度為外部通路長度。（）24、 (B)。樹中樹葉的通路長度為內(nèi)部通路長度。（）25、 (A)。任何一棵二

6、叉樹的樹葉可對應(yīng)一個(gè)前綴碼。（）26、(A)。任何一個(gè)前綴碼都對應(yīng)一棵二叉樹。（）三綜合題1.證明:若圖是自對偶的，則.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+x T的邊數(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ù)測造價(jià)。試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小,并計(jì)算出最小造價(jià)。解：最小生成樹為因此如圖T

7、G架線使各城市間能夠通訊，且總造價(jià)最小，最小造價(jià)為：()23484.求出下所示圖的鄰接矩陣和可達(dá)性矩陣，并找出。解：鄰接矩陣答案錯(cuò)誤5.求下圖的一棵最小生成樹.解：因?yàn)閳D中n8，所以按算法要執(zhí)行n17次，其過程見下圖中(1)(7)。6.v1到v4,v4到v1長為3的通路各有多少條?求出下所示圖的鄰接矩陣和可達(dá)性矩陣v1到v4長為3的通路0條，v4到v1長為3的通路3條?？倧?fù)習(xí)題二1、 (B)。設(shè)是半群，其中為非空集合，如果是上滿足交換律的二元運(yùn)算，則稱為。、半群、可交換半群、可交換群、域2、 (D)。設(shè)是代數(shù)系統(tǒng)，其中為非空集合，如果,+是上的二元運(yùn)算，則稱環(huán)、為半群、為阿貝爾群、乘法對加法適

8、合分配律、滿足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)，對任意，且均有逆元，則為（）。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)。在群中，對于，必存在，使得，則為（）。A、 B、 C、 D、9、 (C)。設(shè)代數(shù)系統(tǒng)是群，則運(yùn)算滿足（）條件，是阿貝爾

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

10、(x+y+2xy)z = x+y+z+2xy+2xz+2yz+4xyz x(yz) = x+(y+z+2yz)+2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz(2) 設(shè)運(yùn)算的單位元和零元分別為 e 和 q，則對于任意 x 有 xe = x 成立，即 x+e+2xe = x Þe = 0 由于運(yùn)算可交換，所以 0 是幺元.對于任意 x 有xq= q成立，即x+q+2xq =qÞx+2xq= 0 Þq = -1/2 給定 x，設(shè) x 的逆元為 y, 則有 xy = 0 成立，即 x+y+2xy = 0 Þ (x -1/2 )因此當(dāng)x&

11、#185;-1/2時(shí)， 是x的逆元. 2.S = P(1, 2), Å為對稱差運(yùn)算，寫出 <s,Å>的運(yùn)算表，并判斷此代數(shù)系統(tǒng)是一個(gè)群。解：ÅÆ1 2 1,2Æ121,2Æ 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)

12、 (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)ÚØr公式的析取范式與合取范式以及成真賦值成假賦值。解 (p®Øq)®rÛ (pÙq)Úr（析取范式） (pÙq) Û (pÙq)Ù(ØrÚr)Û (p&

13、#217;qÙØr)Ú(pÙqÙr)Ûm6Úm7 rÛ (ØpÚp)Ù(ØqÚq)ÙrÛ (ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr)Ûm1Úm3Úm5Úm7 , 代入并排序，得 (p®Øq)®r

14、9;m1Úm3Úm5Úm6Úm7（主析取范式）(p®Øq)®rÛ (pÚr)Ù(qÚr) （合取范式） pÚrÛpÚ(qÙØq)ÚrÛ (pÚqÚr)Ù(pÚØqÚr) ÛM0ÙM2 qÚrÛ (pÙØp)ÚqÚrÛ (pÚqÚr)Ù(&#

15、216;pÚqÚr) ÛM0ÙM4, 代入 并排序，得 (p®Øq)®rÛM0ÙM2ÙM4（主合取范式）成真賦值為 001, 011, 101, 110, 111，成假賦值為 000, 010, 100. （2）已知命題公式A中含3個(gè)命題變項(xiàng)p, q, r，并知道它的成真賦值為001, 010, 111, 求A的主析取范式和主合取范式，及A對應(yīng)的真值函數(shù).解：A的主析取范式為m1 Úm2Úm7A的主合取范式為M0ÙM3ÙM4 ÙM5ÙM

16、6 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）若明天是星期一或星期三，我明天就有課. 若我明天有課，今天必備課. 我今天沒備課. 所以，明天不是星期一、也不是星期三. 解(1) 設(shè)命題并符號(hào)化 設(shè) p：明天是星期一，q：明天是星期三，r：我明天有課，s：我今天備課(2) 寫出證明的形式結(jié)構(gòu) 前提：(pÚq)®r, r®s, Øs結(jié)論：ØpÙØq(3) 證明 r®s前提引入 Ø

17、s前提引入 Ør 拒取式 (pÚq)®r前提引入 Ø(pÚq) 拒取式 ØpÙØq 置換（2）2是素?cái)?shù)或合數(shù). 若2是素?cái)?shù)，則 是無理數(shù). 若 是無理數(shù)，則4不是素?cái)?shù). 所以，如果4是素?cái)?shù)，則2是合數(shù). 解 用附加前提證明法構(gòu)造證明 (1) 設(shè) p：2是素?cái)?shù)，q：2是合數(shù)，r： 是無理數(shù)，s：4是素?cái)?shù) (2) 推理的形式結(jié)構(gòu) 前提：pÚq, p®r, r®Øs結(jié)論：s®q(3) 證明 s附加前提引入 p®r前提引入 r®Øs前提引入 p

18、®Øs 假言三段論 Øp 拒取式 pÚq前提引入 q 析取三段論（3）前提：Ø(pÙq)Úr, r®s, Øs, p 結(jié)論：Øq證明 用歸繆法 q結(jié)論否定引入 r®s前提引入 Øs前提引入 Ør 拒取式 Ø(pÙq)Úr前提引入 Ø(pÙq) 析取三段論 ØpÚØq 置換 Øp 析取三段論 p前提引入ØpÙp 合取（4） (P®（QR)(S

19、4;Q)(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） S®Q P（7） Q T(3)，(6) I11（8） R T(5)，(7) I11四求下列公式的前束范式。解：五將下列命題符號(hào)化。(1) 所有的人都長著黑頭發(fā)；(2)有的人登上過月球；(3) 沒有人登上過木星； (4)在美國留學(xué)的學(xué)生未必都是亞洲人。解：令M(x)：x 為人。(1)  令F(x)：x長著黑頭發(fā)。則"x (M(x) F(x)。 (2) 令G(x)：

20、x登上過月球。則$x (M(x)G(x)。(3) 令H(x)：x登上過木星。則 $x (M(x)H(x)。(4) 令F(x)：x是在美國留學(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

21、(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) "x$y L(x,y); (4) $y"x 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 Û

22、; (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) Û 0七求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個(gè)？S = x | xÎZ1£x£1000 A = x | xÎSx可被5整除B = x | xÎSx可被6整除C = x | xÎSx可被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,