1、 第1學期離散數(shù)學試卷 A（試卷共6頁，答題時間120分鐘）題號一二三四總分統(tǒng)分人復核人得分得分閱卷人一、選擇題（每小題 2分，共 20 分。請將答案填在下面的表格內(nèi)）題號12345 678 910答案1、從集合分類的角度看,命題公式可分為(   )  A.永真式、矛盾式          B. 永真式、可滿足式、矛盾式 C. 可滿足式、矛盾式        D. 永真式、可滿足式 2、

2、設B不含有x，等值于 (   )A.   B. C.   D.3、設S,T,M是集合，下列結(jié)論正確的是（     ）A如果ST=SM，則T=M B如果S-T=，則S=TC D4、設R是集合A上的偏序關(guān)系，則R不一定是(   )A.自反的     B. 對稱的   C. 反對稱的      D. 傳遞的5 設R為實數(shù)集，定義R上4個二元運算

3、，不滿足結(jié)合律的是（ ）。A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy  D. f4(x,y)=maxx,y 6、設<L,>是一個格，則它不滿足(   )A.交換律     B. 結(jié)合律   C. 吸收律      D. 消去律7、設A=1,2,則群的單位元和零元是(   )A. 與A      B.&

4、#160;  A 與  C. 1與    D. 1與A 8、下列編碼是前綴碼的是(    ).A.1,11,101  B.1,001,0011 C. 1,01,001,000  D.0,00,0009、下圖中既是歐拉圖又是哈密頓圖的是（     ） A B C D 10、下圖所示的二叉樹中序遍歷的結(jié)果是（     ）Aabcde Bedcba Cbdeca Dbadce得分閱卷

5、人二、填空題（每題3分，共24分）1、含3個命題變項的命題公式的主合取范式為,則它的主析取范式為 。()2、，模4加群， 則3是 階元，33= ，3的逆元是 。 3、設V=<Z,+>,其中“+”是普通加法。，令1(x)=x, 2(x)=-x,3(x)=x+5, 4(x)=2x，其中有 個自同構(gòu).4、設是集合A=1，2，3，4,5,6上的一個置換，則把它表示成不相交的輪換的積是 。4、已知n階無向簡單圖G有m條邊，則G的補圖有 條邊。5、一個有向圖是強連通的充分必要條件是 。7、已知n階無向圖G中有m條邊，各頂點的度數(shù)均為3。又已知2n-3=m，則m= .8、在下圖中從A點開始，用普

6、里姆算法構(gòu)造最小生成樹，加入生成樹的第三條邊是 （ ）。得分閱卷人三、計算題（每題9分，共 36分）1、已知命題公式，(1) 構(gòu)造真值表。 (2) 求主析取范式(要求通過等值演算推出)。2、R1=<1,2>,<1,3>,<2,3>, R2=<2,2>,<2,3>,<3,4>,求： (1) （） () 求 、設<A,R>為一個偏序集，其中，A=1，2，3，4，6，9，12，24,R是A上的整除關(guān)系。（1）畫R出的哈斯圖； （2）求A的極大元和極小元； （3）求B=4,6的上確界和下確界。、畫一棵帶權(quán)為1，1，1，

7、3，3，5，8的最優(yōu)二叉樹T，并計算它的權(quán)W（T）。得分閱卷人四、證明題（共 20分）1、（7分）前提： 結(jié)論: 2、（7分）A=(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1),R=<(a,b),(c,d)>| (a,b),(c,d)A且a+b=c+d .(1)證明：R是A上的等價關(guān)系 (2)給出R確定的對A的劃分(分類).3、（6分）設是群, ,證明S是G的子群.離散數(shù)學試卷 A參考答案一、選擇題（每小題 2分，共 20 分。請將答案填在下面的表格內(nèi)）題號12345 678 910答案cadbbdbcaa 得分閱卷人二、填空題（每題3分，共24

8、分）1、 2、4,2,13、2 4、（123）（45）。4、 5、存在經(jīng)過每個頂點的回路 7、 9 . 8、 d,c 或 c，d 三、計算題（每題9分，共 36分）1、(1)構(gòu)造真值表(4分)p,q 0 0 0 1 1 0 1,101111011 1011(2) 主析取范式(5分): 2、(每小題3分) (1)= <1,2>,<1,3>() =<2,1>,<3,1>,<3,2> (1) 求=<1,2>,<1,3>,<1,4>,<2,4> 、 (每小題3分)(1)（4分）（2）（3分）A的極大元9,24; 極小元1;（3）（2分）B=4,6的上確界12 下確界2。、畫圖(7分) W（T）=55(2分) 四、證明題（共 20分）1、（7分）證明：附加前提證明法.1分 r . 3分 . 5分 . 7分2、證明：（1）（5分）自反性。對于 自反性成立對稱