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

第一部分数学基础课程

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

（共40 分）

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

1. 有些人运气好，但并非所有人都运气好。

解析：P(x) : x 是人， Q(x)： x运气好， R(x,y)： $x \neq y$

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

2. 不管黄狗还是花狗，能够看家护院就是好狗。

解析：P(x) : x 是狗， Q(x)： x是黄色， R(x)： x是花色，S(x) ：x看家护院，T(x)：x是好狗

$\forall x P(x) \land (Q(x) \lor R(x)) \land S(x) \rightarrow T(x)$

二、填空题（每小题2 分，共12 分）

1. 设A ={1,2,3,4}, B ={a,b,c}，从A 到B 不同的二元关系共有_4096_个。从A 到B 不同的函数共有__81_ 个。

解析：第一空|A| = 4, |B| = 3,因此A到B的不同二元关系个数为 $2^{|A|*|B|} = 2^{12}$ =1024*4=4096

第二空从A到B不同的函数个数为 $|B|^{|A|}= 3^4=81$

2. 设 |A| = n（即集合 A 的基数为 n），问在 A 上有_ $2^{ \frac { n+n^2 }{2 }}$ __ 个不同的对称关系。

解析：以矩阵来解析方便理解，以对角线分开，对角线以下或以上包括对角线的元素个数为 $\frac{(1+n)*n}{2} = \frac{n+n^2}{2}$ , 因此，此时的对称关系有 $2^{ \frac { n+ n^2 }{ 2 }}$ 个。

3．对 $（2x_1-3x_2 + x_3 )^6$ 进行展开合并同类项后， ${x_1}^3 x_2 {x_3}^2$ 的系数是 __-1440_ 。

解析：【定理】设n是正整数，则对一切实数 $x_1,x_2,x_3,...,x_t$ 则有 $(x_1+x_2+...+x_t) = \sum\nolimits_{} (_{n_1 n_2 ...n_t}^{n} ) {x_1}^{n_1}{x_2}^{n_2}...{x_t}^{n_t} =\sum\nolimits_{} ( \frac{n!}{n_1!*n_2! ...n_t! } ) {x_1}^{n_1}{x_2}^{n_2}...{x_t}^{n_t}$ ,因此原题的系数为 $\frac{6 !}{3!*1! *2! }(2^3 * (-3)^1* 1^2 ) = 60*8*(-3) = -1440$

4. 从 m 个人中选取 n 个人（n≤m）围成一个圆桌就座，则不同的就座方法数是 $\frac{m!}{(n(m-n)!) }$ 。

解析：先从m中选取n个人，有 $C_{(m,n)} = \frac{m!}{n!(m-n)!}$

接着n个人围成一圈排列为 $Q(n) = (n-1)!$

因此总排列数为： $C_{(m,n)} *Q_{(n) } = \frac{m!}{n!(m-n)!} * (n-1)! = \frac{m!}{n (m-n)!}$

5. 设 G 是顶点个数为 n，边数为 e，连通分支数为 k 的简单图，T 是包含 G 的所有顶点的森林，则 G 的不在 T 中的边有 __ e+k-n__ 条。

解析：分支数为k的简单图，即有k棵树，因此整个森林边条数为 $(n_1-1)+(n_2-1)+...+(n_k -1) = n-k, (n_1+n_2+...+n_k = n)$

则该题中G 的不在 T 中的边有 e-n+k条边。

6. 设 u,v 是图 G 的两个不邻接的顶点，S 是图 G 的顶点割集，且 u,v 是属于 G—S 的两个不同的连通分支，称 S 为一个 uv 分离集。设最小的 uv 分离集中所含顶点的个数为 a，且 G 中从 u 到 v 内部不相交的路径的最大条数为 b ，则 a 和 b 满足的关系为(a=b) 。

解析：（仅供参考）在无向连通图 G=(V,E)中：若对于x∈V，从图中删du去节点x以及所有与x关联的边之后， G分裂成两个或两个以上不相连的子图，则称x为G的割点。简而言之，割点是无向连通图中的一个特殊的点，删去中这个点后，此图不再连通，而所以满足这个条件的点所构成的集合即为割点集合。根据Menge定理，图的连通度为k，则任意点间必有k条不相交路径。题中a即|S|，G中从u到v内部不相交路径最大条数b，因此要满足a=b。

三、计算题（每个问题4 分，共8 分）

设 $a_1,a_2,a_3,a_4,a_5,a_6,a_7$ 是 7 个互不相同的非零实数， 这七个数的全排列中， 数 $a_i（i=1, …,7）$ 的原来位置是指第 i 个位置。求这七个数的全排列中：

（1） $a_1,a_3,a_5,a_7$ 都不在原来的位置上，而 $a_2,a_4,a_6$ 都在原来位置上的排列数目。

（2） $a_2,a_4,a_6$ 都不在原来位置上的排列数目。

解析：知识点是完全错排，用容斥原理来推断。

(1) $a_1,a_3,a_5,a_7$ 完全错排 $D_4 =4!(1-\frac{1}{1!} + \frac{1}{2!} -\frac{1}{3!} + \frac{1}{4!}) = 4*3- 4 +1 =9$

(2) 用A,B,C表示 $a_2,a_4,a_6$ 都在原来位置上的排列集合，都不在原位即 $| \bar { A } \cap \bar{ B } \cap \bar{ C } | = |S| -|A \cup B \cup C|$

$= |S| -(|A| + |B| + |C| - |A \cap B| - |A \cap C| - |C \cap B| + |A \cap B \cap C|)= 7! - (3*6! - 3*5! +4!)$

$=7! -76*4! = 134 * 4! = 3216$

四、证明题（第1，2 小题各4 分，第3 小题8 分，共16 分）

1．下列公式是否正确？如正确请证明，如错误试举出反例。(∀x) (∀y) (P(x)∧P(y) →Q(x,y)) =¬ (∃x) (∃y) (P(x)∧P(y)∧¬Q(x,y))

解析：公式正确，(∀x) (∀y) (P(x)∧P(y) →Q(x,y)) = (∀x) (∀y) ┐(P(x)∧P(y) ）∨Q(x,y)

=(∀x) (∀y) ┐((P(x)∧P(y) ）∧ ┐Q(x,y)) =(∀x) (∀y) ┐(P(x)∧P(y) ∧ ┐Q(x,y))

=(∀x)┐ (∃y) (P(x)∧P(y) ∧ ┐Q(x,y))

=┐(∃x) (∃y) (P(x)∧P(y) ∧ ┐Q(x,y)) ,得证。

2．用“≈”表示等势，试证明(0,1] ≈ (a, b] (a, b∈R, a < b，R 为实数集)。

解析：只需找到集合(0,1]到(a,b]之间的一个双射函数 $f$ 证明即可，该函数满足定义域为(0,1],值域满足(a,b],可设 $f(x) = kx+i , f(0) = a, f(1) = b.$ 可以求解出 i = a, k = b-a 求解得 $f(x) = (b-a)x+a$ ，因此得证(0,1] ≈ (a, b]

3．设 $\{ a_1, a_2, …, a_n… \}$ 满足 $𝒂_𝒏 = \sum_{k=1}^{𝒏−𝟏} 𝒂_𝒌𝒂_{𝒏−𝒌}$ ,且 $\{ a_1, a_2, …, a_n… \}$ 的母函数为 $A(x) = \sum_{n \geq 1}^{} 𝒂_nx^n$ , $a_1 = 1$

（1）（4 分）证明 $A^2(x) - A(x) + x = 0$

（2）（4 分）证明 $a_n = \frac{1}{n} {( _{n-1} ^{2n-2})}$ ，n≥1，其中 ${( _{n-1} ^{2n-1})}$ 表示从 2n-2 个数中取出 n-1 个的组合数。

解析：(1) $A(x) = \sum_{n \geq 1}^{} 𝒂_nx^n$ ，则 $A^2(x) = (\sum_{n= 1}^{∞} 𝒂_nx^n)^2 = (\sum_{i= 1}^{∞} 𝒂_ix^i)(\sum_{k = 1}^{∞} 𝒂_k x^k) =\sum_{i = 1}^{∞} \sum_{k= 1}^{∞} 𝒂_i 𝒂_k x^{i+k}$ $𝒂_𝒏 = \sum_{k=1}^{𝒏−𝟏} 𝒂_𝒌𝒂_{𝒏−𝒌}$ ,n,i,k趋向于无穷,因此n可以表示为n = i+k ，n ≥ 2 可得

$A^2(x) = \sum_{n= 2}^{∞} 𝒂_nx^n = \sum_{n= 1}^{∞} 𝒂_nx^n - a_1x = A(x) -x$ ,

$A^2(x) = A(x) -x \Leftrightarrow A^2(x) - A(x) +x =0$ 得证。

(2)根据第一问结论 $A^2(x) - A(x) +x =0$ ，利用一元二次方程的求根公式可以求出A(x)的两个根： $A(x)_1 = \frac {1- \sqrt {1 - 4x} }{2} , A(x)_2 = \frac {1+ \sqrt{1 - 4x} }{2} ,$ 因为 $A(x) = \sum_{n \geq 1}^{} 𝒂_nx^n$ ，当x = 0时 A(x) = 0.因此要舍弃 $A(x)_2$ ，因此 $A(x) = \frac{1- \sqrt{1 - 4x} }{2} = \frac{1}{2} - \frac{(1-4x)^{\frac{1}{2} }}{2} = \frac{1}{2} - \frac{1 }{2} (1-4x)^{\frac{1}{2}}$ ,

由牛顿二项式推广公式：

$(1+ax)^\frac{1}{2} = \sum_{n=0}^{∞ } \frac{ (-1)^{n-1}}{2^{2n-1} n } C_{(2n-2, n-1)}(a^n )x^n$

推理如下：

$(1+ax)^\frac{1}{2} = \sum_{n=0}^∞ C_{\frac{1}{2} } ^ n a^n x^n = 1 + \sum_{n=1}^∞ \frac { \frac {1 }{2} (\frac{1 }{2} -1) ( \frac {1 }{2} -2) ... (\frac{1 }{2} -n+1) }{n! } a^n x^n$

$= 1 + \sum_{n=1}^∞ \frac{(1 - 2) (1 -4) ... (1 -2n+2) }{2 ^n n!} a^n x^n = 1 + \sum_{n=1}^∞ \frac{(-1)^{n-1}1*3*5 ... (2n-3 ) }{2 ^n n!} a^n x^n$ -------式1

$(2n)! = 1*3*5*7*...*(2n-1)*2*4*6*...*2n = 1*3*5*7*...*(2n-1)* 2^n *n!$ ---------式2

把 n-1 = N 代入式2：

$(2(n-1))! = 1*3*5*7*...*(2(n-1)-1)*2*4*6*...*2(n-1) = 1*3*5*7*...*(2n-3)* 2^{(n-1)} *(n-1)!$ -----式3

式3代入式1得：

$1 + \sum_{n=1}^∞ \frac{(-1)^{n-1} (2(n-1))! }{2 ^n n! 2^{(n-1)} (n-1)! } a^n x^n = 1 + \sum_{n=1}^∞ \frac{(-1)^{n-1} (2(n-1))! }{2 ^{(2n-1)} n! (n-1)! } a^n x^n = 1 + \sum_{n=1}^∞ \frac{(-1)^{n-1} (2n-2))! }{2 ^{(2n-1)} n (n-1)! (n-1)! } a^n x^n$

$= 1 + \sum_{n=1}^∞ \frac{(-1)^{n-1} }{2 ^{(2n-1)} n }C_{2n-2}^{ n-1} a^n x^n$ 得证

把A(x)代入 $A(x)= \frac{1}{2} - \frac{1}{2} - \frac{1}{2} *\sum_{n=0}^{∞ } \frac{ (-1)^{n-1}}{2^{2n-1} n } C_{(2n-2, n-1)}((-4)^n )x^n= \sum_{n=0}^{∞ } \frac{ (-1)^{n}}{2^{2n} n } C_{(2n-2, n-1)}((-1)^n2^n )x^n$

因此得到 $a_n = \frac{1}{n} {C_{( {2n-2,n-1})}} = \frac{1}{n} {( _{n-1} ^{2n-2})}$