2019年计算机真题

2019年计算机真题
离散数学
一、用逻辑符号表达下列语句(论域为包含一切事物的集合)
1）过平面上的两个点，有且仅有一条直线通过。
解: (1) $\mathrm{P}_{(\mathrm{x}, \mathrm{y})}: \mathrm{x}, \mathrm{y}$ 是平面上的两个点。 $\mathrm{Q}_{(\mathrm{x}, \mathrm{y}, \mathrm{z})}: \mathrm{z}$ 是 $\mathrm{x}$ 和 $\mathrm{y}$ 的直线; $\mathrm{R}_{(\mathrm{x}, \mathrm{y})}: \mathrm{x}$ 和 $\mathrm{y}$ 相同。 $\forall x \forall y \forall z \exists w P_{(x, y)} \wedge Q_{(x, y, z)} \wedge Q_{(x, y, w)} \rightarrow R_{(z, w)}$

2）并不是所有的士兵都想当将军，而且不想当将军的士兵未必不是好士兵（一种形式，包含全称量词和存在量词）。

(2) P_{(x)}: x 是士兵; Q_{(x)} : 相当将军; R_{(x)}: x 是好士兵。

$\forall \mathrm{xP}_{(\mathrm{x})} \rightarrow \mathrm{Q}_{(\mathrm{x})} \wedge \exists \mathrm{x}\left(\neg \mathrm{Q}_{(\mathrm{x})} \wedge \mathrm{R}_{(\mathrm{x})}\right)$
二、填空题
1.集合A={1,2,3,4,5,6,7}, A上的一个划分R={{1,2},{3,4,5},{6,7}}.那么所对应的等价关系R包含的有序对的个数是( )个.定义偏序关系为集合A上的整除关系,则这个偏序关系上含有的有序对个数是( )个.集合A上有( )个既是对称又是反对称的关系。
在这里插入图片描述

3.一个商店提供了3种不同的钢笔，假设顾客小王进店时，每种钢笔至少有5支.则小王选5支钢笔的方式有( )种.
在这里插入图片描述

4.设Km,n是两部分分别有m和n个顶点的完全二部图,则Km,n的着色数是( 2 )。
在这里插入图片描述

5.设树T的顶点集合为V={v1, v2, …, vn}, T的平均度为,请用D表示出树T的顶点个数n=( )
在这里插入图片描述

三、计算题
1）个体域{a,b,c},将下列公式写成命题逻辑公式（）P(x) -> ()Q(y)
在这里插入图片描述

计算下式的主析取范式和主合取范式（）用极小项和极大项数字表示简洁。

在这里插入图片描述

四、解答题
四、解答题

写出集合A上的一种关系，它既是等价关系，又是偏序关系，并简要说明这种关系的特点。

解析：设集合 $A=\{a, b ， c\}$ ，等价关系满足的条件是：自反，对称，传递；而满足偏序关系的条件是：自反，反对称，传递。条件中A的关系 R 需满足等价和偏序关系，也就是 R 必须满足既是对称又是反对称关系。则 $R=\{<x, y>\mid x=y\}$ 即关系矩阵对角线上的数都为1，因此该关系为集合A上的每个元素自成环，无其他关系路径。
2.求满足递推关系 $h_{n}=h_{n-1}+9 h_{n-2}-9 h_{n-3}$ 中 $h_{n}$ 的表达式，其中 $\geq 3$ ，初始条件 $h_{0}=0, h_{1}=1, h_{2}=2$

解析: 本题考的是常系数齐次递推关系。题中原式转化成 $h_{n}-h_{n-1}-9 h_{n-2}+9 h_{n-3}=0$ ，因此该式特征方程为 $q^{3}-q^{2}-9 q+9=0 q^{2}(q-1)-9(q-1)=0 \Rightarrow\left(q^{2}-9\right)(q-1)=0$ 。得到特征根 $q_{1}=-3, q_{2}=3, q_{3}=1$ 。三个特征无重根，则该 h_{n} 的一般解为:
$H_{n}=C_{1} q_{1}^{n}+C_{2} q_{2}^{n}+C_{3} q_{3}^{n}$ 把三个特征根代入式子中可得
$H_{n}=C_{1}(-3)^{n}+C_{2}(3)^{n}+C_{3}(1)^{n}=C_{1}(-3)^{n}+C_{2} 3^{n}+C_{3}$ 。把 $h_{0}=0, h_{1}=1, h_{2}=2$ 代入 $H_{n}$ 得到三个等式

$H_{0}=C_{1}+C_{2}+C_{3}=0 ; \quad H_{1}=-3 C_{1}+3 C_{2}+C_{3}=1 ; \quad H_{2}=9 C_{1}+9 C_{2}+C_{3}=2$ .

解这三个三元一次方程组得 : $C_{1}=-\frac{1}{12}, C_{2}=\frac{1}{3}, C_{3}=-\frac{1}{4}$ 代入得解

$H_{n}=-\frac{1}{12} *(-3)^{n}+\frac{1}{3} * 3^{n}-\frac{1}{4}=\frac{1}{4} *(-3)^{(n-1)}+3^{(n-1)}-\frac{1}{4}$

设序列 $\left\{a_{i}\right\}$ 的母函数是 $A_{(x)}$ ，序列 $\left\{b_{i}\right\}$ 的母函数是 $B_{(x)}$ ，如果 $b_{k}=\sum_{i=0}^{k} a_{i}$ ，且 $B_{(x)}=f_{(x)} A_{(x)}$ ，求 $f_{(x)}$ 。

解析: 有题可知 $A_{(x)}=\sum_{i=0}^{\infty} a_{i} x^{i}$ ，且 $b_{k}=\sum_{i=0}^{k} a_{i}$ ，得

$B_{(x)}=\sum_{i=0}^{\infty}\left(\sum_{j=0}^{i} a_{j}\right) x^{i} = a_{0} x^{0}+\left(a_{0} x^{1}+a_{1} x^{1}\right)+\left(a_{0} x^{2}+a_{1} x^{2}+a_{2} x^{2}\right)+\ldots+\left(a_{0} x^{n}+a_{1} x^{n}+\ldots+a_{n} x^{n}\right)+\ldots$

$=a_{0}\left(x^{0}+x^{1}+\ldots+x^{n}+\ldots\right)+a_{1} x\left(x^{0}+x^{1}+\ldots+x^{n}+\ldots\right)+a_{2} x^{2}\left(x^{0}+x^{1}+\ldots+x^{n}+\ldots\right)+\ldots$