一、概念与简答题

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

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

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

4. 比较数据报服务与虚电路服务的异同。

相同点：

  • 都属于分组交换技术，将长报文拆分成若干分组进行转发。
  • 都采用动态分配带宽，通过统计时分复用提高线路利用率。

不同点：

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

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

4. 椭圆曲线密码学（ECC）计算

在有限域 $GF(17)$ 上，椭圆曲线方程为 $y^2 \equiv x^3+2x+2 \pmod{17}$，基点 $B=(5,1)$，用户 A 私钥 $\alpha=3$，求公钥 $3B$。

核心公式：

  • 倍点运算（$P=Q$）：$\lambda \equiv \frac{3x_1^2 + a}{2y_1} \pmod{p}$
  • 点加运算（$P \neq Q$）：$\lambda \equiv \frac{y_2 - y_1}{x_2 - x_1} \pmod{p}$
  • 结果点：$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$

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

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

【答案】用户 A 的公钥为 $(10, 6)$。

5. Shamir 门限秘密共享

在 $GF(17)$ 上，二次多项式 $f(x) \equiv a+bx+cx^2 \pmod{17}$，已知份额 $(1,8)$、$(3,10)$、$(5,11)$，求多项式和秘密值 $a$。

建立方程组：

消元求解：

  • ②-①：$2b + 8c \equiv 2$，化简得 $b + 4c \equiv 1$ ④
  • ③-②：$2b - c \equiv 1$ ⑤
  • 由⑤得 $c \equiv 2b-1$，代入④：$9b \equiv 5$，因 $9^{-1} \equiv 2$，得 $b \equiv 10$
  • $c \equiv 2(10)-1 = 19 \equiv 2 \pmod{17}$
  • 代入①：$a \equiv 8 - 10 - 2 = -4 \equiv 13 \pmod{17}$

【答案】 $f(x) \equiv 2x^2 + 10x + 13 \pmod{17}$，秘密值 $a = 13$。

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

6. CSMA/CD 碰撞退避

10 Mbps 以太网，发送一帧需 25.6 ms，争用期 $2\tau = 0.0512$ ms。

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

最短时间取退避 $r=0$：

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

最长时间取每次退避最大值（$r_1=1, r_2=3$）：

7. TCP 拥塞控制

文件 40000 B，MSS = 1000 B（40 MSS），初始 ssthresh = 8 MSS，初始 cwnd = 1 MSS。

cwnd 变化过程：

RTT cwnd 阶段 累计发送
1 1 慢开始 1
2 2 慢开始 3
3 4 慢开始 7
4 8 慢开始→拥塞避免 15
5 9 拥塞避免 24
6 10 拥塞避免（超时） —

(1) 第 5 次传输时 cwnd = 9 MSS = 9000 字节。

(2) 第 6 次超时后：

  • $ssthresh = 10/2 = \textbf{5 MSS}$，$cwnd = \textbf{1 MSS}$
  • 剩余 40 - 24 = 16 MSS 待发送

超时后恢复过程：

RTT cwnd 剩余
7 1 15
8 2 13
9 4 9
10 5（达到新 ssthresh） 4
11 6（拥塞避免，只需发 4） 0 ✓

【答案】总共需要 11 个 RTT。