離散數(shù)學(xué)試卷A答案

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

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

3、，不滿(mǎn)足結(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、設(shè)<L,>是一個(gè)格，則它不滿(mǎn)足(   )A.交換律     B. 結(jié)合律   C. 吸收律      D. 消去律7、設(shè)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、下圖所示的二叉樹(shù)中序遍歷的結(jié)果是（     ）Aabcde Bedcba Cbdeca Dbadce得分閱卷

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

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

7、3，3，5，8的最優(yōu)二叉樹(shù)T，并計(jì)算它的權(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上的等價(jià)關(guān)系 (2)給出R確定的對(duì)A的劃分(分類(lèi)).3、（6分）設(shè)是群, ,證明S是G的子群.離散數(shù)學(xué)試卷 A參考答案一、選擇題（每小題 2分，共 20 分。請(qǐng)將答案填在下面的表格內(nèi)）題號(hào)12345 678 910答案cadbbdbcaa 得分閱卷人二、填空題（每題3分，共24

8、分）1、 2、4,2,13、2 4、（123）（45）。4、 5、存在經(jīng)過(guò)每個(gè)頂點(diǎn)的回路 7、 9 . 8、 d,c 或 c，d 三、計(jì)算題（每題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。、畫(huà)圖(7分) W（T）=55(2分) 四、證明題（共 20分）1、（7分）證明：附加前提證明法.1分 r . 3分 . 5分 . 7分2、證明：（1）（5分）自反性。對(duì)于 自反性成立對(duì)稱(chēng)