2025年大學(xué)《數(shù)學(xué)與應(yīng)用數(shù)學(xué)》專業(yè)題庫(kù)——離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中的應(yīng)用考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每題2分，共20分）1.在集合論中，集合A包含于集合B記作________。A.A=BB.A?BC.A?BD.A∩B2.一個(gè)有向圖是強(qiáng)連通的，當(dāng)且僅當(dāng)該圖________。A.沒(méi)有環(huán)B.任何兩個(gè)頂點(diǎn)間都有路徑C.是樹(shù)D.是完全圖3.邏輯表達(dá)式(P∧?Q)∨(?P∧Q)等價(jià)于________。A.P→QB.P?QC.?(P?Q)D.Q→P4.在組合數(shù)學(xué)中，從n個(gè)不同元素中取出k個(gè)元素的組合數(shù)記作________。A.P(n,k)B.C(n,k)C.S(n,k)D.H(n,k)5.無(wú)向圖G的補(bǔ)圖G'是指________。A.G'中包含G中所有邊B.G'中包含G中所有不存在的邊C.G'與G有相同的頂點(diǎn)集D.G'是G的子圖6.一個(gè)圖的最小生成樹(shù)是________。A.包含所有頂點(diǎn)的極小連通子圖B.包含所有邊的極小連通子圖C.包含所有頂點(diǎn)的極大連通子圖D.包含所有邊的極大連通子圖7.在命題邏輯中，永真式是指________。A.在任何解釋下都為假的命題B.在任何解釋下都為真的命題C.僅在一個(gè)解釋下為真的命題D.僅在一個(gè)解釋下為假的命題8.下列哪個(gè)不是圖論中的基本概念？________A.頂點(diǎn)B.邊C.環(huán)D.函數(shù)9.在數(shù)理邏輯中，量詞?表示________。A.存在B.對(duì)于所有C.或者D.并且10.哈密頓路徑是指________。A.經(jīng)過(guò)所有頂點(diǎn)的路徑B.經(jīng)過(guò)所有邊的路徑C.簡(jiǎn)單路徑D.回路二、填空題（每題2分，共10分）1.如果集合A有n個(gè)元素，則A的冪集的元素個(gè)數(shù)為_(kāi)_______。2.一個(gè)無(wú)向圖G是連通的，當(dāng)且僅當(dāng)G中存在________。3.邏輯表達(dá)式P∧(Q∨R)的對(duì)偶式為_(kāi)_______。4.卡特蘭數(shù)C(n)是________數(shù)目。5.在樹(shù)中，每個(gè)頂點(diǎn)的度數(shù)最大為_(kāi)_______。三、判斷題（每題2分，共10分）1.如果集合A包含集合B，那么B也包含A。（）2.在有向圖中，如果存在一條從頂點(diǎn)u到頂點(diǎn)v的路徑，也必然存在一條從v到u的路徑。（）3.命題邏輯中的重言式與永真式是同一個(gè)概念。（）4.任何圖的最小生成樹(shù)都是唯一的。（）5.在組合數(shù)學(xué)中，排列數(shù)P(n,k)是從n個(gè)不同元素中取出k個(gè)元素的排列數(shù)。（）四、簡(jiǎn)答題（每題10分，共30分）1.簡(jiǎn)述圖論中歐拉回路和哈密頓回路的概念及其區(qū)別。2.解釋什么是命題邏輯中的對(duì)偶式，并舉例說(shuō)明。3.描述圖論中拓?fù)渑判虻母拍罴捌鋺?yīng)用。五、計(jì)算題（每題20分，共40分）1.給定集合A={1,2,3}，B={2,3,4}，C={3,4,5}，計(jì)算A∪(B∩C)和(A∩B)∪C，并畫(huà)出它們的文氏圖。2.對(duì)于邏輯表達(dá)式(P∧Q)→(?P∨R)，寫(xiě)出其真值表，并判斷該表達(dá)式是否為重言式。試卷答案一、選擇題1.B解析：集合A包含于集合B表示為A?B。2.B解析：強(qiáng)連通圖定義要求圖中任意兩個(gè)頂點(diǎn)間都有相互之間的路徑。3.C解析：根據(jù)德摩根定律和邏輯等價(jià)式，(P∧?Q)∨(?P∧Q)與?(P?Q)等價(jià)。4.B解析：從n個(gè)不同元素中取出k個(gè)元素的組合數(shù)記作C(n,k)。5.B解析：補(bǔ)圖G'是指G中所有不存在的邊構(gòu)成的圖。6.A解析：最小生成樹(shù)是包含所有頂點(diǎn)的極小連通子圖。7.B解析：永真式是在任何解釋下都為真的命題。8.D解析：函數(shù)不是圖論中的基本概念，頂點(diǎn)和邊是圖的基本構(gòu)成元素。9.B解析：量詞?表示“對(duì)于所有”。10.A解析：哈密頓路徑是指經(jīng)過(guò)所有頂點(diǎn)的路徑。二、填空題1.2^n解析：集合A的冪集元素個(gè)數(shù)為2的n次方。2.連通分支解析：無(wú)向圖G是連通的，當(dāng)且僅當(dāng)G中存在連接所有頂點(diǎn)的連通分支。3.(?P∨?Q)∧(?P∨?R)解析：根據(jù)對(duì)偶規(guī)則，將原表達(dá)式中的∧換成∨，∨換成∧，?保持不變。4.不同元素的排列解析：卡特蘭數(shù)C(n)是不同元素的排列數(shù)目。5.n-1解析：在樹(shù)中，每個(gè)頂點(diǎn)的度數(shù)最大為n-1（除了根節(jié)點(diǎn)，其他節(jié)點(diǎn)度數(shù)為n-1）。三、判斷題1.錯(cuò)解析：集合包含關(guān)系是單向的，A包含B不一定B包含A。2.錯(cuò)解析：有向圖中路徑方向固定，從u到v的路徑不一定存在從v到u的路徑。3.對(duì)解析：重言式與永真式在命題邏輯中是同一個(gè)概念。4.錯(cuò)解析：最小生成樹(shù)可能不唯一，取決于圖的邊權(quán)和構(gòu)造。5.對(duì)解析：排列數(shù)P(n,k)是從n個(gè)不同元素中取出k個(gè)元素的排列數(shù)。四、簡(jiǎn)答題1.解析：歐拉回路是經(jīng)過(guò)圖中所有邊恰好一次的回路；哈密頓回路是經(jīng)過(guò)圖中所有頂點(diǎn)恰好一次的回路。區(qū)別在于前者關(guān)注邊，后者關(guān)注頂點(diǎn)。2.解析：對(duì)偶式是將命題邏輯表達(dá)式中的∧換成∨，∨換成∧，?保持不變得到的新表達(dá)式。例如，P∧(Q∨R)的對(duì)偶式是?P∨(?Q∧?R)。3.解析：拓?fù)渑判蚴菍?duì)有向無(wú)環(huán)圖頂點(diǎn)的一種線性排序，使得對(duì)于每條有向邊(u,v)，頂點(diǎn)u都在頂點(diǎn)v之前。應(yīng)用包括任務(wù)調(diào)度、依賴關(guān)系處理等。五、計(jì)算題1.解析：A∪(B∩C)={1,2,3}∪{3}={1,2,3}(A∩B)∪C={2}∪{3,4,5}={2,3,4,5}文氏圖略。2.解析：真值表：|P|Q|R|(P∧Q)|?P|?P∨R|(P∧Q)→(?P∨R)||---|---|---|---------|----|--------|----------------------||T|T|T|T|F|T|T||T|T|F|T|F|T|T||T|F|T|F|F|T|T||T|F|F|F|F|T|T||F|T|T|F|T|T|T||F|T|F|F|T|F|T