離散數(shù)學 練習題

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

2、lt;G, *>（其中*是普通加法運算），(1) G為整數(shù)集合；(2) G為偶數(shù)集合；(3) G為有理數(shù)集合；(4) G為自然數(shù)集合。其中， 不是群。6設G為任意的連通平面圖，則有n-m+r = ；若G是簡單連通平面圖(n3)，則m ；若G是簡單連通平面圖(n3)，且G是二部圖，則m 。（其中n表示頂點數(shù)，m表示邊數(shù)，r表示平面數(shù)。）7一棵樹T中有2個2度頂點，3個3度頂點，4個4度頂點，且沒有大于4度的頂點，那么T中有 片樹葉。8設有下列集合，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設集合A=a，b，c，R=<a，a>，<a，b>，<a，c>，<c，a>，則R是 。自反的反自反的對稱的反對稱的傳遞的不可傳遞的10在圖1所示的二部圖中，其最大匹配含有 條邊。圖111設<A，>是格，其中A=1，2，3，4，6，8，12，24>，為整除關系，則3的補元是 ，8的補元是 ，1的補元是 。12在如圖2所示的二叉樹中，后序遍歷序列為： ，中序遍歷序列為： 。ABCDEFGHJIKLM圖213對于S6中的置換，若表示成不交的輪換之積，則s = ，t = ，st = 。14設某班有學生50人，

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

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

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

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