離散數(shù)學(xué) 練習(xí)題

1、模擬題一、選擇與填空題：1設(shè)<A，+，´>是代數(shù)系統(tǒng)，其中+和´為普通的加法和乘法，則當(dāng)A= 時(shí)，<A，+，´>是域。x|x是整數(shù)x|x0，x是有理數(shù)x|x0，x是實(shí)數(shù)x|x是偶數(shù)x|x=a+b，a, b是有理數(shù)2設(shè)G是由6個(gè)元素構(gòu)成的循環(huán)群，a是G的一個(gè)生成元素，則G有_個(gè)子群，G的生成元是_。3ÆÆ = ，Æ，Æ-Æ = 。4設(shè)集合A=a，b，c，d，e，f，g，=a，b，c，d，e，f，g是A上的一個(gè)劃分，則所對(duì)應(yīng)的等價(jià)關(guān)系R應(yīng)有 個(gè)有序?qū)Α?51617181449275下列代數(shù)系統(tǒng)&

2、lt;G, *>（其中*是普通加法運(yùn)算），(1) G為整數(shù)集合；(2) G為偶數(shù)集合；(3) G為有理數(shù)集合；(4) G為自然數(shù)集合。其中， 不是群。6設(shè)G為任意的連通平面圖，則有n-m+r = ；若G是簡(jiǎn)單連通平面圖(n3)，則m ；若G是簡(jiǎn)單連通平面圖(n3)，且G是二部圖，則m 。（其中n表示頂點(diǎn)數(shù)，m表示邊數(shù)，r表示平面數(shù)。）7一棵樹(shù)T中有2個(gè)2度頂點(diǎn)，3個(gè)3度頂點(diǎn)，4個(gè)4度頂點(diǎn)，且沒(méi)有大于4度的頂點(diǎn)，那么T中有 片樹(shù)葉。8設(shè)有下列集合，A =0，10，110，1111，B =1，01，001，000，C =1，11，101，001，0011，D =b，c，aa，ac，aba，a

3、bb，abc，則 是前綴碼。9設(shè)集合A=a，b，c，R=<a，a>，<a，b>，<a，c>，<c，a>，則R是 。自反的反自反的對(duì)稱的反對(duì)稱的傳遞的不可傳遞的10在圖1所示的二部圖中，其最大匹配含有 條邊。圖111設(shè)<A，>是格，其中A=1，2，3，4，6，8，12，24>，為整除關(guān)系，則3的補(bǔ)元是 ，8的補(bǔ)元是 ，1的補(bǔ)元是 。12在如圖2所示的二叉樹(shù)中，后序遍歷序列為： ，中序遍歷序列為： 。ABCDEFGHJIKLM圖213對(duì)于S6中的置換，若表示成不交的輪換之積，則s = ，t = ，st = 。14設(shè)某班有學(xué)生50人，

4、其中有28人在第一次考試中得到優(yōu)，有23人在第二次考試中得到優(yōu)，有15人兩次考試都沒(méi)有得到優(yōu)，那么兩次考試都得到優(yōu)的學(xué)生人數(shù)是 。15設(shè)個(gè)體域D =a，b，c，消去下列謂詞公式中的量詞："x(F(x，y)®$yG(y) Û 。二、判斷題：1“你真棒！”是個(gè)真命題。（ ）2在主合取范式中，每個(gè)極大項(xiàng)都對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，該二進(jìn)制數(shù)是極大項(xiàng)的成真賦值。（ ）3ÆÍÆ，但ÆÏÆ。（ ）4極小元是指集合中大小最小的元素。（ ）5aÍa，b（ ）6二元關(guān)系不是集合。（ ）7最大元一定是極大元。（ ）8函數(shù)的

5、逆也是一個(gè)函數(shù)。（ ）9設(shè)S，T為任意集合，若S-T=Æ，則S=T。（ ）10由握手定理可以推導(dǎo)出無(wú)向圖中的奇度頂點(diǎn)有奇數(shù)個(gè)。（ ）三、綜合題：1設(shè)<A，R>是偏序集，A =1，2，3，4，6，8，12，24，60，R是A上的整除關(guān)系，（1）畫出R的哈斯圖；（2）設(shè)子集B =2，4，6，12，寫出B的極大元、極小元、最大元、最小元、上界、下界、最小上界和最大下界。1設(shè)偏序集<S30，D>，其中，S30表示30的所有因子集合，D表示整除關(guān)系。（1）試作出該偏序集的哈斯圖；（2）設(shè)B=1,3,6,15，求B的最大元素、最小元素、極大元素、極小元素、最小上界和最大下

6、界。 2在一階邏輯中將下列命題符號(hào)化：（1）沒(méi)有不吃飯的人。（2）在北京賣菜的人不全是東北人。（3）自然數(shù)全是整數(shù)。（4）有的人天天鍛煉身體。2在一階邏輯中將下列命題符號(hào)化：（1）所有大學(xué)生都要參加考試。（2）有些大學(xué)生愛(ài)唱歌。（3）并非每個(gè)實(shí)數(shù)是無(wú)理數(shù)。（4）雖然有些實(shí)數(shù)是無(wú)理數(shù)，但未必一切實(shí)數(shù)都是無(wú)理數(shù)。四、計(jì)算題： 1用Dijkstra算法求圖3中a到z的最短路徑，并求出最短路徑長(zhǎng)度。abcagdefz632734215223564v1v2v4v32有向圖D如圖4所示。（1）寫出D的鄰接矩陣A；（2）D中長(zhǎng)度為3的通路有多少條？ 長(zhǎng)度為2的回路有多少條？（3）求該圖的可達(dá)矩陣，D是哪類連

7、通圖？v4v5v3v1v22有向圖D如圖4所示。（1）寫出D的鄰接矩陣A；（2）D中長(zhǎng)度為2的通路有多少條？ 長(zhǎng)度為3的回路有多少條？（3）求該圖的可達(dá)矩陣，D是哪類連通圖？3用克魯斯克爾(Kruskal)算法求下列帶權(quán)無(wú)向圖的最小生成樹(shù)，并計(jì)算出最小生成樹(shù)的權(quán)值。e1234567891011abcdf4求命題公式（ØPQ）Ù（PR）的主析取范式。5設(shè)七個(gè)字母在通訊中出現(xiàn)的頻率如下： a：35%，b：20%，c：15%，d：10%，e：8%，f：6%，g：3%.（1）以頻率（或乘100）為權(quán)，求最優(yōu)二元樹(shù)；（2）求每個(gè)字母對(duì)應(yīng)的前綴碼；（3）傳輸10 000個(gè)按上述比例出現(xiàn)的字母需要傳輸多少個(gè)二進(jìn)制位？比用長(zhǎng)度為3的等長(zhǎng)碼子傳輸節(jié)省了多少個(gè)二進(jìn)制位？5設(shè)七個(gè)數(shù)字在通訊中出現(xiàn)的頻率如下： 0：35%，1：20%，2：15%，3：10%，4：8%，5：6%，6：6%.（1）以頻率（或乘100）為權(quán)，求最優(yōu)二元樹(shù)；（2）求每個(gè)數(shù)字對(duì)應(yīng)的前綴碼。五、證明題：1證明下列命題中結(jié)論的有效性：如果這里有球賽，則通行是困難的。如果他們按時(shí)到達(dá)，則通行是不困難的。他們按時(shí)到達(dá)了。所以，這里沒(méi)有球賽。1構(gòu)造下面推理的證明：如果