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

2021年同等学力申硕计算机综合试题-数学部分

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

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

∀:表示所有的，一切的，全称量词；∃:表示存在1个，至少有1个，存在量词

答：

(1)设F(x)：x是计算设备，G(x):x是问题，R(x,y):x求解y；

(∀x)(F(x)→(∃y)(G(y)∧R(x,y)))

解释：所有事物x，如果它是计算设备，那么它就可以求解存在的一些问题y。

二、填空题

1、设集合A={1,2,3,4}，则集合A上有__15__种等价关系。(2021年真题)

答：考察等价关系，集合划分问题

给定集合A的一个划分={S,S,S,⋅⋅⋅,S}，则由该划分确定的关系

123n

R=(S×S)∪(S×S)∪⋅⋅⋅∪(S×S)是A上的等价关系，我们称该关系R为由划分所

1122nn

导出的等价关系.

方法1：公式法

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

根据公式：S(n,1)=1；S(4,1)=1，

根据公式：S(n,2)=2−1−1；S(4,2)=24−1−1=8−1=7，

根据公式：S(n,n-1)=C(n,2)；S(4,3)=C(4,2)=6，

根据公式：S(n,n)=1；S(4,4)=1，

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

方法2：画图法

①S(4,1),4个元素做1个划分，有1种等价关系；

②S(4,2),4个元素做2个划分，有C(4,1)+C(4,2)/2!=7种等价关系；

③S(4,3),4个元素做3个划分，有C(4,2)=6种等价关系；

④S(4,4),4个元素做4个划分，有1种等价关系；

2、设P是所有人的集合，R和S是集合P上的关系，R={x,y|x是y的父亲}，

S={x,y|x是y的母亲}，（∀x,∀y∈P），当关系Q为__∘−1__时，xQy表示x

是y的妻子。注：用R1∘R2表示关系R1与R2的复合。

答：考察逆关系和复合关系

设z是x的子女，记作−1={z,y|z是y的子女}，S={x,z|x是z的母亲}，

根据复合关系：x→z→y得Q=∘−1，即为所求.

3、有5个男同学和3个女同学站成一排，如果没有2个女同学相邻，共有__

14400__种不同的排法。

答：考察排列与组合

5个男同学全排列有P(5)=5!=120，要求2个女生不能相邻，则用插排法，将3个女同学插排

到5个男同学间隙中，有6个间隙，即女生的排法有P(6,3)=6*5*4=120，因此一共有：

P(5)*P(6,3)=120*120=14400种排法。

4、设G是有10个顶点的无奇圈的简单连通图，则G的着色数是__2__

（简单图的着色数是指相邻的顶点着不同的颜色所需的最少颜色的个数）。

解：考察图的点着色数问题,

“无奇圈”的简单连通图指的是图中不包含奇数长度的回路。

一个无奇圈的图意味着所有回路的长度都是偶数。

一个无奇圈的图也可以等价地定义为二部图。

()=2⟺G是二部图⟺G无奇圈。

根据定理，二部图的着色数为2。

1∞

5、如果2=∑⋅,求=_____。

(1−2)=0

解：考察母函数，广义牛顿二项式定理

根据推广的牛顿二项式定理：1=∞⋅，则

∑+−1

(1−)=0

ak=k⋅2k=k⋅2k=(k+1)2k

2+k−1k+1