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

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