1離散結(jié)構(gòu)2007A一、填空（每空2分，共30分）1、設(shè)P224，Q3是奇數(shù)將命題“224，當(dāng)且僅當(dāng)3是奇數(shù)”符號化_1_，其真值為_2_。2、在公式中，自由出現(xiàn)的變元為_3_。,YXF3、若關(guān)系R具有自反性，當(dāng)且僅當(dāng)在關(guān)系矩陣中，主對角上元素_4_，若關(guān)系R具有對稱性，當(dāng)且僅當(dāng)關(guān)系矩陣是_5_。4、若關(guān)系，則關(guān)系一定具有_6_性。15、有向圖的連通性可分為弱連通、強連通、_7_。6、前綴表達式2/843的值是_8_。7、設(shè)G是完全二元樹，G有15個頂點，其中有8個葉子，則G有_9_條邊，G的總度數(shù)是_10_。8、十進制3位數(shù)的數(shù)字中恰好有一個8和一個9，共有_11_個這樣的3位數(shù)。9、設(shè)集合，上的運算定義為,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDACE則代數(shù)系統(tǒng)中單位元是_12_，的左逆元是_13_，無左逆元的元素是_14_。,SB10、設(shè)是由元素生成的循環(huán)群，且的階為4，則集合_15_。SASS二、選擇題（每題2分，共30分）1、下列語句中，_是命題。A、地球上的人真多B、把門關(guān)上2C、下午有會嗎D、65X2、一個公式在等價意義下，下面哪個寫法是唯一的_。A、析取范式B、合取范式C、主析取范式D、以上都不唯一3、設(shè)命題公式，則G是_。QPGA、永真式B、矛盾式C、可滿足式D、以上都不是4、設(shè)I是如下一個解釋，其中，為真，為假，則在,BAD,AP,B,BAP,解釋I下取真值的公式是_A、B、C、D、,YXP,YX,X,YX5、下列哪個表達式錯誤_。A、QPB、XXQXPC、D、6、設(shè)R，S是集合上的兩個關(guān)系，其中，4,321A4,3,2,1,R，則S是R的_閉包。4,1A、自反B、反對稱C、對稱D、傳遞7、設(shè)R和S是非空集合A上的等價關(guān)系，下列各式是A上等價關(guān)系的是_。A、B、C、D、的對稱閉包SRSRSR8、設(shè)偏序集（）關(guān)系R的哈斯圖如右所示，若A的子集，則元素6為B的,5,432B_。A、下界B、上界C、最小上界D、以上都不對9、以下整數(shù)序列，能成為一個簡單圖的頂點度數(shù)序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、1，1，1，2，3D、2，3，3，4，5，610、設(shè)圖G是有6個頂點的連通圖，總度數(shù)為20，則從G中至少刪去_條邊后使之成為樹。A、10B、5C、3D、2311、在下列關(guān)于圖論的命題中，正確的是_。A、哈密頓圖一定是歐拉圖B、無向完全圖都是歐拉圖3NKC、度數(shù)為奇數(shù)的頂點個數(shù)為0個或2個的連通無向圖可一筆畫出D、哈密頓圖是平面圖12、下面編碼_不是前綴碼。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、5階非同構(gòu)的無向樹有_棵。A、1B、2C、3D、414、由0、1、2、3這四個數(shù)字能構(gòu)成_個3位數(shù)A、64B、48C、24D、1815、在下列選項中，不是群的是_。A、，為有理數(shù)，為加法運算,QB、，為非零實數(shù)集，為乘法運算RC、全體實對稱矩陣集合，對于矩陣的加法運算D、，為有理數(shù)，為乘法運算,三、計算題（5分5分8分，共18分）1、設(shè)有5個城市，任意兩城市之間的鐵路造價如下54321,V，,2VW716,4W10,5V13,2VW，84,523354試求出連接5個城市的且造價最低的鐵路網(wǎng)2、構(gòu)造前序遍歷為A，B，F(xiàn)，C，G，H，I，D，E，J，K，P的有序樹，其中A有4個子結(jié)點，C有3個子結(jié)點，J有2個子結(jié)點，B和E都有一個子結(jié)點，所有其它結(jié)點都是樹葉。34、設(shè)集合，A上的關(guān)于等價關(guān)系R的商集，試求5,431A/5,432,1（1）等價關(guān)系R4（2）寫出關(guān)系矩陣RM（3）畫出關(guān)系圖（4）寫出R的傳遞閉包四、證明題（5分5分6分，共16分）1、設(shè)R是A上的等價關(guān)系，S是B上的等價關(guān)系，且A和B非空，關(guān)系T滿足且，證明T是上的等價關(guān)系。TBYAX,RYX,SBA,BA2、設(shè)G為N階無向簡單圖，證明若G為自補圖（若一個圖的補圖為本身則稱為自補圖），則或，其中K為正整數(shù)。K413、若是群，定義G中的運算“”為，對,UBUA1GA,證明為群。G五、應(yīng)用題（6分）的意義如下P張群是大學(xué)生，Q張群心情愉快，R張群唱歌RQP,試用日常語言說明下列復(fù)合命題12RQP32007B一、填空（每空2分，共30分）1、表達式中謂詞的個體域是，將其中的量詞消去，寫成與之等價的命題XGXFC,BA公式為_1_。2、設(shè)R是集合A上的二元關(guān)系，如果關(guān)系R同時具有_2_、_3_和傳遞，則稱R是A上的偏序關(guān)系。3、已知集合上的二元關(guān)系，5,43212,4,32,1，則_4_，_5_。,1,4SS4、若有限集關(guān)系具有自反性，則其對應(yīng)的關(guān)系矩陣主對角元素全為_6_。AR55、若某個簡單圖不是歐拉圖但具有歐拉通路，則圖中頂點度數(shù)為奇數(shù)的頂點個數(shù)一定為_7_。6、設(shè)是圖，如果G是_8_并且_9_則G是樹。EVG,7、一個無向圖的歐拉回路要求經(jīng)過圖中_10_一次且僅一次，哈密頓回路要求經(jīng)過圖中_11_一次且僅一次。8、樹是平面圖，它有_12_個面。9、在群、半群、獨異點中，_13_滿足消去律。10、設(shè)Q為有理數(shù)集，笛卡爾積，是S上的二元運算，有QSSYXBA,，則運算的單位元為_14_，（），則BYAXBA,0的逆元為_15_。二、選擇題（每題2分，共30分）1、下列語句中_是命題。A、把門關(guān)上B、地球外的星球上也有人C、65XD、下午有會嗎2、已知命題，則所有使G取真值的解釋是_。RQPGA、000，001，100B、100，101，110C、010，101，001D、001，101，1113、命題公式A和B是等價的是指A、A和B由相同的原子變元B、A和B都是可滿足的C、當(dāng)A的真值為真時，B的真值也為真D、A和B有相同的真值4、對、而言，下列是極小項的是_。PQRA、B、QPC、D、R5、設(shè)集合，R、S、T都是A上的關(guān)系，3,213,1,2,，則T_。,S312,A、B、C、D、RS66、若T為樹，以下敘述不正確的是_。A、T是連通的且不含回路B、T的每對頂點之間有唯一的一條路徑C、T是連通的且每條邊都是割邊D、T是連通的且每個點都是割點7、設(shè)集合為，下列關(guān)系R中不是等價關(guān)系的是_。3,21AA、,RB、3,2,C、12,11D、3,2,3,8、設(shè)集合，A上的關(guān)系，則R不具備322R_。A、自反性B、傳遞性C、對稱性D、反對稱性9、設(shè)T是由N個頂點的完全二元樹，則T的葉子數(shù)為_。A、B、C、D、112N2/1N3/2N10、設(shè)無向圖G有12條邊，已知G中3度頂點有6個，其余頂點度數(shù)均小于3，則G中頂點數(shù)最多有_。A、6B、8C、9D、1211、設(shè)I是如下一個解釋，其中，為真，為假，則,BAD,AP,B,BAP,在解釋I下取真值的公式是_。A、B、C、D、,YXP,YX,X,YXP12、設(shè)R和S是非空集合A上的等價關(guān)系，下列各式是A上等價關(guān)系的是_。A、B、C、D、的對稱閉包SRSRSR13、下面編碼_不是前綴碼。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010114、由0、1、2、3這四個數(shù)字能構(gòu)成_個3位數(shù)A、64B、48C、24D、18715、在下列選項中，不是群的是_。A、，為有理數(shù)，為加法運算,QB、，為非零實數(shù)集，為乘法運算RC、全體實對稱矩陣集合，對于矩陣的加法運算D、，為有理數(shù)，為乘法運算,三、計算題（5分5分8分，共18分）1、已知有向圖，E，EV,5,43213,24,12,，求有向圖D的鄰接矩陣和可達矩陣。15,3,42、求葉的權(quán)值分別為2，4，6，8，10，12，14的最優(yōu)二元樹及其權(quán)值。3、試畫出集合，在偏序關(guān)系整除下的哈斯圖，并分別求出,53,1A1集合的最大元，最小元，極大元，極小元；2集合的上界，下界，最小上界，最小下界。6,2B四、證明題（5分5分6分，共16分）1、證明利用命題演繹法證明RSQPSRQP2、設(shè)R和S是A上的二元關(guān)系，證明11S3、證明設(shè)是一個代數(shù)系統(tǒng)，是上的二元運算，則,R,RBABA0是單位元，且是含幺半群。（為實數(shù)集合）。五、應(yīng)用題（共6分）的意義如下P張群是大學(xué)生，Q張群心情愉快，R張群唱歌RQP,試用日常語言說明下列復(fù)合命題（1）（2）RQP8（3）RQP2008AV11一、填空（每空2分，共30分）1、設(shè)P112，Q2是偶數(shù)，將命題“112，僅當(dāng)2是偶數(shù)”符號化1_，其真值為2_。2、在公式中，約束出現(xiàn)的變元為3_。,YXGZFX3、給定集合上的3個關(guān)系如下,21A，1,1R1,3,1,23,2,2R，,2,3,3,23則其中滿足對稱性的關(guān)系是4_；滿足自反性的關(guān)系是5_。4、非空集合A上的自反、6_和傳遞的關(guān)系稱為A上的偏序關(guān)系。5、后綴表達式35274/的值是7_。6、設(shè)無向圖G有11條邊，2，3，4，5，6度頂點各1個，其余頂點均為懸掛頂點即1度頂點，則G中有8_個懸掛頂點。7、設(shè)G為連通的平面圖，有5個面，總度數(shù)為14，則G有9_條邊，有10_個頂點。8、已知一棵無向樹T中有4度、3度和2度分支點各1個，其余頂點均為樹葉，則T有11_個樹葉。9、設(shè)集合，上的運算定義為,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDBCE則代數(shù)系統(tǒng)中單位元是12_，的右逆元是13_，無右逆元的元素是14,S_。910、設(shè)運算的運算表如下所示，則運算滿足交換律、冪等律、結(jié)合律中的15_。ABCACABBABCCBCA二、選擇題（每題2分，共30分）1、下面語句是真命題的為_。A、我正在說謊。B、如果112，則太陽從西邊升起來。C、如果113，則太陽從西邊升起來。D、吃飯了嗎2、命題公式PQP為_。A、重言式B、可滿足式C、矛盾式D、等值式3、下面聯(lián)結(jié)詞不具有交換律的是_。A、B、C、D、4、設(shè)I是如下一個解釋，其中，為真，為假，則在,BAD,AP,B,BAP,解釋I下取真值的公式是_A、B、C、D、,YXP,YX,X,YX5、下列哪個表達式錯誤_。A、QPB、XXQXPC、D、6、設(shè)集合上的兩個關(guān)系，則R具有_。4,321A4,3,23,1,RA、自反性B、傳遞性C、對稱性D、反自反性7、下述結(jié)論錯誤的是_。A、存在這樣的關(guān)系，它可以既滿足對稱性，又滿足反對稱性。B、存在這樣的關(guān)系，它可以既不滿足對稱性，又不滿足反對稱性。10C、存在這樣的關(guān)系，它可以既滿足自反性，又滿足反自反性。D、存在這樣的關(guān)系，它可以既不滿足自反性，又不滿足反自反性。8、設(shè)偏序集（）關(guān)系R的哈斯圖如右所示，若A的子集，則元素6為B的,A5,432B_。A、下界B、上界C、最小上界D、以上都不對9、以下整數(shù)序列，能成為一個簡單圖的頂點度數(shù)序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、2，2，3，4，5，6D、1，2，2，3，3，510、設(shè)圖G是有6個頂點的連通圖，總度數(shù)為16，則從G中刪去_條邊后可以使之成為樹。A、10B、5C、3D、211、在下列關(guān)于圖論的命題中，正確的是_。A、哈密頓圖一定是歐拉圖B、無向完全圖都是歐拉圖3NKC、度數(shù)為奇數(shù)的頂點個數(shù)為0個或2個的連通無向圖可一筆畫出D、哈密頓圖是平面圖12、下面編碼_不是前綴碼。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、6階非同構(gòu)的無向樹有_棵。A、5B、6C、7D、814、實數(shù)集R關(guān)于下列二元運算滿足結(jié)合律和交換律的是_。A、B、C、D、BA2BAABA2|BA15、在下列選項中，不是群的是_。A、，為有理數(shù)，為加法運算,QB、，為非零實數(shù)集，為乘法運算R11C、，為實數(shù)集，為加法運算,RD、，為有理數(shù)，為乘法運算Q三、計算題（5分6分8分，共19分）1、求下圖中的最小生成樹，并計算它的權(quán)。V1V2V6V3V5V41352467892、設(shè)有7個字母在通信中出現(xiàn)的頻率如下A35B20,C15,D10,E10,F5,G51以頻率或乘100為權(quán)，求最優(yōu)2元樹2利用所求最優(yōu)2元樹找出每個字母的前綴碼3求傳輸10000個按上述比例出現(xiàn)的字母需要多少個二進制數(shù)字若用等長的長為3的碼字傳輸需要多少個二進制數(shù)字節(jié)約多少個二進制位3、設(shè)集合，X上的關(guān)系R如圖所示，試求,DCBAABCD（1）寫出關(guān)系R的關(guān)系矩陣RM（2）求關(guān)系R的自反閉包RR的關(guān)系矩陣,RRXIR0（3）求關(guān)系R的對稱閉包SR的關(guān)系矩陣,S1（4）求關(guān)系R的傳遞閉包TR的關(guān)系矩陣,RT432四、證明題（5分5分5分，共15分）1、設(shè),在A上定義二元關(guān)系R如下Z，證明R是A上的等價關(guān)系。ZVUYXXVVUYX,其中122、設(shè)N階M條邊的無向圖G中，MN1，證明G中存在頂點VDV3。3、設(shè)G為群，令，證明H是G的子群。A|ZKA五、應(yīng)用題（共6分）1如果王小紅努力學(xué)習(xí)，她一定取得好成績。若王小紅貪玩或不按時完成作業(yè)，她就不能取得好成績。所以，如果王小紅努力學(xué)習(xí)，她就能按時完成作業(yè)。1將命題中的4個簡單命題依次符號化為P,Q,R,S；2將命題符號化，即將命題的前提和結(jié)論符號化；3在自然推理系統(tǒng)P中構(gòu)造命題的推理證明。20082A一、填空（每空2分，共30分）1、設(shè)P張曉拿一個蘋果，Q張曉拿一個梨，將命題“張曉只能拿一個蘋果或拿一個梨”符號化1_。2、設(shè)PXX是偶數(shù)，QXX是奇數(shù)，在實數(shù)R個體域中將命題“存在偶數(shù)，也存在奇數(shù)”符號化2_，其真值為3_。3、非空集合A上的自反、對稱和4_的關(guān)系稱為A上的等價關(guān)系。4、給定集合上的3個關(guān)系如下,21，1,1R3,2,1,2R，23323則其中滿足自反性的關(guān)系是5_；滿足對稱性的關(guān)系是6_；滿足傳遞性的關(guān)系是7_。5、關(guān)系，3,2,4,12,R，則RS3S8_。6、波蘭符號表達式45/821的值是9_。7、設(shè)無向圖G有11條邊，2，3，4，5，6度頂點各1個，其余頂點均為懸掛頂點即1度頂點，則G中13有10_個懸掛頂點。8、設(shè)G為連通的平面圖，有5個面，總度數(shù)為16，則G有11_條邊，有12_個頂點。9、已知一棵無向樹T中有4度、3度和2度分支點各1個，其余頂點均為樹葉，則T有13_個樹葉。10、設(shè)是無向圖，如果G是14_并且15_則G是樹。EV,二、選擇題（每題2分，共30分）1、下面語句是命題的為_。A、我正在說謊。B、把門關(guān)上。C、地球外的星球上也存在生命。D、吃飯了嗎2、命題公式PQPQP為_。A、重言式B、非重言式的可滿足式C、矛盾式D、等值式3、下列集合不是連接詞完備集的為_。A、,B、,C、,D、4、下列謂詞公式不是命題公式PQ的代換實例的是_A、B、C、D、YGXF,YXGYXFXGFX5、下列哪個表達式錯誤_。A、XPXB、QXPC、QD、XX6、下列哪個表達式錯誤_。A、BAXB、XC、D、X147、設(shè)集合上的兩個關(guān)系，則R具有_。4,321A3,2,4,1,RA、對稱性B、傳遞性C、自反性D、反自反性8、下述結(jié)論錯誤的是_。A、存在這樣的關(guān)系，它可以既滿足對稱性，又滿足反對稱性。B、存在這樣的關(guān)系，它可以既不滿足對稱性，又不滿足反對稱性。C、存在這樣的關(guān)系，它可以既滿足自反性，又滿足反自反性。D、存在這樣的關(guān)系，它可以既不滿足自反性，又不滿足反自反性。9、下面關(guān)于對稱關(guān)系的描述錯誤的是_。A、對稱關(guān)系與其逆關(guān)系相等B、對稱關(guān)系的矩陣與其逆矩陣相等C、對稱關(guān)系的矩陣與其轉(zhuǎn)置矩陣相等D、對稱關(guān)系的關(guān)系圖中任何兩個頂點之間如果有邊必是一對方向相反的邊10、以下無向圖中，不是二部圖的是_。A、B、C、D、11、在下列關(guān)于圖論的命題中，正確的是_。A、哈密頓圖一定是歐拉圖B、無向完全圖都是歐拉圖3NKC、度數(shù)為奇數(shù)的頂點個數(shù)為0個或2個的連通無向圖可一筆畫出D、哈密頓圖是平面圖12、以下無向圖中，不是平面圖的是_。A、B、C、D、1513、下面編碼_不是前綴碼。A、11，00，10，01B、01，11，001，1001C、101，11，001，011，010D、010，11，011，1011，1001，1110114、5階非同構(gòu)的無向樹有_棵。A、3B、4C、5D、615、在下列選項中，關(guān)于N階樹N1的性質(zhì)描述不正確的是_。A、在連通N階圖中，N階樹的邊的數(shù)量最少B、在N階無回路圖中，N階樹的邊的數(shù)量最多C、N階樹不一定是平面圖D、N階樹N1至少有兩片樹葉三、計算題（5分8分，共13分）1、如下圖所示的賦權(quán)圖表示某七個城市，及預(yù)先算出它們之間直接通信線路造價，試給721,V出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小，并計算出最小造價。V1V2V3V4V5V6135246789V7102、設(shè)集合，X上的關(guān)系R如圖所示，試求,DCBAABCD（1）寫出關(guān)系R的關(guān)系矩陣；RM（2）畫出關(guān)系R的自反閉包RR的關(guān)系圖；（3）畫出關(guān)系R的對稱閉包SR的關(guān)系圖；16（4）畫出關(guān)系R的傳遞閉包TR的關(guān)系圖。四、證明題（6分，共6分）1、設(shè)T是N階非平凡的無向樹，證明T至少有兩片樹葉。五、應(yīng)用題（9分6分6分，共21分）1、給出集合，分別求出6,5432,1A1畫出集合的整除偏序關(guān)系的哈斯圖；2集合的最大元，最小元，極大元，極小元；3集合的上界，下界，最小上界，最小下界。,B2、某研究機構(gòu)要從A,B,C三人中選派若干人出國考察,由于工作需要必須滿足下述條件若A去，則C必須去；若B去，則C不能去；若C不去，則A或B可以去。請按以下三個步驟篩選可能的選派方案1符號化命題；2求命題的主析取范式；3列出可行的選派方案。3、請在自然推理系統(tǒng)P中構(gòu)造下面的證明如果數(shù)A是實數(shù)，則它不是有理數(shù)就是無理數(shù)；若A不能表示成分數(shù)，則它不是有理數(shù)；A是實數(shù)且它不能表示成分數(shù)，因此A是無理數(shù)。1將命題中的4個簡單命題依次符號化為P,Q,R,S；2將命題符號化，即將命題的前提與結(jié)論符號化；3在自然推理系統(tǒng)P中構(gòu)造命題的推理證明。20082B一、填空（每空2分，共30分）1、設(shè)P112，Q2是偶數(shù)，將命題“112，僅當(dāng)2是偶數(shù)”符號化1_，其真值為2_。172、在公式中，約束出現(xiàn)的變元為3_。,YXGZFX3、給定集合上的3個關(guān)系如下,21A，1,1R1,3,1,23,2,2R，,2,3,3,23則其中滿足對稱性的關(guān)系是4_；滿足自反性的關(guān)系是5_。4、非空集合A上的自反、6_和傳遞的關(guān)系稱為A上的偏序關(guān)系。5、后綴表達式35274/的值是7_。6、設(shè)無向圖G有11條邊，2，3，4，5，6度頂點各1個，其余頂點均為懸掛頂點即1度頂點，則G中有8_個懸掛頂點。7、設(shè)G為連通的平面圖，有5個面，總度數(shù)為14，則G有9_條邊，有10_個頂點。8、已知一棵無向樹T中有4度、3度和2度分支點各1個，其余頂點均為樹葉，則T有11_個樹葉。9、設(shè)集合，上的運算定義為,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDBCE則代數(shù)系統(tǒng)中單位元是12_，的右逆元是13_，無右逆元的元素是14,S_。10、設(shè)運算的運算表如下所示，則運算滿足交換律、冪等律、結(jié)合律中的15_。ABCACABBABCCBCA18二、選擇題（每題2分，共30分）1、下面語句是真命題的為_。A、我正在說謊。B、如果112，則太陽從西邊升起來。C、如果113，則太陽從西邊升起來。D、吃飯了嗎2、命題公式PQP為_。A、重言式B、可滿足式C、矛盾式D、等值式3、下面聯(lián)結(jié)詞不具有交換律的是_。A、B、C、D、4、設(shè)I是如下一個解釋，其中，為真，為假，則在,BAD,AP,B,BAP,解釋I下取真值的公式是_A、B、C、D、,YXP,YX,X,YX5、下列哪個表達式錯誤_。A、QPB、XXQXPC、D、6、設(shè)集合上的兩個關(guān)系，則R具有_。4,321A4,3,23,1,RA、自反性B、傳遞性C、對稱性D、反自反性7、下述結(jié)論錯誤的是_。A、存在這樣的關(guān)系，它可以既滿足對稱性，又滿足反對稱性。B、存在這樣的關(guān)系，它可以既不滿足對稱性，又不滿足反對稱性。C、存在這樣的關(guān)系，它可以既滿足自反性，又滿足反自反性。D、存在這樣的關(guān)系，它可以既不滿足自反性，又不滿足反自反性。8、設(shè)偏序集（）關(guān)系R的哈斯圖如右所示，若A的子集，則元素6為B的,A5,432B_。19A、下界B、上界C、最小上界D、以上都不對9、以下整數(shù)序列，能成為一個簡單圖的頂點度數(shù)序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、2，2，3，4，5，6D、1，2，2，3，3，510、設(shè)圖G是有6個頂點的連通圖，總度數(shù)為16，則從G中刪去_條邊后可以使之成為樹。A、10B、5C、3D、211、在下列關(guān)于圖論的命題中，正確的是_。A、哈密頓圖一定是歐拉圖B、無向完全圖都是歐拉圖3NKC、度數(shù)為奇數(shù)的頂點個數(shù)為0個或2個的連通無向圖可一筆畫出D、哈密頓圖是平面圖12、下面編碼_不是前綴碼。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、6階非同構(gòu)的無向樹有_棵。A、5B、6C、7D、814、實數(shù)集R關(guān)于下列二元運算滿足結(jié)合律和交換律的是_。A、B、C、D、BA2BAABA2|BA15、在下列選項中，不是群的是_。A、，為有理數(shù)，為加法運算,QB、，為非零實數(shù)集，為乘法運算RC、，為實數(shù)集，為加法運算,D、，為有理數(shù)，為乘法運算三、計算題（5分6分8分，共19分）1、求下圖中的最小生成樹，并計算它的權(quán)。20V1V2V6V3V5V41352467892、設(shè)有7個字母在通信中出現(xiàn)的頻率如下A35B20,C15,D10,E10,F5,G51以頻率或乘100為權(quán)，求最優(yōu)2元樹2利用所求最優(yōu)2元樹找出每個字母的前綴碼3求傳輸10000個按上述比例出現(xiàn)的字母需要多少個二進制數(shù)字若用等長的長為3的碼字傳輸需要多少個二進制數(shù)字節(jié)約多少個二進制位3、設(shè)集合，X上的關(guān)系R如圖所示，試求,DCBAABCD（1）寫出關(guān)系R的關(guān)系矩陣RM（2）求關(guān)系R的自反閉包RR的關(guān)系矩陣,RRXIR0（3）求關(guān)系R的對稱閉包SR的關(guān)系矩陣,S1（4）求關(guān)系R的傳遞閉包TR的關(guān)系矩陣,RT432四、證明題（5分5分5分，共15分）1、設(shè),在A上定義二元關(guān)系R如下Z，證明R是A上的等價關(guān)系。ZVUYXXVVUYX,其中2、設(shè)N階M條邊的無向圖G中，MN1，證明G中存在頂點VDV3。3、設(shè)G為群，令，證明H是G的子群。A|ZKA21五、應(yīng)用題（共6分）1如果王小紅努力學(xué)習(xí)，她一定取得好成績。若王小紅貪玩或不按時完成作業(yè)，她就不能取得好成績。所以，如果王小紅努力學(xué)習(xí)，她就能按時完成作業(yè)。1將命題中的4個簡單命題依次符號化為P,Q,R,S；2將命題符號化，即將命題的前提和結(jié)論符號化；3在自然推理系統(tǒng)P中構(gòu)造命題的推理證明。20092A一、判斷題（本大題共10小題，每小題1分，共10分）1、“如果天氣好，那么我去散步”是命題。2、“我正在說謊話”是命題。3、既是合取范式也是析取范式。QP4、是前束范式。XGXF5、A，B，C都是集合，如果ABAC，則BC。6、和是集合A上的具有自反性的關(guān)系，則也一定具有自反性。1R221R7、頂點數(shù)目相同，邊數(shù)也相同的兩個無向圖一定同構(gòu)。8、每個頂點的度數(shù)都是偶數(shù)的無向圖一定是歐拉圖。9、五階完全圖既是歐拉圖，也是哈密頓圖。5K10、設(shè)無向圖T是樹，則T中一定沒有簡單回路。二、選擇題（本大題共15小題，每小題2分，共30分）1、下面語句是簡單命題的為_。A、3不是偶數(shù)。B、李平既聰明又用功。C、李平學(xué)過英語或日語。D、李平和張三是同學(xué)。2、下列命題公式中是矛盾式的有_。得分15CM22A、B、PPPQC、D、QR3、下列集合不是連接詞極小全功能集的為_。A、,B、,C、D、4、下列謂詞公式不是命題公式PQ的代換實例的是_A、B、YGXF,YXGYXFC、D、X5、設(shè)個體域為整數(shù)集，下列公式中其值為1的是_。A、0YXB、0YXC、D、6、下列哪個表達式錯誤_。A、BXAXB、C、D、XX7、設(shè)集合A1,2,3,4,5,6,7,8，則下列各式為真的是_。A、1AB、4,5AC、1,2,3AD、A8、設(shè)集合，集合，則_。12,0864,18,529,63BA、B、C、D、5328,5049,69、設(shè)集合上的兩個關(guān)系，則R具有_。4,14,3,23,1,RA、對稱性B、傳遞性C、自反性D、反自反性10、下述結(jié)論錯誤的是_。A、存在這樣的關(guān)系，它可以既滿足對稱性，又滿足反對稱性。B、存在這樣的關(guān)系，它可以既不滿足對稱性，又不滿足反對稱性。C、存在這樣的關(guān)系，它可以既滿足自反性，又滿足反自反性。23D、存在這樣的關(guān)系，它可以既不滿足自反性，又不滿足反自反性。11、集合A上的關(guān)系R為一個等價關(guān)系，當(dāng)且僅當(dāng)R具有_。A、自反性、對稱性和傳遞性B、自反性、反對稱性和傳遞性C、反自反性、對稱性和傳遞性D、反自反性、反對稱性和傳遞性12、以下整數(shù)序列，能成為一個簡單圖的頂點度數(shù)序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、2，2，3，4，5，6D、1，2，2，3，3，513、設(shè)無向圖G的關(guān)聯(lián)矩陣為，則G的頂點數(shù)與邊數(shù)分別為_。021A4,5B4,10C5,4D5,1014、以下無向圖中，不是二部圖的是_。A、B、C、D、15、設(shè)G是由5個頂點組成的無向完全圖，則從G中刪去_條邊可以得到樹。A、4B、5C、6D、10三、填空題（本大題共10小題，每小題2分，共20分）1、設(shè)P天冷，Q小王穿羽絨服，將命題“除非天冷，小王才穿羽絨服”符號化1_。2、命題公式的對偶式是2_。RQP得分15CM243、PQ的主合取范式是3_。4、設(shè)GXX愛美，F(xiàn)XX為人，在全總個體域中將命題“人都愛美”符號化4_。5、設(shè)FXX是兔子，GYY是烏龜，HX,YX比Y跑得快，在全總個體域中將命題“有的兔子比所有的烏龜跑得快”符號化5_。6、設(shè)集合，集合，則6_。12,086A12,963BAB7、設(shè)集合，則7_。AAP8、設(shè)集合A1,2,3,4，R,和S,是集合A上關(guān)系，則RS8_。9、設(shè)無向圖G有12條邊，2，3，4，5，6度頂點各1個，其余頂點均為懸掛頂點即1度頂點，則G中有9_個懸掛頂點。10、寫出波蘭符號表達式ABCDEFG對應(yīng)的算術(shù)表達式10_。四、計算題（本大題共2小題，每小題6分，共12分）1、求1到1000之間的整數(shù)（包含1和1000在內(nèi)）既不能被6和7整除，也不能被8整除的數(shù)有多少個2、有向圖D如圖41所示，試求1寫出有向圖D鄰接矩陣A；2判斷有向圖D的連通性。V1V2V3V4圖41得分15CM25五、應(yīng)用題（本大題共2小題，每小題8分，共16分）1、給出集合，分別求出12,09,8765,4321A1畫出集合的整除偏序關(guān)系的哈斯圖；2集合的最大元，最小元，極大元，極小元；3集合的上界，下界，最小上界，最大下界。,B2、設(shè)集合，X上的關(guān)系R如圖51所示，試求,EDCBAXABCDE圖51（1）寫出關(guān)系R的關(guān)系矩陣；RM（2）畫出關(guān)系R的自反閉包RR的關(guān)系圖；（3）畫出關(guān)系R的對稱閉包SR的關(guān)系圖；（4）畫出關(guān)系R的傳遞閉包TR的關(guān)系圖。六、證明題（本大題共2小題，每小題6分，共12分）1、公安人員審查一件盜竊案，已知的事實如下甲或乙盜竊了錄音機；若甲盜竊了錄音機，則作案時間不能發(fā)生在午夜前；若乙的證詞正確，則午夜時屋里燈光未滅；若乙的證詞不正確，則作案時間發(fā)生在午夜之前；午夜時屋里燈光滅了。試問誰盜竊了錄音機將命題符號化，即將命題的前提符號化；然后在自然推理系統(tǒng)中構(gòu)造命題的推理證明過程。2、求下列謂詞公式的前束范式，要求使用自由變項換名規(guī)則，請寫出推理過程,ZYXHZYXGFX得分得分15CM15CM2620092B一、判斷題（本大題共10小題，每小題1分，共10分）1、奇數(shù)階完全圖一定是歐拉圖。012NK2、二階以上連通沒有回路的無向圖是二部圖。3、“如果天氣好，那么我去散步”是命題。4、“我正在說謊話”是命題。5、既是合取范式也是析取范式。QP6、是前束范式。XGXF7、A，B，C都是集合，如果ABAC，則BC。8、和是集合A上的具有自反性的關(guān)系，則也一定具有自反性。1R221R9、頂點數(shù)目相同，邊數(shù)也相同的兩個無向圖一定同構(gòu)。10、每個頂點的度數(shù)都是偶數(shù)的無向圖一定是歐拉圖。二、選擇題（本大題共15小題，每小題2分，共30分）1、下面語句是真命題的為_。A、我正在說謊。B、如果112，則太陽從西邊升起來。C、如果113，則太陽從西邊升起來。D、吃飯了嗎2、命題公式PQP為_。A、重言式B、可滿足式C、矛盾式D、等值式3、下面聯(lián)結(jié)詞不具有交換律的是_。A、B、C、D、4、設(shè)I是如下一個解釋，其中，為真，為假，則在,BAD,AP,B,BAP,解釋I下取真值的公式是_得分15CM27A、B、C、D、,YXP,YXP,XP,YXP5、下列哪個表達式錯誤_。A、QPB、XXQXPC、D、6、設(shè)集合上的兩個關(guān)系，則R具有_。4,321A4,3,23,1,RA、自反性B、傳遞性C、對稱性D、反自反性7、下述結(jié)論錯誤的是_。A、存在這樣的關(guān)系，它可以既滿足對稱性，又滿足反對稱性。B、存在這樣的關(guān)系，它可以既不滿足對稱性，又不滿足反對稱性。C、存在這樣的關(guān)系，它可以既滿足自反性，又滿足反自反性。D、存在這樣的關(guān)系，它可以既不滿足自反性，又不滿足反自反性。8、設(shè)偏序集（）關(guān)系R的哈斯圖如右所示，若A的子集，則元素6為B的,A5,432B_。A、下界B、上界C、最小上界D、以上都不對9、以下整數(shù)序列，能成為一個簡單圖的頂點度數(shù)序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、2，2，3，4，5，6D、1，2，2，3，3，510、設(shè)圖G是有6個頂點的連通圖，總度數(shù)為16，則從G中刪去_條邊后可以使之成為樹。A、10B、5C、3D、211、在下列關(guān)于圖論的命題中，正確的是_。A、哈密頓圖一定是歐拉圖B、無向完全圖都是歐拉圖3NKC、度數(shù)為奇數(shù)的頂點個數(shù)為0個或2個的連通無向圖可一筆畫出D、哈密頓圖是平面圖12、下面編碼_不是前綴碼。28A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、6階非同構(gòu)的無向樹有_棵。A、5B、6C、7D、814、實數(shù)集R關(guān)于下列二元運算滿足結(jié)合律和交換律的是_。A、B、C、D、BA2BAABA2|BA15、在下列選項中，不是群的是_。A、，為有理數(shù)，為加法運算,QB、，為非零實數(shù)集，為乘法運算RC、，為實數(shù)集，為加法運算,D、，為有理數(shù)，為乘法運算三、填空題（本大題共10小題，每小題2分，共20分）1、設(shè)P112，Q2是偶數(shù)，將命題“112，僅當(dāng)2是偶數(shù)”符號化1_。2、在公式中，約束出現(xiàn)的變元為2_。,YXGZFX3、給定集合上的3個關(guān)系如下,1A，1,22,1R1,3,1,23,2,2R，,3則其中滿足對稱性的關(guān)系是3_；4、非空集合A上的自反、4_和傳遞的關(guān)系稱為A上的偏序關(guān)系。5、后綴表達式35274/的值是5_。6、設(shè)無向圖G有11條邊，2，3，4，5，6度頂點各1個，其余頂點均為懸掛頂點即1度頂點，則G中有6_個懸掛頂點。7、設(shè)G為連通的平面圖，有5個面，總度數(shù)為14，則G有7_個頂點。15CM298、已知一棵無向樹T中有4度、3度和2度分支點各1個，其余頂點均為樹葉，則T有8_個樹葉。9、設(shè)集合，上的運算定義為,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDBCE則代數(shù)系統(tǒng)中單位元是9_。,S10、設(shè)運算的運算表如下所示，則運算滿足交換律、冪等律、結(jié)合律中的10_。ABCACABBABCCBCA四、計算題（本大題共2小題，每小題6分，共12分）1、求下圖中的最小生成樹，并計算它的權(quán)。V1V2V6V3V5V41352467892、設(shè)有7個字母在通信中出現(xiàn)的頻率如下A35B20,C15,D10,E10,F5,G51以頻率或乘100為權(quán)，求最優(yōu)2元樹2利用所求最優(yōu)2元樹找出每個字母的前綴碼3求傳輸10000個按上述比例出現(xiàn)的字母需要多少個二進制數(shù)字若用等長的長為3的碼字傳輸需要多少個二進制數(shù)字節(jié)約多少個二進制位15CM30五、應(yīng)用題（本大題共2小題，每小題8分，共16分）1、設(shè)集合，X上的關(guān)系R如圖所示，試求,DCBAABCD（1）寫出關(guān)系R的關(guān)系矩陣RM（2）求關(guān)系R的自反閉包RR的關(guān)系矩陣,RRXIR0（3）求關(guān)系R的對稱閉包SR的關(guān)系矩陣,S1（4）求關(guān)系R的傳遞閉包TR的關(guān)系矩陣,RT4322、如果王小紅努力學(xué)習(xí)，她一定取得好成績。若王小紅貪玩或不按時完成作業(yè)，她就不能取得好成績。所以，如果王小紅努力學(xué)習(xí)，她就能按時完成作業(yè)。1將命題中的4個簡單命題依次符號化為P,Q,R,S；2將命題符號化，即將命題的前提和結(jié)論符號化；3在自然推理系統(tǒng)P中構(gòu)造命題的推理證明。六、證明題（本大題共2小題，每小題6分，共12分）1、設(shè),在A上定義二元關(guān)系R如下Z，證明R是A上的等價關(guān)系。ZVUYXXVVUYX,其中2、設(shè)N階M條邊的無向圖G中，MN1，證明G中存在頂點VDV3。2010一、選擇題（本大題共15小題，每小題2分，共30分）1、給定語句如下，則_是復(fù)合命題。A、15是素數(shù)B、2X23得分15CM15CM31C、小王和小李是好朋友。D、小王和小李成績都好。2、給定下列語句中，是真命題的是_。A、這個男孩真勇敢呀。B、明年5月1日是晴天。C、如果226，則3是奇數(shù)。D、2X233、下列哪個表達式錯誤_。A、XQPXB、QXPC、XXD、QPX4、斯科特先生、他的妹妹、兒子、女兒都是網(wǎng)球選手，關(guān)于這四個人，有如的情況最佳選手的孿生同胞與最差選手性別不同；最佳選手與最差選手年齡相同。則_是最佳選手。A、斯科特B、斯科特妹妹C、斯科特兒子D、斯科特女兒5、是人，活百歲以上；則“有人能活百歲以上”可表示為_。XMXFA、B、XXC、MFD、XX6、給定解釋如下個體域為整數(shù)集合；中特定元素；特定函數(shù)IIDI1,0AID；上特定謂詞為。給定下面各公式Y(jié)XGYXF,IYXF32A、,11AXGFFB、,YFYXC、,XGFD、,0YXGFFAYF則公式_真值為假。7、若，則上可以定義_個二元關(guān)系。3|AA、9B、27C、81D、5128、下列關(guān)于關(guān)系的等式不成立的是_。A、HGFB、11C、D、HGFG9、若關(guān)系的關(guān)系矩陣為對稱矩陣，則關(guān)系一定具有_。RRA、自反性B、對稱性C、反對稱D、傳遞性10、若T為樹，以下敘述不正確的是_。A、T是連通的且每個點都是割點B、T的每對頂點之間有唯一的一條路徑C、T是連通的且每條邊都是割邊D、T是連通的且不含回路11、在下列選項中，不是群的是_。A、，為有理數(shù)，為乘法運算,QB、，為非零實數(shù)集，為乘法運算,R33C、全體實對稱矩陣集合，對于矩陣的加法運算D、，為有理數(shù)，為加法運算,Q12、給定下列各序列，可以構(gòu)成無向簡單圖的度數(shù)序列為_。A、1,1,2,2,3B、1,1,2,2,2C、0,1,3,3,3D、1,3,4,4,513、5個頂點非同構(gòu)的根樹有_個。A、7B、8C、9D、1014、下面編碼_不是前綴碼。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010115、無向完全帶權(quán)圖中，按權(quán)計算最多有_條不同的哈密頓回路。NK2A、B、C、D、12/1N2/N二、填空題（本大題共15空，每空2分，共30分）1、若有限集合上的等價關(guān)系有三個等價類，則其關(guān)系圖的連通分支數(shù)為_。AR2、設(shè)個體域為整數(shù)集合，命題的真值為_。0YX3、的前束范式為_。,YXGYXF4、設(shè)R是集合A上的二元關(guān)系，如果關(guān)系R同時具有自反性、_和傳遞性，則稱R是A上的偏序關(guān)系。5、設(shè)，定義S上的關(guān)系，則R具有_性10,2S10,|YXSYXR質(zhì)。6、在有理數(shù)集上定義二元運算，有，則關(guān)于運算的幺元是QQ,_。7、在群、半群、獨異點中，_滿足消去律。得分348、35條邊，每個頂點的度數(shù)至少為3的圖最多有_個頂點。9、設(shè)階圖中有條邊，每個頂點的度數(shù)不是就是，若中有_個度頂點（用關(guān)于NGMK1GKM、N、K的表達式表示）。10、若10階平面圖中有5個面，則圖中有_條邊。G11、一顆帶權(quán)為1，2，3，4，5，6的最優(yōu)三元樹，其權(quán)為_。12、群中（為模6加法運算），則5的階為_。,Z13、若某個簡單圖不是歐拉圖但具有歐拉通路，則圖中奇度數(shù)的頂點個數(shù)一定為_。14、N個頂點的無向樹是平面圖，它的無窮面的次數(shù)為_。15、求滿足不等式的正整數(shù)解的個數(shù)有_6321X三、計算題（本大題共4個小題，每題5分，共20分）1、畫出下列集合關(guān)于整除關(guān)系的哈斯圖，并指出它的極小元、最小元、極大元、最大元。2,158,63,22、已知有向圖，E，EVD,4,3213,24,12,，求有向圖D的鄰接矩陣和可達矩陣。134,33、帶有N個頂點的2元完全正則樹有多少樹葉4、設(shè)有A、B、C、D、E、F、G七個人，他們分別會講的語言如下A英，B漢、英，C英、西班牙、俄，D日、漢，E德、西班牙，F(xiàn)法、日、俄，G法、德，能否將這七個人的座位安排在圓桌旁，使得每個人均能與他旁邊的人交談四、證明題（本大題共4個小題，每題5分，共20分）15CM351、RPQRP2、設(shè)和是集合上的等價關(guān)系，且，證明1R2A121R是集合上的對稱關(guān)系。3、設(shè)G為N階無向簡單圖，證明若G為自補圖（若一個圖的補圖為本身則稱為自補圖），則或，其中K為正整數(shù)。K414、證明設(shè)是一個代數(shù)系統(tǒng)，是上的二元運算，,RR,RBAAB則0是