2021-2021離散數(shù)學(xué)A卷試題

1、2021-2021離散數(shù)學(xué)a卷試題 2021-2021學(xué)年第一學(xué)期 離散數(shù)學(xué)期末考試試卷a 一、選擇題（共6題，每題3分，共18分） 1.設(shè)p：天下大雨,q：他在室內(nèi)運(yùn)動(dòng),命題“除非天下大雨，否則他不在室內(nèi)運(yùn)動(dòng)”可符合化為（ ） a. pq b. pq c. p q d.p q 2.謂詞公式 x(p(x) yr(y)q(x)中變?cè)獂是（ ） a.自由變?cè)?b.約束變?cè)?c.既不是自由變?cè)膊皇羌s束變?cè)?d.既是自由變?cè)彩羌s束變?cè)?3.下列命題中不正確的是（ ） a.xx-x b.x x-x c.a=xx,則xa且x a d.a-b= a=b 4.設(shè)集合a ,a，則下面（ ）是 a的冪集： a

2、 ,a,a b , ,a, , a c ,a, ,a d , ,a 5.設(shè)集合a=1，2，3，下列關(guān)系r中不是等價(jià)關(guān)系的是（ ） a.r=1,1,2,2,3,3 b.r=1,1,2,2,3,3,3,2,2,3 c.r=1,1,2,2,3,3,1,2 d.r=1,1,2,2,3,3,1,2,2,1,1,3,3,1,2,3,3,2 6. (a) (b) (c) (d) a （a）是歐拉圖，（b）是哈密頓圖 b （a）是歐拉圖，（c）是哈密頓圖 c （b）是歐拉圖，（d）是哈密頓圖 d （c）是歐拉圖，（d）是哈密頓圖 二、填空題（共8題，每題3分,共24分） 1.已知a 3,p(b) 64,p(a

3、 b) 256，則b ， a b ，p(a b) . 2. 命題公式a p (q r),b (p q) r，它們關(guān)系是 a b （填寫“ , , ”）. 3 .判別命題公式的類型： (p q) q是. 4.中根遍歷下圖中結(jié)點(diǎn)的次序?yàn)?. 5.設(shè)fr r,f(x)=x+3,grr,g(x)=2x+1,則復(fù)合函數(shù)(f g)(x) _, (g f)(x) _。 6. 一棵樹有2個(gè)2度結(jié)點(diǎn)，1個(gè)3度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其他為樹葉結(jié)點(diǎn)，則它 有 個(gè)結(jié)點(diǎn)， 條邊， 片樹葉. 7.設(shè)有連通平面圖有12個(gè)結(jié)點(diǎn)，22條邊，則有 個(gè)面. 8.設(shè)有二部圖如右圖，則其互補(bǔ)結(jié)點(diǎn)子集分別為 v1= , v2= . v2v

4、1 v4 v3 三、計(jì)算證明題（共4小題，前3題每題6分，第4小題7分，共25分） 1、設(shè)a,b為任意集合，證明：(a-b)-c = a-(bc). 2、用等值演算算法證明等值式 (pq)(p q) p 1，2 ，求公式： 3、設(shè)p x,y 為x整除y，q x 為x 2，個(gè)體域?yàn)?x y p x,y q x 的真值。 1,2,4,8,12,24, 上的整除關(guān)系4、設(shè)a r a1,a2a1,a2 a,a1整除a2 ，r是否為a上 的偏序關(guān)系？若是，則：（1）畫出r的哈斯圖；（3分）（2）求它的最小元，最大元。（4分） 四 有向圖g如右圖所示。 （1）求g的鄰接矩陣a； （2分） （2）g中v1到v4長(zhǎng)度為4的通路路有幾條？ （3分） （3）g中v1到自身長(zhǎng)度為3的回路有幾條？ （3分） （4）g是否強(qiáng)連通圖？ （2分） 五、求下圖的最小生成樹及權(quán)。（6分） 5 4 7 3 ev2 六、求葉的權(quán)重分別為3,5,6,7,8,10的最優(yōu)二元樹，并求其權(quán)重。（7分） 七、符號(hào)化下面的命題，并證明其推理是正確的。（10分） 每個(gè)運(yùn)動(dòng)員都是強(qiáng)壯