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

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

第一部分数学基础课程

（共40 分）

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

1.发光的不都是金子。（注：给出两种表达，一种用存在量词，另一种用全称量词）

解析：(1)：P(x)表示 x 发光； Q(x) 表示 x 为金子，

全称量词表示为： ¬∀x(P(x)→Q(x))

存在量词表示为： ∃x(P(x) ∧ ¬Q(x))

2.有些大学生不尊敬老人。

解析：S(x) ：x是人， P(x)： x 为大学生；Q(x) ：x 尊敬老人

∃x(S(x) ∧P(x) ∧ ¬Q(x))

二、填空题（第1 小题2 分，第2 到第6 小题每空2 分，共16 分）

1. 设集合 A 有 100 个元素，则 A 有 _ $2^{100}$ _个子集。其中有 _ $2^{99}$ __个子集其元素个数为奇数。

解析：第一空，可以理解成 $A = \{ a_1,a_2,a_3,...,a_{100} \}$ ,对于A中子集，即A中每个元素存在两种情况：“有” 与 “没有”，因此子集个数为 $2^{100}$ ；

第二空，整个集合中子集的个数只有奇数和偶数两种情况表示，因此子集元素个数位奇数的子集有 $\frac{2^{100}}{2} = 2^{99}$

2. 任意一个图中度数是奇数的顶点个数一定是 __偶数____ 。

解析：图的度数总和为偶数，因此奇数点的一定是偶数个。

3．如果四对夫妻围圆桌就座，没有任何限制条件，共有 _ $5040$ __种不同的座法；如果这四对夫妻中的四个男士和四个女士排成一排，要求男女交替，则有 _ $1152$ __ 种不同的排法；如果这四对夫妻围圆桌就座, 要求夫妻相邻的座法有__96_ _种。

解析：第一空，没有任何限制的情况为圆周全排列 $Q(8) = (8-1)! = 7!=5040$

第二空，女士一排全排序 $4！$ ，男士一排全排序 $4！$ ，女士整排选择前插或者后插加入到男士队伍有2种情况，因此总排列数为 $2*(4!)^2 = 1152$

第三空，四对围成一圈先坐有 $Q(4) = (4-1)! = 3!$ ，每对夫妻的妻子可以做到丈夫的左边或者右边 $2^4$ ,因此有 $3！*2^4 = 6*16=96$

4. 设 G=(V,E)是顶点集为V、边集为 E 的图。令 $D(G)= \frac {1}{|V|} \sum_{v ∈ V } 𝐝(𝐯)$ ，则用 D(G)和|V|把|E|表示出来的表达式是_ $\frac{|V|* D(G)}{2}$ __ 。这里 d(v)是顶点 v 的度数（或次数），|V|和|E|分别是 V 和 E 中所含元素的个数。

解析：图中边的数量E是总度数D的 $\frac{1}{2 }$ ，如题干中D总数为 $D= |V|* D(G)$ ,因此 $|E|= \frac{D}{2} = \frac{|V|* D(G)}{2}$

5. 设 Q 是一个有理数集。对任意的 a,b∈Q，定义二元运算 aΔb = (a×b) / 2，则 Q 关于运算Δ 的单位元是 __2__ ，其中“×”是有理数中通常的乘法运算。

解析： 设单位元为e则满足 $e \Delta a = \frac{e \times a}{2 } = a$ ,因此 $e = 2$ .

6. 把 6 个相同的球分到 3 个同学手里，允许有的同学未分配到球的情况出现，则有 __28__种不同的分法。

解析：这个就相当于把6个相同的球放到3个不同的筐里，允许存在空筐，因此该题目可以理解为6个球与2个筐壁的组合问题。分法为 $C_{(8,2)}=\frac{7*8}{2*1} = 28$ ,得到答案。

三、计算题（第1 小题3 分，第2 小题4 分，第3 小题6 分，共13 分）

1. 定义 P↑Q = ¬(P∧Q)，试仅用与非联结词↑分别表示出

（1）¬P

（2）P∧Q

（3）P→Q

均要求结果简洁。

解析：

(1) ¬P = ¬(P∧P) = P↑P （幂等律）

(2) P∧Q = ¬(¬(P∧Q)) = ¬(¬(P∧Q) ∧ ¬(P∧Q) ) = (P↑Q)↑(P↑Q) (可以用第一个的结论)

(3)P→Q = ¬P∨Q =¬(P∧¬Q) = ¬(P∧¬(Q∧Q)) = P↑(Q↑Q)

2. 设a、b、c、d 这四个元素的全排列中不允许出现ac 和bd 的排列数。

解析：本题考的是容斥原理。假设ac出现的排列数为 $|A_1|$ ,bd出现的排列数为 $|A_2|$ ,本题的要求是不允许出现ac和bd的排列，即 $| \bar{A_{1}} \cup \bar{A_{2}} |=|A| - |A_1| -|A_2| + |A_1 \cap A_2|$

首先，4个元素的全排列数 $|A| = 4！= 24$

接着 $|A_1|$ 和 $|A_2|$ 相等，相当于把ac绑定换成bd绑定，因此排列数为 $|A_1| = |A_2| = 3！=6$

$|A_1 \cap A_2|$ 指出同时出现ac,bd排列数为 $|A_1 \cap A_2| =2！ = 2$

因此 $| \bar{A_{1}} \cup \bar{A_{2}} |=|A| - |A_1| -|A_2| + |A_1 \cap A_2| = 24 - 6- 6+2 = 14$

3．用红、黄、蓝色对1× n 的棋盘方格涂色，设涂红色方格的个数是偶数且至少有一个方格涂黄色的涂色方法数为 $h_n$ （n 是正整数）。

（1）试确定 $h_n$ 的指数型生成函数；

（2）求 $h_n$ 。

解析：(1) 黄色无限制，红色方格数为偶数，至少有一个黄色格子，因此 $h_n$ 的指数型生成函数G(x)为：

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

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

(2)根据第一步 $G(x)= \frac {1}{2} \sum_{ k=0 }^∞(3^k +1-2^k) \frac { x^k }{k!} + \frac {1}{2}$ ,把n替换k 得：

$G(x)= \frac {1}{2} \sum_ {n=0}^∞(3^n +1-2^n) \frac {x^n}{n!} + \frac {1}{2}$ 因此 $h_n = \frac{1}{2}(3^n +1-2^n) = \frac{1}{2}(3^n -2^n +1)$

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

1. 给出命题：“对于集合 A 上的任意关系 R，如果R 是对称的和传递的，则 R 一定是自反的。” 若命题正确，则给出完整证明；若命题错误，则指出错误所在，并在集合{1, 2, 3}上构造一个关系R1（反例）使得R1 是对称的和传递的，但不是自反的。

证明：该命题错误

解析：自反即关系矩阵上对角线上全为1，集合A={1,2,3}, 关系子集R1={<1,1>,<1,2>,<2,1>,<2,2>},即没有3的环，R1满足前提假设，但是不满足自反关系。因此得证。

2. 设A 为包含n 个元素的有限集，R 是A 上的关系，则必存在s 和t，使得 $𝑹^𝒔=𝑹^𝒕$ , 且 $0≤s< t≤𝟐^{𝒏^𝟐}$ 。

证明：用鸽笼原理证明。

解析：【定理】设A为含有n个元素的有穷集， $R \subseteq A \times A$ ，则存在自然数s,t, 且满足 $0 \leq s < t \leq 2^{n^2}$ ,使得 $R^s = R^t$ 。

显然 $P(A \times A)$ 中元素对幂运算是封闭的，即对任意的自然数k,有 $R^k \in P(A \times A), k = 0,1,2,...$ 而且 $|P(A \times A)| = 2^{n^2}$ ,

考虑R的各项幂 $R^0, R^1,...,R^{2^{n^2}}$ ,共产生了 $2^{n^2} + 1$ 个 $P(A \times A)$ 的二元关系，

由鸽巢原理可知，存在s,t,满足 $0 \leq s < t \leq 2^{n^2}$ ，使得 $𝑹^𝒔=𝑹^𝒕$ 。