大学离散数学复习试题

1离散数学练习题目一、选择题1．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是错的。A、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.RQP；B.)()(QPRP；C.)()(RQQP；D、))()(())((RPQPRQP。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、)),()((yxAxLx；B、))),()(()((yxAyJyxLx；C、)),()()((yxAyJxLyx；D、)),()()((yxAyJxLyx。7.关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是__B_____A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）2B．z是该谓词公式的约束变元C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元8．设BAS，下列各式中____B___________是正确的。A、domSB；B、domSA；C、ranSA；D、domSranS=S。9．设集合X，则空关系X不具备的性质是____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)}已知集合RA,且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.二部图3,3K是欧拉图B.二部图3,3K是哈密尔顿图C.二部图3,3K是平面图3D.二部图3,3K是既不是欧拉图也不哈密尔顿图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(b1)if(c0)coutabc;请将这段程序化简，并说明化简的理由。解：简化的程序：if(a=0&&b1&&c0)coutabc;简化理由：设置命题变量：p:a=0；q:b1;r:c0;s:coutabc原来的程序语句表示成命题公式：A=P→(q→(r→s))经过等值演算可得，A与下面的公式是等值的P∧q∧r→s42.集合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多重集组合数的计算公式是),1()!1(!)!1(rrkCkrkrN所以：N=C(3+5-1,5)=c(7,5)=21②可自由选取的球只有2个k=3,r=2N=C(3+2-1,2)=C(4,2)=655．某软件公司将职工分为三种岗位。该公司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.求2812的个位数是多少?解：2812的个位数就是2812mod10的余数610mod810mod)10mod2(10mod210mod)10mod12(10mod124477*4282868.已知图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的显示关系表达式0)1(1)1()(TnnTnT7解：2)1()(k)2(1-)(12)(123)3(12)2(1)1()(kkknknTknknTnnknknTnnnnTnnnTnnTnT令n-k=1，那么k=n-1，所以：2)1(2)1(02)1()1()(nnnnnnTnT答：T与n的显示关系是：2)1()(nnnT11.解下列一阶同余方程组)5mod(3)4mod(2)3mod(1xxx解：已知5,4,3m;3,2,1321321mmaaa方程组的齐次通解是：kLcmkx6)3,2,1(60k根据中国剩余定理，特解是：)mmod()mmod()mmod(3133321222111110MMaMMaMMax12,15,20213312321mmMmmMmmM111mmodM是下列同余方程的解)m(mod111xM即)3(mod120x，解得：x=2，即211M同理可解得：312M，313M8所以：5860mod23860mod)1089040(60mod312331522201mmod)mmod()mmod()mmod(3133321222111110）（MMaMMaMMax同余方程组的解是5860kxxx60k12.假设需要加密的明文数据是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.②加密50133mod)113*64(133mod))133mod8(*)133mod8((133mod8mod325nmcw③解密133mod50mod65ncad60AAa其中，500A,21)(iiAA根据上述递推公式可以计算出：106133mod5021A,64133mod10622A106133mod6423A，……,64133mod10626A8133mod)64*50(60AAa解密后的明文与原来的明文是相等的，所以算法正确。913.设A={1，2，3，4，6，9，12，24},R定义为{(,)|ab(mod3)}Rab，（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