西电25年953考研专业课部分真题解析

一、 概念与简答题（数据结构与计算机网络）

1. 简述二叉排序树（Binary Sort Tree）的相关概念与操作，以及稀疏矩阵的常用压缩存储方式 。

2. 简述局域网的相关特性与工作原理。

3. 简述密码体制中“密钥”的概念 。

4. 在网络寻址中，请比较数据报服务与虚电路服务的异同

相同点：

• 交换方式： 两者都属于分组交换（Packet Switching）技术，即将长报文拆分成若干个较短的分组进行转发。
• 资源共享： 都采用动态分配带宽的方式，通过统计时分复用提高线路利用率。

不同点（如下表所示）：

比较维度	数据报服务 (Datagram)	虚电路服务 (Virtual Circuit)
连接性	无连接。发送前无需建立连接。	面向连接。发送前必须建立连接。
目标地址	每个分组携带完整的目标地址。	分组仅携带短小的虚电路号 (VCI)。
路由选择	每个分组独立选择路由。	仅在建立连接时确定路径，后续不变。
分组顺序	不保证按序到达，可能乱序或丢失。	保证分组按发送顺序到达。
节点状态	路由器不维护连接状态（无状态）。	路由器需维护虚电路转发表（有状态）。
故障影响	故障时可自动寻找绕行路径，鲁棒性强。	路径上任一节点故障，连接即中断。

二、 综合计算题（密码学）

4. 椭圆曲线密码学（ECC）计算 在有限域 $GF(17)$ 上有一椭圆曲线，其方程为 $y^2 \equiv x^3+2x+2 \pmod{17}$ 。已知该曲线上的一基点 $B=(5,1)$，用户 A 的私钥为 $\alpha=3$ 。请计算用户 A 的公钥（即求点乘 $3B$）。

这是一道关于椭圆曲线密码学（ECC）中点运算的经典计算题。在有限域 $GF(p)$ 上计算 $3B$，需要通过两次加法运算：首先计算 $2B = B + B$（倍点运算），然后计算 $3B = 2B + B$（点加运算）。

核心公式回顾

对于曲线 $y^2 \equiv x^3 + ax + b \pmod{p}$，已知两点 $P(x_1, y_1)$ 和 $Q(x_2, y_2)$：

1. 倍点运算（$P=Q$）：斜率 $\lambda \equiv \frac{3x_1^2 + a}{2y_1} \pmod{p}$
2. 点加运算（$P \neq Q$）：斜率 $\lambda \equiv \frac{y_2 - y_1}{x_2 - x_1} \pmod{p}$
3. 结果点 $R = P + Q = (x_3, y_3)$：
   • $x_3 \equiv \lambda^2 - x_1 - x_2 \pmod{p}$
   • $y_3 \equiv \lambda(x_1 - x_3) - y_1 \pmod{p}$

第一步：计算 $2B = B + B$

已知 $B = (5, 1)$，$a = 2$，$p = 17$。

1. 计算斜率 $\lambda$：

   $$\lambda \equiv \frac{3 \times 5^2 + 2}{2 \times 1} \equiv \frac{75 + 2}{2} \equiv \frac{77}{2} \pmod{17}$$

   由于 $77 \div 17$ 余 $9$：

   $$\lambda \equiv 9 \times 2^{-1} \pmod{17}$$

   在 $\pmod{17}$ 下，$2$ 的逆元是 $9$（因为 $2 \times 9 = 18 \equiv 1$）：

   $$\lambda \equiv 9 \times 9 = 81 \equiv 13 \pmod{17}$$

2. 计算坐标 $(x_2, y_2)$：

   • $x_2 \equiv 13^2 - 5 - 5 = 169 - 10 = 159 \pmod{17}$

     $159 = 17 \times 9 + 6 \implies x_2 = 6$

   • $y_2 \equiv 13(5 - 6) - 1 = 13(-1) - 1 = -14 \pmod{17}$

     $-14 + 17 = 3 \implies y_2 = 3$

     所以 $2B = (6, 3)$。

第二步：计算 $3B = 2B + B$

计算 $2B(6, 3) + B(5, 1)$。

1. 计算斜率 $\lambda’$：

   $$\lambda' \equiv \frac{1 - 3}{5 - 6} = \frac{-2}{-1} = 2 \pmod{17}$$

2. 计算坐标 $(x_3, y_3)$：

   • $x_3 \equiv 2^2 - 6 - 5 = 4 - 11 = -7 \pmod{17}$

     $-7 + 17 = 10 \implies x_3 = 10$

   • $y_3 \equiv 2(6 - 10) - 3 = 2(-4) - 3 = -8 - 3 = -11 \pmod{17}$

     $-11 + 17 = 6 \implies y_3 = 6$

解析总结

1. 倍点计算：通过基点 $B$ 的切线斜率求得 $2B = (6, 3)$。
2. 点加计算：通过 $2B$ 与 $B$ 的连线斜率求得 $3B = (10, 6)$。

【答案】

用户 A 的公钥为 (10, 6)。

5. Shamir 门限秘密共享体制

在一个基于有限域 $GF(17)$ 的 Shamir 秘密共享方案中，分配者构造了一个二次多项式 $f(x) \equiv a+bx+cx^2 \pmod{17}$ 。其中常数项 $a$ 为隐藏的秘密。现收集到 3 个参与者的子密钥份额分别为 $(1,8)$、$(3,10)$ 和 $(5,11)$ 。请恢复原多项式 $f(x)$，并求解秘密值 $a$。

1. 核心原理与数学模型

在 Shamir $(t, n)$ 门限方案中，秘密 $a$ 被隐藏在一个 $t-1$ 次多项式 $f(x)$ 的常数项中。

本题中：

• 有限域：$GF(17)$，即所有运算都在模 17 下进行。
• 多项式：$f(x) \equiv a + bx + cx^2 \pmod{17}$（二次多项式，$t=3$）。
• 份额 (Shares)：$(1, 8), (3, 10), (5, 11)$。

2. 解析过程：求解多项式系数

我们可以将已知的三个点代入多项式方程，得到一个三元一次方程组：

1. 当 $x=1$ 时：$a + b(1) + c(1)^2 \equiv 8 \pmod{17} \implies a + b + c \equiv 8 \pmod{17}$ —— ①

2. 当 $x=3$ 时：$a + b(3) + c(3)^2 \equiv 10 \pmod{17} \implies a + 3b + 9c \equiv 10 \pmod{17}$ —— ②

3. 当 $x=5$ 时：$a + b(5) + c(5)^2 \equiv 11 \pmod{17} \implies a + 5b + 8c \equiv 11 \pmod{17}$ —— ③

   (注：$5^2 = 25 \equiv 8 \pmod{17}$)

第一步：消元法求解

• ② - ①：$(3b - b) + (9c - c) \equiv 10 - 8 \pmod{17}$

  $\implies 2b + 8c \equiv 2 \pmod{17}$

  同时除以 2：$b + 4c \equiv 1 \pmod{17}$ —— ④

• ③ - ②：$(5b - 3b) + (8c - 9c) \equiv 11 - 10 \pmod{17}$

  $\implies 2b - c \equiv 1 \pmod{17}$ —— ⑤

第二步：求 $b$ 和 $c$

• 由 ⑤ 得：$c \equiv 2b - 1 \pmod{17}$。

• 代入 ④：$b + 4(2b - 1) \equiv 1 \pmod{17}$

  $b + 8b - 4 \equiv 1 \pmod{17}$

  $9b \equiv 5 \pmod{17}$

• 为了解出 $b$，需要求 9 在模 17 下的逆元：

  因为 $9 \times 2 = 18 \equiv 1 \pmod{17}$，所以 $9^{-1} = 2$。

  $b \equiv 5 \times 2 = \mathbf{10} \pmod{17}$。

• 代入求 $c$：$c \equiv 2(10) - 1 = 19 \equiv \mathbf{2} \pmod{17}$。

第三步：求秘密值 $a$

• 将 $b=10, c=2$ 代入 ①：

  $a + 10 + 2 \equiv 8 \pmod{17}$

  $a + 12 \equiv 8 \pmod{17}$

  $a \equiv 8 - 12 = -4 \pmod{17}$

  $a \equiv -4 + 17 = \mathbf{13} \pmod{17}$。

3. 答案总结

• 恢复的原多项式为：

  $$f(x) \equiv 2x^2 + 10x + 13 \pmod{17}$$

• 隐藏的秘密值 $a$ 为：

  $$a = 13$$

验证：

• $f(1) = 2(1)^2 + 10(1) + 13 = 25 \equiv 8 \pmod{17}$ （符合）
• $f(3) = 2(9) + 10(3) + 13 = 18 + 30 + 13 = 61 = 17 \times 3 + 10 \equiv 10 \pmod{17}$ （符合）
• $f(5) = 2(25) + 10(5) + 13 = 50 + 50 + 13 = 113 = 17 \times 6 + 11 \equiv 11 \pmod{17}$ （符合）

三、 综合计算题（计算机网络）

6. 介质访问控制（MAC 层） 在一个采用 1-坚持 CSMA/CD 协议的传统以太网（10 Mbps）中 ，发送一个完整数据帧所需的时间为 25.6ms 。

(1) 若某节点发送该数据帧时在发送过程中连续经历了一次碰撞，到第二次成功 ，求从开始发送到确认成功所需的最短时间。 (2) 若该节点在发送过程中连续经历了两次碰撞，直到第三次才发送成功，求完成该数据帧发送所需的最长可能时间（需考虑截断二进制指数退避算法） 。

(1) 经历一次碰撞，第二次成功的最短时间

【解析】

要求时间最短，需要所有不可控的延迟环节都取极小值：

1. 第一次碰撞耗时：假设碰撞发生在极近的距离，检测到碰撞的时间趋近于 0。但在标准的计算机网络考题中，通常默认一次完整的碰撞处理（包含发送强化干扰信号）会消耗掉一个争用期 $2\tau$。

   • 耗时 = 0.0512 ms。

2. 第一次退避耗时：碰撞次数 $n=1$，退避指数 $k=\min(1,10)=1$。

   节点在集合 ${0, 1}$ 中随机选择 $r$。要求时间最短，必须随机到 $r=0$。

   • 耗时 = $0 \times 2\tau =$ 0 ms。

3. 第二次发送并成功：题目已知发送该帧需要 25.6 ms。

【答案】

最短耗时 = 第一次碰撞耗时 + 退避耗时 + 成功发送耗时

计算：0.0512 ms + 0 ms + 25.6 ms = 25.6512 ms。

(若按理想极端情况不计入碰撞处理时间，则直接为 25.6 ms)。

(2) 经历两次碰撞，第三次成功的最长可能时间

【解析】

要求时间最长，需要每一次碰撞都发生在最远端，且每次退避都随机到最大值：

1. 第一次碰撞耗时（最坏情况）：信号传到最远端才发生碰撞并传回，耗费一个完整的争用期。
   • 耗时 = $2\tau =$ 0.0512 ms。
2. 第一次退避耗时（最坏运气）：$n=1$，$k=1$，随机集合 ${0, 1}$。取最大值 $r=1$。
   • 耗时 = $1 \times 2\tau =$ 0.0512 ms。
3. 第二次碰撞耗时（最坏情况）：再次在最远端碰撞。
   • 耗时 = $2\tau =$ 0.0512 ms。
4. 第二次退避耗时（最坏运气）：此时 $n=2$，$k=\min(2,10)=2$，随机集合扩展为 ${0, 1, 2, 3}$。取最大值 $r=3$。
   • 耗时 = $3 \times 2\tau = 3 \times 0.0512 =$ 0.1536 ms。
5. 第三次发送并成功：耗时 25.6 ms。

【答案】

最长耗时总和公式 = 碰撞1 + 退避1 + 碰撞2 + 退避2 + 发送耗时

代入公式：$2\tau + 1\times2\tau + 2\tau + 3\times2\tau + 25.6\text{ms} = 6 \times (2\tau) + 25.6\text{ms}$

计算：$6 \times 0.0512 \text{ ms} + 25.6 \text{ ms} = 0.3072 \text{ ms} + 25.6 \text{ ms} =$ 25.9072 ms。

(说明：在前面的通用解答中，公式推导为 $12\tau + 25.6\text{ms}$，这里的 $12\tau$ 等价于 $6 \times (2\tau)$，代入传统以太网的争用期 $2\tau = 0.0512\text{ms}$ 后，结果是一致的。)

7. TCP 拥塞控制 主机 A 向主机 B 通过 TCP 连接发送一个大小为 40000 B的文件 。已知网络的最大报文段长度 $MSS=1000$ B ，发送方的初始慢开始门限 ssthresh 为 8 MSS 。

(1) 在第 5 次传输（即第 5 个 RTT）时，拥塞窗口（cwnd）的大小是多少字节 ？

(2) 若在第 6 次传输时发生超时 ，此时的拥塞窗口（cwnd）和慢开始门限（ssthresh）将分别更新为多少？发送完整个文件一共需要多少个 RTT ？

核心初始参数梳理

• 最大报文段长度 (MSS) = 1000 B
• 文件总大小 = 40000 B = 40 个 MSS
• 初始慢开始门限 (ssthresh) = 8 MSS
• 初始拥塞窗口 (cwnd) = 1 MSS （TCP 默认初始值）

(1) 第 5 次传输时，拥塞窗口 (cwnd) 的大小

【解析】 TCP 建立连接后，首先进入慢开始 (Slow Start) 阶段，窗口大小呈指数级增长，直到达到慢开始门限 (ssthresh)，随后进入拥塞避免 (Congestion Avoidance) 阶段，窗口大小呈线性增长。

• 第 1 次传输 (RTT 1)：cwnd = 1 MSS，发送 1 个报文段。
• 第 2 次传输 (RTT 2)：收到 1 个确认，cwnd 翻倍 = 2 MSS，发送 2 个报文段。
• 第 3 次传输 (RTT 3)：收到 2 个确认，cwnd 翻倍 = 4 MSS，发送 4 个报文段。
• 第 4 次传输 (RTT 4)：收到 4 个确认，cwnd 翻倍 = 8 MSS。此时 cwnd 达到了 ssthresh (8 MSS)，慢开始阶段结束，接下来进入拥塞避免阶段。发送 8 个报文段。
• 第 5 次传输 (RTT 5)：收到 8 个确认，因为处于拥塞避免阶段，cwnd 只能线性加 1。因此 cwnd = 8 + 1 = 9 MSS。

【答案】 在第 5 次传输时，未发生异常，拥塞窗口（cwnd）的大小是 9 个 MSS，即 9000 字节。

(2) 第 6 次发生超时后的更新与总 RTT 计算

【解析】

1. 超时后的参数更新：
   • 在第 5 次传输顺利完成后，第 6 次传输开始时，cwnd 会再加 1，变为 10 MSS。
   • 如果在第 6 次传输时发生超时 (Timeout)，TCP 会采取严厉的降速措施：
     • 新的慢开始门限 ssthresh = 发生超时那一刻 cwnd 的一半，即 10 / 2 = 5 MSS。
     • 新的拥塞窗口 cwnd 直接重置为 1 MSS，并重新进入慢开始阶段。
2. 计算发送完整个文件需要的总 RTT： 我们需要追踪已经发送成功的数据量，以及超时后重新发送的过程。
   • 第 1~5 次传输（顺利完成）： 累积成功发送的数据量 = 1 + 2 + 4 + 8 + 9 = 24 MSS。 剩余未发送/需重传的数据量 = 40 - 24 = 16 MSS。 (注：第 6 次传输发送了 10 个 MSS，但因为超时全部丢失，不计入成功发送量)
   • 第 6 次传输（发生超时）： 计为 1 个 RTT（等待超时重传定时器触发）。
   • 超时后的恢复阶段（剩余 16 MSS）：
     • 第 7 次传输：cwnd = 1 MSS，发送 1 个，剩余 15 MSS。（慢开始）
     • 第 8 次传输：cwnd = 2 MSS，发送 2 个，剩余 13 MSS。（慢开始）
     • 第 9 次传输：cwnd = 4 MSS，发送 4 个，剩余 9 MSS。（慢开始）
     • 第 10 次传输：cwnd = 5 MSS（由于达到新的 ssthresh = 5，慢开始结束），发送 5 个，剩余 4 MSS。
     • 第 11 次传输：进入拥塞避免，cwnd = 6 MSS。我们只需要发送最后剩余的 4 MSS，文件传输完成！

【答案】

• 发生超时时更新的值：此时的拥塞窗口（cwnd）将更新为 1 个 MSS（1000 字节），慢开始门限（ssthresh）将更新为 5 个 MSS（5000 字节）。
• 总 RTT 数量：发送完整个文件一共需要 11 个 RTT（包含超时浪费的那 1 个 RTT）。