《离散数学模拟题和答案》由会员分享，可在线阅读，更多相关《离散数学模拟题和答案（5页珍藏版）》请在金锄头文库上搜索。
1、复习要点1.加法原理与乘法原理2.圆排列公式与应用3.鸽巢原理及其应用4.容斥原理及其应用（错位排列数Dn）5.S(n，k)的意义及计算。6.B(n，k) 的意义及计算。7.数值函数的性质及其计算。8.利用生成函数求解。9.建立递推关系式。10. 求解递推关系式。11. P lya 定理的应用。复习题一1. 6 个男孩和6 个女孩围成一个圆圈，若男孩和女孩交替就坐，有多少种方法？2. 考试中有 15 个判断“对”或“错”的答题。允许学生对某些题不回答，有多少种回答方法？3. （1）在一边长为1 的等边三角形中任取5 个点，则其中必有两点，该两点的距离至多为21；（2）在一边长为1 的等边三角形
2、中任取10 个点，则其中必有两点，该两点的距离至多为31；（3）确定 mn，使得在一边长为1 的等边三角形中任取mn个点， 则其中必有两点，该两点的距离至多为 n1。4. 一位学生有37 天时间准备考试，根据以往的经验，他知道至多只需要60 个小时的复习时间，他决定每天至少复习1 小时。证明：无论他的复习计划怎样，在此期间都存在连续的一些天，他正好复习了13 个小时。5. 有 8 个人寄存帽子，问各有多少种方法交还帽子使得(1) 没有一个人得到自己的帽子。(2) 至少有一个人得到自己的帽子。(3) 至少有两个人得到自己的帽子。6. 已知数值函数a：ai=60525120030iiiib：bi=
3、1201111.000iii试求： a+b，a?b，S3a，S-2b， a，a*b。7. 一个质点在水平方向上运动，每秒中走过的距离等于前一秒中走过距离的两倍，已知起始位置为3，第3 秒钟时的位置是10，试求第i 秒钟时质点的位置。8. 已知常系数线性递推关系：c0ai+ c1ai-1+ c2ai-2=6 的解为 a：ai=3i+4i+2 (i0)，试求 c0，c1和 c2。9. 设 ai是如 1，1，2，3，5，6，13，21，34，, 的Fibonacci 数列，证明：（1）a0+ a2+,+a2i= a2i+1 （2）a1+ a3+,+a2i-1= a2i-1 （3）a02+ a12+,
4、+ ai2=a i ai+110. 将 n 个不同的球放入r 个不同的盒子里，盒内的球是有序的，求其分配方案数。11. 有 n 个不同的整数， 从中取出两组来， 要求第一组里的最小数大于第二组里的最大数，问有多少种方案？答案一1 解. 5！ 6！2 解. 3153 解. （1）（2）（3）mn=n2+1 4 解. 设 ai（1 i37）表示第 i 天复习的累计小时数，则显然有1a1a2,a3760 （1）于是14a1+13a2+13,a37+1377 （2）由（ 1）和（ 2）可知1a1，a2，, ， a37，a1+13， a2+13，, a37+13 73 （3）即 74 个数只有73 个值
5、，故根据鸽巢原理可知数列（3）中至少有两个数是相等的，又因为数列（1）和（ 2）都是严格单增的，所以应有1i，j37，使ai=aj13 即ai- aj=13 因此从第j1 天开始到第i 天为止，该学生恰好复习13 小时。5 解. (1) D8。(2)8！- D8。 (3) 8！ - D8 - 8 D7。6 解. a+b=1201161 .0521 .511 .20030iiiii，a?b=60525.01200iiii，S3a=90855420330200iiiii，S-2b= 100901.0ii， a=6055420115010iiiii，a*b=170165 .0151145 .1132
6、124116755 .64635.5251300iiiiiiiiiiiii。7 解.a0=3，a3=10， a1= a0+s，a2= a1+2s，a3= a2+4s， a3= a0+7s，解得 s=1，ai= ai-1+2i-1= a 0+20+21+2i-1=2i+2 8 解. 特征方程c02+ c 1+ c2=(-3)( -4), 解得： c0=1，c1=-7，c2=12 9 解.（ 1）a0+ a2+,+a2i= a1+ a3- a1+ a5- a3+,+ a2i+1 -a2i-1= a2i+1（2）a1+ a3+,+a2i-1= a4-1+ a6- a4+,+ a2i -a2i-2=
7、a2i-1 （3）a02+ a12+,+ ai2= a a 0+ a1(a2-a0)+ a2(a3-a1),+ ai(ai+1- ai-1)=ai ai+110 解.n!C(n+r-1,n) 11 解.(n-2)2n-1+1 复习题二1. 设平面上有25 个点，其中任何3 点都不共线，试问平面上确定多少直线和三角形？2. 一个徒步旅行的人用10 小时走 45 公里，已知他第一小时走6 公里，最后一小时走3 公里，试证他必须在某相邻的两小时内至少走9 公里。3. 已知12,4, 1, 0)2(032102211 aaaaiacacaiii试求 ai。4. 把 4 个球 a，a，b，b 放入 3
8、个不同的盒子里，求分配方案数。若不允许有空盒，问有多少种分配方案？5. i 位三进制数中，没有1 出现在任何2 的右边的序列的数目记为ai，求 ai满足的递推关系。6. 已知 S= ? e1，? e2，? e3，? e4，数值函数a：ai分别表示满足下列条件的S的 i 组合数，试分别求出生成函数A(z)：（1）每个 ei出现奇数次；（2）每个 ei出现 3 的倍数次；（3）e1不出现， e2至多出现一次；（4）e1出现 1 次、 3 次或 5 次， e2出现 2 次、 4 次或 6 次；（5）每个 ei至少出现10 次。7. 用红、 白和蓝三种颜色给1i 棋盘上的方格着色，设 ai表示没有两个
9、相邻的方格都着红色的方案数，试建立 ai的递推关系，并求出ai的表达式。8. 求下列递推关系的一个特解（1）ai- 4ai-1+4ai-2=2i(i0) （2）ai- 2ai-1=7i2(i0) 9. 在无限多红球、黄球、绿球和白球中选i 个球，使满足“红球是偶数个，黄球是奇数个”，令 a：ai表示上述取球方式的组合函数。（1）求 a 的生成函数A(z)；（2）写出 a 的表达式；（3）计算 a23。10. 在 102和 106之间有多少个整数，其各位数字之和等于5？答案二1.解：因为任何3 点都不共线，故可以确定C(25，2)条直线和C(25， 3)个三角形。2.解：设 ai表示第 i 小时
10、走的路程， 则 （a1+a2） ，（ a2+a3） ， ，（a9+a10） 共 9 个数，他们相加等于45+45-6-3=81 。则由鸽巢原理至少存在一个数大于等于9，不可能都小于9。3.解：将 a0,a1,a2,a3代入，解得c1=-4,c2=4。递推方程为：ai-4ai-1+4ai-2=0。特征方程为：2-4 +4=0，解得特征根：1=2=2。所以数值函数ai =( 0i+ 1)2i, 解得 0=0.5; 1=0所以 ai =0.5i2i= i2i-14.解： 66=36；125.解： ai=2ai-1+2i-16.解： （1） ( z+z3+z5+ )4=(z/(1-z2)4（2）( 1+z3+z6+)4=(1/(1-z3)4（3）( 1+z) (1+z+z2+ )2=( 1+z)/(1-z)2（4）( z+z3+z5) ( z2+z4+z6) (1+z+z2+ )2（5）(z10+ z11 +z12+)4=(z10/(1-z)47.解： ai=2ai-1+ 2ai-2 初值 a1=3，a2=8 10.解：方程x1+x2+,+x6= 5 的非负整数解的个数为：C(n+r-1,n)= C(5+6-1,5)=252 ； 方程x5+x6= 5 的非负整数解的个数为：C(n+r-1,n)= C(5+2-1,5)=6 ；所以所求结果为：252-6=246.
