《離散數(shù)學(xué)》習(xí)題2-B

2B第7頁共8頁一、單選題（20小題，每小題2分，共40分）得分1、給定命題公式如下：（PQ）（PQ）該命題公式的成真賦值個(gè)數(shù)（）A．0B．1C．2D．32、下面哪個(gè)圖是強(qiáng)連通的（）．3、無向圖中有16條邊，且每個(gè)結(jié)點(diǎn)的度數(shù)均為2，則結(jié)點(diǎn)數(shù)是（）．A．8B．16C．4D．324、設(shè)，以下哪一個(gè)關(guān)系是從到的滿射（）．A． B．C． D．5、給定命題公式：（PQ）（PR），與之等價(jià)的是（）A．P（QR）B．P（QR）C．P（QR）D．P（QR）6、設(shè)，則有（）個(gè)元素。A．3；B．6；C．7；D．87、下列各圖是歐拉圖的是（）．8、，其中，為集合的對(duì)稱差運(yùn)算，則方程的解為（）。A．；B．；C．；D．9、下面四組數(shù)能構(gòu)成無向簡(jiǎn)單圖的度數(shù)列的有（）。A．2,2,2,2,2,2；B．1,2,3,4,5,5；C．1,2,3,4,5,6；D．2,2,3,4,5,610、設(shè)和是集合上的任意兩個(gè)關(guān)系，則下列命題為真的是（）．A．若和是自反的，則也是自反的B．若和是非自反的，則也是非自反的C．若和是對(duì)稱的，則也是對(duì)稱的D．若和是傳遞的，則也是傳遞的11、設(shè)N為自然數(shù)集，：NN，則是()．A．是入射不是滿射 B．既非入射也非滿射C．是滿射不是入射 D．是雙射12、設(shè)為實(shí)數(shù)集，函數(shù)：，，則是（）．A．是入射不是滿射 B．是滿射不是入射C．既非入射也非滿射 D．是雙射13、設(shè)A={1，2，3}，關(guān)系R是A上的二元關(guān)系，且R={<1，2>}，則關(guān)系R所具有的性質(zhì)是（）A．自反性，反對(duì)稱性，可傳遞性B．反自反性，反對(duì)稱性，可傳遞性C．自反性，對(duì)稱性，可傳遞性D．反自反性，反對(duì)稱性14、謂詞演算中，是的有效結(jié)論，其理論依據(jù)是（）．A．全稱指定規(guī)則（US）C．全稱推廣規(guī)則（UG）B．存在指定規(guī)則（ES）D．存在推廣規(guī)則（EG）．15、謂詞公式中量詞（）轄域是（）。A． B．C． D．16、由前提：(x)(P（x）（Q（x）R（x）），(x)(P（x）（R（x）S（x）））,(x)(P（x）S（x））,則它的有效推論為（）A．(x)(P（x）Q（x））B．(x)(P（x）Q（x））C．(x)(P（x）Q（x））D．(x)(P（x）Q（x））17、下圖中既不是歐拉圖，也不是漢密爾頓圖的圖是（）。ABCD18、下列等價(jià)公式正確的是（）。A．；B．；C．；D．．19、設(shè)是集合上的任意函數(shù)，下列哪個(gè)命題是真命題（）．A． B．C． D．20、一個(gè)無向樹中有7條邊，則它結(jié)點(diǎn)數(shù)為()。A.5；B.6；C.7；D.8．二、填空題（20小題，每空1分，共20分）得分1、命題公式?（PQ）的主析取范式為2、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除關(guān)系，則集合={2,3,4,6}的最大元是3、設(shè)有33盞燈，擬公用一個(gè)電源，則至少需要5插頭的接線板的數(shù)目為。4、命題公式?（PQ）的主合取范式為5、設(shè)，上的二元關(guān)系=，則具有___________________性。6、設(shè)圖G=〈V，E〉，V＝｛,,,｝的鄰接矩陣A(G)=，則的入度為。7、無向圖G具有生成樹，當(dāng)且僅當(dāng)___________________。8、設(shè)，則=。其中表示集合Ａ的冪集。9、設(shè)=｛｛，｛｝｝｝，則×=。其中表示集合的冪集．10、無向圖中有10條邊，且每個(gè)結(jié)點(diǎn)的度數(shù)均為4，則結(jié)點(diǎn)數(shù)是．11、設(shè)R是實(shí)數(shù)集合，，，且，則12、設(shè)是集合上的具有自反性、對(duì)稱性、反對(duì)稱性和傳遞性的二元關(guān)系，則=13、對(duì)謂詞公式（（x）P（x）（y）Q（y））（x）R（x）中約束變?cè)獞?yīng)用變換規(guī)則所得到的前束范式是14、設(shè)表示“我將去書店”，表示“我有時(shí)間”，則命題“我將去書店，僅當(dāng)我有時(shí)間”符號(hào)化為。15、設(shè)集合Ａ＝｛ａ，ｂ，ｃ｝上的關(guān)系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，則Ｒ具有______________________________16、設(shè)A為任一集合，則．17、設(shè)是到的函數(shù)，當(dāng)為雙射時(shí)，是到的函數(shù)，=18、設(shè),則的雙射共有．19、設(shè)表示“我將取得好成績”，表示“我努力學(xué)習(xí)”，則命題“我將取得好成績，僅當(dāng)我努力學(xué)習(xí)”符號(hào)化為。20、設(shè)表示“是馬”，表示“是動(dòng)物”．則命題“馬是動(dòng)物，動(dòng)物不一定是馬”符號(hào)化為．三、簡(jiǎn)答題（4小題，每小題6分，共24分）得分1、以給定權(quán)1,4,9,16,25,36,49,64,81,100構(gòu)造一棵最優(yōu)二叉樹。2、對(duì)有向圖求解下列問題：1）寫出鄰接矩陣；2）中由到長度為2和4的路有幾條？3）求出的可達(dá)性矩陣。3、下圖給出的賦權(quán)圖表示七個(gè)城市及架起城市間直接通訊線路的預(yù)測(cè)造價(jià)，試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小，并計(jì)算出最小造價(jià)。4、設(shè)={1,2,3,5,6,10,15,30}，“／”為集合上的整除關(guān)