1A第8頁共9頁一、單選題（20小題，每小題2分，共40分）得分1、設(shè)為整數(shù)集，：，，則是（）．A．是入射不是滿射B．是滿射不是入射C．既非入射也非滿射D．是雙射．2、設(shè)A={1，2，3}上的關(guān)系如下，有傳遞性的有（）。A．{<1，2>，<2，1>，<1，3>，<3，1>}B．{<1,3>，<3,1>}C．{<1，2>，<2,3>，<1，1>}D．{<1,2>，<3，2>}3、設(shè)有向圖，其中，則G是（）。A．強連通圖B．單向連通圖C．弱連通圖D．非連通圖4、取個體域為整數(shù)集，則下列公式中真命題為（）。A．（x）（y）（x×y=0） B．（x）（y）（x×y=1）C． D．（x）（x×y=x）5、下列蘊含式不成立的是（）.A． B．C． D．.6、設(shè)，下列二元關(guān)系為到的函數(shù)的是()A．B．C．D．7、下列各式哪個是錯的（）？A.;B.{};C.;D.{,{}8、N是自然數(shù)集，定義，則f是（）。A．是單射不是滿射 B．是滿射不是單射C．既非單射也非滿射 D．是雙射9、設(shè)G=〈V，E〉為（ｎ，ｍ）連通圖，則要確定Ｇ的一棵生成樹，必刪去Ｇ的邊數(shù)是（）．A．ｎ－ｍ－１；B．ｎ－ｍ＋１；C．ｍ－ｎ＋１；D．ｍ－ｎ－１．10、令:是金屬，：是液體，：可以溶解在中，則命題“任何金屬可以溶解在某種液體中”可符號化為（）．A．B．C．D．11、下列各圖不是歐拉圖的是（）．12、下圖中是哈密爾頓圖的是（）。13、設(shè)圖G有5個結(jié)點，若各結(jié)點的度數(shù)分別為：3,4,6,2,3,則G有（）條邊。A．10；B．20；C．9；D．18．14、n階完全圖結(jié)點v的度數(shù)為（）。A．n；B．n-1；C．n+1；D．2(n-1)15、設(shè)N為自然數(shù)集，：NN，則是()．A．是入射不是滿射 B．既非入射也非滿射C．是滿射不是入射 D．是雙射16、關(guān)系R所具有的關(guān)系矩陣，則關(guān)系R所具有的性質(zhì)是（）A．自反的，對稱的，可傳遞的B．自反的，反對稱的，可傳遞的C．自反的，對稱的D．都不是17、，其中，為集合的對稱差運算，則方程的解為（）。A．；B．；C．；D．18、下列句子是命題的是()．A．再過5000年，地球上就沒水了．B．．C．水開了嗎?D．我正在說謊．19、給定命題公式如下：（PQ）（PQ）該命題公式的成真賦值個數(shù)（）A．0B．1C．2D．320、在下述公式中是重言式為（）A．? B．C． D．P（QR）二、填空題（20小題，每空1分，共20分）得分1、若P，Q為二命題，P→Q真值為0當(dāng)且僅當(dāng)。2、設(shè)A、B、C和D四個人中派兩個人出差，需要滿足下列條件：（1）若A去，則C和D中要去一人；（2）B和C不能都去；（3）C去則D要留下。則有3種派法，分別為。3、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除關(guān)系，則集合={2,3,4,6}的極小元是4、如果有一臺計算機，它有一條加法指令，可計算四個數(shù)的和。現(xiàn)有28個數(shù)需要計算和，它至少要執(zhí)行次這個加法指令。5、。6、完全圖K5的連通分支數(shù)是。7、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除關(guān)系，則集合={2,3,4,6}的下確界是8、設(shè)是到的函數(shù)，如果對，都有，則稱為9、設(shè)圖G=〈V，E〉，V＝｛,,,｝的鄰接矩陣A(G)=，則從到長度為２的路共有條。10、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除關(guān)系，則集合={2,3,4,6}的最大元是11、謂詞公式（F（x,y）R（x,y））R（x,y）是（重言式，矛盾式，可滿足式）12、設(shè)是集合上的具有自反性、對稱性、反對稱性和傳遞性的二元關(guān)系，則=13、寫出下表中所定義的命題聯(lián)結(jié)詞00011011000114、設(shè)A為任一集合，則．15、設(shè)集合Ａ＝｛ａ，ｂ，ｃ｝上的關(guān)系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，ｔ（Ｒ）＝16、設(shè)是到的函數(shù)，當(dāng)為雙射時，是到的函數(shù)，=17、集合的冪集=。18、命題公式的逆反式是。19、若一棵樹有2個結(jié)點度數(shù)為2，一個結(jié)點度數(shù)為3，3個結(jié)點度數(shù)為4，其余是葉結(jié)點，則該樹有個葉結(jié)點。20、設(shè)集合，R和S均為A上的二元關(guān)系，且，則_三、簡答題（4小題，每小題6分，共24分）得分1、今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示．要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用．AABCDEFGHIJKS2222223.554526345312、對下圖所給的偏序集，求下表所列集合的上界，下界，并將結(jié)果填入表中。子集上界下界3、以給定權(quán)1,4,9,16,25,36,49,64,81,100構(gòu)造一棵最優(yōu)二叉樹。4、