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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上離散數(shù)學(xué)練習(xí)題目一、選擇題1設(shè)A=1，2，3，4，5，6，7，8，下列各式中_D_是錯(cuò)的。A、； B、6，7，8A；C、4，5A； D、1，2，3A 。2.已知集合A=a,b,c,B=b,c,e,則 AB=_C_ A.a,b B=c C=a,e D= 3.下列語句中，不是命題的是_A_A.我說的這句話是真話； B. 理發(fā)師說“我說的這句話是真話”； C. 如果明天下雨，我就不去旅游； D. 有些煤是白的，所以這些煤不會燃燒；4.下面_D_命題公式是重言式。 A. ； B. ；C.； D、。5.公式(pq)(pq)的主析取范式是_B_ A.m1m2 B.m2m3 C.m

2、0m2 D. m1m3 6設(shè)L(x)：x是演員，J(x)：x是老師，A(x , y)：x欽佩y，命題“所有演員都?xì)J佩某些老師”符號化為_D_。A、； B、 ；C、； D、 。7.關(guān)于謂詞公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中錯(cuò)誤的是_B_ A（x）的轄域是（y）（P（x,y）Q(y,z)） Bz是該謂詞公式的約束變元 C（x）的轄域是P（x,y） Dx是該謂詞公式的約束變元8 設(shè)，下列各式中_B_是正確的。A、domSB ； B、domSA； C、ranSA； D、domS ranS = S。9設(shè)集合，則空關(guān)系不具備的性質(zhì)是_A_。A、自反性； B、反自反性

3、； C、對稱性； D、傳遞性。10. 集合A，R是A上的關(guān)系，如果R是等價(jià)關(guān)系，則R必須滿足的條件是_D_ A. R是自反的、對稱的 B. R是反自反的、對稱的、傳遞的 C. R是自反的、對稱的、不傳遞的 D.R是自反的，對稱的、傳遞的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)12.已知集合A=1,2,3,4, RA,且R=(1,2),(1,2)

4、,(2,1),(2,2),(2,3),(2,4),(3,4),(4,1),則頂點(diǎn)2的入度和出度分別是_D_A.2,3 B.2,4 C.3,3 D.3,4 13.設(shè)完全圖Kn有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng)下面條件_C_滿足時(shí)，Kn中存在歐拉回路 Am為奇數(shù) Bn為偶數(shù) Cn為奇數(shù) Dm為偶數(shù)14.下面敘述正確的是_B_ A.二部圖是歐拉圖 B. 二部圖是哈密爾頓圖 C. 二部圖是平面圖 D. 二部圖是既不是歐拉圖也不哈密爾頓圖15.已知某平面圖的頂點(diǎn)數(shù)是12，邊數(shù)是14，則該平面圖有_D_個(gè)面 A. 3 B.2 C.5 D.416設(shè)G是n個(gè)結(jié)點(diǎn)、m條邊和r個(gè)面的連通平面圖，則m等于_A_。A、n

5、+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2 。17. 下面幾種代數(shù)結(jié)構(gòu)中，不是群的是_D_ A. B. C. D. (這里Z，Q，R，N分別表示整數(shù)集、有理數(shù)集、實(shí)數(shù)集、自然數(shù)集，+普通加法)二、問答題1.在程序設(shè)計(jì)過程中，有如下形式的判斷語句： if(a=0) if(b1) if(c0) coutab=0 & b1 & c0) coutab=0；q:b1;r:c0;s:coutabc 原來的程序語句表示成命題公式：A=P(q(rs) 經(jīng)過等值演算可得，A與下面的公式是等值的Pqrs2.集合A= 1, 2, 3, 4, 5, 6, 7, 8, 9 ，R=(x,y)|

6、x|y,證明R是偏序關(guān)系。寫出偏序集（A，R）的極小元、極大元；最小元、最大元寫出A的子集B=1,2,3,6的最小上界、最大下界解：根據(jù)整除性質(zhì)可知，R滿足自反性，反對稱性，傳遞性。所以R是A上的偏序關(guān)系。偏序集（A，R）的極小元：1，極大元：5, 6，7，8，9 最小元：1； 最大元：無子集B=1,2,3,6的最小上界：6 子集B=1,2,3,6的最大下界：13.(1) m個(gè)男孩子，n個(gè)女孩排成一排，任何兩個(gè)女孩不相鄰，有多少種排法？ (n=m) 插空問題 (2)如果排成一個(gè)園環(huán)，又有多少種排法？ 解：(1) 考慮5個(gè)男孩，5個(gè)女孩的情況男孩的安排方法： _B_B_B_B_B_ 排列總數(shù)P(

7、5,5)女孩的安排方法：6個(gè)位置安排5個(gè)女孩，排列中數(shù) P(6,5)所以：總的排列方法數(shù)是 m!*p(m+1,n)(2) 考慮男孩的圓排列情況，結(jié)果是 (m-1)!*p(m,n)4.某商家有三種品牌的足球，每種品牌的足球庫存數(shù)量不少于10只，如果我想買5只足球，有多少種買法？如果每種品牌的足球最少買一只，有多少種買法？解：這是一個(gè)多重集的組合問題 類別數(shù)是k=3，選取的元素個(gè)數(shù)是 r=5 多重集組合數(shù)的計(jì)算公式是 所以：N=C(3+5-1,5)=c(7,5)=21可自由選取的球只有2個(gè) k=3,r=2 N=C(3+2-1,2)=C(4,2)=65某軟件公司將職工分為三種崗位。該公司65人，有些

8、職工（例如項(xiàng)目管理人員、設(shè)計(jì)人員）可能從事不止一個(gè)崗位的工作。每個(gè)職工至少被分在一個(gè)崗位?，F(xiàn)在軟件設(shè)計(jì)崗位（崗位A）（包括需求分析、概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)等工作）的人數(shù)是15人， 代碼編寫崗位（崗位B）的人數(shù)是32人，軟件測試崗位（崗位C）的人數(shù)是28人， 同時(shí)參加崗位A和崗位B的有12人, 同時(shí)參加崗位B和崗位C的有8人, 同時(shí)參加崗位A和崗位C組的有3人，問，三個(gè)崗位參加的有多少人？解： 已知 |A|=15，|B|=32，|C|=28， |AB|=12，|BC|=8，|AC|=3 設(shè)S表示全班同學(xué)總?cè)藬?shù)，則 |S|=65 求：|ABC|=？ 根據(jù)容斥原理： |ABC|=|A|+|B|+|C|-

9、|AB|-|BC|-|AC|+|ABC|所以|ABC|=|ABC|-|A|-|B|-|C|+|AB|+|BC|+|AC|因?yàn)槊總€(gè)同學(xué)至少參加一個(gè)小組，所以：|ABC|=|S|因此：|ABC|=65-15-32-28+12+8+3=13答：三個(gè)小組都參加的人數(shù)是13人6.證明組合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)說明：也可以直接利用組合演算公式進(jìn)行演算7.求的個(gè)位數(shù)是多少?解：的個(gè)位數(shù)就是 mod 10的余數(shù) 8. 已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小于2, 問G至少有多少個(gè)頂點(diǎn)?解：由握手定理d(v)=2m=20，度數(shù)為3的頂點(diǎn)有3個(gè)占去12度，

10、還有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） 甲或乙盜竊了電腦。（2） 若甲盜竊了電腦， 則作案時(shí)間不能發(fā)生在午夜前。（3） 若乙證詞正確， 則在午夜時(shí)屋里燈光未滅。（4） 若乙證詞不正確， 則作案時(shí)間發(fā)生在午夜前。（5） 午夜時(shí)屋里燈光滅了。 請通過命題邏輯推理，推論出誰是真正的盜竊犯？（寫出詳細(xì)的推理步驟）解 設(shè)p： 甲盜竊了電腦， q： 乙盜竊了電腦， r： 作案時(shí)間發(fā)生在午夜前，s： 乙證詞正確， t：午夜時(shí)屋里燈光滅了。 前提：

11、pq， pr， st， sr， 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ù)中國剩余定理，特解是：是下列同余方程的解即，解得：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

12、) =(p-1)*(q-1)=(7-1)*(19-1)=108選取較小的數(shù)w,使w與108互質(zhì), 5是最小的,于是w=5計(jì)算d,使d*w1(mod (n),即d*5 mod 108=1,取d=65，d*5除以108余數(shù)為1, 于是算出d=65至此加密、解密參數(shù)計(jì)算完成：公鑰w=5,n=133. 私鑰d=65,n=133. 加密 解密 其中，, 根據(jù)上述遞推公式可以計(jì)算出：,，, 解密后的明文與原來的明文是相等的，所以算法正確。13.設(shè)A=1，2，3，4，6，9，12，24,R定義為，（1）證明R是一個(gè)等價(jià)關(guān)系； （2）寫出A的商集； 14.基于字典序的組合生成算法問題說明：假設(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è)元素的組合void next_comb(int s,int n,int r)解：void next_comb(into s,int n,int r)int j