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

PAGEPAGE2一、填空1設(shè)集合A,B，其中A＝{1,2,3},B={1,2},則A—B＝____________________; (A)-(B)＝__________________________.2.設(shè)有限集合A,|A|=n,則|(A×A)|=__________________________.3.設(shè)A、B為兩個(gè)集合,A={1,2,4},B={3,4},則從AB＝_________________________;AB＝_________________________;A－B＝_____________________.4.設(shè)R是集合A上的等價(jià)關(guān)系，則R所具有的關(guān)系的三個(gè)特性是______________________,________________________,_______________________________.5.設(shè)有限集A,B，|A|=m,|B|=n,則||(AB)|=_____________________________.6設(shè)A,B,R是三個(gè)集合，其中R是實(shí)數(shù)集，A={x|-1≤x≤1,xR},B={x|0≤x<2,xR},則A-B=__________________________,B-A=__________________________,A∩B=__________________________,.7．設(shè)（N：自然數(shù)集，E+正偶數(shù)）則。8．A，B，C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為ABCABC9．圖的補(bǔ)圖為。10.n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為，歐拉圖的充要條件是。11.設(shè)G為9階無(wú)向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6，則G中至少有個(gè)5度結(jié)點(diǎn)。12.有向圖中從v1到v2長(zhǎng)度為2的通路有條。13.已知一棵無(wú)向樹T有三個(gè)3頂點(diǎn),一個(gè)2度頂點(diǎn),其余的都是1度頂點(diǎn),則T中有個(gè)1度頂點(diǎn)。14.n階完全圖Kn的邊數(shù)為。15右圖的鄰接矩陣A=。16.設(shè)G是n階完全圖，則G的邊數(shù)m=。17.設(shè)G是具有8個(gè)頂點(diǎn)的樹，則G中增加_________條邊才能把G變成完全圖。18．設(shè)P，Q的真值為0，R，S的真值為1，則的真值=。19．公式的主合取范式為。20.若P，Q為二命題，真值為1，當(dāng)且僅當(dāng)。21.稱為命題。22.命題P→Q的真值為0，當(dāng)且僅當(dāng)。23.一個(gè)命題含有4個(gè)原子命題，則對(duì)其所有可能賦值有種。24.若P，Q，為二命題，真值為0當(dāng)且僅當(dāng)。二、選擇題（可多選）1、下列是真命題的有（）A．； B．；C．；D．。2、下列集合中相等的有（）A．{4，3}；B．{，3，4}；C．{4，，3，3}；D．{3，4}。3.設(shè)集合A={2,{a},3,4}，B={{a},3,4,1}，E為全集，則下列命題正確的是()。 (A){2}A(B){a}A (C){{a}}BE(D){{a},1,3,4}B.4.設(shè)集合A={1,2,3},A上的關(guān)系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備(). (A)自反性 (B)傳遞性 (C)對(duì)稱性 (D)反對(duì)稱性5.設(shè)集合A={1,2,3,4},A上的關(guān)系R＝{(1,1),(2,3),(2,4),(3,4)},則R具有()。 (A)自反性 (B)傳遞性 (C)對(duì)稱性(D)以上答案都不對(duì)6.下列關(guān)于集合的表示中正確的為()。 (A){a}{a,b,c} (B){a}{a,b,c} (C){a,b,c}(D){a,b}{a,b,c}7.設(shè)A={1，2，3}，則A上的二元關(guān)系有（）個(gè)。A．23；B．32；C．；D．。8.若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是(). (A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5) (C)(1,1,1,2,3)(D)(2,3,3,4,5,6).9.圖中從v1到v3長(zhǎng)度為3的通路有（）條。A．0； B．1； C．2； D．3。10、在一棵樹中有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹有（）個(gè)4度結(jié)點(diǎn)。A．1； B．2； C．3； D．4。11..設(shè)G是5個(gè)頂點(diǎn)的完全圖，則從G中刪去()條邊可以得到樹. (A)6(B)5 (C)10(D)4.12.設(shè)圖G的相鄰矩陣為，則G的頂點(diǎn)數(shù)與邊數(shù)分別為(). (A)4,5 (B)5,6 (C)4,10 (D)5,8.11.A. 12.D13、設(shè)，S上關(guān)系R的關(guān)系圖為則R具有（）性質(zhì)。A．自反性、對(duì)稱性、傳遞性；B．反自反性、反對(duì)稱性；C．反自反性、反對(duì)稱性、傳遞性；D．自反性。14、在如下的有向圖中，從V1到V4長(zhǎng)度為3的道路有（）條。A．1；B．2；C．3；D．4。15、在如下各圖中（）歐拉圖。16.在下述公式中是重言式為（）A．；B．；C．；D．。17.下述命題公式中，是重言式的為（）。A、；B、；C、；D、。18.設(shè)，則有（）。A、{{1,2}}；B、{1,2}；C、{1}；D、{2}。19.下列語(yǔ)句是命題的有（）。明年中秋節(jié)的晚上是晴天；B、；C、當(dāng)且僅當(dāng)x和y都大于0；D、我正在說(shuō)謊。20.下列各命題中真值為真的命題有（）。2+2=4當(dāng)且僅當(dāng)3是奇數(shù)；B、2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)；C、2+2≠4當(dāng)且僅當(dāng)3是奇數(shù)；D、2+2≠4當(dāng)且僅當(dāng)3不是奇數(shù)；21.下列符號(hào)串是公式的有（）A、；B、；C、；D、。22.下列等價(jià)式成立的有（）。A、；B、；C、；D、。23.下面四組數(shù)能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列的有（）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；C、（1，1，2，2，2）；D、（0，1，3，3，3）。24.如果一個(gè)有向圖D是強(qiáng)連通圖，則D是歐拉圖，這個(gè)命題的真值為（）A、真；B、假。25.如右圖相對(duì)于完全圖K5的補(bǔ)圖為（）。26.一棵無(wú)向樹T有7片樹葉，3個(gè)3度頂點(diǎn)，其余頂點(diǎn)均為4度。則T有（）4度結(jié)點(diǎn)。A、1；B、2；C、3；D、427.下面四組數(shù)能構(gòu)成無(wú)向圖的度數(shù)列的有()。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。28.圖的鄰接矩陣為()。A、；B、；C、；D、。29.下列圖中是歐拉圖的有()。30.一棵無(wú)向樹T有8個(gè)頂點(diǎn)，4度、3度、2度的分枝點(diǎn)各1個(gè)，其余頂點(diǎn)均為樹葉，則T中有（）片樹葉。A、3；B、4；C、5；D、631.設(shè)S={N，Q，R}，下列命題正確的是（）。A、；B、；C、；D、。32.下列語(yǔ)句不是命題的有（）。x=13；B、離散數(shù)學(xué)是計(jì)算機(jī)系的一門必修課；C、雞有三只腳；D、太陽(yáng)系以外的星球上有生物；E、你打算考碩士研究生嗎？33.的合取范式為（）。A、；B、；C、D、34.設(shè)|A|=n，則A上有（）二元關(guān)系。A、2n；B、n2；C、；D、nn；E、。35.下列各符號(hào)串，不是合式公式的有（）。A、；B、；C、；D、。36.下列語(yǔ)句是命題的有（）。A、2是素?cái)?shù)；B、x+5>6；C、地球外的星球上也有人；D、這朵花多好看呀！。37.下列公式是重言式的有（）。A、；B、；C、；D、38.下列問題成立的有（）。若，則；B、若，則；C、若，則；D、若，則。39.有向圖D=<V,E>，則長(zhǎng)度為2的通路有（）條。A、0；B、1；C、2；D、3。40.集合的冪集為（）。A、；B、；C、；D、41.下列結(jié)果正確的是（）。A、；B、；C、；D、；E、；F、A⊕A=A。問答題1、如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（９分）2.權(quán)數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二元樹。（7分）3、在二元樹中求帶權(quán)為2，3，5，7，8的最優(yōu)二元樹T。（5分）求T對(duì)應(yīng)的二元前綴碼。（5分）4.如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信成路造價(jià)（單位：萬(wàn)元），試給出一個(gè)設(shè)計(jì)方案，使得各城市之間既能夠通信又使總造價(jià)最小。5.在通訊中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求傳輸它們最佳前綴碼（寫出求解過(guò)程）。6.如下圖所示的賦