2008年同等学力申硕计算机综合试题解析--数学基础

声明：本套试题的填空题解析补充是本人自己做的，其他的答案来自原题评分标准，如发现答案有错误或者不够准确请及时给我留言，如需转载请表明出处。感谢所有提出意见和建议，以及帮助过我的朋友。如果觉得还行，欢迎点赞转发，谢谢！

***马上就考试了，祝大家逢考必过***

一、用逻辑符号形式化下列语句（本大题共 2 小题，每小题 2 分，共 4 分）

1．每个人的指纹都不相同。

解析：设 M(x)：x 是人；N(x, y)：x ≠ y，即 x 与 y 是不同的人；E(x，y)：x 与 y 的指纹相

同。则原句可形式化为以下两种形式之一：

$(\forall x)( \forall y) (M(x)∧M(y)∧N(x, y) \rightarrow ┐E(x, y))$

$(\forall x)( M(x) \rightarrow (\forall y)(M(y)∧N(x, y)\rightarrow ┐E(x, y)))$

说明：如仅缺少 N(x, y)的内容，则只给 1 分

2．自然数不是奇数就是偶数，且奇数不能被 2 整除

解析：设 P(x)：x 是自然数，Q(x)：x 是奇数，R(x)：x 是偶数，D(x)：x 能被 2 整除。

原句可形式化为：

$(\forall x)((P(x)\rightarrow (Q(x)∨R(x))∧(Q(x)\rightarrow ┐D(x)))$

说明：（1）如仅答对部分内容最多给 1 分。

（2）全句必须写成一个式子，且中间用联结词∧联结，否则扣 0.5 分。

二、填空题（本大题共 4 小题，第 1 小题每空 1 分，第 2、3、4 小题每空 2 分，共 10 分）

1．设 A、B 均为有穷集合，A 和 B 的基数分别是 m 和 n（m >0, n >0）。

（1）当 m 和 n 满足 _m = n ______ 时，存在从 A 到 B 的双射函数。

此时共可生成 __m!_____ 个不同的双射函数。

（2）当 m 和 n 满足___ $m \leq n$ ____ 时，存在从 A 到 B 的单射函数。

此时共可生成 _ $A(n,m)$ ______ 个不同的单射函数。

解析：该题请参考同等学力申硕计算机专业--数学公式集合 函数部分

2．已知 5 位老师和 3 位学生围圆桌就座，如果要求学生两两不相邻，则有___1440____ 种就座方案。

解析： 老师围坐一圈的方法有(5-1)!= 4!=24,此时有5个空档可以安排3位学生，这样可以保证学生不相邻，则有 $A(5,3) = 5*4*3 = 60$ , 因此总数为 24*60=1440

3．整除 2310 的正奇数有 ___16____ 个。

解析： 2310的因式分解集合为{1，2，3，5，7，11}，里面除了1以外的数乘积为奇数的集合A={3，5，7，11}，集合A中所有元素出现的次数为0或1，此时有 $2^4 =16$ 种减去全0组合，则有15种，再加上元素1的组合有1种，因此总共有15+1=16种。

4．设图的顶点集合为V(G)={ $v_{1},v_{2},v_{3},v_{4}$ } ，边集合为 E(G)={ $v_{1}v_{2},v_{2} v_{3},v_{3}v_{4},v_{4}v_{1},v_{1}v_{3}$ }。则G 的生成树有 ____8___ 棵。

解析：该题先画图，接着用破圈法变成生成树，删除可以分为两个部分一部分包含边 $v_1v_3$ ，另一部分不包含。包含该边的有 $C_{(4,1)} = 4$ ,不包含的有 $C_{(2,1)}*C_{(2,1)} = 4$ ,因此总共有8棵树。

三、解答题（本大题共 3 小题，第 1、2 小题每题 4 分，第 3 小题 8 分，共 16 分）

1．设 $P↓Q = ┐(P∨Q)$ ，仅用联结词↓分别表示出┐P，P∧Q，P∨Q 。

解析：

（1） $┐P \Leftrightarrow ┐(P∨P) \Leftrightarrow P↓P$ -----------1 分

（2） $P∧Q \Leftrightarrow ┐ (┐P∨┐Q) \Leftrightarrow (┐P)↓(┐Q)\Leftrightarrow (P↓P)↓(Q↓Q)$

（3） $P∨Q \Leftrightarrow ┐ ( ┐(P∨Q)) \Leftrightarrow ┐(P↓Q) \Leftrightarrow (P↓Q)↓(P↓Q)$

如（2）、（3）小题中仅做对一题则给 2 分，（2）和（3）小题都做对则给 3 分。

2．设T 是一棵有 13 个顶点的树，称树中度为 1 的顶点为叶子。如果T 的顶点的度只可能是 1,2,5 且T 恰好有 3 个度为 2 的顶点，那么，T 中有多少个叶子？

解析： 设T 中有 x 个叶子，则T 中有 13 - 3 - x = 10-x 个度为 5 的顶点，

由于树中的边数等于顶点个数减去 1，即边数为 12 -----------2 分

由顶点度数之和等于边数的两倍得 x + 3*2 + 5*(10-x) = 12 * 2 = 24

解得 x = 8，故中有8个叶子。 -----------2 分

3．求 1,4,5,8,9 这五个数字组成的n 位数的个数，要求 4,8 出现的次数均为偶数，而 1,5,9 出现的次数不加限制。

解析：设满足条件的 i 位数的个数为 $a_i$ ，则序列 $a_1,a_2,a_3,...$ 对应的指数型母函数为 $G(x) = (1+x+\frac{x^2}{2!} +\frac{x^3}{3!} +\frac{x^4}{4!} +... )^3(1+\frac{x^2}{2!} +\frac{x^4}{4!} +... )^2$ -----------2 分

由于 $e^x = (1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + .... )$ ,

$e^{-x} = (1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - ....+(-1)^n\frac{x^n}{n!} +...)$

于是 $(1+\frac{x^2}{2!} +\frac{x^4}{4!} +... ) = \frac{e^x + e^{-x}}{2}$ ---------3 分

则 $G(x) = (e^x)^3(\frac{e^x + e^{-x}}{2})^2= e^{3x}(\frac{e^{2x} + 2 +e^{-2x}}{4}) = \frac{1}{4} (e^{5x } + 2e^{ 3x }+ e^{x } ) = \frac{1}{4}\sum_{n=0}^∞ (5^n + 2*3^n + 1 ) \frac{x^n}{n!}$ ---------2 分

故 $a_n = = \frac { 1}{4}(5^n + 2*3^n + 1 )$ ---------1 分

四、证明题（本大题共 2 小题，第 1 小题 4 分，第 2 小题 6 分，共 10 分）

1．设 R 是非空集合 A 上的二元关系，R 满足条件：

（1）R 是自反的；

（2）若<a，b>∈R ∧<a，c>∈R，则<b，c>∈R；

试证明 R 是 A 上的等价关系。

证明：由条件（1），R 已满足自反性。需证明 R 满足对称性和传递性。

1）对于任意的<a，b>，

<a，b>∈R 且由条件（1）

$\Rightarrow$ <a，b>∈R ∧<a，a>∈R -----------1 3分

由条件（2） $\Rightarrow$ <b，a>∈R -----------1 分

所以，R 满足对称性。

2）对于任意的<a，b>，<b，c>

<a，b>∈R ∧<b，c>∈R

由对称性 $\Rightarrow$ <b，a>∈R ∧<b，c>∈R -----------1 分

由条件（2） $\Rightarrow$ <a，c>∈R -----------1 分

所以，R 满足传递性。综合 1），2）可得，R 是 A 上的等价关系。

2．随意地把一个9X3 棋盘的每个方格涂成红色或蓝色，求证：必有两行方格的涂色是一样的。

证明：用红、蓝两色去涂1x3 棋盘，共有 $2^3 = 8$ 种涂色方法。 -----------2 分

设 $a_i (i = 1,2,3,...,8)$ 表示第i 种涂色方法。设 $J$ 是任一个已用红、蓝涂了色的 9x3 棋盘，以 $b_k (k = 1,2,3,...,8,9)$ 表示 $J$ 的第 k 行的涂色方法。设 $B = \{ b_1, b_2, b_3, b_4,...,b_9\}$ 并令 $B_j = \{b \in B 且 b = a_j \} , (j = 1,2,...,8)$ 则

$B_j \subseteq B$ 且 $\bigcup_{j=1}^{8} B_j = B$ -----------2 分

B 中 9 个元素放到 $B_j (j=1,2,...,8)$ 这 8 个抽屉里，由鸽笼原理，必有正整数 $t (1 \leq t \leq 8)$ 使得 $|B_t| \geq 2$ , 即 $B_t$ 中至少有两个元素不妨设 $B_m$ 和 $B_l$ ,这说明在 $J$ 涂色中，棋盘的第 $m$ 行和第 $l$ 行的涂色一样。 -----------2 分