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