单选
1-5 BCDAC
6-10 DABDB
11-15 BACDB
填空
1、(rear-front+M)%M
2、有穷性
3、01122123412234
4、最优子结构性质和子问题重香性质
5、3
6、24000bit/s
7、单工、半双工、全双工
8、100s、5x10^3
9、信息帧、监督帧和无编号帧
10、11111001111101110111
11、维吉尼亚密码
12、8
13、23
14、有无密钥
15、(18,20)
简答
1
朴素的模式匹配思想是：从目标 S 中的第一个字符开始和模式 T 中的第一个字符比较（用 i 和 j 分别指示 S 串和 T 串中正在比较的字符位置），若相等，则继续逐个比较后续字符，否则从目标 S 的第二个字符开始再重新与模式串的第一个字符比较，依次类推，直至模式 T 中的每个字符依次和目标S 中的一个连续字符序列相等为止，则匹配成功，返回模式 T 中第一个字 符在目标 S 中的位置，否则匹配失败，返回 -1 值
KMP 的改进之处在于：每当一趟匹配过程中出现字符比较不相等时，不需回溯i值，而是利用已经得到的“部分匹配"的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较
表述清楚主串模式串之间的回溯，可以通过 next 数组消除回溯，设计 next 数组时可以通过最长前缀找到回溯位置等问题即给分
2
0-1 背包问题是指每一种物品都只有一件，可以选择放或者不放
背包问题(Knapsack problem)：是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高
背包问题可以用贪心算法求解，而 0-1 背包问题不能用贪心算法求解（用动态规划）
参照书本，表述清楚两个问题的概念，比较他们的不同点，如何解决这两个问题，即可给分（为什么 0-1 背包问题不可用贪心，这个最好提一下）
3
确认帧，超时重传，滑动窗口，答到三点内容并解释清楚即给分
4
相同点
- 都是动态路由协议
- 都是内部路由协议
- 如果 RIP 是版本 2（RIPv2）的话，那 OSPF 一样都支持变长子网掩码，支持 VLSM。
不同点
- RIP 是按跳数来算路由的，OSPF 是状态路由协议
- RIP 的算法简单，但在路径较时收敛速度慢，广播路由信息时占用的带宽资源较多，它适用于网络拓扑结构相对简单且数据链路故障率极低的小型网络，在大中型企业网络中，一般不使用 RIP
- OSPF 不会产生路由环路，不受路数限制，能够用于规模很大的网络，收敛速度快，支持大型异构网络的互联，并且不容易出现错误的路由信息，同时支持多重路径，支持路由验证提高了网络的安全性，支持负载均衡，支持 VLSM
5
ELGamal 签名体制
- 体制参数
- p：大素数
- g：Zp 的一个生成元
- x：用户私钥
- y：用户公钥
- 签名产生过程
- 计算 m 的哈希值 H(m)
- 选择随机数 k，计算 r = g^k (mod p)
- 计算 s = (H(m)-xr)k^(-1) (mod p-1)
- 以 (r,s) 作为数字签名
- 验证过程
应用
1
A：01011 B：0100 C：011
D：110 E：1110 F：00
G：10 H：01010 I：1111
2
线性探查法
- 查找成功：2.5
- 查找不成功：7
拉链法
- 查找成功：1.67
- 查找不成功：0.923
3
| 循环 | U | K | D[0]......D[6] | P[0]......P[6] | S[0]......S[6] |
|---|---|---|---|---|---|
| 初始化 | V1 | - | 5 M 14 M M M | 1 1 0 1 0 0 0 | 1 0 0 0 0 0 0 |
| 1 | V1 V2 | 1 | 5 15 14 12 M M | 1 1 2 1 2 0 5 | 1 1 0 0 0 0 0 |
| 2 | V1 V2 V5 | 4 | 5 15 14 12 1 8 15 | 1 1 2 1 2 4 5 | 1 1 0 0 1 0 0 |
| 3 | V1 V2 V5 V4 | 3 | 5 15 14 12 1 8 15 | 1 1 2 1 2 4 5 | 1 1 0 1 1 0 0 |
| 4 | V1 V2 V5 V4 V3 | 2 | 5 15 14 12 1 8 15 | 1 1 2 1 2 4 5 | 1 1 1 1 1 0 0 |
| 5 | V1 V2 V5 V4 V3 V6 | 5 | 5 15 14 12 1 8 15 | 1 1 2 1 2 4 5 | 1 1 1 1 1 1 0 |
| 6 | V1 V2 V5 V4 V3 V6 V7 | 6 | 5 15 14 12 1 8 15 | 1 1 2 1 2 4 5 | 1 1 1 1 1 1 1 |
4
活动和事件开始最早时间，最晚时间，要求全部写出
关键路径 <V1,V2>，<V2,V4>，<V2,V5>，<V4,V5>，<V5,V7>
5
不正确，正确的为 01100
6
(1)
分别写出组织机构 1，2，3，4 的 IP 地址
- 组织机构 140.24.7.0/26
- 组织机构 140.24.7.64/26
- 组织机构 140.24.7.128/26
- 组织机构 140.24.7.192/26
(2)
R1 路由表
| 子网掩码 | 网络地址 | 下一跳地址 | 接口 |
|---|---|---|---|
| /26 | 140.24.7.0 | Direct | 140.24.7.1 |
| /26 | 140.24.7.64 | Direct | 140.24.7.65 |
| /26 | 140.24.7.128 | Direct | 140.24.7.129 |
| /0 | 0.0.0.0 | 默认 | 222.118.2.3 |
R2 路由表
| 子网掩码 | 网络地址 | 下一跳地址 | 接口 |
|---|---|---|---|
| /26 | 140.24.7.192 | 222.118.3.3 | 222.118.2.1 |
| /24 | 140.24.7.0 | 222.118.2.3 | 222.118.2.2 |
| /32 | 222.118.3.2 | 222.118.3.3 | 222.118.2.1 |
| /0 | 0.0.0.0 | 默认 | 130.11.120.1 |
R3 路由表
| 子网掩码 | 网络地址 | 下一跳地址 | 接口 |
|---|---|---|---|
| /26 | 140.24.7.192 | Direct | 222.118.7.193 |
| /32 | 222.118.3.2 | Direct | 222.118.3.1 |
| /0 | 0.0.0.0 | 默认 | 222.118.3.3 |
7
(1)
求主机的源 MAC 地址和源 IP 地址
- 源 MAC 地址：00-15-C5-C1-5E-28
- 源 IP 地址：10.2.128.100
(2)
求该报文段 IP 数据报总长度和位偏移量
- 总长度：01ef=495B
- 偏移量：64*8=512B
(3)
结合该数据报文分析该主机请求通信中可能使用了哪些协议，并简述这些协议功能？
RIP，IP，TCP，HTTP，PPP 或 HDLC，ARP，NAT（注意该 IP 地址为私有地址，其它协议合理即可）
8
(1)
如用户 A 和用户 B 希望交换一个密钥，取素数 p 和整数 g，g 是 p 的一个原根，公开 g 和 p (2分)
- A 选择随机数 X1 < p，并计算 Y1 = g^(X1) mod p
- A 选择随机数 X2 < p，并计算 Y2 = g^(X2) mod p
- A 计算密钥的方式是：K = Y2^(X1) (mod P)
- B 计算密钥的方式是：K = Y1^(X2) (mod P)
该方法存在中间人攻击(1分)
描述中间人攻击(2分)
(2)
选择 p 阶循环群 G、GT，选择 g∈G，e(g, g) ≠ lcr
第一轮
- A 选择私钥 a∈G，并且计算 e(g^a, g) 发给 B
- B 选择私钥 b∈G，并且计算 e(g^b, g) 发给 C
- C 选择私钥 c∈G，并且计算 e(g^c, g) 发给 A
第二轮
- A 计算 [e(g^c, g)]^a 发给 B
- B 计算 [e(g^a, g)]^b 发给 C
- C 计算 [e(g^b, g]^c 发给 A
第三轮
- A 计算 e(g^b, g^c)^a = e(g, g)^(abc)
- B 计算 e(g^a, g^c)^b = e(g, g)^(abc)
- C 计算 e(g^a, g^b)^c = e(g, g)^(abc)