大學(xué)離散數(shù)學(xué)復(fù)習(xí)試題

離散數(shù)學(xué)練習(xí)題目一、選擇題1．設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，以下各式中____D______是錯(cuò)的。A、；B、{6，7，8}A；C、{{4，5}}A；D、{1，2，3}A。2.集合A={a,b,c},B={b,c,e},那么A⊕B=___C___________A.{a,b}B={c}C={a,e}D=φ3.以下語(yǔ)句中，不是命題的是____A_________A.我說(shuō)的這句話是真話；B.理發(fā)師說(shuō)“我說(shuō)的這句話是真話〞；C.如果明天下雨，我就不去旅游；D.有些煤是白的，所以這些煤不會(huì)燃燒；4.下面___D______命題公式是重言式。A.；B.；C.；D、。5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______A.m1∨m2B.m2∨m3C.m0∨m2D.m1∨m36．設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x欽佩y，命題“所有演員都?xì)J佩某些老師〞符號(hào)化為_(kāi)__D______。A、；B、；C、；D、。7.關(guān)于謂詞公式〔x〕(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中錯(cuò)誤的選項(xiàng)是__B_____A．〔x〕的轄域是〔y〕〔P〔x,y〕∧Q(y,z)〕B．z是該謂詞公式的約束變?cè)狢．〔x〕的轄域是P〔x,y〕 D．x是該謂詞公式的約束變?cè)O(shè)，以下各式中____B___________是正確的。A、domSB；B、domSA；C、ranSA；D、domSranS=S。9．設(shè)集合，那么空關(guān)系不具備的性質(zhì)是____A________。A、自反性；B、反自反性；C、對(duì)稱(chēng)性；D、傳遞性。10.集合A，R是A上的關(guān)系，如果R是等價(jià)關(guān)系，那么R必須滿足的條件是__D___A.R是自反的、對(duì)稱(chēng)的B.R是反自反的、對(duì)稱(chēng)的、傳遞的C.R是自反的、對(duì)稱(chēng)的、不傳遞的D.R是自反的，對(duì)稱(chēng)的、傳遞的11.集合A={a,b,c,d},B={1,2,3},那么以下關(guān)系中__ACD______是函數(shù)A.R={(a,1),(b,2),(c,1),(d,2)}B.R={(a,1),(a,2),(c,1),(d,2)}C.R={(a,3),(b,2),(c,1)}D.R={(a,1),(b,1),(c,1),(d,1)}集合RA,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},那么頂點(diǎn)2的入度和出度分別是___D_______A.2,3B.2,4C.3,3D.3,413.設(shè)完全圖Kn有n個(gè)結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)下面條件__C____滿足時(shí)，Kn中存在歐拉回路．A．m為奇數(shù)B．n為偶數(shù)C．n為奇數(shù)D．m為偶數(shù)14.下面表達(dá)正確的選項(xiàng)是____B______A.二部圖是歐拉圖B.二部圖是哈密爾頓圖C.二部圖是平面圖D.二部圖是既不是歐拉圖也不哈密爾頓圖15.某平面圖的頂點(diǎn)數(shù)是12，邊數(shù)是14，那么該平面圖有__D___個(gè)面A.3B.2C.5D.416．設(shè)G是n個(gè)結(jié)點(diǎn)、m條邊和r個(gè)面的連通平面圖，那么m等于___A____。A、n+r-2；B、n-r+2；C、n-r-2；D、n+r+2。17.下面幾種代數(shù)結(jié)構(gòu)中，不是群的是___D____A.<Z,+>B.<Q,+>C.<R,+>D.<N,+>(這里Z，Q，R，N分別表示整數(shù)集、有理數(shù)集、實(shí)數(shù)集、自然數(shù)集，+普通加法)二、問(wèn)答題1.在程序設(shè)計(jì)過(guò)程中，有如下形式的判斷語(yǔ)句：if(a>=0)if(b>1)if(c<0)cout<<a<<b<<c;請(qǐng)將這段程序化簡(jiǎn)，并說(shuō)明化簡(jiǎn)的理由。解：簡(jiǎn)化的程序：if(a>=0&&b>1&&c<0)cout<<a<<b<<c;簡(jiǎn)化理由：設(shè)置命題變量：p:a>=0；q:b>1;r:c<0;s:cout<<a<<b<<c原來(lái)的程序語(yǔ)句表示成命題公式：A=P→(q→(r→s))經(jīng)過(guò)等值演算可得，A與下面的公式是等值的P∧q∧r→s2.集合A={1,2,3,4,5,6,7,8,9}，R={(x,y)|x|y},①證明R是偏序關(guān)系。②寫(xiě)出偏序集〔A，R〕的極小元、極大元；最小元、最大元③寫(xiě)出A的子集B={1,2,3,6}的最小上界、最大下界解：①根據(jù)整除性質(zhì)可知，R滿足自反性，反對(duì)稱(chēng)性，傳遞性。所以R是A上的偏序關(guān)系。②偏序集〔A，R〕的極小元：1，極大元：5,6，7，8，9最小元：1；最大元：無(wú)③子集B={1,2,3,6}的最小上界：6子集B={1,2,3,6}的最大下界：13.(1)m個(gè)男孩子，n個(gè)女孩排成一排，任何兩個(gè)女孩不相鄰，有多少種排法？(n<=m)插空問(wèn)題(2)如果排成一個(gè)園環(huán)，又有多少種排法？解：(1)考慮5個(gè)男孩，5個(gè)女孩的情況男孩的安排方法：_B_B_B_B_B_排列總數(shù)P(5,5)女孩的安排方法：6個(gè)位置安排5個(gè)女孩，排列中數(shù)P(6,5)所以：總的排列方法數(shù)是m!*p(m+1,n)(2)考慮男孩的圓排列情況，結(jié)果是(m-1)!*p(m,n)4.某商家有三種品牌的足球，每種品牌的足球庫(kù)存數(shù)量不少于10只，如果我想買(mǎi)5只足球，有多少種買(mǎi)法？如果每種品牌的足球最少買(mǎi)一只，有多少種買(mǎi)法？解：①這是一個(gè)多重集的組合問(wèn)題類(lèi)別數(shù)是k=3，選取的元素個(gè)數(shù)是r=5多重集組合數(shù)的計(jì)算公式是所以：N=C(3+5-1,5)=c(7,5)=21②可自由選取的球只有2個(gè)k=3,r=2N=C(3+2-1,2)=C(4,2)=65．某軟件公司將職工分為三種崗位。該公司65人，有些職工〔例如工程管理人員、設(shè)計(jì)人員〕可能從事不止一個(gè)崗位的工作。每個(gè)職工至少被分在一個(gè)崗位?，F(xiàn)在軟件設(shè)計(jì)崗位〔崗位A〕〔包括需求分析、概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)等工作〕的人數(shù)是15人，代碼編寫(xiě)崗位〔崗位B〕的人數(shù)是32人，軟件測(cè)試崗位〔崗位C〕的人數(shù)是28人，同時(shí)參加崗位A和崗位B的有12人,同時(shí)參加崗位B和崗位C的有8人,同時(shí)參加崗位A和崗位C組的有3人，問(wèn)，三個(gè)崗位參加的有多少人？解：|A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3設(shè)S表示全班同學(xué)總?cè)藬?shù)，那么|S|=65求：|A∩B∩C|=？根據(jù)容斥原理：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C|因?yàn)槊總€(gè)同學(xué)至少參加一個(gè)小組，所以：|A∪B∪C|=|S|因此：|A∩B∩C|=65-15-32-28+12+8+3=13答：三個(gè)小組都參加的人數(shù)是13人6.證明組合恒等式C(n,r)=C(n-1,r-1)+C(n-1,r)說(shuō)明：也可以直接利用組合演算公式進(jìn)行演算7.求的個(gè)位數(shù)是多少?解：的個(gè)位數(shù)就是mod10的余數(shù)8.圖G有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)的度數(shù)均小于2,問(wèn)G至少有多少個(gè)頂點(diǎn)?解：由握手定理∑d(v)=2m=20，度數(shù)為3的頂點(diǎn)有3個(gè)占去12度，還有8度由其余頂點(diǎn)占有，而由題意，其余頂點(diǎn)的度數(shù)可為0，1，當(dāng)均為1時(shí)所用頂點(diǎn)數(shù)最少，所以應(yīng)有8個(gè)頂點(diǎn)占有此8度，即G中至少有8+4=12個(gè)頂點(diǎn)。9刑偵人員審一件盜竊案時(shí)，已經(jīng)掌握的線索如下：〔1〕甲或乙盜竊了電腦?！?〕假設(shè)甲盜竊了電腦，那么作案時(shí)間不能發(fā)生在午夜前?！?〕假設(shè)乙證詞正確，那么在午夜時(shí)屋里燈光未滅?！?〕假設(shè)乙證詞不正確，那么作案時(shí)間發(fā)生在午夜前。〔5〕午夜時(shí)屋里燈光滅了。請(qǐng)通過(guò)命題邏輯推理，推論出誰(shuí)是真正的盜竊犯？〔寫(xiě)出詳細(xì)的推理步驟〕解設(shè)p：甲盜竊了電腦，q：乙盜竊了電腦，r：作案時(shí)間發(fā)生在午夜前，s：乙證詞正確，t：午夜時(shí)屋里燈光滅了。前提：p∨q，p→~r，s→~t，~s→r，t(7)非p。。。10.插入排序算法的時(shí)間T與數(shù)據(jù)規(guī)模n的遞推關(guān)系如下，求出T與n的顯示關(guān)系表達(dá)式解：令n-k=1，那么k=n-1，所以：答：T與n的顯示關(guān)系是：11.解以下一階同余方程組解：方程組的齊次通解是：60k根據(jù)中國(guó)剩余定理，特解是：是以下同余方程的解即，解得：x=2，即同理可解得：，所以：同余方程組的解是60k12.假設(shè)需要加密的明文數(shù)據(jù)是a=8,選取兩個(gè)素?cái)?shù)p=7,q=19,使用RSA算法：①計(jì)算出密鑰參數(shù)②利用加密算法計(jì)算出密文c③利用解密算法根據(jù)密文c反求出明文a解：①取p=7,q=19;計(jì)算n=p*q=7*19=133計(jì)算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108選取較小的數(shù)w,使w與108互質(zhì),5是最小的,于是w=5計(jì)算d,使d*w≡1(modφ(n)),即d*5mod108=1,取d=65，d*5除以108余數(shù)為1,于是算出d=65至此加密、解密參數(shù)計(jì)算完成：公鑰w=5,n=133.私鑰d=65,n=133.②加密③解密其中，,根據(jù)上述遞推公式可以計(jì)算出：,，……,解密后的明文與原來(lái)的明文是相等的，所以算法正確。13.設(shè)A={1，2，3，4，6，9，12，24},R定義為，〔1〕證明R是一個(gè)等價(jià)關(guān)系；〔2〕寫(xiě)出A的商集；14.基于字典序的組合生成算法問(wèn)題說(shuō)明：假設(shè)我們需要從5個(gè)元素中選取3個(gè)的所有組合，組合個(gè)數(shù)為C〔５，３〕＝１０，按字典序，其具體組合為：123,124,125,134,135,145,234,235,245,345所謂按字典序生成組合，就是當(dāng)前的組合〔例如135〕，求下一個(gè)組合〔例如，145〕。下面給出算法的函數(shù)頭：//數(shù)組s[]:函數(shù)運(yùn)行前，保存當(dāng)前的組合，函數(shù)結(jié)束后，是新生成的下一個(gè)組合//n,r:表示從n個(gè)元素中選取r個(gè)元素的組合voidnext_comb(ints[],intn,intr)解：voidnext_comb(intos[],intn,intr){