Loading... ## data structure ### 选择题汇总 1. 广义表 head tail 1. head 取表头的 原子 or 表 2. tail 取尾部的 表，且必须加 ()，tail 会把除了头以外所有组成一个表取完 3. 广义表的深度，长度 2. 树 1. 树转二叉树、逆过程；[参考](https://zhuanlan.zhihu.com/p/134251528) 2. 树转森林 3. 完全二叉树；[参考](https://zhuanlan.zhihu.com/p/152285749) 4. 前中后序遍历、层次遍历 1. 已知 前序 + 中序 或者 后序 + 中序，就可以唯一确认一颗二叉树 1. 层次遍历；从根节点开始，逐层遍历，从左往右遍历 5. 二叉排序树：概念，作用；使用中序遍历就能获取从小到大的数据排序 6. 线索二叉树，[参考](https://zq99299.github.io/dsalg-tutorial/dsalg-java-hsp/10/03.html#介绍) 7. 二叉树的算法表示 8. 树转森林的方法；从 root 开始，子树的右边拆掉，直接连接到当前根 9. 最优二叉树、哈夫曼树，[参考](https://www.cnblogs.com/wkfvawl/p/9783271.html) 1. 给权 {5 6 7 8 15}；构造：每次都取最小的两个，合成最大的，不能计算合成的数，构造哈夫曼树时，先排序，全部放到最底端，然后连线，最后可以再优化着画，这样方便计算层数 2. WPL：由各点的带权值之和，权值乘频率的累积 3. 前缀编码 10. 平衡二叉树；平衡二叉树左右深度差不高于 1；平衡二叉树一定是二叉排序树 11. 124 个叶子节点，问节点最多有多少；124 个叶子，表示有 124 - 2 个分支（有一个是 root 没有父节点），所以总共有 124 + 123 个节点，最后一个节点可以有 0/1 个节点，故最多 124 + 123 + 1 = 248 个 12. 有 n 个结点的二叉树采用二叉链表存储；空指针有 2n-(n-1)=n+1 个；其中的 n-1 是分支的个数，2n 是总共指针域的个数（每个结点左右两个指针域）；[参考](https://www.nowcoder.com/questionTerminal/6fa5f1aaee7b45dfa67f1ad5708a84a0) 13. 度为 4 的树 T，求 T 的叶子数；树的结点数 = 边数 + 1 = 4+4+3+4 + 1 = 16，叶子数 = 结点数 - 度不为 0 的结点数量 = 16 - 4-2-1-1 = 8；[参考](https://www.nowcoder.com/questionTerminal/4bbf16bb8b444170bb438a8ab0976f56) 14. 一颗完全二叉树第 6 层有 8 个叶结点，求完全二叉树结点最多个数；前 6 层满有 2^n-1=63，第七层有 2^(n-1)=64，缺少 2*8=16个，故最终有 63 + 64 - 16 = 111 个 3. 线性表 1. 二分查找； 1. 要求必须有序； 2. 画出折半查找过程的判定树 3. 计算 ASL 失败 和 ASL 成功 2. 线性表的岗哨模式； 4. 遍历算法 1. BFS，广度优先，队列 2. DFS，深度优先，栈 5. 图 G<V,E>，顶点 V（vertex），边 E（edge），[参考](https://www.bilibili.com/video/BV1D5411c71o) 1. 无向图、有向图 2. 带权不带权 1. 带权有向图：AOE 网， 1. 关键路径：路径长度最长的路径；由于在 AOE 网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（路径上各活动持续时间之和） 1. 找出关键路径和关键活动：列出活动表，e[i] 是最早开始时间，l[i] 最晚开始时间，e[i] == l[i] 即为关键活动；列出每个节点的最大权值，最早时间从前往后，最晚时间从后往前（如果上一个节点不是关键节点，得再往前找关键节点） 2. 拓扑序列：解决能否顺利完成任务 3. 邻接矩阵，带权邻接矩阵 4. 邻接表，有向图的邻接表； 5. 数组存储，链表结合存储（表头，链式） 6. 稀疏图、稠密图 7. 连通图：每个节点之间都必须能连通，因此至少有 n - 1 条边 8. 迪杰斯特拉（Dijkstra）算法， 9. 拓扑排序算法；可以用于判断一个有向图是否存在回路，如果存在拓扑排序，一定是无回图，否则至少包含一个环路 10. 最小生成树算法；[参考](https://zhuanlan.zhihu.com/p/136387766) 用于在无向加权图中找到连接所有结点且权重和最小的子图； 1. Kruskal 算法，遇到回路就放弃，但不能用于判断图是否有回路； 2. Prim 算法，每次都找最小边 6. 散列表，哈希查找；散列函数必须解决两个问题：解决冲突和散列函数设计 1. 构造哈希函数的常用方法；[参考](https://zhuanlan.zhihu.com/p/31441081) 1. 除留余数法：关键字除以一个不大于哈希表长度的正整数 P，哈希的输出为其所得余数；P 值选择接近表长且不与组成关键字的字符基数直接相关的质数； 2. 数字分析法；取一组数据中共同有规律的部分作为哈希的输出； 3. 平方取中法；取关键字平方后的中间几位数作为散列地址 2. 开地址法、线性探测法；[参考](https://www.cnblogs.com/-beyond/p/7726347.html)， 1. 增加：code % e.key，已有就往后占位 2. 查找：code % e.key，与所找不同就往后找，直到找到，或者碰到空的 3. 删除：code % e.key，与所找不同就往后找，找到以后删除，然后继续往后重新对所存在的序列进行 rehash 并置位 4. 扩容：将原来的数组遍历，取出数据后重新 hash 放到新的数组中，增加的法则与前文相同 5. 同义词指的是模后映射到相同地址的关键字（尽管可能往后占位解决冲突了） 3. 二次开地址法解决冲突，[参考](https://blog.51cto.com/u_15072917/4731787) 1. 基本法则与开地址法相同，在碰到冲突时，不是直接往后占位，而是 29 % 11 = 7，冲突，则 (7 + 1) % 11 = 8 4. 链地址法、拉链法；在同一位置上维护一个链表存储每个落到当前位置的关键字 5. 处理冲突的查找成功和查找失败平均查找长度； 1. 拉链法查找成功时，分母为关键字个数；拉链法查找不成功时，分母为哈希表长度； 2. 线性探测法，[参考](https://www.cnblogs.com/47Gamer/p/13160610.html)；asl 成功，是各元素对应冲突次数的合集，除以元素个数；asl 失败，是散列表各位置往后碰到第一个为空的格子，所走过的格子数量和，分母是散列表长度 6. 装填因子，指关键字个数除以散列表的长度 7. 排序算法 1. 所需辅助空间，最坏情况下时间复杂度； 1. 快速排序；O(logn)，O(n^2) 2. 2-路归并排序；O(n)，O(nlogn) 3. 堆排序；O(1)，O(nlogn) 2. 起泡、气泡、冒泡 3. 希尔排序 4. 归并排序 1. 2-路归并排序，[参考](https://www.bilibili.com/video/BV1ta4y1s7iK) 5. 基数排序，[参考](https://www.runoob.com/w3cnote/radix-sort.html) 6. 选择排序 7. 堆排序； 1. 如果向堆中插入新数据；将新元素放在堆的末尾，然后进行上浮操作，将新元素与父结点比较并交换，直到满足堆的性质；堆通常是完全二叉树，插入会导致树的高度增加，高度增加对应着对数增长，其时间复杂度是O(log n) 1. 堆排序时，从下往上，从右往左开始调，并且选择非叶子结点；[参考](https://7km.top/algorithm/heapsort/) 8. 选择排序，[参考](https://www.runoob.com/w3cnote/selection-sort.html) 9. 插入排序；[参考](https://www.runoob.com/w3cnote/insertion-sort.html) 10. 快速排序；[参考](https://www.bilibili.com/video/BV18T4y197xL) 8. 链表的操作 1. 单链表 2. 双链表 3. 增删查改 9. 串 1. 连接串的概念 10. 队列 1. 循环队列 1. 循环队列的引入是为了解决假溢出时造成的大量移动数据 2. 增删查改 3. 一个队列 Q，计算其中元素个数；front 一般指向对头元素的前一个位置，rear 一般指向队尾元素，故元素个数：(Q.rear - Q.front + maxSize) % maxSize 2. 单向队列的增删查改 3. 双向队列的增删查改 11. 栈 12. 解决优化问题算法 1. 动态规划算法；有最优子结构，通常用于解决最长公共子序列、背包问题等 2. 贪心算法；每一步的最优选择可以推导出全局最优解，用于求解最短路径、最小生成树问题 13. 数组与对角矩阵，[参考](https://www.bilibili.com/video/BV1QV4y1s7Nn) 1. 压缩矩阵；节省空间 1. 对称矩阵 $a_{12} = a_{21}$，有 i 行 j 列 2. 在逻辑上是矩阵的二维形式，在物理上是使用一维数组来存储的，因此在取第 $a_{ij}$ 个元素时，需要先求出前面 i - 1 行再加上当前行前面 j 个元素总共占用了一维数组多少个位置；其中第 i 行有 i 个元素 计算法则： $$ \begin{align} & a_{ij} = \frac{(1 + (i - 1))(i - 1)}{2} + j - 1 = \frac{i(i - 1)}{2} + j - 1, &i \geq j \\ & a_{ji} = \frac{(1 + (j - 1))(j - 1)}{2} + i - 1 = \frac{j(j - 1)}{2} + i - 1, & i \lt j \end{align} $$ $\frac{i(i-1)}{2}$ 是前 i - 1 行有的数量，$+ j$ 是当前行的 $a_{ij}$ 前面有的数量，$-1$ 是由于矩阵从 $(1, 1)$ 开始，而数组从 0 开始；得知 $a_{ij}$ 后，只需要对调 i 和 j 即可求出 $a_{ji}$ 2. 下三角矩阵； 1. 只有下半有数，上半全为 0 2. 下三角矩阵转化成数组时，分为两部分，前面部分全部存储下三角中的数据，后部分只占 1 个数组位，整个数组看起来为 `arr[n] = [1, 2, 3, ..., 0]`， 计算法则如下 $$ \begin{align} & a_{ij} = \frac{(1 + (i - 1))(i - 1)}{2} + j - 1 = \frac{i(i - 1)}{2} + j - 1, &i \geq j \\ & a_{ij} = \frac{(n + 1)n}{2} + 1 - 1 = \frac{(n + 1)n}{2}, & i \lt j \end{align} $$ 表示要取上半部分的内容时（即 i < j 时），直接取数组最后一位的 0 即可 3. 上三角矩阵 1. 只有上半有数，下半全为 0 2. 可以参考下三角矩阵，计算公式如下： $$ \begin{align} a_{ij} &= \frac{[n + (n - (i - 2))](i - 1)}{2} + (j - i) + 1 - 1 \\ &= \frac{(2n + 2 - i)(i - 1)}{2} + (j - i), &i \leq j \\ a_{ij} &= \frac{(n + 1)n}{2} + 1 - 1 = \frac{(n + 1)n}{2}, &i \gt j \end{align} $$ 注意 i 和 j 的大小关系与下三角的区别就好 4. 三对角矩阵 1. 三条对角线引出来，只有对角线上有数，其他全为 0；因此三对角矩阵有 $3n - 2$ 个非零元素 2. 计算法则过于复杂，只给出式子；假设给出了数组中的第 k 位，要求其在三对角矩阵中的位置，也就是求 i 和 j，式子如下： $$ k = 2i + j - 3 $$ 根据 k 倒推出 i 和 j 流程：由 $i = [(k + 1) \bmod 3] + 1$ 推出 i 的位置，再由上式中的 $j = k + 3 - 2i$ 计算出 j 5. 稀疏矩阵 1. 写出稀疏矩阵的三元组线性表表达形式； 2. 给出三元组顺序存储表示；第一行元素分别代表：多少行，多少列，非零元素个数 14. 串 1. 串的模式匹配 2. kpm 匹配算法，参考第 57 页，先写出完整串，大致思想如下 | next | 模式匹配：abaabcac | | ---- | ------------------ | | -1 | abaabcac | | 0 | a | | 0 | a b | | 1 | a b a | | 1 | a b a a | | 2 | a b a a b | | 0 | a b a a b c | | 1 | a b a a b c a | | 0 | a b a a b c a c | 最终从 -1 开始各 next 值 +1，最后一行不要，得 next 值：01122312 ## computer networking ### 基础知识 1. 因特网的前身是 ARPANET 2. 网络的拓扑可以分为：星形网、总线网；总共有星形、环形、树形、总线性、网形 3. 计算机网络由 通信子网 和 资源子网 构成 4. 互联设备； 1. 物理层（中继器）； 1. 数据链路层（网桥/交换机）； 1. 网络层（路由器）； 1. 高层设备（网关）； 5. 死锁主要有重装死锁和直接死锁 6. 网络协议三要素：语义、语法、时态 7. tcp/ip 参考模型（五层结构）：网络接口层（物理层、数据链路层合并）、网络层、传输层、应用层 8. 计算机网络等两大功能是连通和共享 9. 计算机网络的分类 1. 作用范围：广域网 WAN，城域网 MAN，局域网 LAN，个人 PAN； 2. 使用者：公用网，专用网 3. 介质：光纤、有线、无线 10. **协议** 规定了对等层实体之间交互的数据、交互方式等规程 11. 流量整型是指调节进入网络的数据流的平均速率和缓冲区大小 12. OSI 各层的主要功能： 1. 物理层： 2. 数据链路层：流量控制、差错控制、成帧 3. 传输层：差错控制、流量控制、顺序管理 13. 使用隧道技术进行网络互联的前提是原主机和目的主机所处的网络使用相同的网络层技术 14. RFC 文档（Request for Comments，请求评论）是一系列记录关于互联网标准、协议和最佳实践的文件集合；互联网 **协议** 标准是按照 OSI 参考模型制定的，RFC 是记录这些协议标准的文件集合；所有互联网标准都是 RFC，但 RFC 不仅仅是互联网标准 15. ISM，指工业、科学和医疗，是一些由 ITU 指定的在全球范围广泛使用的特定频段； 16. 综合业务数字网，ISDN；数字电话网络国际标准，是一种典型的电路交换网络系统；综合两字指使用一条线路就能传输语音、数据和图像等 17. 主要的网络标准化组织有：ISO、IEEE、IETF（因特网工程任务组）、ITU-T（国际电信联盟标准化部） 18. 下层为上层提供的服务是由一组系统调用或命令实现的，这些调用或命令被称为原语； 19. 数据交换的方式；电路交换，报文交换，分组交换 1. 电路交换（数据链路层）；通信双方建立一条物理链路，只能被单独占用，适合长时间、连续地传输数据 2. 报文交换（网络层）：发送的信息被组成报文，在网络中经过多次存储转发到目标结点，存在通信转发时延 3. 分组交换（网络层）：将数据分为多个小的固定长度的数据报；接收方需要对接收到的各个分组重新排序； 1. 使用 ATM （异步传输模式）网络； 1. ATM 是以信元为基础的一种分组交换和复用技术，支持许多种类型如声音、数据、传真、实时视频、CD质量音频和图像的通信，面向连接 2. ATM单元，长度 53 字节（5 字节头，48 有效载荷），ATM 单元就是信元 2. 虚电路，X.25，采用 X.21 接口标准；953 里是虚呼叫（交换虚电路，不需要建立固定连接），永久虚电路（固定虚电路，连接前需要建立固定路径） 20. 数据通信的分类：按照数据传输的方向分类；按照同步的方式分类 1. 数据传输的方向 1. 单工，信道只能单向，例如广播； 2. 半双工，信道可以双向，但是一次只能一边进行单向传输，例如对讲机； 3. 全双工，信道允许同时在两个方向上进行通信，信道被分为两个部分，一个发送数据，一个接收数据；例如打电话 2. 同步的方式 1. 同步传输，双方时钟频率要一致，发送方发送连续的比特流； 2. 异步传输，发送方发送完一个字节后，可以经过任意长的时间间隔再发送下一个字节 ### OSI 七层参考模型 #### 物理层 1. 电气特性（0、1 哪个是电压）、机械特性（双绞线、接口之类的）、过程特性、功能特性 2. 双绞线易受电磁干扰，耐久性低 3. 以太网的物理层标准 100BaseT，表示 数据速率 100Mb/s、基带信号、双绞线 4. 编码：电压（模拟信号）转 0101；调制：0101（数字信号）转电压 5. ADSL，非对称数字用户线路；用电话线的较低频率来接入互联网，需要调制解调器（Modem）来实现数字信号和模拟信号之间的转换，适配于 ADSL 的调制解调器是被称之为 DSL 调制解调器 6. 物理层信道复用（Division Multiplexing）的方式有：频分复用（Frequency DM，FDM）、时分复用（Time DM，TDM）、码分复用（Code DM，CDM） 7. 典型的有线传输介质是：光纤、双绞线、同轴电缆、电力线 8. 信号在传输，可能出现的传输损伤为：衰减、噪声 9. 在电话网中，一路话音经过 PCM 编码后的传输速率为 64kbps 10. V.28 电气特性（负逻辑）；-3～-15 是 1，+3～+15 是 0 #### 数据链路层 1. 以太网、数据链路层中的基本单位是帧 2. ARP，地址解析协议； 1. ARP，，主要作用是将 IP 地址转换为 MAC 地址，arp 请求是广播，响应是单播；跨子网传输时，以太网帧头的目的地址是路由器端口的 MAC 地址 2. 用于将 ip 地址映射为 mac 地址； 3. 成帧 1. 成帧的方式主要有：零比特填充（5 个 1 后加 0），字节填充（添加转义字符 0x7D，一般用于帧界定） 2. PPP 协议，Point-to-Point Protocol，是一种用于在两个结点之间进行数据传输的数据链路层协议，PPP 不具备 MAC 功能 4. 介质访问控制，MAC；局域网中最重要的技术：介质访问控制技术 1. 衡量介质访问控制子层中，多路访问协议性能的主要指标有：迟延、吞吐量 2. ALOHA：用户有帧就发，采用冲突监听和随机重发机制；容易重叠破坏 3. 载波监听多路访问，CSMA；站点要发数据前，先监听总线上有无正在发送数据的计算机，如果有则等待，随后找时间再发；以太网监听方式、或者问常用的载波侦听多路访问协议（CSMA）如下 1. 非坚持型 CSMA，随机时延后退，减少冲突，但是增大发送时延 2. 1-坚持型 CSMA，持续监听信道，遇到空闲就发送，有利于抢占信道，减少信道空闲时间，但是增大冲突概率 3. p-坚持型 CSMA，在信道空闲时以概率 P 发送，以概率 1-P 延时，关键在于 P 的选择 4. 载波监听多路访问/冲突检测（CSMA/CD）；主要是用于总线式以太网，检测电压变化，当数据发生碰撞，电压就会跟着发生变化； 1. 总结为：先听再说、边说边听、冲突检测、冲突停止； 2. 该协议的三个通信状态是：空闲、冲突、传输 3. 半双工工作模式下，采用 CSMA/CD 多址接入时，可以利用 Hub 和 switch 进行组网 5. CSMA/CA；也是载波监听，这是 WLAN 的；主要应付隐藏终端和暴露终端的问题 1. MACA，用于解决 WLAN 中的多址接入和避免冲突；主要原理是采用请求发送（RTS，Request to Send）和清除发送（CTS，Clear to Send）的机制，要发数据前，先发一个 RTS 给目标，目标如果可以接收消息，就广播 CTS 给其他所有节点，通知他们这段时间被占用，有效解决因为隐藏终端产生的碰撞 5. 多路复用技术：即多个用户共享线路资源 1. 频分复用，按频率划分不同信道 2. 时分复用，按时间划分，用户在不同时间使用相同的频率传输 3. 波分复用，在波长划分 4. 码分复用（码分多址 CDMA），为用户分配独特的码片序列，每个站点的码片序列各不相同且正交 6. 交换机转发分组的依据是目的 MAC 地址 7. 交换机上的端口没有 MAC 和 IP，工作在数据链路层不具备寻址和路由能力； 8. 数据链路层成帧的方法 1. 字符计数法：用特定字符来指示数据帧中数据字段的长度 2. 字符填充法：数据帧以特定的开始和结束字符标记，如果数据中包含这些标记，需要添加转义字符 3. 比特填充法：11111 后添加 0 4. 物理层编码违例法：每个数据帧都以特定的帧头尾标识； 9. 在传输层，无连接指类似 udp 协议，面向连接指 tcp 协议 10. 位图协议是 mac 协议的一种，通常用于卫星通信等网络，是一种无冲突协议；其他无冲突协议还有：令牌传递、二进制倒计数法 11. IEEE 802 标准将数据链路层划分为：逻辑链路控制 LLC 子层、媒体接入控制 MAC 子层 1. IEEE 802.5 局域网环令牌 2. IEEE 802.3 以太网标准，规定数据帧格式，传输速率，物理介质等 3. IEEE 802.11，无线局域网标准 12. 数字载波标准（数字电话和数据通信系统），T1 的速率是 1.544 Mbps （采取时分多路复用技术有 24 个信道，每个信道的速率是 64 kbps）；E1 的速率是 2.048 Mbps，中国采用的是 E1 标准； 13. HDLC（高级数据链路控制），一种面向 bit 的通信控制流程，可以实现错误检测，也就是规定了使用曼彻斯特编码等； #### 网络层 1. 路由器 1. 使用路由器互联多个局域网时，这些局域网的数据链路层协议和物理层协议都可以不同 2. 路由器转发分组的依据是 IP 地址 3. 路由器工作在网络层，具备路由能力，各端口有 MAC 和 IP 4. 路由器可以隔离 MAC 层广播帧 5. 分组转发时，如果出现两个都可以达到的网络地址，则优先选择 cidr 更长的 6. 在大型网络中，为了防止路由表过大，减小路由开销，通常采用分层路由策略 7. 路由协议（算法） 1. 链路状态路由算法（LR）中每个节点都需要向全部节点发送链路状态信息；OSPF 是一种基于链路状态的路由协议 2. 距离矢量路由算法；RIP 协议是分布式域内路由协议，采用距离矢量算法，这种算法不能获取网络拓扑结构（只知道下一个要去的路由器是哪个） 2. 在网络层，无连接说的是"每个数据包独立传输"，面向连接说的是"使用虚电路进行通信" 3. ipv4 1. TTL 字段的作用是规定路由的跳数 2. ipv4 分组的分段可以在任何一个途径的路由器进行，但是 ip 分段的重组只能在最终的目的主机进行 3. ipv6 有 128 位，ipv4 是 32 位 4. ip 1. 在整个因特网传输过程中，ip 数据报首部中的源地址和目标地址都不会改变 2. ip 地址中，网络号的作用是指定主机所属的网络 3. 在 internet 上传输的 ICMP 报文封装于 ip 报文中 4. ip 协议提供不可靠无连接的网络传输服务 5. Internet 通过 ip 地址和端口号来标识传输地址 6. ip 地址采用分层编址方式，常见的分层编址还有身份证，邮编等 7. ip 划分； 8. ip 中，全 0 的地址一般称为整个网络，全 1 的地址为广播地址；另外，在 TCP/IP 中，**主机号** 全 0 称为本地地址，全 1 称为广播；进行主机地址选择时，主机位全为 1 时是广播地址，全为 0 是网络地址；假如 cidr 为 22 时， x.x.01 / 110000.FF 可以作为主机地址，但是 x.x.01 / 000000.00 则不可以，因为其后面全是 0 ，这是子网的网络地址； 9. ip 报文中，端口长度为 2 字节，主要作用是标识应用程序或通信进程；在 TCP/UDP 传输段中，源端口地址与目的端口地址不能相同 #### 传输层 1. 滑动窗口协议有：后退式 n-ARQ、停等式 ARQ、选择重发式 ARQ 1. ARQ 技术，即自动请求重发技术；利用差错检测技术自动地对丢失的帧和错误帧请求重发 2. 回退 N 帧：发送窗口大于等于 1，接受窗口为 1，不用缓存，发送方可以连续发送多个分组，当收到窗口第一个分组的 ACK 后，窗口向后滑动一位；如果迟迟没有收到某一分组的 ACK，则超时后重发该分组以及之后所有分组；发送窗口最大为 $2^{n}-1$； 3. 停等式：发送和接收窗口都为 1，发送数据后等待接收方回复，若收到回复则继续发送下一个分组，若没有则超时重传； 4. 选择重发式：接收方发现某个帧出错，将之后的帧都放到接收缓冲区，要求发送方重传出错的帧（发送一个重传请求 NAK），接收方重传该帧。等到所有帧都按顺序到位后，再在缓冲区中组合并交付给上层；发送窗口和接收窗口最大都为 $2^{n-1}$ 2. 传输层提供了两种类型的服务：面向连接的服务（TCP）和无连接的服务（UDP） 1. tcp 1. 进行面向连接的数据传输，要经历：建立连接、传输数据、释放连接三个过程，意味着可靠，顺序 2. tcp 在确认信息中会捎带下一个希望接收的字节（也就是 ack） 3. tcp 发送方的窗口大小取决于：接收方允许窗口、拥塞窗口 2. udp 1. 无连接的服务，每个分组独立地到达目的地，不保证可靠的顺序提交； 2. udp 协议的特性是：提供无连接服务、端到端服务、全双工服务 #### 会话层 #### 表示层 #### 应用层 1. 电子邮件；smtp 是专门发送邮件的通讯协议，走互联网，端口号 25；pop3 是专门接收，端口号 110； ### 一些表格 中英文简称对照表： | 英文简称 | 中文名 | 英文简称 | 中文名 | | -------- | ----------------------------- | -------- | -------------------------- | | ADSL | 非对称数字用户线路 | NAT | 网络地址转换协议 | | ARQ | 自动重传请求 | OSI | 开放式通信系统互联参考模型 | | ATM | 异步传输模式 | OSPF | 开放式最短路径优先 | | B2C | 商对客 | PAN | 个人区域网，个域网 | | BGP | 边界网关协议 | PSTN | 公共电话交换网 | | CIDR | 无类别域间路由 | QoS | 服务质量 | | CSMA/CA | 载波侦听多址接入/尽量避免冲突 | REID | 资源管理实体标识 | | CSMA/CD | 载波侦听多址接入/冲突检测 | RIP | 路由信息协议 | | DHCP | 动态主机设置协议 | RTP | 实时传输协议 | | DMT | 离散多音 | RTCP | 实时传输控制协议 | | ICMP | 互联网控制报文协议 | SONET | 同步光网络 | | IEEE | 美国电气和电子工程师协会 | TCP | 传输控制协议 | | IGMP | 因特网组管理协议 | TSAP | 传输服务访问点 | | ITU | 国际电信联盟 | UTP | 无屏蔽双绞线 | | MAC | 介质访问控制 | UDP | 用户数据报协议 | | MACA | 多址访问冲突避免协议 | | | --- ip 几类网划分，共有 A，B，C，D，E 五类地址，[参考](https://blog.csdn.net/kzadmxz/article/details/73658168) | 名称 | 范围 | 描述 | | ---- | --------------------------- | -------------------------------------------------------- | | A 类 | 1.0.0.0 - 126.0.0.0 | **0000** 0000.0.0.0，前 8 位是网络地址，后面全是主机地址 | | B 类 | 128.0.0.0 - 191.255.0.0 | **1000** 0000.0.0.0，前 16 位是网络地址 | | C 类 | 192.0.0.0 - 223.255.255.0 | **1100** 0000.0.0.0，前 24 位 | | D 类 | 224.0.0.0 - 239.255.255.255 | **1110** 0000.0.0.0，用于多播 | | E 类 | 224.0.0.0 - 255.255.255.255 | **1111** 0000.0.0.0，保留地址 | --- 一个 TCP/IP 标准模型参考 | 模型层 | 相关概念 TCP | 相关概念 UDP | | -------------------- | --------------------------------- | --------------------- | | 应用层 | TELNET、FTP、SMTP、HTTP | DNS、TFTP、SNMP、DHCP | | 运输层 | 采用 TCP | 采用 UDP | | 网际层 | （该层）ICMP、IGMP、IP、RARP、ARP | | | 网络层（网络接口层） | | | ### 计算题 #### CRC 冗余码计算 1. 求生成多项式 2. 由生成多项式倒推是否传输出错 生成多项式：G(x) = x6 + x5 + x + 1，多项式有 7 位，则其余数应该取 6 位，则 n = 6，1100 011 信息位：1101 1100 1000 1，计算补 6 个 0， 1101 1100 1000 1 000000 冗余码：长度与 n = 6 一致，0 10110 最终结果：1101 1100 1000 1 010110 验算：最终结果 / 生成多项式 = 0，则无差错；在验证题目时，看清楚题目要求的是数据中某位出现错误，也即上面的 1101 1100 1000 1，不包括最终结果中最后的 6 位 crc --- #### 数据报的分片 1. 给出 TCP 数据报长度，给出 MTU，问分片标识符（基本不变）、对应片偏移（当前片对应数据报起始位置 / 8，原因是 ipv4 中的偏移单位为 1 字 = 8 Bytes）、DF、MF、几个分片？注意数据报长度 ≠ 分片长度，需要 + 20 Bytes 2. 给出 UDP 数据报长度，UDP 不能在运输层分片（TCP 可以）。当 udp 报文要使用以太网来传输时，必须加上 tcp 的 20 Bytes 的头，因此包含有 udp 的报文总长为 1480 = 1472 数据 + 8 udp 头 > 一个 UDP 用户数据报的数据字段有 6192 Bytes，在链路层使用以太网来传输，问应当划分几个 IP 数据报片，要求说明每一个数据报字段长度以及片偏移字段的值。 该 UDP 用户数据报总长度需要加上 8B，故要传输的总长度为 6192 + 8 = 6200 B；使用以太网来传输，需要添加 ip 报头，在 MTU 为 1500 的情况下，每使用一个 ip 数据报运载 udp 报文时，其长度为 1500 = 20 B 的 ip 报头 + 1480 B 数据段；故总共有 6200 / 1480 = 4 完整片 + 1 剩余片，故总共需要分 5 片，得到片偏移字段分别为 0、185、370、555、740 3. 注意题目要求的是 IP 数据报片（需要加上标准数据报头），还是纯数据报片（不用考虑 ip 数据报标准头） TCP，UDP 报文的标准结构：TCP 20 Bytes，UDP 8 Bytes，[参考 1，tcp](https://www.cnblogs.com/JCpeng/p/15256786.html)，[参考 2，udp](https://www.cnblogs.com/JCpeng/p/15260266.html) DF：Dont fragment MF：More fragment MTU：Maximum Transmission Unit，最大传输单元，常见的是 1500，其中包括对应的 tcp 或者 udp 头占用，则数据段分别为 1480 Bytes 和 1492 Bytes 的大小 1 Byte = 8 bit --- #### 码分多址通信 多个站使用同一个信道发送序列，收到了（-1 +1 -3 +1 -1 -3 +1 +1）的序列，四个站的码片序列其中的有 （-1 -1 -1 +1 +1 -1 +1 +1），使用接收到的序列和码片序列进行正交运算如下 $$ \begin{align} & (-1 +1 -3 +1 -1 -3 +1 +1) \times (-1 -1 -1 +1 +1 -1 +1 +1) \\ & = \frac{(1 - 1 + 3 + 1 - 1 + 3 + 1 + 1)}{8} \\ & = 1 \end{align} $$ 结果若为 0，则该站点无发送；若为 1，表示该站点发的 1；若为 -1，表示发的 0 --- #### 地址聚合 地址聚合是指将一组相邻的IP地址块合并为一个更大的IP地址块的过程。超网（Supernet）是一种网络设计概念，旨在通过合并多个较小的IP地址块，创建一个更大的、更紧凑的地址块。这种合并的过程有助于简化路由表，减少路由表的大小，提高网络的效率。超网主要通过地址聚合实现。 有以下四个地址：212.56.132.0/24，212.56.133.0/24，212.56.134.0/24，212.56.135.0/24；要求进行最大可能的聚合； 做法：找不同的位，匹配最大前缀；例如以上四个地址转化成二进制位得 212.56.1000 0100.0/24， 212.56.1000 0101.0/24， 212.56.1000 0110.0/24， 212.56.1000 0111.0/24 则共同最大前缀为 8 + 8 + 6 = 22 位，所以聚合得到的 CIDR 地址为 212.56.1000 0100.0/22，即212.56.132.0/22 --- #### 路由表的更新 采用 RIP 协议交换路由信息，有如图所示表达 | G1 当前路由表信息：目的，距离，下一跳 | G2 发来路由表更新信息：目的，距离 | 最终 G1 路由表信息：目的，距离，下一跳 | | ------------------------------------- | --------------------------------- | -------------------------------------- | | 10.0.0.0；1；direct | 10.0.0.0；4 | 10.0.0.0；1；direct | | 20.0.0.0；5；G9 | 25.0.0.0；3 | 20.0.0.0；5；G9 | | 25.0.0.0；4；G2 | 30.0.0.0；4 | 25.0.0.0；4；G2 | | 30.0.0.0；6；G8 | 40.0.0.0；3 | 30.0.0.0；5；G2 | | 40.0.0.0；3；G2 | 60.0.0.0；2 | 40.0.0.0；3；G2 | | 55.0.0.0；4；G5 | 80.0.0.0；3 | 55.0.0.0；4；G5 | | 80.0.0.0；4；G5 | 90.0.0.0；4 | 80.0.0.0；4；G5 | | | | 90.0.0.0；5；G2 | 在计算前，需要将 G2 发来的路由表 +1 --- #### 编码 1. 海明码，[参考](https://www.bilibili.com/video/BV1FM4y1y7Kp)，传送 11010011，需要多少冗余位？； 1. m + k + 1 < 2^k，其中 m 为信息位的长度 8，算得 k 为 4； 2. 将 2^0，2^1，2^3 和 2^4 几个位置提出来，剩下的位置填入要发送的内容； 3. 然后根据奇偶校验的原则，提取位置上的值 2. 曼彻斯特编码（数据链路层 HDLC 使用的编码），差分曼彻斯特编码 1. 曼彻斯特编码（有两种约定，IEEE 802.3 用的是第二种约定，下以后者为准），低到高是 1，高到低是 0；即前 T/2 画相反，后 T/2 画本身 2. 差分曼彻斯特编码，和前一个图形，0 先相反再相反（有跳变），1 先复制后相反（无跳变）； 3. 3. 归零码，不归零码 --- #### 奈奎斯特定理、香农定理 [参考](https://www.bilibili.com/video/BV1KN4y1j7MD) 1. 奈奎斯特定理，求无干扰低通信道的最大传输速率（也叫数据率）；$速率 = B\log_{2}V = 2W\log_{2}V$，其中 $B = 2W$ 是码元传输速率（波特率），$W$ 是信道带宽，$V$ 是单个信号的离散状态数； 2. 香农定理，有干扰情况下信道的最大传输速率；$速率 = W\log_{2}(1+\frac{S}{N})$，其中信噪比 $\frac{S}{N}$ 可由 $dB = 10*log_{10}\frac{S}{N}$ 来求; 3. 如果同时计算奈奎斯特定理和香农定理，由于都是理论极限，两者取最小值 例题： 1. 带宽 4KHz 的无噪信道，1 个码元带 3bit 信息，问最大传输数率，若信噪比为 20db，问此时最大又是多少； 1. 奈奎斯特定理：$R_{max} = 2 * 4Khz * log_{2}3 = 8 * 1.58 = 12.64mbps$； 2. 香农定理：$20dB=10*\lg{\frac{S}{N}}$，得 $\frac{S}{N}=100$，因此 $R_{max}=4KHz*\log_{2}{(1 + \frac{S}{N})} = 26.6mbps$ 2. 波特率 1000Baud，若令其有效传输速率为 4kb/s，问单个信号码元有效离散值个数；16 --- #### CSMA/CD 1. 信道传播速度，指从源头到目标走一趟，符号为 $\tau$，信道长度除以信号传输速率；争用期指的是来回一趟，就是 $2\tau$ 2. 最短帧长 = 发送速率 * 争用期 --- #### TCP 滑动窗口机制 又称信用量机制，信贷滑窗协议 ### 简答题 1. 从网络规模的角度，网络大致可以分为几类，这几类网络各自有什么特点？ 1. 按照规模来分，可以分为： 2. 个域网：设备围绕着一个人通信，典型为蓝牙 3. 局域网：私有网络，传输范围有限，广泛用于连接个人计算机和其他终端，典型是 WIFI 4. 城域网：可以覆盖一座城市，典例为有线电视 5. 广域网：跨越很大的地理区域，国家地区大陆等，例如 vpn 6. 互联网：一组相互之间不同且不兼容的网络连接起来组成的网络，典例为 Internet 2. 分别论述电路交换和分组交换 1. 电路交换：通信双方在通信前要建立起一条独占的物理通路 2. 分组交换：采用存储转发的方式，将一个长报文分割为较短的分组，然后逐个地发送到目标终端 3. 简要介绍 tcp 通信（或者面向连接的通信）过程，假设 A 是 client，B 是 server 1. 第一次握手：A 向 B 发送连接请求报文 [SYN=1，seq=x]； 2. 第二次握手：B 向 A 发送确认报文 [SYN=1，ACK=1，seq=y，ack=x+1]，此处 B 自己选择一个序号 y，并且将 ack 置为 A 第一次握手时的发来的序列加一，ack 是期望接受的下一个传输段载荷的首字节序号； 3. 第三次握手：A 向 B 发送确认报文 [ACK=1，seq=x+1，ack=y+1]，同样的，ack 也要置成第二次握手时发来的序列加一； 4. 此时双方都进入 ESTABLISHED 状态，说明连接已经建立完成，可以发送数据了 4. 简述 OSI 参考模型下各层功能 1. 物理层：利用传输介质为数据链路层提供物理链接，实现比特流的透明传输； 2. 数据链路层：通过各种控制协议，将有差错的物理信道转变为无差错的、可靠传输的数据链路；主要行为是成帧（帧定界）、差错控制、流量控制； 3. 网络层：通过路由算法，为报文或分组选择合适的路径，主要是用于控制传输层和链路层之间的路由关系； 4. 传输层：为用户提供可靠的端到端差错和流量控制，保证报文正确传输，向高层屏蔽下层数据细节，向用户透明地传输报文； 5. 会话层：向两个实体的表示层提供建立和使用连接的方式，协调两个回话进程之间的通信； 6. 表示层：对来自应用层的数据和命令进行解释，按照一定格式传给会话层； 7. 应用层：直接向用户提供服务，完成用户的各类要求 5. 简述透明网桥的工作原理（网桥的逆向地址自学习法） 1. 每个网桥保存一个动态转发表，包含目的站点 mac 和 端口号； 2. 采用逆向自学习法：初始时，转发表为空，当一个 MAC 帧到达网桥，网桥根据其源 MAC 以及来源端口添加或刷新一条记录； 3. 转发表的每一项都设置一个超时计时器，如果超时了就会删除； 4. 某一帧到达网桥时，查询转发表：如果找到记录，则向对应端口转发；如果没有则向除了到来的端口外所有端口广播； 6. 透明网桥在处理 MAC 帧时，如何处理？ 1. 如果目的端口和源端口相同，丢弃该帧； 2. 如果目的端口与源端口不同，则转发到目的端口； 3. 如果目的端口未知，采用泛洪法，向所有除了来向外的端口转发该帧； 7. 简要说明无线局域网中隐藏站、暴露站的问题，给出解决方案；p 239 1. 隐藏站点问题；假设有终端 A、B 分别在 Server 左右两边（无线信号覆盖不到另一边），A 到 Server 在通信时，B 在另一方向并不知道 Server 目前正在被占用，就会导致数据无法被接收等问题；解决方法是 MACA 协议； 2. 暴露终端问题；A、B、C、D 一字排开，B 的信号可以覆盖 A、C，而 C 的信号可以覆盖 B、D，此时 B 在给 A 发信息，而 C 想要给 D 发信息，却因为 B 在发信息导致以为信道忙，对于 C 来说，B 就是暴露终端； 8. 简述流量控制和差错控制机制，在数据链路层和传输层上的相同点与不同点 对于数据链路层和传输层； 1. 流量控制，前者主要考虑接收方的接收能力；后者由于往返迟延变化大，主要考虑拥塞问题； 2. 差错控制，前者主要针对误码；后者主要针对分组的排序； 9. 给出数据链路层帧定界的方法并简要说明 1. 比特填充；发送方连续 5 个 1 后插入一个 0，接收方连续 5 个 1 后删除一个 0，以 FLAG 定界； 2. 字符填充：FLAG 字符、ESC 字符，发送方在数据 FLAG 和数据 ESC 前插入 ESC，接收方删除 ESC FLAG 和 ESC ESC 的第一个 ESC，以单个 FLAG 定界； 10. 简述距离矢量路由算法的基本原理 1. 确定相邻节点距离，建立初始路由表； 2. 与相邻节点交换路由表； 3. 根据收集到的路由表和相邻节点距离，优化和计算新的路由表； 4. 反复交换反复优化，动态掌握路由信息； 11. 简述 UDP 和 TCP 之间的区别 1. UDP 是一个简单面向数据报的传输层协议，不提供可靠性，只发但不保证到达目的地，没有超时重传等机制，故而传输速度很快； 2. TCP 提供面向连接、可靠的字节流服务，通信前必须建立一个 TCP 连接，之后才能传输数据，TCP 提供超时重传、丢弃重复数据、校验、流量控制等功能，保证数据能够安全送达； ## Cryptography 1. (a, b) = 1 表示最大公因数是 1，[a, b] = c 表示最小公倍数是 c；若 a=bc，则表示为 b|a，称 b 能整除 a ### 计算题 1. 求 a，b 的最大公约数；使用辗转相除法求出最大公约数 r，再使用拓展欧几里得算法求出 a = bx + r 的形式，所得即为乘法逆元 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏