2026年離散數學測試題及答案

2026年離散數學測試題及答案

一、單項選擇題（每題2分，共20分）1.設命題公式G=(p→q)∧(?q∨r)，則使G為假的真值指派是A.p=1,q=1,r=1B.p=1,q=0,r=0C.p=0,q=1,r=0D.p=1,q=0,r=12.在集合A={1,2,3,4}上，關系R={(x,y)|x+y為偶數}的等價類個數為A.1B.2C.3D.43.下列哪一條不是偏序集的性質A.自反性B.對稱性C.反對稱性D.傳遞性4.無向圖G有12條邊且每個頂點度數為3，則G的頂點數為A.6B.8C.9D.125.設函數f:?→?,f(x)=2x+1，則f是A.滿射非單射B.單射非滿射C.雙射D.既非單射又非滿射6.在代數系統??,?中，運算ab=a+b+ab，其單位元為A.0B.1C.-1D.不存在7.下列邏輯等價式正確的是A.?(p∨q)??p∧?qB.?(p∧q)??p∨qC.p→q?q→pD.p∨?p?08.設樹T有n個頂點且恰有3個葉子，則T的邊數為A.n-1B.n-2C.n-3D.n-49.若群G的階為素數p，則G的子群個數為A.1B.2C.pD.p+110.命題“所有可滿足的公式都是重言式”是A.真B.假C.無法判斷D.依賴于語言二、填空題（每題2分，共20分）11.命題公式(p→q)∧(q→?p)的主合取范式中含________個極大項。12.集合A={a,b,c}的冪集元素個數為________。13.若關系R的關系圖中有環，則R一定不滿足________性。14.完全二分圖K_{3,4}的邊數為________。15.設f:A→B，|A|=5,|B|=3，則不同的滿射函數共有________種。16.格中若a∧b=a∨b，則a與b的關系是________。17.循環群C_{12}的生成元個數為________。18.具有n個頂點的有向完全圖的邊數為________。19.設圖G的鄰接矩陣A滿足A^3的(2,3)元為4，則G中從頂點2到3長度為3的通路有________條。20.設命題p,q的真值分別為1,0，則(p↑q)↓(p↓q)的真值為________。（↑表示與非，↓表示或非）三、判斷題（每題2分，共20分）21.空關系在任意非空集上都是等價關系。22.若圖G的色數為2，則G必為二分圖。23.任意有限格都必有最大元和最小元。24.命題公式(p∨?p)→q是重言式。25.若函數f有左逆，則f必為滿射。26.群中任意元的階都整除群的階。27.有向圖存在歐拉回路當且僅當強連通且每個頂點入度等于出度。28.集合上的全序關系一定是良序。29.若R是A上的偏序，則R的逆關系也是偏序。30.樹中任意兩頂點間恰有一條簡單通路。四、簡答題（每題5分，共20分）31.敘述并證明集合A上等價關系與A的劃分之間的一一對應。32.給出哈密頓圖的必要條件和充分條件各一條，并說明其區別。33.設?L,∧,∨?是分配格，證明對任意a,b,c∈L，有a∧(b∨c)=(a∧b)∨(a∧c)。34.說明命題邏輯中“可滿足”與“有效”的區別，并舉例。五、討論題（每題5分，共20分）35.討論在有限域上構造一個階為16的有限域的思路，需涉及多項式不可約性的作用。36.對比Prim算法與Kruskal算法在稠密圖與稀疏圖下的時間表現，并給出適用場景。37.群同態基本定理指出ker(f)?G，討論其在判定兩個群是否同構時的實際應用價值。38.命題邏輯與一階邏輯在表達“每個數都有素因子”時的差異，說明為何前者無法直接表達。答案與解析一、1.B2.B3.B4.B5.B6.A7.A8.A9.B10.B二、11.212.813.反自反14.1215.15016.a=b17.418.n(n-1)19.420.0三、21.×22.√23.√24.×25.×26.√27.√28.×29.√30.√四、31.對任意等價關系R，其商集A/R構成劃分；反之給定劃分π，定義xRy當且僅當x,y同屬π的某塊，則R為等價關系。兩映射互逆，故為雙射。32.必要條件：若圖G為哈密頓圖，則對任意非空真子集S?V，有ω(G-S)≤|S|。充分條件：Ore定理——若對任意不相鄰頂點u,v有deg(u)+deg(v)≥n，則G為哈密頓圖。前者用于否定，后者用于肯定。33.分配格定義即滿足a∧(b∨c)=(a∧b)∨(a∧c)，無需再證；若題目要求驗證，可用真值表或格圖逐點檢驗。34.“可滿足”指存在至少一個解釋使其為真，如p∨q；“有效”指所有解釋下為真，如p∨?p。前者不要求普遍真，后者要求普遍真。五、35.先取F=?_2，找四次不可約多項式f(x)∈F[x]，則F[x]/?f(x)?為含16元域，其乘法群為15階循環群，可用本原元生成。36.Prim用鄰接矩陣實現O(V^2)，稠密圖占優；Kruskal用并查集O(ElogE)，稀疏圖占優。稠密圖選Prim，稀疏圖選Kruskal。3