浙江2025自考[計算機科學(xué)與技術(shù)]離散數(shù)學(xué)主觀題專練一、填空題（每空2分，共20分）題目：1.在集合論中，集合A包含元素a，記作__________。2.設(shè)函數(shù)f:A→B，若對于任意b∈B，存在a∈A使得f(a)=b，則稱f為__________。3.命題公式“p∧q→?r”的等價式為__________。4.在圖論中，一個圖G=(V,E)中，若所有頂點的度數(shù)均為k，則稱G為__________。5.關(guān)系R滿足自反性、對稱性和傳遞性時，稱R為__________。6.邏輯聯(lián)結(jié)詞“?”的優(yōu)先級__________（高于/低于/等于）“∧”。7.有限狀態(tài)自動機M=(Q,Σ,δ,q?,F)中，Q表示__________。8.哈密頓路徑是指經(jīng)過圖G中每個頂點__________的路徑。9.樹的度是指樹中__________的最大值。10.邏輯表達式“(p∨q)∧(?p∨r)”的析取范式為__________。答案：1.a∈A2.全函數(shù)（或滿射）3.?p∨?q∨?r4.正則圖（或k正則圖）5.等價關(guān)系6.高于7.狀態(tài)集8.且僅一次9.度數(shù)（或頂點的度數(shù)）10.(p∧?q∧?r)∨(?p∧q∧?r)∨(?p∧?q∧r)二、判斷題（每題2分，共10分）題目：1.集合A={1,2,3}的真子集有8個。（）2.若函數(shù)f和g都是滿射，則f°g也是滿射。（）3.命題公式“p∨(q∧r)”與“(p∨q)∧(p∨r)”等價。（）4.完全二叉樹的所有葉子節(jié)點都在同一層。（）5.無向圖G中，若G是連通的，則G至少存在一條Hamilton回路。（）答案：1.√2.√3.×（正確應(yīng)為“p∨(q∧r)≡(p∨q)∧(p∨r)”）4.√5.×（連通不保證存在Hamilton回路，如樹）三、簡答題（每題5分，共25分）題目：1.簡述集合的并、交、差運算的定義。2.解釋什么是命題邏輯中的析取范式和合取范式。3.說明圖論中“樹”的定義及其性質(zhì)。4.什么是等價關(guān)系？舉例說明其三個性質(zhì)。5.有限自動機如何識別語言？（結(jié)合實例說明）答案：1.并集：A∪B={x|x∈A∨x∈B}；交集：A∩B={x|x∈A∧x∈B}；差集：A-B={x|x∈A∧x?B}。2.析取范式：由邏輯變量及否定通過“∨”連接的式子，如p∨?q∨r；合取范式：由邏輯變量及否定通過“∧”連接的式子，如(p∧?q)∧(?p∧r)。3.樹：無環(huán)連通圖。性質(zhì)：①任意兩頂點間有唯一路徑；②刪除任意邊會變不連通；③n個頂點的樹有n-1條邊。4.等價關(guān)系：滿足自反性（aRa）、對稱性（aRb?bRa）、傳遞性（aRb∧bRc?aRc）的關(guān)系。例如：整數(shù)集合中的“模2同余”關(guān)系。5.有限自動機通過狀態(tài)轉(zhuǎn)移識別語言。例如：識別語言{0n1n|n≥1}的自動機，狀態(tài)q?（初始）→接受狀態(tài)q?（讀0轉(zhuǎn)移），再讀1→回到q?。四、計算題（每題10分，共40分）題目：1.證明命題公式“p→q”與“?q→?p”等價。2.設(shè)集合A={1,2,3}，B={a,b}，計算A×B及B×A，并說明笛卡爾積的性質(zhì)。3.用Warshall算法求矩陣M=(010；101；010)的最短路徑長度矩陣。4.構(gòu)造一個識別語言L={w|w∈{a,b}且w不含子串“aa”}的有限自動機。答案：1.證明：“p→q”≡“?p∨q”；“?q→?p”≡“?(?q)∨?p”≡“q∨?p”≡“?p∨q”，故等價。2.笛卡爾積：A×B={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}；B×A={<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}；性質(zhì)：①A×B≠B×A；②(A×B)×C=A×(B×C)；③A×(B∪C)=(A×B)∪(A×C)。3.Warshall算法：M?=010；101；010M?=111；101；110M?=111；111；110最短路徑長度矩陣為M?。4.有限自動機：狀態(tài)：q?（初始，接受），q?（非接受）；轉(zhuǎn)移：-q?→a→q?（禁止aa），b→q?；-q?→a→q?，b→q?；識別規(guī)則：狀態(tài)q?為接受態(tài)，q?為非接受態(tài)。五、證明題（每題15分，共30分）題目：1.證明：一棵樹至少有兩片葉子節(jié)點（若樹的頂點數(shù)≥2）。2.設(shè)R是集合A上的關(guān)系，若R是自反的、對稱的，證明R是等價關(guān)系。答案：1.證明：設(shè)樹T有n個頂點，若n=1，無葉子節(jié)點；若n≥2，樹的總邊數(shù)為n-1。每個非葉子節(jié)點至少關(guān)聯(lián)2條邊（否則會形成環(huán)），故葉子節(jié)點至少為n-（n-2）=2。2.證明：①自反性：?a∈A，aRa成立（已知）；②對稱性：?a,b∈A，aRb?bRa成