- 1AI绘画专栏之Stablediffusion SD/SDXL Comfyui Stableforge全网第一套系统的AI绘画课_puffy-nipples
- 2【d3.js入门】d3-drag介绍和实战
- 3 python 使用PyQt5
- 4普乐蛙元宇宙VR体验馆设备集体亮相VR文旅景区展
- 5ros中的message filters时间同步--＞ 用于image和imu的结合_message_filters::sync_policies::approximatetime
- 6【SpringBoot】Java SpringBoot 企业微信机器人发送文本消息、图片消息_java企业机器人发送图片
- 7python循环结构程序设计,Python之循环结构
- 8非线性系统的混沌特性分析方法--相图/分岔图分析法_重构混沌相图
- 9springSecurity中jwt机制及应用详解_spring security jwt
- 10苹果软件扣费申请退款_reportaproblem申请退款官网
同等学习计算机科学与技术真题-2022年_同等学力申硕的计算机专业试卷结构
赞
踩
第一部分 数学基础课程
(共: 40 分) \text { (共: } 40 \text { 分) } (共: 40 分)
一、用逻辑符号表达语句 (论域为包含一切求物的集合) (共 3 分)
每个自然数有且仅有一个后继。
答：
N(x) : x 是自然数
A(x, y): y 是 x 的后续
S(x, y): x 等于 y
( ∀ x N ( x ) → ∃ y A ( x , y ) ) ∧ ( ( ∀ x N ( x ) ) ∧ ∃ z ( A ( x , z ) ∧ S ( y , z ) ) ) (\forall x N(x) \rightarrow \exists y A(x, y)) \wedge((\forall x N(x)) \wedge \exists z(A(x, z) \wedge S(y, z))) (∀xN(x)→∃yA(x,y))∧((∀xN(x))∧∃z(A(x,z)∧S(y,z)))
∀ x ∃ y ∃ z ( ( N ( x ) → A ( x , y ) ) ∧ ( ( A ( x , z ) → S ( y , z ) ) ) \forall x \exists y \exists z((N(x) \rightarrow A(x, y)) \wedge((A(x, z) \rightarrow S(y, z))) ∀x∃y∃z((N(x)→A(x,y))∧((A(x,z)→S(y,z)))
∀ x ( N ( x ) → ∃ ! y A ( x , y ) ) \forall x(N(x) \rightarrow \exists ! y A(x, y)) ∀x(N(x)→∃!yA(x,y))
二、填空题 (每空 2 分, 共 10 分)
- 已知推理前提为 ¬ ( P ∨ R ) , ¬ ( P ∧ ¬ Q ) , ¬ R \neg( P \vee R), \neg(P \wedge \neg Q), \neg R ¬(P∨R),¬(P∧¬Q),¬R, 则有效结论为______(要求尽可能简洁)。
¬ ( P ∨ R ) 为 T ¬ P ∧ ¬ R 为 T 。 ¬ R 为 T ，则 ¬ P 是 T ( P 是 F ) P → ¬ Q 为 T ¬ ( P → ¬ Q ) 为F。与条件矛盾。
¬(P∨R)为T¬P∧¬R为T。¬R为T，则¬P是T(P是F)P→¬Q为T¬(P→¬Q) 为F。与条件矛盾。 ¬(P∨R)为T¬P∧¬R为T。¬R为T，则¬P是T(P是F)P→¬Q为T¬(P→¬Q) 为F。与条件矛盾。
所以结论为F
- 设 Z 为整数集 , 关系 R = { ⟨ x , y > ∣ x ∈ Z ∧ y ∈ Z ∧ y = x 2 + 1 } 。集合 S 在 R 下的象定义为 : R [ S ] = { y ∣ ( ∃ x ) ( x ∈ S ∧ < x , y > ∈ R } 。已知集合 A = { 0 , 1 , 2 } , B = { 0 , − 2 } , 则 R [ A ⊕ B ] = 设 \mathbf{Z} 为整数集, 关系 R=\left\{\langle x, y>| x \in Z \wedge y \in Z \wedge y=x^{2}+1\right\} 。集合 S 在 R 下的象定义为: R[S]=\{y \mid(\exists x)(x \in S \wedge<x, y>\in R\} 。已知集合 A=\{0,1,2\}, B=\{0,-2\} , 则 R[A \oplus B]= 设Z为整数集,关系R={⟨x,y>∣x∈Z∧y∈Z∧y=x2+1}。集合S在R下的象定义为:R[S]={y∣(∃x)(x∈S∧<x,y>∈R}。已知集合A={0,1,2},B={0,−2},则R[A⊕B]=__________
{ 2 , 5 } \{2,5\} {2,5}
A ⊕ B = ( A − B ) ∪ ( B − A ) = ( A ∪ B ) − ( A ∩ B ) A \oplus B=(A-B) \cup(B-A)=(A \cup B)-(A \cap B) A⊕B=(A−B)∪(B−A)=(A∪B)−(A∩B)
如下图：
所以： A ⊕ B = { 1 , 2 , − 2 } A \oplus B=\{1,2,-2\} A⊕B={1,2,−2},由于二元关系是 y = x 2 + 1 y=x^{2}+1 y=x2+1，所以 R [ A ⊕ B ] = { 2 , 5 } R[A \oplus B]=\{2,5\} R[A⊕B]={2,5}
- 大学教务处要把 11 名同学安排到一个课程的四个组里面, 要求第一组有 4 名同学, 第二组 有 3 名同学, 第三组没有同学, 第四组有 4 名同学, 则有____种安排方法。
C 11 4 C 7 3 C 4 4 = 11550 C_{11}^{4} C_{7}^{3} C_{4}^{4}=11550 C114C73C44=11550
- 如下 Peterson 图是 10 个顶点 15 条边的简单图, 则它的边着色数是__4_
考察边着色数问题
奇阶K正则简单图, 边色数 =k+1
因为每个顶点 3 条边, 此图为 3 阶,
- 设 G \mathrm{G} G 是 n ( n ≥ 3 ) n(n \geq 3) n(n≥3) 个顶点的简单连通平面图且每个面的度数（也称次数）都是 3 , 则此图 的边数是_________
解：根据题意，n≥3由于G是简单连通平面图，且每个面的度数都是3。
N 为顶点数, e 为边数, f 为面数。根据欧拉公式 n-e+f=2
因为每个面的度为 3 , 度数是面数的 2 倍
所以 3 f=2 e (2) 联立 (1) (2),
解得 e=3n-6
三、计算题（共 4 分)
设序列
(
a
n
)
\left(a_{n}\right)
(an) 的生成函数是
g
(
x
)
=
∑
k
=
0
∞
a
k
x
k
=
1
+
x
+
x
2
+
x
3
1
−
x
g(x)=\sum_{k=0}^{\infty} a_{k} x^{k}=\frac{1+x+x^{2}+x^{3}}{1-x}
g(x)=∑k=0∞akxk=1−x1+x+x2+x3 。求:
(1)
a
3
a_{3}
a3 。
(2) 序列
(
a
n
)
\left(a_{n}\right)
(an) 。
1 + x + x 2 + x 3 1 − x = ( 1 + x + x 2 + x 3 ) ( 1 + x + x 2 + x 3 + … ) = 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 + … x + x 2 + x 3 + x 4 + x 5 + x 6 + … + x 2 + x 3 + x 4 + x 5 + x 6 + … + x 3 + x 4 + x 5 + x 6 + … = 1 + 2 x + 3 x 2 + 4 x 3 + 4 x 4 + 4 x 5 + 4 x 6 + … ∴ an = { 1 n = 0 2 n = 1 3 n = 2 4 n ≥ 3 a 3 = 4 a n = 4
\begin{array}{l} \frac{1+x+x^{2}+x^{3}}{1-x}=\left(1+x+x^{2}+x^{3}\right)\left(1+x+x^{2}+x^{3}+\ldots\right) \\ =1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+\ldots \\ \qquad x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+\ldots \\ \quad+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+\ldots \\ \quad+x^{3}+x^{4}+x^{5}+x^{6}+\ldots \\ =1+2 x+3 x^{2}+4 x^{3}+4 x^{4}+4 x^{5}+4 x^{6}+\ldots \\ \therefore \text { an }=\left\{\begin{array}{ll} 1 & n=0 \\ 2 & n=1 \\ 3 & n=2 \\ 4 & n \geq 3 \end{array}\right. \\ a_{3}=4 \quad\end{array} 1−x1+x+x2+x3=(1+x+x2+x3)(1+x+x2+x3+…)=1+x+x2+x3+x4+x5+x6+…x+x2+x3+x4+x5+x6+…+x2+x3+x4+x5+x6+…+x3+x4+x5+x6+…=1+2x+3x2+4x3+4x4+4x5+4x6+…∴ an =⎩ ⎨ ⎧1234n=0n=1n=2n≥3a3=4an=4an=4
考察知识点：母函数和泰勒展开。
( 1 ) 、 e x = 1 + x + x 2 2 ! + ⋯ + x n n ! + o ( x n ) ; (1) 、 e^{x}=1+x+\frac{x^{2}}{2 !}+\cdots+\frac{x^{n}}{n !}+o\left(x^{n}\right) ; (1)、ex=1+x+2!x2+⋯+n!xn+o(xn);
( 2 ) 、 sin x = x − x 3 3 ! + x 5 5 ! + ⋯ + ( − 1 ) m − 1 x 2 m − 1 ( 2 m − 1 ) ! + o ( x 2 m ) ; (2)、 \sin x=x-\frac{x^{3}}{3 !}+\frac{x^{5}}{5 !}+\cdots+(-1)^{m-1} \frac{x^{2 m-1}}{(2 m-1) !}+o\left(x^{2 m}\right) ; (2)、sinx=x−3!x3+5!x5+⋯+(−1)m−1(2m−1)!x2m−1+o(x2m);
( 3 ) 、 cos x = 1 − x 2 2 ! + x 4 4 ! + ⋯ + ( − 1 ) m x 2 m ( 2 m ) ! + o ( x 2 m + 1 ) (3) 、 \cos x=1-\frac{x^{2}}{2 !}+\frac{x^{4}}{4 !}+\cdots+(-1)^{m} \frac{x^{2 m}}{(2 m) !}+o\left(x^{2 m+1}\right) (3)、cosx=1−2!x2+4!x4+⋯+(−1)m(2m)!x2m+o(x2m+1)
( 4 ) 、 ln ( 1 + x ) = x − x 2 2 + x 3 3 + ⋯ + ( − 1 ) n − 1 x n n + o ( x n ) ; (4)、 \ln (1+x)=x-\frac{x^{2}}{2}+\frac{x^{3}}{3}+\cdots+(-1)^{n-1} \frac{x^{n}}{n}+o\left(x^{n}\right) ; (4)、ln(1+x)=x−2x2+3x3+⋯+(−1)n−1nxn+o(xn);
( 5 ) ( 1 + x ) α = 1 + α x + α ( α − 1 ) 2 ! x 2 + ⋯ + α ( α − 1 ) ⋯ ( α − n + 1 ) n ! x n + o ( x n ) ; (5) (1+x)^{\alpha}=1+\alpha x+\frac{\alpha(\alpha-1)}{2 !} x^{2}+\cdots+\frac{\alpha(\alpha-1) \cdots(\alpha-n+1)}{n !} x^{n}+o\left(x^{n}\right) ; (5)(1+x)α=1+αx+2!α(α−1)x2+⋯+n!α(α−1)⋯(α−n+1)xn+o(xn);
( 6 ) 1 1 − x = 1 + x + x 2 + ⋯ + x n + o ( x n ) . (6) \frac{1}{1-x}=1+x+x^{2}+\cdots+x^{n}+o\left(x^{n}\right) . (6)1−x1=1+x+x2+⋯+xn+o(xn).
四、解答题 (共 13 分)
- (8 分) 设集合
A
=
{
1
,
2
,
3
}
,
B
=
{
1
,
2
}
A=\{1,2,3\}, B=\{1,2\}
A={1,2,3},B={1,2} , 在 A 的幂集 P(A) 上定义二元关系 R 如下: 对于任意的
S
,
T
∈
P
(
A
)
,
⟨
S
,
T
⟩
∈
R
S, T \in P(A),\langle S, T\rangle \in R
S,T∈P(A),⟨S,T⟩∈R 当且仅当
S
∪
B
=
T
∪
B
S \cup B=T \cup B
S∪B=T∪B
(1) 求关系 R 的基数, 并画出 R 的关系图。
(2) 试问 R 是否为 P(A) 上的等价关系, 如果是则写明依据, 并给出商集
P
(
A
)
/
R
P(A) / R
P(A)/R ; 如果不是 则说明原因。
因为
S
∪
B
=
T
∪
B
S \cup B=T \cup B
S∪B=T∪B , 所以 S=T ,
因为
⟨
S
,
T
⟩
∈
R
,
⇒
⟨
S
,
S
⟩
∈
R
,
\langle S, T\rangle \in R, \quad \Rightarrow\langle S, S\rangle \in R, \quad
⟨S,T⟩∈R,⇒⟨S,S⟩∈R, 自反性
因为
⟨
S
,
T
⟩
∈
R
,
⟨
S
,
S
⟩
∈
R
\langle\mathrm{S}, \mathrm{T}\rangle \in R,\langle\mathrm{~S}, \mathrm{~S}\rangle \in \mathrm{R}
⟨S,T⟩∈R,⟨ S, S⟩∈R , 所以
⟨
T
,
S
⟩
∈
R
,
\langle\mathrm{T}, \mathrm{S}\rangle \in \mathrm{R}, \quad
⟨T,S⟩∈R, 对称性
知识点：
- 集合A中元素的数目称为集合 A 的基数, 记为 |A| 。
- P ( A ) = { ∅ , 1 , 2 , 3 , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } \mathrm{P}(\mathrm{A})=\{\varnothing, 1,2,3,\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} P(A)={∅,1,2,3,{1,2},{1,3},{2,3},{1,2,3}} 因为 ⟨ S , T ⟩ ∈ R , S , T ∈ P ( A ) \langle S, T\rangle \in R, S, T \in P(A) ⟨S,T⟩∈R,S,T∈P(A) , 当且仅当 S ∪ B = T ∪ B S \cup B=T \cup B S∪B=T∪B 故 S=T , 故 S, T 可能为 ∅ , 1 , 2 , 3 , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } \varnothing, 1,2,3,\{1,2\},\{1,3\},\{2,3\},\{1,2,3\} ∅,1,2,3,{1,2},{1,3},{2,3},{1,2,3}
- (5 分) 某出版公司聘请五位专家审阅 5 本不同的书, 这五位专家都有资格审阅这 5 本书中 的每一本, 要求每本书有两个不同的审阅专家, 试问一共有多少种满足要求的分配方案。
完全错排
5 ! D 5 = 5 ! ⋅ 5 ! ( 1 − 1 + 1 2 ! − 1 3 ! + 1 4 ! − 1 5 ! ) = 5280. 5 ! D_{5}=5 ! \cdot 5 !\left(1-1+\frac{1}{2 !}-\frac{1}{3 !}+\frac{1}{4 !}-\frac{1}{5 !}\right)=5280 . 5!D5=5!⋅5!(1−1+2!1−3!1+4!1−5!1)=5280.
五、证明题 (共 10 分)
- (4 分) 判断 ∃ x P ( x ) → Q ( x ) ⇒ ( ∀ x ) P ( x ) → ( ∃ x ) Q ( x ) \exists xP(x) \rightarrow Q(x) \Rightarrow(\forall x)P(x) \rightarrow (\exists x)Q(x) ∃xP(x)→Q(x)⇒(∀x)P(x)→(∃x)Q(x) 是否正确, 如果正确, 则给出证明; 如果不正确, 给出反例。
∀ ( x ) P ( x ) → ∃ x Q ( x ) ⇔ ¬ ( ∀ ( x ) P ( x ) ) ∨ ( ∃ x Q ( x ) ) ⇔ ∃ x ¬ P ( x ) ∨ ∃ x Q ( x ) ⇔ ∃ x ¬ P ( x ) ∨ Q ( x ) ⇔ ∃ x ( P ( x ) → Q ( x ) )
⇔⇔⇔⇔∀(x)P(x)→∃xQ(x)¬(∀(x)P(x))∨(∃xQ(x))∃x¬P(x)∨∃xQ(x)∃x¬P(x)∨Q(x)∃x(P(x)→Q(x))⇔⇔⇔⇔∀(x)P(x)→∃xQ(x)¬(∀(x)P(x))∨(∃xQ(x))∃x¬P(x)∨∃xQ(x)∃x¬P(x)∨Q(x)∃x(P(x)→Q(x))
- 证明: C ( n , r ) = C ( n , n − r ) 和 C ( 2 n , n ) = ∑ k = 0 n C ( n , k ) 2 \text { 证明: } \boldsymbol{C}(\boldsymbol{n}, \boldsymbol{r})=\boldsymbol{C}(\boldsymbol{n}, \boldsymbol{n}-\boldsymbol{r}) \text { 和 } \boldsymbol{C}(2 \boldsymbol{n}, \boldsymbol{n})=\sum_{k=0}^{\mathrm{n}} \boldsymbol{C}(\boldsymbol{n}, \boldsymbol{k})^{2} 证明: C(n,r)=C(n,n−r) 和 C(2n,n)=∑k=0nC(n,k)2
证明: 实际上, 从 n 个不同元素中选出 r 个元素的同时, 就有 n-r 个元素没有被选出, 因此选出 r 个元素的方式数 等于选出 n-r 个元素的方式数, 即 C(n, r)=C(n, n-r) 。得证。
第二部分 专业知识课程
I ．计算机系统结构
（共 30 分）
一、选择题（每小题 1 分, 共 5 分）
-
RISC 执行程序的速度比 CISC 快的原因是 ( )。
A. RISC 指令系统的指令数较少
B. RISC 的指令平均周期较少
C. 目标程序的指令条数较多
D. 只允许 Load 和 Store 指令访存 -
多处理机实现的并行主要是 ( )。
A. 指令级并行
B. 任务级并行
C. 操作级并行
D. 操作步骤的并行 -
采用相刘寻址方式的转移指令占两个字节, 第一个字节是操作码, 第二个字节是相对位移 量 (用补码表示)。每次 CPU 从存储器取出一个字节, 并自动完成 ( P C ) + 1 → P C (\mathrm{PC})+1 \rightarrow \mathrm{PC} (PC)+1→PC 。若执行 到该转移指令时 P C \mathrm{PC} PC 的内容为 2005 H 2005 \mathrm{H} 2005H , 要求转移到 200 B H 200 \mathrm{BH} 200BH 地址, 则该转移指令中第二个字 节的内容应该为 ( )。
A. 04 H 04 \mathrm{H} 04H
B. 05 H 05 \mathrm{H} 05H
C. 06 H 06 \mathrm{H} 06H
D. F 6 H \mathrm{F} 6 \mathrm{H} F6H -
一个存储器地址为 14 位, 每个存储单元长度为 8 位, 若有 1 \mathrm{~K} \times 4 位的 SRAM 芯片来组成 该存储器, 则需要的芯片数量是 ( ), 片选译码的地址码位数是 ( )。
A. 16 、 4
B. 32 、 4
C. 16 、 8
D. 32 、 8 -
下列 4 种消息寻径方式中，不属于包交换的消息寻径方式是（）。
A. 存储转发寻径
B. 虚拟直通寻径
C. 虫蚀寻径
D. 线路交换寻径
二、填空题 (每空 1 分, 共 10 分)
- 在中断输入输出方式中, 由____执行_____ 程序来完成输入输出工作; 在直接存储 器访问 (DMA) 方式中, 由 来完成输入输出工作; 在通道输入输出方式中，由 执行____ 来完成输入输出工作。
- 向量流水处理机和并行处理机都可以执行向量指令, 前者提高并行性的途径是 后者提高并行性的途径是____
- 系统总线按传输信息分为三类, 即____、_____ 和_____。
三 计算题 (共 15 分)
II . 计算机网络
（共 30 分）
一、填空题（每空 1 分, 共 6 分)
- 802.11 局域网 MAC 层协议是__CSMA/CA协议__ ，采用 _检测帧 RTS____帧来解决碰撞后的重传问题。
解释：CSMA/CA，载波侦听多路访问➕冲突避免:发送前发送一小的检测帧 RTS，若收到 CTS 说明空闲，之后发送数据帧，等待对方确认收到（ ACK）再发送下一帧
- 一个 Internet 的地址块表示为 a.b.c.d/20, 其中______位可以用来标识该地址块中的主机， 子网掩码用点分十进制表示为______
答：
需要了解概念无分类编址 CIDR - 构造超网，斜线记法
CIDR 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念，因而可以更加有效地分配 IPv4 的地址空间。CIDR使用各种长度的“网 络前缀”(network-prefix)来代替分类地址中的网络号和子网号。IP 地址从三级编址 (使用子网掩码) 又回到了两级编址。CIDR的IP地址 可表示为：IP 地址 ::=<网络前缀, 主机号 > CIDR 使用“斜线记法”(slash notation), 它又称为 CIDR 记法, 即在 IP 地址面加上一个斜线“", 然后写上网络前缀所占的位数（这个数 值对应于三级编址中子网掩码中 1 的个数）。例如：220.78 .168 .0 / 24 由题意可知，网络前缀是 20 位，故主机号占 12 位。
- 传输层的复用 (multiplexing) 是指_____
答： 应用层的所有进程都可以通过传输层再传递到 IP 层
- 一台路由器的路由表项如下所示:
| 地址/掩码 | 下一跳 |
|---|---|
| 10.46.56.0/22 | 接口0 |
| 10.46.60.0/22 | 接口1 |
| 192.168.40.0/23 | 路由器1 |
| Default | 路由器2 |
若目的地址为 10.46 .65 .14 , 该路由器通过_____转发。
答：路由器 2
地址: 10. 46.56.0 根据斜线后面的22可也得出，子网掩码为11111111 11111111 11111100 00000000，转为10进制，子网掩码为: 255.255 .252 .0
地址: 10. 46.60.0 子网掩码为: 255.255 .252 .0
地址: 192.168 .40 .0 子网掩码为: 255.255 .254 .0
目的地址为 10. 46. 65.14 与子网掩码 255.255 .252 .0 相与, 得到地址为 10.46 .64 .0
64 = 01000000 60 = 00111100 56 = 0011100064=0100000060=0011110056=0011100064=0100000060=0011110056=00111000
目的地址为 10. 46. 65. 14 与子网掩码 255.255.254. 0 相与, 得到地址为 0.40 .0 .0 故目的地址为 10. 46. 65. 14 时, 没有向匹配的，所以从路由器 2 转发出去。
二、单项选择题 (每小题 1 分, 共 5 分)
- 下列关于虚拟局域网 (VLAN) 的描述, 错误的是（B ）。
A. IEEE 802.1Q 协议定义了虚拟局域网的概念
B. 虚拟局域网是由一些局域网段组成的、与物理位置相关的结点集合
C. 虚拟局域网的帧格式与传统以太网的帧格式不同
D. 虚拟局域网可以隔离广播风暴
解：选择 B，虚拟局域网(VLAN)，是指网络中的站点不拘泥于所处的物理位置，而可以根据需要灵活地加入不同的逻辑子网中的一种网络技术
- 在部署分层 OSPF 协议时, 如果一个路由器同时连接到两个不同区域上, 其中一个是主干 区域, 则该路由器 ( B)。
A. 是内部路由器
B. 需要维护一个统一的链路状态数据库
C. 需要为每个区域单独运行距离向量算法
D. 需要为每个区域单独运行最短路径算法
解：选择 B
对于 A 项，该路由器为主干路由器或者区域边界路由器，所以内部路由器不对。
对 C 项， OSPF 采用的是最短路径算法，所以 C 不对
对 D 项， OSPF 采用的是最短路径算法，不应该是某个路由器为某个区域单独运行的，而应该是全网的。所以 D 不对
- 设有下面 4 条路由: 10.18 .96 .0 / 21 、 10.18 .104 .0 / 21 、 10.18 .112 .0 / 21 、 10.18 .120 .0 / 21 , 如果 进行 CIDR 路由汇聚, 能覆盖这 4 个路由的地址是 ( B )。
A. 10.18 .120 .0 / 18
B. 10.18 .96 .0 / 19
C. 10.18 .120 .0 / 20
D. 10.18 .96 .0 / 20
解: 选择 B
96 = 01100000 104 = 01101000 112 = 01110000 120 = 0111100096=01100000104=01101000112=01110000120=0111100096=01100000104=01101000112=01110000120=01111000
上面四个的前缀有3个是相同，相与后是01100000，他们前面两个字段相同都是10.18 所以有16位+3位=19。
因此能覆盖这四个路由器的是 10.18 .96 .0 / 19
- 下面各项中能造成过多 UDP 广播报文的是（A）。
A. 路由器发出的 ARP 请求包
B. 服务器发出的 ARP 响应包
C. 大量的基于 RIP 协议的路由表更新报文
D. 大量的基于 OSPF 协议的路由表更新报文
路由器发出的ARP请求包是广播报文, 它会向本地网络中的所有设备发 出请求, 以查找特定IP地址的MAC地址。如果网络中有大量的ARP请求, 就可能 导致过多的UDP广播报文。
- 某单位分配了一个 B 类地址, 计划将内部网络分成 20 个子网, 将来要增加 16 个子网, 每 个子网的主机数接近 800 台, 可行的掩码方案为 ( )。
A. 255.255 .128 .0
B. 255.255 .248 .0
C. 255.255 .254 .0
D. 255.255 .252 .0
解: 选择 D \mathrm{D} D , 因为总共需要 36 个子网, 需要 6 位, 则需要拿出 6 位主机号 (全 1 ) 作为子网号
(全 0 )
B 类地址的子网掩码为 255.255 .0 .0 , 因为借用 5 位子网, 故可行的掩码方案为 255.255 .252 .0
11111000=252
三、名词解释 (每小题 2 分, 共 4 分)
- 内部网关协议 IGP
内部网关协议 IGP: IGP 协议是自治系统 AS 内各网关交换路由信息的 协议，包括 RIP、OSPF 协议等 - 套接字 socket
套接字唯一标识了网络中的一个主机和它上面的一个进程。 Scoket = 主机号：端口号
四、问答和计算题 (共 15 分)
( 计算中记 : 1 G ≈ 1 0 9 ; 1 M ≈ 1 0 6 ; 1 K ≈ 1 0 3 ) (计算中记: 1 \mathrm{G} \approx 10^{9} ; 1 \mathrm{M} \approx 10^{6} ; 1 \mathrm{~K} \approx 10^{3} ) (计算中记:1G≈109;1M≈106;1 K≈103)
- (4 分) 某网络采用 RIP 路由协议, 当路由器 A \mathrm{A} A 收到从路由器 C \mathrm{C} C 发来的距离向量时, 试问: A \mathrm{A} A 的路由表将发生怎样的变化? 请写出路由器 A 新的路由表。
A 的路由表:
目的网络
距离
下一跳路由器
Net1
1
直接连接
Net2
10
A
Net4
2
C
Net6
7
D
Net7
6
B
Net8
2
D
C
发来的距离向量表:
目的网络
距离
Net1
1
Net2
2
Net3
1
Net4
3
Net5
3
Net6
5
解: 先将收到的 C 发来的距离向量表更新如下表 C, 记为表 D: （对每一个相邻 路由器发送过来的 RIP 报文, 进行以下步骤:
- 对地址为
C
\mathrm{C}
C 的相邻路由器发来的 RIP 报文, 先修改此报文的所有项目: 把
“下一跳” 字段中的地址都改为 C , 并把所有的 “距离” 字段值加 1
目的网络
距离
下一跳路由器
N
e
t
1
2
C
N
e
t
2
3
C
N
e
t
3
2
C
N
e
t
4
4
C
N
e
t
5
4
C
N
e
t
6
6
C
- RIP 路由矢量算法:
- 若 (原来的路由表中没有目的网络 N): 把该项目添加到路由表中 (#本路由表中没有到目的网络 Net3 的路由, 那么路由表中就要加入新的项目)
- 若在路由表中有目的网络 N, 查看下一跳路由器地址: 如果 (下一跳路由器地址是 C)：把收到的项 目替换原路由表中的项目（#不管原来路由表中项目时 “Net2，3，C” 还是 “Net2，5，C”，都要更 新为 “Net2, 4, C” )
- 若在路由表中有目的网络 N, 但下一跳路由器不是
C
\mathrm{C}
C , 比较距离
d
\mathrm{d}
d 与路由表中的距离: 若（收到的项 目中的距离
d
\mathrm{d}
d 小于于路由表中的距离): 更新(掿路由表中已有项目 “Net2, 5, P”, 就更新为 “Net2,4， C” ）否则，不更新（ #若距离更大了，显然不应更新；若距离不变，也不更新）
解： 对修改后的 RIP 报文中的每个项目，执行以下步骤：
对表 D 和 A 的路由表进行比较：
row1：有 Net1， 但下一跳路由器是不同，比较距离得到，新的距离小于路由表中距离，更新 A 的路由表，距离为 2，下一跳路由器为 C。
row2:有 Net2， 但下一跳路由器是不同，比较距离得到，新的距离小于路由表中距离，更新 A 的路由表，距离为 3，下一跳路由器为 C
row3:无 Net3，将 Net3 加入到 A 的路由表，距离为 2，下一跳路由器为 C
row4:有 Net4， 且下一跳路由器相同，更新 A 的路由表，距离为 4，下一跳路由器为 C；
row5: 无 Net5，将 Net5 加入到 A 的路由表，距离为 4，下一跳路由器为 C；
row6: 有 Net6， 但下一跳路由器是不同，比较距离得到，新的距离小于路由表中距离，更新 A 的路由表，距离为 6，下一跳路由器为 C更新后， A 的路由表如下图所示：
2.(5分) 传输一个10M字节的文件，若传播时延为20ms，分组大小为2K字节。初始“握手”延迟为两倍的往返时延。文件的最后 1 位到达目的地表示传输完成。
（1）若带宽为 10
M
b
p
s
\mathrm{Mbps}
Mbps , 数据可以被连续发送, 计箅传输文件所需的时间。
解: (1) 握手时延 =
2
k
T
T
=
2
⋅
2
⋅
20
m
s
=
80
m
s
2 k T T=2 \cdot 2 \cdot 20 \mathrm{~ms}=80 \mathrm{~ms}
2kTT=2⋅2⋅20 ms=80 ms
传输时延 =20 \mathrm{~ms}
发送时延 =
10
m
B
10
M
b
p
s
=
10
×
1
0
6
×
8
b
i
t
10
×
1
0
6
b
p
s
=
8
s
\frac{10 \mathrm{mB}}{10 \mathrm{Mbps}}=\frac{10 \times 10^{6} \times 8 \mathrm{~bit}}{10 \times 10^{6} \mathrm{bps}}=8 s
10Mbps10mB=10×106bps10×106×8 bit=8s
所以文件传输的总时延=80ms+20ms+8s=8.1s
（2）若链路允许无限快速发送, 每个 RTT 仅发送 10 个分组，计算传输文件所需的时间。
因为链路允许无限发送，故带宽为无限大，即发送时延为0s，并且在等待每个RTT后只能发送10个分组。
所以，分组大小=10MB/2kb=5000个分组。
5000/10=500个RTT。
第一个发送的10个分组有0.5个RTT=传输时延。
所以总的时延为20ms+80ms+499*2*20ms=20.06s
3. （6 分) 考虑一个
T
C
P
\mathrm{TCP}
TCP 连接 (Reno）使用一条带䆕为
100
M
b
p
s
100 \mathrm{Mbps}
100Mbps 的链路发送一个大文件, 这 条链路是发送方和接收方之间的唯一拥塞链路。接收方的接收缓存比拥塞窗口大得多。假设端到端的传播时延为30ms。如果传输层采用TCP协议，报文段长度为1500字节。假 TCP 连接总是处于拥塞避免阶段, 忽略慢启动。试回答:
（1）这条 TCP 连接能取得的最大窗口大小是多少报文段?
（2）这条 TCP 连接从丢包恢复后, 再次达到最大窗口大小需要多长时间?
解: 做这一题, 首先了解几个概念
TCP 协议: TCP 协议定义（Transimission Control Protocol）是以一种面向连接的、可靠的、基于字节流的传输层通信 协议。TCP 是基于不可靠的网路实现可靠传输, 肯定会存在丢包问题。如果在通信过程中, 发现缺少数据或者丢包, 那边么最大 的可能性是程序发送过程或者接受过程中出现问题。例如: 我有 2 台服务器 , \mathrm{A} 和 \mathrm{B} 服务器。A 服务器发送数据给 \mathrm{B} 服务器频 率过高时，B 服务器来不及处理, 造成数据丢包。(原因可能是程序逻辑问题，多线程同步问题，缓冲区溢出问题）
丢包: 如果 A 服务器不对发送频率进行控制, 或者数据进行重发的话, 那么 B 服务器收到数据就会少。就会造成丢失数 据。
端到端时延: 端到端时延 (end-to-end delay) 是指 IP 数据报从离开源点时算起一直到抵达终点时为止一共经历了多长时 间的时延。即包的延时就是指包的接收时间与包的发送时间差。为 0.5 倍的 RTT。
拥塞避免算法：让拥塞窗口 cwnd 缓慢地增大, 即每经过一个往返时间 RTT 就把发送方的拥塞窗口 cwnd 加 1 , 而 不是加倍。这样拥塞窗口 cwnd 按线性规律缓慢增长, 比慢开始算法的拥塞窗口增长速率缓慢得多。
在慢开始和拥塞避免算法中使用了“乘法减小” 和“加法增大”方法。“乘法减小”是指不论在慢开始阶段还 是拥塞避免阶段, 只要出现一次超明时 (即很可能出现了网络拥塞), 就把慢开始门限值 ssthresh 设置为当前的 拥塞窗口值的一半。当网络频繁出现拥塞时, ssthresh值就下降得很快, 以大大减少注入到网络中的分组数。而 “加法增大” 是指执行拥塞避免算法后, 在收到对所有报文段的确认后 (即经过一个 RTT), 就把拥塞窗口cwnd 增加一个 MSS 大小, 使拥塞窗口缓慢增大, 以防止网络过早出现拥塞。
答：
（1）当发送速率最大只能等于链路带宽时, 才能不发生丢包（即数据溢出）。设窗口大小为
W
\mathrm{W}
W , 因此由公式
W
∗
M
S
S
/
R
T
T
=
100
M
b
p
s
\mathrm{W} * \mathrm{MSS} / \mathrm{RTT}=100 \mathrm{Mbps}
W∗MSS/RTT=100Mbps , 因为端到端的时 延是 30ms，因此
R
T
T
=
2
∗
30
m
s
RTT =2 * 30 \mathrm{~ms}
RTT=2∗30 ms
由题意可知 MSS 为报文段长度 1500 字节,
W
∗
1500
∗
8
b
i
t
/
2
∗
30
m
s
=
100
M
b
p
s
W*1500*8bit / 2 * 30 \mathrm{~ms}=100 \mathrm{Mbps}
W∗1500∗8bit/2∗30 ms=100Mbps 因此求出
W
=
500
\mathrm{W}=500
W=500
(2) 因为 TCP 丢包（即出现超时, 出现了网络拥塞溢出问题），这时需要 把慢开始的门限值 ssthresh 设置为当前的拥塞窗口值的一半, 因为恢复过 程中, TCP 总是处于拥塞避免状态, 因此, 每个RTT 窗口尺寸增加 1 个 MSS，因此总共需要的时间
T
=
(
500
/
2
)
∗
R
T
T
=
(
500
/
2
)
∗
2
∗
3
∗
1
0
−
2
s
=
15
s
\mathrm{T}=(500 / 2) * \mathrm{RTT}=(500 / 2) * 2 * 3 * 10^{-2} \mathrm{~s}=15 \mathrm{~s}
T=(500/2)∗RTT=(500/2)∗2∗3∗10−2 s=15 s
软件工程
一、单项选择题 (每空 1 分, 共 5 分)
软件开发模型是指软件开发的全部过程、活动和任务的结构框架。主要的开发模型佯瀑布模型、演化模型、螺旋模型、喷泉模型等。螺旋模型将瀑布模型和演化模型相结合, 并增 加了（1）, 它建立在（2）的基础上, 沿螺旋自内向外每旋转一圈, 就得到它的一个新 版本。喷泉模型描述了（3) 的开发模型, 它休现了这种开发方法创建软件过程所固有的 ( 4) 和 ( 5) 的特征。
供选择的答案:
(1): A. 系统工程 B. 风险分析 C. 设计评审 D. 进度控制
(2): A. 模块划分 B. 子程序分解 C. 设计 D. 原型
(3): A. 面向对像 B. 面向数据流 C. 面向数据结构 D. 面向事件驱动
(4): A. 归纳 B. 推理 C. 迭代 D. 递归
(5)：A．开发各阶段之间无 “间隙” B. 开发各阶段分界明显 C. 部分开发阶段分界明显 D. 开发过程不分段
答案:
1、B 2、D 3、A 4、C 5、A
二、判断题 (每小题 1 分, 共 5 分。如果正确, 用 “、” 表示; 否则, 用 “×”表示)
- 对象把数据和处理数据的操作结合为一体。
- 程序是一些对象的集合, 在程序运行时对象都处于活动状态。
- 用计数方法而不是用文件结束符或输入序列结束符来判断程序输入的结束。
- 在面向对象系统中, 类与对象的关系是抽象与具体的关系。
- 接受消息的对象必须回答消息发送者。
三、简答题 (每小题 4 分, 共 12 分)
- 以 G.J.Myers 的观点, 简述软件测试的目的。
软件测试的目的是:
(1) 为了发现错误而执行程序的过程。
(2) 一个好的用例能够发现至今尚末发现的错误的测试。
(3) 一个成功的测试是发现至今尚末发现的错误的测试。
- 消息传递是面向对象方法中对象之间进行交互的机制, 消息传递机制与传统程序设计模式 中的过程调用有什么本质区别?
(1)消息传递必须给出信道的消息, 通常需要指出明确的接收方。
(2)由于接收方是一通信实体, 具有保持状态的能力, 所以同一发送方在不同时刻向同一接收 方发送相同的消息, 可因接收方的当前在状态不同而得到不同的结果。
(3)消息传递可以是异步的, 发送方可以不必等待接收方返回信息就可以继续执行后面的操作, 而传统的过程调用只能是同步的, 本质上是串行的。
- 说明面向对象分析阶段所建立的对象模型、动态模型和功能模型之间的关系。
- 功能模型: 表达系统的详细需求, 为软件的进一步分析和设计打下基础。在面向对象方 法中, 由用例冬和场景描述组成。
2）对象模型: 表示静态的、结构化的系统 “数据” 性质。描述现实世界中实体的对象以及 它们之间的关系, 表示目标系统的静态数据结构。在面向对象方法中, 类图是构建对 象模型的核心工具。
3）动态模型: 描述系统的动态结构和对象之间的交互, 表示瞬时的、行为化的系统的 “控 制” 特性。面向对象方法中, 常用状态图、顺序图、合作图、活动图构建系统的动态模 型。
与功能模型的关系:
(1) 对象模型展示了功能模型中的动作者、数据存储和流的结构, 动 态模型展示了执行加工的顺序。
(2) 与对象模型的关系: 功能模型展示了类上的操作和每个操作的变量, 因此它也表示 了类之间的 “供应者一客户”关系; 动态模型展示了每个对象的状态以及 它接收事件 和改变状态时所执行的操作。
(3) 与动态模型的关系: 功能模型展示了动态模型中末定义的不可分解的动作和活动的定义, 对象模型展示了是谁改变了状态和承受了操作。
四、建模题 (共 8 分)
某培训中心要研制一个计算机管理系统, 它的业务是将学员发来的信息收集分类后, 按 以下不同情况进行处理:
- 如果是报名, 则将报名信息送给负责报名事务的职员, 他们将查阅课程文件, 检查该课程 是否满额, 然后在学生文件、课程文件、账目文件上登记, 并开出报名单交财务部门, 财 务人员开出发票给学生;
- 如果是想注销原来已选修的课程, 则由注销人员在课程文件、学生文件和账目文件上做相 应的修改, 并给学生注销单;
- 如果是付款, 则由财务人员在账目文件上登记, 也给学生一张收费收据。 请根据该计算机管理系统的功能描述, 采用 “自顶向下” 的原则, 画出其分层数据流图 (顶层 DFD 和 0 层 DFD)。
IV ． 人工智能原理 (共 30 分）
一、单项选择题 (每小题 3 分, 共 9 分)
-
主观贝叶斯方法是一种（） 方法。
A. 机器学习的分类
B. 不确定性推理
C. 知识表示 -
关于启发式搜索描述正确的是（）。
A. 启发函数没有固定的模式, 需要针对具体问题分析
B. 启发式搜索不能在盲目搜索基础上增加启发函数完成
C. 启发式搜索可以不用启发函数指导搜索 -
下面关于 BP 神经网络描述正确的是 ( )。
A. 允许同层神经元有连接
B. 采用梯度下降法进行训练
C. 可以不使用激活函数来完成非线性可分数据的多分类
二、证明题（共 9 分）
使用归结法证明: ( ( T ∧ Q ) → P ) → ( T → ( Q → ( S ∨ P ) ) ) \quad((T \wedge Q) \rightarrow P) \rightarrow(T \rightarrow(Q \rightarrow(S \vee P))) ((T∧Q)→P)→(T→(Q→(S∨P))) 。
三、简答题（每小题 4 分, 共 12 分) -
说明使用支持向量机求解二分类问题的原理。
-
解释什么是分支界限法。
-
说明在证据理论中, 用哪三个函数来描述和处理知识的不确定性。
