2025年大學(xué)《數(shù)學(xué)與應(yīng)用數(shù)學(xué)》專業(yè)題庫——離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中的作用考試時(shí)間：______分鐘總分：______分姓名：______一、1.設(shè)命題公式P和Q滿足P?Q為真，Q?P為假。請(qǐng)用真值表證明P與Q互為矛盾命題。2.在謂詞邏輯中，解釋謂詞?x(P(x)∨Q(x))與?xP(x)∨?xQ(x)的區(qū)別，并舉例說明它們?cè)诓煌榫诚碌恼嬷悼赡懿煌?.寫出集合{1,2,3}的所有子集，并從中選出三個(gè)集合，分別說明它們是可數(shù)無限集、有限集和空集的實(shí)例（需明確指出對(duì)應(yīng)集合）。二、1.設(shè)集合A={a,b,c,d},B={1,2},C={x|x為小于5的正偶數(shù)}。計(jì)算(A∩B)×C，并寫出結(jié)果。2.定義關(guān)系R和S在集合A={1,2,3}上如下：R={(1,2),(2,3)}，S={(1,1),(2,2)}。請(qǐng)分別寫出關(guān)系R和S的關(guān)系矩陣M<0xE2><0x82><0x99>和M<0xE2><0x82><0x9B>，并計(jì)算R∪S和R-S的關(guān)系矩陣。3.判斷下列關(guān)系是否為等價(jià)關(guān)系，并說明理由。*設(shè)A為任意集合，R={(a,b)|a∈A∧b∈A∧a=b}。*設(shè)N為自然數(shù)集，R={(a,b)|a∈N∧b∈N∧a+b為偶數(shù)}。三、1.用鄰接表表示圖G=(V,E)，其中V={v1,v2,v3,v4}，E={(v1,v2),(v2,v3),(v3,v4),(v4,v1),(v1,v4)}。請(qǐng)分別寫出從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的頂點(diǎn)訪問序列。2.給定有向圖G如下（請(qǐng)用邊列表表示，無需畫出圖形）：頂點(diǎn)集V={A,B,C,D,E}，邊集E={(A,B),(A,C),(B,D),(C,D),(D,E)}。請(qǐng)判斷圖G是否存在拓?fù)渑判?，如果存在，?qǐng)給出一個(gè)拓?fù)渑判蛐蛄小?.在一個(gè)無向連通圖中，有10個(gè)頂點(diǎn)和15條邊。請(qǐng)計(jì)算該圖的最小生成樹包含多少條邊，并說明理由。四、1.計(jì)算C(10,6)的值，并解釋其組合意義。2.在一個(gè)袋子里有5個(gè)紅球和7個(gè)藍(lán)球，從中不放回地取出3個(gè)球。求取出的3個(gè)球中至少有一個(gè)紅球的概率。3.用鴿巢原理證明：在任意集合S中，如果S有10個(gè)元素，則S的任何113個(gè)子集至少有一個(gè)包含相同的元素。五、1.解釋歐幾里得算法用于計(jì)算兩個(gè)正整數(shù)a和b的最大公約數(shù)（GCD）的原理。并用歐幾里得算法計(jì)算252和198的最大公約數(shù)。2.解釋RSA公鑰密碼體制的基本原理，包括密鑰生成（選擇n,?(n),e,d）、加密（C=M^emodn）、解密（M=C^dmodn）的步驟。假設(shè)選擇p=61,q=53，計(jì)算n,?(n)，并選擇e=7，求出d。3.設(shè)a=3,b=10。計(jì)算a模b的剩余（即a÷b的余數(shù)），并寫出a≡b(modm)的形式。試卷答案一、1.真值表如下：|P|Q|P?Q|Q?P|(P?Q)∧?(Q?P)||:--|:--|:----|:----|:----------------||T|T|T|T|F||T|F|T|T|F||F|T|T|F|T||F|F|T|T|F|當(dāng)且僅當(dāng)P為真，Q為假時(shí)，(P?Q)∧?(Q?P)為真。因此，P與Q互為矛盾命題。2.?x(P(x)∨Q(x))表示對(duì)于集合S中的所有元素x，P(x)或Q(x)至少有一個(gè)為真。?xP(x)∨?xQ(x)表示對(duì)于集合S中的所有元素x，P(x)都為真，或者對(duì)于集合S中的所有元素x，Q(x)都為真。前者允許P(x)和Q(x)對(duì)某些x為真，對(duì)另一些x為假；后者要求P(x)對(duì)所有x都為真，或者Q(x)對(duì)所有x都為真。例如，令S={1,2}，P(x)表示“x是偶數(shù)”，Q(x)表示“x是奇數(shù)”。則?x(P(x)∨Q(x))為真，但?xP(x)∨?xQ(x)為假。3.子集：?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}。實(shí)例：可數(shù)無限集的實(shí)例可以是自然數(shù)集N={0,1,2,...}；有限集的實(shí)例可以是{a,b}；空集的實(shí)例是?。二、1.A∩B=?×C=?。因?yàn)锳與B的交集為空集。2.M<0xE2><0x82><0x99>=[[0,1,0],[0,0,1]]；M<0xE2><0x82><0x9B>=[[1,0],[0,1],[0,0]]。R∪S={(1,2),(2,3),(1,1),(2,2)}，其關(guān)系矩陣為[[0,1,0],[0,0,1],[1,0,0],[0,1,0]]。R-S={(1,2),(2,3)}，其關(guān)系矩陣為[[0,1,0],[0,0,1]]。3.*是等價(jià)關(guān)系。滿足自反性（(a,a)∈R對(duì)任意a∈A），對(duì)稱性（若(a,b)∈R，則a=b，故(b,a)∈R），傳遞性（若(a,b)∈R且(b,c)∈R，則a=b且b=c，故a=c，(a,c)∈R）。同時(shí)，它也是等價(jià)類劃分，每個(gè)元素的等價(jià)類僅包含其自身。*不是等價(jià)關(guān)系。不滿足傳遞性。例如，取a=1,b=1,c=2。則1+1=2為偶數(shù)，(1,1)∈R；(1,2)∈R。但1+2=3不是偶數(shù)，(1,2)?R。存在反例，故不是等價(jià)關(guān)系。三、1.鄰接表（以v1為例，鄰接鏈表節(jié)點(diǎn)為(鄰接頂點(diǎn),指向下一個(gè)節(jié)點(diǎn)的指針，這里用逗號(hào)分隔表示）：v1:(v2,v4),v2:(v3,),v3:(v4,),v4:(v1,)）。*DFS序列：v1,v2,v3,v4（或v1,v4,v1,v2,v3,v4等，取決于訪問順序和回溯）。*BFS序列：v1,v2,v4,v3（或v1,v4,v2,v3等，取決于隊(duì)列操作）。2.拓?fù)渑判虼嬖?。一個(gè)可能的序列是A,C,B,D,E。*理由：從A出發(fā)，可以到達(dá)C和B；從B出發(fā)，可以到達(dá)D；從C出發(fā)，可以到達(dá)D；從D出發(fā)，可以到達(dá)E。不存在環(huán)。根據(jù)入度算法，A和C入度為0，可排在前面。然后依此類推。3.最小生成樹包含5條邊。*理由：根據(jù)歐拉公式，對(duì)于具有n個(gè)頂點(diǎn)的連通無向圖，其邊數(shù)e滿足e=n-f，其中f是連通分支數(shù)。當(dāng)f=1時(shí)（連通圖），e=n-1。這里n=10，所以最小生成樹的邊數(shù)為10-1=9。*（修正：連通圖最小生成樹邊數(shù)為n-1。n=10,所以最小生成樹邊數(shù)應(yīng)為9。如果題目意圖是計(jì)算原圖邊數(shù)，則為15。此處按最小生成樹定義回答）。*四、1.C(10,6)=10!/(6!*4!)=(10*9*8*7)/(4*3*2*1)=210。組合意義：從10個(gè)不同元素中取出6個(gè)元素組成一個(gè)子集的方法數(shù)。2.P(至少一個(gè)紅球)=1-P(全是藍(lán)球)=1-C(7,3)/C(12,3)=1-(7*6*5)/(3*2*1)/(12*11*10)/(3*2*1)=1-35/220=1-7/44=37/44。3.鴿巢原理：將113個(gè)子集放入10個(gè)不同的元素（鴿子）中。由鴿巢原理，至少有一個(gè)元素x包含在這113個(gè)子集中的至少?113/10?=12個(gè)子集中。因此，存在至少一個(gè)元素x，使得包含x的子集至少有12個(gè)。這保證了至少有一個(gè)子集包含相同的元素（即元素x）。五、1.歐幾里得算法原理：利用a和b的最大公約數(shù)d等于a和b的余數(shù)r的最大公約數(shù)，即d(a,b)=d(b,r)，且當(dāng)r=0時(shí)，d(a,b)=b。通過不斷用較小數(shù)替換較大數(shù)，直到余數(shù)為0，最終非零余數(shù)即為GCD。*計(jì)算：252÷198=1余54；198÷54=3余36；54÷36=1余18；36÷18=2余0。所以GCD(252,198)=18。2.RSA原理：*密鑰生成：n=p*q=61*53=3233。?(n)=(p-1)(q-1)=60*52=3120。選擇e(1<e<?(n),gcd(e,?(n))=1)，e=7。求d，滿足(d*e)mod?(n)=1，即(d*7)mod3120