天津大學(xué)研究生考試離散數(shù)學(xué)試卷及答案解析

PAGEPAGE2天津理工大學(xué)2007年碩士研究生入學(xué)復(fù)試試題考試科目：離散數(shù)學(xué)共３頁第１頁一、填空題（每空1分，共25分）1．無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是，并且所有結(jié)點(diǎn)的度數(shù)都是。２．設(shè)Z是整數(shù)集，在Z上定義二元運(yùn)算*為a*b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)<Z,*>的幺元是，零元是。3．某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是，其關(guān)系矩陣是。4．一個(gè)格稱為布爾代數(shù)，如果它是______格和______格.設(shè)〈B,∧,∨,′，0，1〉是布爾代數(shù)，對任意的a∈B,有a∨a′=____,a∧a′=______。5．謂詞公式(x)(y)（P(x,y)∨R(y)）→Q(y)，則其約束變元是________，自由變元是________。6．設(shè)G是n個(gè)結(jié)點(diǎn)m條邊的連通平面圖，則當(dāng)n≥3時(shí)必有成立。7．設(shè)命題公式A的真值表為PQR000001010011100101110111A00101100則命題公式A的主析取范式（編碼形式）為。8．一棵有6個(gè)葉結(jié)點(diǎn)的完全二叉樹，有____個(gè)內(nèi)點(diǎn)；而若一棵樹有2個(gè)結(jié)點(diǎn)度數(shù)為2，一個(gè)結(jié)點(diǎn)度數(shù)為3，3個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，則該樹有_____個(gè)葉結(jié)點(diǎn)。9．在一棵根樹中，有且只有一個(gè)結(jié)點(diǎn)的入度為_____，其余所有結(jié)點(diǎn)的入度均為_____。10．設(shè)圖G1=，如果，則稱G2是G1的子圖，如果，則稱G2是G1的生成子圖。11．設(shè)圖G的鄰接矩陣為M=，則G的可達(dá)性矩陣為______.12．在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除關(guān)系，則集合D={2,3,4,6}的極大元是，極小元是，上確界是，下確界是。二、單項(xiàng)選擇題（每小題2分，共20分）1．設(shè)N為自然數(shù)集(含0)，函數(shù)F：N→N×N,F(n)=<n,n+1>是()。(1)．滿射，不是入射；(2)．入射，不是滿射；(3)．雙射；(4)．不是入射，不是滿射．２．設(shè)和是集合Ａ上的任意兩個(gè)關(guān)系，則下列命題為真的是（）．(1)．若和是自反的，則也是自反的；(2)．若和是非自反的，則也是非自反的；天津理工大學(xué)2007年碩士研究生入學(xué)復(fù)試試題考試科目：離散數(shù)學(xué)共３頁第２頁(3)．若和是對稱的，則也是對稱的；(4)．若和是傳遞的，則也是傳遞的．３．下面哪個(gè)偏序集構(gòu)成有界格（）．(1)．；(2)．／，其中／為整除關(guān)系；(3)．；(4)．；其中Ａ＝｛ａ，ｂ，ｃ｝，為Ａ的冪集．４．設(shè)個(gè)體域是正整數(shù)集，則下列公式中真值為真的公式是()．(1)．(x)(y)(x·y=0)(2)．(x)(y)(x·y=1)(3)．(x)(y)(x·y=2)(4)．(x)(y)(z)(x-y=z)．５．設(shè)P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）．(1)．P→┐Q；(2)．P∨┐Q；(3)．P∧Q；(4)．P∧┐Q．６．設(shè)<A,*,>是環(huán)，則下列正確的是（）．(1)．<A,>是交換群；(2)．<A,*>是加法群；(3)．對*是可分配的；(4)．*對是可分配的７．設(shè)G是連通平面圖，G中有6個(gè)頂點(diǎn)8條邊，則G的面的數(shù)目是（）．(1)．2個(gè)面；(2)．4個(gè)面；(3)．3個(gè)面；(4)．5個(gè)面．８．下面哪個(gè)哈斯圖構(gòu)成分配格（）．９．設(shè)完全二叉樹Ｔ有ｔ片葉子。ｅ條邊，則有（）．(1)．ｅ>2(t-1)；(2)．e<2(t-1)；(3)．e=2(t-1)；(4)．e=2(t+1)．10．下列各圖是平面圖的是()．三、簡答題（每小題6分，共30分）1．設(shè)A={a,b,c}，P（A）是A的冪集，是集合對稱差運(yùn)算。已知<P(A),>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使?jié)M足{a}x=。２．設(shè)有6個(gè)城市V1，V2，…，V6，它們之間有輸油管連通，其布置如下圖,Si(數(shù)字)中Si為邊的編號，括號內(nèi)數(shù)字為邊的權(quán)，它是兩城市間的距離，為了保衛(wèi)油管不受破壞，在每段油管間派一連士兵看守，為保證每個(gè)城市石油的正常供應(yīng)最少需多少連士兵看守?天津理工大學(xué)2007年碩士研究生入學(xué)復(fù)試試題考試科目：離散數(shù)學(xué)共３頁第３頁輸油管道總長度越短，士兵越好防守。求他們看守的最短管道的長度。(要求寫出求解過程)３．公安人員審理某珠寶商店的鉆石項(xiàng)鏈的失竊案，已知偵察結(jié)果如下：（1）營業(yè)員A或B盜竊了鉆石項(xiàng)鏈（2）若B作案，則作案時(shí)間不在營業(yè)時(shí)間（3）若A提供的證詞正確，則貨柜未上鎖（4）若A提供的證詞不正確，則作案發(fā)生在營業(yè)時(shí)間（5）貨柜上了鎖試問：作案者是誰？要求寫出推理過程。４．設(shè)Ａ={1,2,4,6,8,12,18,72},”/”為A上的整除關(guān)系,(1)．說明〈Ａ，／〉是否為偏序集，若是，畫出其哈斯圖；(2)．說明〈Ａ，／〉是否為格？為什么？(3)．說明〈Ａ，／〉是否構(gòu)成布爾代數(shù)？為什么？５．求命題公式((P∨Q)→R)→P的主析取范式和主合取范式。四．證明題（共25分）１．（8分）設(shè)Q是有理數(shù)集，在Q×Q定義運(yùn)算＊為〈ａ,b〉＊〈ｘ,y〉=〈ax,ay+b〉，(1)．證明〈Q×Q,＊〉是獨(dú)異點(diǎn)；(2)．Q×Q中元素〈ａ,b〉是否有逆元，若有，求出〈ａ,b〉的逆元．２．（6分）證明當(dāng)每個(gè)結(jié)點(diǎn)的度數(shù)大于等于3時(shí)，不存在有7條邊的連通簡單平面圖。（6分）符號化下列命題并推證其結(jié)論．任何