離散數(shù)學往年試題及答案

一、單項選擇題（每題2分，共10題）1.下列語句中，（）是命題。A.請把門關上B.\(x+5>6\)C.地球外的星球上也有人D.下午有會嗎2.設集合\(A=\{1,2,3\}\)，則\(A\)的冪集\(P(A)\)的元素個數(shù)是（）。A.3B.6C.8D.93.若集合\(A=\{a,b\}\)，關系\(R=\{(a,a),(b,b)\}\)，則\(R\)是（）。A.自反的B.對稱的C.傳遞的D.以上都對4.命題公式\((P\toQ)\land\negQ\)的主析取范式是（）。A.\(\negP\land\negQ\)B.\(P\land\negQ\)C.\(\negP\landQ\)D.\(P\landQ\)5.設\(A=\{1,2,3\}\)，\(B=\{a,b\}\)，則從\(A\)到\(B\)的不同函數(shù)個數(shù)為（）。A.\(2^3\)B.\(3^2\)C.\(2\times3\)D.\(3+2\)6.無向圖\(G\)有12條邊，6個3度頂點，其余頂點度數(shù)均小于3，則\(G\)至少有（）個頂點。A.8B.9C.10D.117.設\(R\)是實數(shù)集，運算\(\)定義為\(ab=a+b-ab\)，則\(0\)關于\(\)的逆元是（）。A.0B.1C.-1D.不存在8.下列圖中，（）是歐拉圖。A.有5個頂點，5條邊的連通圖B.有6個頂點，6條邊的連通圖C.有7個頂點，7條邊的連通圖D.有8個頂點，8條邊的連通圖9.命題公式\(P\to(Q\lorR)\)的對偶式為（）。A.\(P\to(\negQ\land\negR)\)B.\(\negP\to(\negQ\land\negR)\)C.\(P\land(\negQ\lor\negR)\)D.\(\negP\land(\negQ\lor\negR)\)10.設\(A=\{1,2,3,4\}\)，關系\(R=\{(1,2),(2,3),(3,4)\}\)，則\(R\)的傳遞閉包\(t(R)\)是（）。A.\(\{(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)\}\)B.\(\{(1,2),(2,3),(3,4),(1,3),(2,4)\}\)C.\(\{(1,2),(2,3),(3,4)\}\)D.\(\{(1,2),(2,3),(3,4),(1,4)\}\)二、多項選擇題（每題2分，共10題）1.以下哪些是命題公式（）。A.\(P\landQ\)B.\(P(x)\toQ\)C.\(\neg(P\lorQ)\)D.\(P+Q\)2.設集合\(A=\{1,2,3,4\}\)，則下列哪些是\(A\)的劃分（）。A.\(\{\{1\},\{2\},\{3\},\{4\}\}\)B.\(\{\{1,2\},\{3,4\}\}\)C.\(\{\{1,2,3\},\{4\}\}\)D.\(\{\{1\},\{2,3,4\}\}\)3.關系\(R\)具有下列哪些性質時一定是等價關系（）。A.自反性B.對稱性C.傳遞性D.反自反性4.下列哪些圖是平面圖（）。A.完全圖\(K_4\)B.完全二分圖\(K_{2,3}\)C.完全圖\(K_5\)D.完全二分圖\(K_{3,3}\)5.以下哪些是代數(shù)系統(tǒng)（）。A.\((\mathbb{Z},+)\)（\(\mathbb{Z}\)為整數(shù)集，\(+\)為普通加法）B.\((\mathbb{R},\times)\)（\(\mathbb{R}\)為實數(shù)集，\(\times\)為普通乘法）C.\((\mathbb{N},-)\)（\(\mathbb{N}\)為自然數(shù)集，\(-\)為普通減法）D.\((\mathbb{Z}_n,+_n)\)（\(\mathbb{Z}_n\)為模\(n\)的整數(shù)集，\(+_n\)為模\(n\)加法）6.命題公式\(P\land(Q\lor\negR)\)的成真賦值有（）。A.\(000\)B.\(011\)C.\(101\)D.\(111\)7.設\(A=\{a,b,c\}\)，關系\(R=\{(a,b),(b,c),(c,a)\}\)，則\(R\)的性質有（）。A.不自反B.不對稱C.不傳遞D.反自反8.下列哪些是格（）。A.集合的冪集\(P(S)\)關于包含關系B.正整數(shù)集關于整除關系C.實數(shù)集關于小于等于關系D.整數(shù)集關于小于關系9.一個簡單圖\(G\)是樹的充分必要條件有（）。A.\(G\)連通且邊數(shù)比頂點數(shù)少1B.\(G\)無回路且邊數(shù)比頂點數(shù)少1C.\(G\)連通且任意刪去一條邊就不連通D.\(G\)無回路且任意增加一條邊就出現(xiàn)回路10.以下哪些是命題邏輯中的基本聯(lián)結詞（）。A.\(\neg\)（否定）B.\(\land\)（合?。〤.\(\lor\)（析?。〥.\(\to\)（蘊含）三、判斷題（每題2分，共10題）1.“\(x>5\)”是命題。（）2.集合\(A\)上的恒等關系\(I_A\)是等價關系。（）3.若關系\(R\)是對稱的，則\(R^{-1}=R\)。（）4.完全圖\(K_n\)的邊數(shù)為\(n(n-1)\)。（）5.命題公式\(P\toQ\)和\(\negP\lorQ\)是等價的。（）6.一個代數(shù)系統(tǒng)中一定有單位元。（）7.有向圖的鄰接矩陣中第\(i\)行元素之和等于頂點\(v_i\)的出度。（）8.偏序集一定是格。（）9.若\(A\)是有限集，\(R\)是\(A\)上的關系，則\(R\)的傳遞閉包一定存在。（）10.歐拉圖一定是哈密頓圖。（）四、簡答題（每題5分，共4題）1.求命題公式\(\neg(P\toQ)\lorR\)的真值表。答案：|\(P\)|\(Q\)|\(R\)|\(P\toQ\)|\(\neg(P\toQ)\)|\(\neg(P\toQ)\lorR\)||:--:|:--:|:--:|:--:|:--:|:--:||0|0|0|1|0|0||0|0|1|1|0|1||0|1|0|1|0|0||0|1|1|1|0|1||1|0|0|0|1|1||1|0|1|0|1|1||1|1|0|1|0|0||1|1|1|1|0|1|2.設集合\(A=\{1,2,3\}\)，關系\(R=\{(1,2),(2,3),(3,1)\}\)，求\(R\)的自反閉包\(r(R)\)和對稱閉包\(s(R)\)。答案：自反閉包\(r(R)=R\cupI_A=\{(1,2),(2,3),(3,1),(1,1),(2,2),(3,3)\}\)；對稱閉包\(s(R)=R\cupR^{-1}=\{(1,2),(2,1),(2,3),(3,2),(3,1),(1,3)\}\)。3.簡述圖的連通性定義。答案：若圖\(G\)中任意兩個頂點\(u\)和\(v\)之間都存在路徑，則稱圖\(G\)是連通圖；否則稱為非連通圖。若一個圖不是連通圖，但它的每個極大連通子圖稱為連通分支。4.設\(A=\{a,b,c\}\)，\(B=\{1,2\}\)，求\(A\timesB\)。答案：\(A\timesB=\{(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)\}\)。五、討論題（每題5分，共4題）1.討論等價關系在實際生活中的應用。答案：等價關系在生活中應用廣泛。比如在垃圾分類中，可將垃圾按可回收、有害、廚余等類別分類，同類垃圾構成等價類；在學生分組活動中，按興趣愛好、能力等標準分組，同組學生屬于一個等價類，方便組織活動和管理。2.探討圖論在計算機網(wǎng)絡中的作用。答案：圖論在計算機網(wǎng)絡中作用重大。網(wǎng)絡拓撲結構可用圖表示，頂點代表節(jié)點，邊代表連接。通過圖論算法能優(yōu)化網(wǎng)絡布線、路徑選擇，如Dijkstra算法找最短路徑，利于數(shù)據(jù)高效傳輸，提高網(wǎng)絡性能，保障網(wǎng)絡可靠性。3.說說命題邏輯在數(shù)學證明中的意義。答案：命題邏輯為數(shù)學證明提供嚴謹邏輯基礎。將數(shù)學命題符號化，利用推理規(guī)則從已知前提推出結論。能清晰展現(xiàn)證明思路，保證證明準確性和嚴密性，是數(shù)學定理證明、理論推導的重要工具。4.論述代數(shù)系統(tǒng)中同態(tài)與同構的重要性。答案：同態(tài)與同構在代數(shù)系統(tǒng)中很重要。同態(tài)保持運算結構，可簡化復雜系統(tǒng)研究；同構表明不同系統(tǒng)本質結構相同，在密碼學、編碼理論等領域，利用同構特性可設計高效算法和安全機制，方便系統(tǒng)間轉換和分析。