2019年计算机真题

离散数学

一、用逻辑符号表达下列语句(论域为包含一切事物的集合)

1）过平面上的两个点，有且仅有一条直线通过。

解析：$P_{(x,y)}:\mathrm{x},\mathrm{y}\text{ 是平面上的两个点，}$
$Q_{(x,y,z)}:\mathrm{z}\text{ 是过 }\mathrm{x}\text{ 和 }\mathrm{y}\text{ 的直线，}$$R_{(x,y)}：x与y相同$

$\forall x\forall y\forall z\exists w{P}_{(x,y)}\wedge Q_{(x,y,z)}\wedge Q_{(x,y,w)}\to R_{(z,w)}$

2）并不是所有的士兵都想当将军，而且不想当将军的士兵未必不是好士兵（一种形式，包含全称量词和存在量词）。
$$\begin{array}{l}\text{ 解析：}{P}_{(x)}:x\text{ 是士兵，}{Q}_{(x)}:\mathrm{x}\text{ 想当将军，}{R}_{(x)}\text{ x是好士兵；}\\ \neg \forall x{P}_{(x)}\to Q_{(x)}\wedge \exists x({┐}_{(x)}\wedge R_{(x)})\end{array}$$

二、填空题

1.集合A={1,2,3,4,5,6,7}, A上的一个划分R={{1,2},{3,4,5},{6,7}}.那么所对应的等价关系R包含的有序对的个数是( )个.定义偏序关系为集合A上的整除关系,则这个偏序关系上含有的有序对个数是( )个.集合A上有( )个既是对称又是反对称的关系。

1. 等价关系的有序对个数：
   每个划分块内的元素形成完全连接的等价类。计算每个块的有序对数目：

   • {1,2}: (2^2 = 4) 个
   • {3,4,5}: (3^2 = 9) 个
   • {6,7}: (2^2 = 4) 个
     总计：(4 + 9 + 4 = 17)

2. 整除关系的有序对个数：
   列出所有整除关系：

   • 1整除所有数：(7) 对（包括自反）
   • 2整除2、4、6：(3) 对
   • 3整除3、6：(2) 对
   • 4、5、6、7仅自反：各(1) 对
     总计：(7 + 3 + 2 + 1 + 1 + 1 + 1 = 16)

3. 既对称又反对称的关系数目：
   这类关系只能包含自反边（若包含非自反边，对称性要求双向，但反对称性强制两端相等，矛盾）。
   每个元素的自反边可独立选择存在与否，共(2^7 = 128) 种可能。

答案：
4. (17)
5. (16)
6. (128)

1. 对称性与反对称性的定义

• 对称性：若关系包含有序对 ((a, b))，则必须包含 ((b, a))。
• 反对称性：若关系同时包含 ((a, b)) 和 ((b, a))，则必有 ( a = b )。

2. 推导关系的形式
同时满足对称和反对称的关系需满足：

• 对任意不同元素 ( a \neq b )：
  不能存在 ((a, b)) 或 ((b, a))。
  原因：若存在 ((a, b))，对称性要求必须存在 ((b, a))，但反对称性要求 ( a = b )，矛盾。因此，对任意 ( a \neq b )，关系中不能包含 ((a, b)) 或 ((b, a))。

• 对任意元素 ( a )：
  可以自由选择是否包含自反对 ((a, a))。
  原因：自反对 ((a, a)) 满足对称性（反向仍是自身），也不违反反对称性（( a = a ) 是允许的）。

3. 可能的组合方式
关系只能由自反对 ((a, a)) 构成，且每个自反对的包含与否是独立的：

• 集合 ( A ) 有 7 个元素，每个元素对应一个自反对 ((a, a))。
• 对每个自反对，有两种选择：包含 或 不包含。

4. 计算总数
总共有 ( 2^7 = 128 ) 种可能的关系。

5. 验证特例

• 空关系：不包含任何自反对，满足对称性和反对称性。
• 全自反关系：包含所有自反对 ((1,1), (2,2), $\dots$, (7,7))，同样满足条件。

---

最终答案
集合 ( A ) 上既对称又反对称的关系共有 $\boxed{128}$ 个。

2、已知集合A={a,b,c,d}上的两个关系R1={<a,a>,<a,b>,<b,c>},R2={<a,b>,<b,c>,<c,d>,<d,b>}.则R2^2=,R2ＯR1=___

R²的计算（R2∘R2）：

• 步骤：对于每个元素<x,y>∈R2，寻找R2中以y为第一个元素的<y,z>，得到<x,z>。
• 结果：
  • <a,b> → 结合<b,c>得<a,c>
  • <b,c> → 结合<c,d>得<b,d>
  • <c,d> → 结合<d,b>得<c,b>
  • <d,b> → 结合<b,c>得<d,c>
• R² = { <a,c>, <b,d>, <c,b>, <d,c> }

R2∘R1的计算：

• 步骤：对于每个元素<x,y>∈R1，寻找R2中以y为第一个元素的<y,z>，得到<x,z>。
• 结果：
  • <a,a> → 结合<a,b>得<a,b>
  • <a,b> → 结合<b,c>得<a,c>
  • <b,c> → 结合<c,d>得<b,d>
• R2∘R1 = { <a,b>, <a,c>, <b,d> }

最终答案：

• R² =
  $\boxed{\{⟨a,c⟩,⟨b,d⟩,⟨c,b⟩,⟨d,c⟩\}}$

• R2∘R1 =
  $\boxed{\{⟨a,b⟩,⟨a,c⟩,⟨b,d⟩\}}$

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

用 S 是有 k 种类型对象的多重集合，每种元素具有无限的重复数，那么 S 的 r 组合的个数为： ${\mathrm{C}}_{(\mathrm{r}+\mathrm{k}-1,\mathrm{r})}$ ；在本题中答案 ${\mathrm{C}}_{(7,5)}={\mathrm{C}}_{(7,2)}=21$

4.设$K_{m,n}$是两部分分别有m和n个顶点的完全二部图,则$K_{m,n}$的着色数是( )。

完全二部图 ( $K_{m,n}$ ) 的顶点可以被划分为两个互不相交的集合，分别包含 ( m ) 个和 ( n ) 个顶点，且两个集合之间的每一对顶点均有一条边相连，而同一集合内的顶点无边相连。根据顶点着色数的定义，相邻顶点需颜色不同。由于二部图的特性，只需用两种颜色分别对两个顶点集着色即可满足条件，因此其顶点着色数为 2。

答案：
($\boxed{2}$)

5．设树 T 的顶点集合为 V = { v 1 , v 2 , … , v n } \mathrm{V}=\{\mathrm{v} 1, \mathrm{v} 2, \ldots, \mathrm{vn}\} V={v1,v2,…,vn} ， T 的平均度为$\mathrm{D}=\frac{1}{\mathrm{n}}{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{v}}_{\mathrm{i}}$，请用 D 表示出树 T 的顶点个数 $\mathrm{n}=()$

树：无圈的连通图即为树（ n 个顶点的树有 n-1 条边）因为数有 n 个顶点，所以有 $\mathrm{n}-1$ 个边，
根据握手定理 ${\sum }_{i=0}^{n}d(\mathrm{vi})=2(\mathrm{n}-1)$
$$\begin{array}{l}2(n-1)=n^{\ast }D\\ n=2/(2-D)\end{array}$$
三、计算题
1）个体域 { a , b , c } \{\mathrm{a}, \mathrm{b}, \mathrm{c}\} {a,b,c} ，将下列公式写成命题逻辑公式 $(\forall \mathrm{x})\mathrm{P}(\mathrm{x})->(\exists y)\mathrm{Q}(\mathrm{y})$

将全称量词和存在量词在个体域{a, b, c}下展开为命题逻辑公式：

原公式为 $(\forall x)P(x)\to (\exists y)Q(y)$，具体步骤如下：

1. 展开全称量词：
   $$\forall xP(x)\equiv P(a)\wedge P(b)\wedge P(c)$$

2. 展开存在量词：
   $$\exists yQ(y)\equiv Q(a)\vee Q(b)\vee Q(c)$$

3. 处理蕴含关系：
   根据命题逻辑的等价关系 $A\to B\equiv \neg A\vee B$，原式可转换为：
   $$\neg (P(a)\wedge P(b)\wedge P(c))\vee (Q(a)\vee Q(b)\vee Q(c))$$

4. 应用德摩根定律：
   $$\neg (P(a)\wedge P(b)\wedge P(c))\equiv \neg P(a)\vee \neg P(b)\vee \neg P(c)$$

5. 合并析取项：
   最终公式为：
   $$\neg P(a)\vee \neg P(b)\vee \neg P(c)\vee Q(a)\vee Q(b)\vee Q(c)$$

答案：
$$\boxed{\neg P(a)\vee \neg P(b)\vee \neg P(c)\vee Q(a)\vee Q(b)\vee Q(c)}$$

2）计算下式的主析取范式和主合取范式 $(\neg \mathrm{P}\vee Q)\to (Q\wedge \neg R)$ 用极小项和极大项数字表示简洁。

要计算公式 ((\neg P \vee Q) \rightarrow (Q \wedge \neg R)) 的主析取范式和主合取范式，首先构造其真值表，并确定结果为真和假的赋值情况：

真值表

P	Q	R	$(\neg P\vee Q)\to (Q\wedge \neg R)$	结果
0	0	0	0	0
0	0	1	0	0
0	1	0	1	1
0	1	1	0	0
1	0	0	1	1
1	0	1	1	1
1	1	0	1	1
1	1	1	0	0

主析取范式（PDNF）

结果为1的赋值对应极小项：

• ( m_2 )（0,1,0）：$\neg P\wedge Q\wedge \neg R$
• ( m_4 )（1,0,0）：$P\wedge \neg Q\wedge \neg R$
• ( m_5 )（1,0,1）：$P\wedge \neg Q\wedge R$
• ( m_6 )（1,1,0）：$P\wedge Q\wedge \neg R$

主析取范式为这些极小项的析取：
$$\boxed{\sum (2,4,5,6)}$$

主合取范式（PCNF）

结果为0的赋值对应极大项：

• ( M_0 )（0,0,0）：$P\vee Q\vee R$
• ( M_1 )（0,0,1）：$P\vee Q\vee \neg R$
• ( M_3 )（0,1,1）：$P\vee \neg Q\vee \neg R$
• ( M_7 )（1,1,1）：$\neg P\vee \neg Q\vee \neg R$

主合取范式为这些极大项的合取：
$$\boxed{\prod (0,1,3,7)}$$

最终答案
主析取范式：(\boxed{\sum(2,4,5,6)})
主合取范式：(\boxed{\prod(0,1,3,7)})
四、解答题
1）写出集合A上的一种关系，它既是等价关系，又是偏序关系，并简要说明这种关系的特点。
2）求满足递推关系 中的表达式，其中n3,初始条件=0,=1,=2。
3）设序列{}的母函数是A(x),序列{}的母函数是B(x),如果=，且B(x)=f(x)A(x),求f(x).
五、证明题
证明下面恒等式

表示n元素中取i个的组合数。
计算机网络
一、填空题
1.以太网的争用期是指（ ），以太网发送数据使用（ ）编码
2.一个广域网传输比特率是4kbps,传播时延为20ms,若采用停-等协议效率是50%，帧长至少为( )位
3.一个网段的网络号为130.10.3.0/21，子网掩码可以写为( )
4,TCP协议中发送窗口的大小应该由（）窗口和（ ）窗口中较小的一个决定

二、判断题
1,面向对象分析方法的常用工具是用例图()
三、简答题
1.软件需求是什么？共分为几个层次？
2.软件质量保证的是什么？它的四个活动是什么？
3.说明客户端/服务器，对等模式采用的三层结构是什么？