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

2022-06-12 本文已影响0人旋风竹影

声明：本人已经在2020年通过了统考（之前时间记错），解数学题也是我的业余爱好。本套试题的填空题解析补充是本人自己做的，如发现答案有错误或者不够准确请及时给我留言，如需转载请表明出处。感谢给我提供题目的同学们（本套题我是通过三位同学提供的路径才合在一起的），感谢所有提出意见和建议。如果觉得还行，欢迎点赞转发，谢谢！(由于简书平台的符号显示异常，有时候会出现公式残缺现象，集合中 $\bar{A}$ 是非A的意思，请网友知悉。)

一、用逻辑符号表达下列语句

1. 任何计算设备都可以求解某个问题。

解析：P(x): x是计算机设备，Q(x): x问题，R(x，y):x求解y

$∀x∃y(P(x) ∧Q(y) \rightarrow R(x,y))$

二、填空题

1. 设集合A={1, 2, 3, 4}，则集合A上有 15 种等价关系。

解析：使用第二类 Stirling 求其不同的划分个数 : $S ( 4 ,1 ) + S ( 4 ,2 ) + S ( 4 , 3 ) + S ( 4 , 4 )$

根据公式 : $S ( n , 1 ) = 1$ , 计算 Stirling 数的值 : $S ( 4 , 1 ) = 1$ $S ( 4 ,1 ) = 1$

根据公式 : $S(n,2) = 2^{n-1} - 1$ ,计算 Stirling 数的值 : $S(4,2)=2 ^{4−1} −1=2^3 −1=7$

根据公式: $S ( n , n − 1 ) = C ( n , 2 )$ ( Stirling 数计算公式 ) ,计算 Stirling 数的值 : $S(4,3) = C(4,2) = 6$

据公式 : $S ( n , n )=1$ , 计算 Stirling 数的值 : $S(4,4)=1$

$S ( 4 ,1 ) + S ( 4 ,2 ) + S ( 4 , 3 ) + S ( 4 , 4 ) =1+7+6+1=15$

2. 设P是所有人的集合，R和S是集合P上的关系，R={<x,y> | x是y的父亲}，S={<x,y> |x是y的母亲} ，( $\forall x , \forall y \in P$ )，当关系Q为 $S \circ R^{-1}$ 时，xQy表示x是y的妻子。注：用R1OR2表示关系R1与R2的复合。

解析：本题考的是逆关系和复合关系，假设z是x的子女记作 $R^{-1}$ = {<z,y>| z 是y的子女}，S={<x,z> |x是z的母亲}，根据复合关系： $x \rightarrow z \rightarrow y$ 得 $Q = S \circ R^{-1}$ ,得到答案。

3. 有5个男同学和3个女同学站成一排，如果没有2个女同学相邻，共有 14400 种不同的排法。

解析：男生的排法有 $P(5) = 5! = 5*4*3*2*1=120$ ,要求2个女生不能相邻，则用插排，将3位女同学插排到5个同学的空当中间，5个男生（包括首尾）有6个空当，即女生的排法有 $P(6,3) = 6*5*4 = 120$ ，因此一共有 $P(5)*P(6,3)=120*120 = 14400$

4. 设G是有10个顶点的无奇圈的简单连通图，则G的着色数是 2 （简单图的着色数是指相邻的顶点着不同的颜色所需的最少颜色的个数）。

解析：【定理一】一个图为二部图当且仅当图G中无奇圈。因此G为二部图。而二部图的着色数为2；

【定理二】图G是2-可着色的当且仅当G是二部图；因此可知该二部图的着色数位为2。

【定理二】奇圈和奇数阶轮图都是3-色图，而偶数阶轮图都是4-色图。

5. 如果⁡ $\frac{1}{(1-2x)^2} = \sum\nolimits_{k=0}^∞ a_{k} x^k$ 则 $a_{k} =$ $C_{k-3}^k 2^k$

解析：根据牛顿公式： $（1+ax）^n = \sum_{k=0}^∞C_{n}^ka^kx^k$ ，以及牛顿公式推广公式 ${(1+ax)}^{-n} = \sum_{k=0}^∞{(-1)}^kC_{n+k-1}^ka^kx^k$ 题目中，a=-2，n=-2，代入推广公式可得： $a_k = (-1)^k C_{k-3}^k (-2)^k = C_{k-3}^k 2^k$

三、计算题

1. 设个体域为{a, b, c}，试写出公式(∃x)P(x) →(∀y)Q(y)的命题逻辑表达。

解析： 个体域{a,b,c} 对于逻辑命题量词， $\exists x$ 即是个体域做析取计算，而 $\forall y$ 则是对个体域做合取运算。因此得 $P(a) \lor P(b) \lor P(c) \rightarrow Q(a) \land Q(b) \land Q(c)$

2. 写出(﹁PVQ)→((Q∧﹁R)VP)的主析取范式和主合取范式（需写出计算过程，且结果简洁表示）。

解析：这个解析方法有两种方法，在本题中就用真值表来做了，另外一种推导的就留给网友们自己推导：

真值表

则主析取范式为 $(﹁PVQ)→((Q∧﹁R)VP) = m_2 \lor m_4 \lor m_5 \lor m_6 \lor m_7$

则主合取范式为 $(﹁PVQ)→((Q∧﹁R)VP) = M_0 \land M_1 \land M_3$

四、解答题

1. 设有四对夫妻围一圆桌就坐，则至少有1对夫妻不相邻的就坐方式有多少种。

解析：四对夫妻至少有一对夫妻不相连，即至多3对夫妻相邻，可以理解成全排列减去4对夫妻相连，得到的就是至多有3对夫妻相邻了。

四对夫妻8人全排列(圆周排列公式见我的公式集) $Q(8,8) = (8-1)! = 7!=5040$ ，4对夫妻相邻的全排列分为两个阶段先女士围成一圈 $Q(4,4) = 3! = 6$ ，再让男士坐到自己的妻子身边，每位男士有两种坐法，坐到妻子左边或者右边，即 $2^4 = 16$ ，因此四对夫妻相邻的排列有 $Q(4,4) * 2^4 = 6 *16 = 96$ ，则题中至少一对夫妻不相邻的排列数为 $Q(8,8) - Q(4,4)*2^4 = 5040 - 96 = 4944$