貴州2025自考[計算機科學(xué)與技術(shù)]離散數(shù)學(xué)簡答題專練題型一：集合論與關(guān)系（共4題，每題5分）1.題目：設(shè)集合A={1,2,3}，B={a,b}，計算A×B的結(jié)果，并說明其含義。2.題目：判斷下列關(guān)系是否為函數(shù)，并說明理由：R1={(1,a),(2,b),(3,a)}；R2={(1,a),(1,b),(2,a)}。3.題目：定義域為N，值域為N的函數(shù)f(n)=n2是否為滿射？為什么？4.題目：設(shè)R為集合A上的關(guān)系，若R是自反的、對稱的，但不傳遞，稱其為“擬等價關(guān)系”。舉例說明擬等價關(guān)系在計算機中的應(yīng)用（如文件分類）。題型二：命題邏輯（共4題，每題5分）1.題目：將下列命題符號化，并求其真值表：“如果今天下雨，我就不去公園，且我會看書?！?.題目：證明命題公式(p→q)?(?q→?p)是重言式。3.題目：簡化命題公式：(p?q)∧(p∨?q)，并說明其邏輯含義。4.題目：舉例說明命題邏輯在軟件需求分析中的作用（如用邏輯表達式描述系統(tǒng)規(guī)則）。題型三：謂詞邏輯（共3題，每題6分）1.題目：將下列自然語言命題翻譯為謂詞邏輯公式：“所有學(xué)生都通過了考試?！?.題目：判斷謂詞公式?x?y(P(x,y))是否為永真式，并解釋原因。3.題目：在貴州某高校數(shù)據(jù)庫中，用謂詞邏輯描述“查詢所有年齡大于20歲的計算機系學(xué)生”的查詢條件。題型四：圖論（共5題，每題6分）1.題目：畫出無向圖G，其頂點集V={a,b,c,d}，邊集E={(a,b),(b,c),(c,d),(a,d)}，并說明其連通性。2.題目：證明：任何無向樹至少有兩個葉子頂點。3.題目：設(shè)一張貴州旅游景點地圖為無向連通圖，如何用圖論方法規(guī)劃最短旅游路線？4.題目：解釋二分圖的定義，并舉例說明其在社交網(wǎng)絡(luò)中的用途。5.題目：用鄰接矩陣表示圖G=(V,E)，其中V={1,2,3}，E={(1,2),(2,3)}，計算頂點1的度數(shù)。題型五：組合數(shù)學(xué)（共4題，每題6分）1.題目：計算從貴陽到重慶的直達航班有3班，中轉(zhuǎn)航班有5班，若選擇任意航班出行，共有多少種選擇方式？2.題目：證明組合恒等式：C(n,0)+C(n,1)+…+C(n,n)=2?。3.題目：在貴州某IT公司的招聘中，需要從6名候選人中選出3名面試，若某位候選人必須被選，共有多少種選擇方案？4.題目：解釋錯排問題的定義，并計算n=4時的錯排數(shù)目。題型六：數(shù)理邏輯在密碼學(xué)中的應(yīng)用（共2題，每題7分）1.題目：用命題邏輯描述RSA加密算法的公鑰和私鑰生成過程。2.題目：貴州某銀行采用哈希函數(shù)校驗數(shù)據(jù)完整性，解釋哈希函數(shù)如何基于謂詞邏輯保證數(shù)據(jù)唯一性。答案與解析題型一：集合論與關(guān)系1.答案：A×B={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}。含義為A和B的所有可能有序?qū)M合，是笛卡爾積的定義。解析：笛卡爾積是集合間的一種乘法運算，適用于計算機中關(guān)系數(shù)據(jù)庫的元組生成。2.答案：R1是函數(shù)，R2不是。R1滿足每個輸入有唯一輸出；R2中輸入1對應(yīng)兩個輸出，違反函數(shù)定義。解析：函數(shù)要求定義域中每個元素在值域中有唯一映射，這是編程中函數(shù)確定性要求的基礎(chǔ)。3.答案：不是滿射。因為N2的元素（如4）在N中不存在，即所有輸出不覆蓋N。解析：RSA加密中模運算常用有限集合，需確保值域覆蓋所有可能輸出。4.答案：例：文件按類型分類（文檔/圖片），自反（文件屬于自身類型）、對稱（文檔與文檔互為同類）、不傳遞（文檔與圖片不相關(guān)）。解析：擬等價關(guān)系常用于數(shù)據(jù)聚類，貴州政務(wù)系統(tǒng)可用此優(yōu)化文件檢索。題型二：命題邏輯1.答案：符號化：(p∧?q)∨(?p∧r)。真值表略。解析：貴州某IT公司考勤規(guī)則常用此類邏輯描述（如“遲到→扣錢”）。2.答案：構(gòu)造真值表驗證，p?q等價于(p→q)∧(q→p)，與?q→?p等價。解析：該公式用于證明邏輯等價，計算機中常用于簡化布爾表達式。3.答案：簡化為p。含義：當(dāng)p和?q同時為真時，公式為假，其他情況為真。解析：貴州某軟件公司需求文檔常用此描述互斥條件。4.答案：例：用(p∧?q)∨(?p∧q)描述“用戶登錄需同時滿足密碼正確且驗證碼輸入”，避免矛盾。解析：貴州銀行系統(tǒng)規(guī)則校驗常用邏輯公式避免歧義。題型三：謂詞邏輯1.答案：?x(P(x,y))，其中P(x,y):“x通過了考試”。解析：貴州某高校教務(wù)系統(tǒng)用此查詢所有考試通過學(xué)生。2.答案：非永真式。例：x=1時，?y(y=0)不成立。解析：貴州某IT公司招聘篩選時需確保?x?y(P(x,y))成立（如“所有人都有技能要求”）。3.答案：?x((年齡(x)>20)∧(系(x)="計算機"))。解析：貴州某高校數(shù)據(jù)庫查詢語句中常用謂詞邏輯過濾數(shù)據(jù)。題型四：圖論1.答案：圖略，連通。解析：貴州某城市地鐵線路可用圖論分析連通性，優(yōu)化票價策略。2.答案：樹性質(zhì)：每個頂點度數(shù)≥1，總度數(shù)=2(n-1)。若n=1，度數(shù)為0矛盾。解析：貴州某IT公司組織結(jié)構(gòu)圖必須至少兩個葉子節(jié)點（基層員工）。3.答案：用最短路徑算法（如Dijkstra）規(guī)劃，頂點代表景點，邊代表距離。解析：貴州某旅游平臺可用圖論優(yōu)化行程規(guī)劃。4.答案：二分圖：頂點分為A,B，每邊連接A和B。例：貴州某婚戀網(wǎng)站用戶匹配。解析：貴州某社交APP用二分圖分析用戶關(guān)系。5.答案：鄰接矩陣：123101021013010頂點1度數(shù)=2。解析：貴州某IT公司網(wǎng)絡(luò)拓?fù)溆绵徑泳仃嚬芾砉?jié)點連接。題型五：組合數(shù)學(xué)1.答案：3+5=8種。解析：貴州某航空公司航班選擇用加法原理。2.答案：數(shù)學(xué)歸納法證明。解析：貴州某IT公司項目分組方案用組合恒等式計算。3.答案：C(5,2)=10種。解析：貴州某公司招聘中“必須選某候選人”用組合減法。4.答案：D?=9。解析：貴州某游戲公司關(guān)卡設(shè)計用錯排計算。題型六：數(shù)理邏輯在密碼學(xué)中的應(yīng)用1.答案：RSA公鑰(n,e)，私鑰(n,d)，邏輯關(guān)系：m^emodn=c,c^dmodn=m