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

声明：题目是我从同学分享那获取的，有可能出现抄错题目的情况。试题解析是本人自己做的，再根据教材理论来完成本文编写，符号太多编写工作量大，如发现答案有错误或者不够准确请及时给我留言讨论，如需转载请表明出处。感谢所有提出意见和建议，以及帮助过我的朋友。如果觉得还行，欢迎点赞转发，谢谢！

一、用逻辑符号表达下列语句（每小题 2 分，共 4 分）

1. 所有正数都可以开平方(注：所设论域均为包含一切事物的集合，下同)。

解析：S(x) : x是数，P(x) ：x是正数， Q(x)：x 可以开方

$\forall x ( S(x) \land P(x) \rightarrow Q(x))$

2. 没有最大的自然数。

解析：S(x) : x是数，P(x) ：x是自然数，Q(x,y): y是 x集合中最大的数

$\forall x ┐\exists y (S(x)\land P(x) \land S(y) \land P(y) \rightarrow Q(x,y))$

二、填空题（第1小题2分，其他每小题3分，共14分）

1.如果 $\frac{1}{(1-2x)^2} = \sum\nolimits_{k=0}^∞a_{k} x ^k$ ,则 $a_{k}$ =__ $(k+1)2^k$ _____

解析：该题考的是牛顿二项式扩展公式。 $\frac{1}{(1-2x)^2} = (1-2x)^{-2} = \sum\nolimits_{k=0}^∞ C_{(n+k-1,k)} 2^k x^k ,(n = 2 )$ , $a_k = C_{(2+k-1,k)} 2^k = C_{(k+1,k)}2^k = (k+1)2^k$

2、n 个男同学和 n 个女同学参加舞会，当第一首舞曲响起时，每个男同学要找一位女同学跳舞，n 个男同学一共有__n!_____种方法选择女同学。当第二首舞曲响起时，要求每个人都要更换舞伴，这时 n 个男同学选择女同学的方法数是___ $n!\sum_{i=0}^n (-1)^i \frac{1}{i!}$ ____

解析：第一空，考的是n个那同学的全排列 $A_n = n!$ ，可以这样理解，女生站一排男生站一排一对一，面对面，女生不动，男生全排列去是适配，因此就是n！种了；

第二空，根据题干要求每个人都更换舞伴，因此考的是完全错排， $D_n = n!(1-\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!}...(-1)^n\frac{1}{n!} ) = n!\sum_{i=0}^n (-1)^i \frac{1}{i!}$

3、设 G 是 n 个顶点的简单连同平面图且每个面的度数（也称次数）都是 3，则此图的边数是___3n-6__________.

解析：根据题干中的信息，可以用欧拉公式去解题： v-e+r =2, d/2 = e, 其中 d代表度，v是点数，e是边数，r是面数。而此题v=n，d=3r，代入欧拉公式n-e+r = 2，且 3r/2 = e。r=2e/3 ，代入前式得 n-e+2e/3 = 2, 得e = 3n-6。

4、设 G 是有 n 个顶点的圈，如果 n 是奇数，则 G 的正常边着色数是______3_______.

解析：根据【定理】奇圈和奇数阶轮图都是3-色图，而偶数阶轮图都是4-色图。因此本题为3。

5、设 $a_n$ 满足的递推关系和初始条件分别为 $a_n =3a_{n-1}+1，a_1=2$ ，则 $a_n$ 的精确表达式是____ $\frac{5}{2} 3^{n-1} - \frac{1}{2}$ _________.

解析：利用递推关系公式求解； $a_n =3a_{n-1}+1, a_{n-1} = 3a_{n-2} +1$ ,两试相减得到 $a_n - a_{n-1}=3a_{n-1}-3a_{n-2} \Rightarrow a_n - 4a_{n-1}+3a_{n-2}=0.$ 则此递推关系的特征方程为 $q^2-4q+3=0 \Leftrightarrow (q-1)(q-3)=0 , q_1 = 1,q_2 = 3.$ 特征根无重复根，因此该递推关系的一般式子为 $H_{(n)} = C_1 q_1^n + C_2 q_2^n$ ， $a_1=2, a_2=7$ 代入式子中得到 $C_1,C_2$ 的解，即 $C_1 = - \frac{1}{2 } ，C_2 = \frac{5}{6}$ 代入一般式，因此得， $a_{n} = \frac{5}{2} 3^{n-1} - \frac{1}{2}$

三、计算题（共 12 分）

1. (3 分) 设集合 A={1,2} , B={a,b,c} 。

(1)问从 A 到 B 有多少个单射函数。

(2)试写出从 A 到 B 所有非单射的函数。

解析：（1） |A|=2，|B|=3，2<3, 则从A到B的单射函数个数为 $A_{(3,2)}=3*2=6$ ,单射函数可以记为： $f_1 = \{ <1,a>,\},f_2 = \{ ,\},f_3 = \{ ,\}$

$f_4 = \{ <1,b>,\},f_5 = \{ ,\},f_6 = \{ ,\}$

(2) A到B的所有函数个数为 $|B|^{|A|} = 3^2 = 9$ ,单射函数有6个，因此剩下还有3个非单射函数：

$f_7 = \{ <1,a>,\},f_8 = \{ ,\},f_9 = \{ ,\}$

2. (3 分)已知集合 A={1,2,…,6}上的等价关系 R 定义为： R= $I_{A}$ ∪ {<1,5>,<5,1>,<2,3>,<3,2>,<2,6>,<6,2>,<3,6>,<6,3>} 求出由 R 诱导的 A 的划分(即由 R 的商集诱导的划分)。

解析：【定理】非空集合S关于它上面的任何等价关系R的商集具有下列特点：S/R ≠ ∅；若A∈S/R，则A ≠ ∅；若A，B∈S/R，A≠B，则A∩B = ∅.

【定义】设A为非空集合，若存在A的一个子集族 $A ^ `$ 满足： $∅ \notin A ^ `；\cup A ^ ` = A；\forall x,y \in A ^ ` \land x\neq y \rightarrow x \cap y = ∅$ , 则称 $A ^ `$ 是A的一个划分， $A ^ `$ 中元素称为划分块。

$R=I_{A} ∪ \{<1,5>,,,,,,, \}$ ， $A/R = \{\{1,5\},\{2,3,6\},\{4\}\}$

因此R 诱导的 A 的划分为 $\{\{1,5\},\{2,3,6\},\{4\}\}$ 。

3. (6 分)已知 A 是由 54 的所有因子组成的集合，设%为 A 上的整除关系。

(1)画出偏序集<A，%>的哈斯图。

(2)确定 A 中最长链的长度，并按字典序写出 A 中所有最长的链。

(3)A 中元素至少可以划分成多少个互不相交的反链，并完整写出这些反链。

解析：（1） 54的整除所有因子集合A = {1，2，3，6，9，18，27，54}，哈斯图如下：

哈斯图

（2）在哈斯图中显示出来最长链长度为5，它们分别如下：

$B_1 = \{1,2,6,18,54\} ; B_2 = \{1,3,6,18,54\} ; B_3 = \{1,3,9,18,54\} ; B_4 = \{1,3,9,27,54\} ;$

（3）反链的定义 $\forall x \forall y(x \in B \land y \in B \land x \neq y ) \rightarrow$ x与y不可比。由【定理】设 $<A, \preceq >$ 为一个偏序集，若A的最长链的长度为n，则A存在n个划分块的划分，每个块都是反链。因此该题有5个互不相交的反链，这些反链是{{1}，{2，3}，{6，9}，{18，27}，{54}}。

四、解答题（每小题 5 分，共 10 分）

1、求方程 $t_1+t_2+t_3+t_4=20$ 整数解的个数，其中 $t_1$ ≥ 3，t2 $t_2$ ≥ 1， $t_3$ ≥ 0， $t_4$ ≥ 5 .

解析：该题主要考察的是组合的母函数，解的个数即 $x^{20}$ 的系数。则本题的母函数表示如下： $G(x) = (x^3+x^4+x^5+...)(x+x^2+x^3+...)(1+x+x^2+...)(x^5+x^6+x^7+...)$

$= x^3(1+x+x^2+...)x(1+x+x^2+...)(1+x+x^2+...) x^5(1+x+x^2+...)=x^9(1+x+x^2+...)^4 =x^9(1-x)^{-4}$

$=x^9 \sum_{k=0}^ ∞ C_{(4+k-1,k)}x^k =x^9 \sum_{k=0}^ ∞ C_{(3+k,k)}x^k =x^9 \sum_{k=0}^ ∞ C_{(3+k,3)}x^k$ ，要求 $x^{20}$ 的系数，即k=20-9=11， $C_{(14,3)} = \frac{14*13*12}{1* 2*3 } = 364$ ，即解的个数为364个。

2.设s={ $∞\cdot 2,∞\cdot 4,∞\cdot 5,∞\cdot 7,∞\cdot 9$ } 是给定的重集，其中2，4，5，7，9是s中的五个不同元素，且每个元素在集合中可以有无穷多。设 $h_n$ 表示从s中取n个元素（可以重复取）且要求2和4出现偶数次的排列数，求 $h_n$

解析：该题考的是重集排列问题，即考指数型母函数。母函数表示如下： $G_{(x)} = (1+\frac{x}{1!} +\frac{x^2 }{2!} +\frac{x^3 }{ 3!} +... ) ^3 (1 +\frac{x^2 }{2!} +\frac{x^4 }{ 4!} +... ) ^2$

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

$= \frac{1}{4} (e^{5 x}+ 2e^{ 3x } +e^{x})=\frac{1}{4}\sum_{k=0}^∞(5^k+2*3^k + 1) \frac{x^k}{k!}$

则此时 $a_{n} = \frac { 1 }{ 4 }(5^n + 2*3^n + 1)$ 即该题的排列数为 $\frac{1}{4}(5^n+2*3^n + 1)$ 。