大学离散数学复习试题

离散数学练习题目一、选择题1设A=1，2，3，4，5，6，7，8，下列各式中_D_是错的。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. 理发师说“我说的这句话是真话”； C. 如果明天下雨，我就不去旅游； D. 有些煤是白的，所以这些煤不会燃烧；4.下面_D_命题公式是重言式。 A. ； B. ；C.； D、。5.公式(pq)(pq)的主析取范式是_B_ A.m1m2 B.m2m3 C.m0m2 D. m1m3 6设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)） Bz是该谓词公式的约束变元 C（x）的辖域是P（x,y） Dx是该谓词公式的约束变元8 设，下列各式中_B_是正确的。A、domSB ； B、domSA； C、ranSA； D、domS ranS = 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)12.已知集合A=1,2,3,4, RA,且R=(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1),则顶点2的入度和出度分别是_D_A.2,3 B.2,4 C.3,3 D.3,4 13.设完全图Kn有n个结点(n2)，m条边，当下面条件_C_满足时，Kn中存在欧拉回路 Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数14.下面叙述正确的是_B_ A.二部图是欧拉图 B. 二部图是哈密尔顿图 C. 二部图是平面图 D. 二部图是既不是欧拉图也不哈密尔顿图15.已知某平面图的顶点数是12，边数是14，则该平面图有_D_个面 A. 3 B.2 C.5 D.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. B. C. D. (这里Z，Q，R，N分别表示整数集、有理数集、实数集、自然数集，+普通加法)二、问答题1.在程序设计过程中，有如下形式的判断语句： if(a=0) if(b1) if(c0) coutab=0 & b1 & c0) coutab=0；q:b1;r:c0;s:coutabc 原来的程序语句表示成命题公式：A=P(q(rs) 经过等值演算可得，A与下面的公式是等值的Pqrs2.集合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=2 N=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， |AB|=12，|BC|=8，|AC|=3 设S表示全班同学总人数，则 |S|=65 求：|ABC|=？ 根据容斥原理： |ABC|=|A|+|B|+|C|-|AB|-|BC|-|AC|+|ABC|所以|ABC|=|ABC|-|A|-|B|-|C|+|AB|+|BC|+|AC|因为每个同学至少参加一个小组，所以：|ABC|=|S|因此：|ABC|=65-15-32-28+12+8+3=13答：三个小组都参加的人数是13人6.证明组合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)说明：也可以直接利用组合演算公式进行演算7.求的个位数是多少?解：的个位数就是 mod 10的余数 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：午夜时屋里灯光灭了。 前提： pq， pr， st， sr， 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*w1(mod (n),即d*5 mod 108=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个元素的组合void next_comb(int s,int n,int r)解：void next_comb(into s,int n,int r)