保研面试408复习 8——计算机网络（浏览器http）、离散数学（平面图）、操作系统、数据结构

一、计算机网络

1、从在浏览器输入网址到页面显示的过程

从在浏览器输入网址到页面显示的过程涉及了多个步骤和不同的计算机网络协议。以下是这一过程的详细步骤：
浏览器检查DNS服务器进行DNS到IP地址的转换→建立TCP连接→浏览器发送HTTP请求→服务器进行HTTP响应→浏览器解析服务器给的HTML→继续HTTP请求，直到获得全部数据→断开TCP连接

1. 输入网址

用户在浏览器的地址栏输入一个URL（统一资源定位符），如 http://www.example.com。

2. DNS 解析

• 域名系统（DNS）查询：浏览器检查本地缓存中是否有此URL的IP地址。如果没有，浏览器会向配置的DNS服务器发送一个DNS查询请求，以解析域名到对应的IP地址。
• 接收IP地址：DNS服务器查找域名对应的IP地址，然后返回给浏览器。

3. 建立TCP连接

• 三次握手：浏览器根据得到的IP地址，通过TCP（传输控制协议）进行三次握手过程，建立一个到服务器的稳定连接。

4. 发送HTTP请求

• 构建HTTP请求：浏览器构建一个HTTP请求，包括请求行（如 GET / HTTP/1.1）、请求头（如主机、用户代理等信息），以及可能的请求体。
• 发送请求到服务器：通过已建立的TCP连接，将HTTP请求发送到服务器。

5. 服务器处理请求并响应

• 服务器接收请求：服务器接收到HTTP请求后，根据请求的类型（如GET、POST）、资源路径（如根目录/），处理请求。
• 服务器发送HTTP响应：服务器处理完请求后，生成一个HTTP响应发送回客户端。响应包括状态码（如200 OK）、响应头（如内容类型、服务器信息等），以及响应体（请求的网页内容）。

6. 浏览器处理响应

• 接收响应数据：浏览器接收到服务器的响应数据。
• 解析HTML内容：浏览器解析HTML标记，并构造DOM（文档对象模型）树。
• 加载资源：解析过程中，浏览器遇到外部资源（如CSS文件、JavaScript文件、图片等）会发送额外的HTTP请求去加载这些资源。
• CSS渲染：浏览器解析CSS样式，并应用到对应的HTML元素上。
• JavaScript执行：浏览器执行页面中的JavaScript代码，可能会修改DOM树和页面的可视表现。

7. 页面渲染

• 视觉呈现：浏览器将解析的结果绘制到屏幕上，用户开始看到最终的网页。

二、离散数学

一、平面图

一个图如果可以被画在平面上，且它的任何两条边都不会相交（除了在顶点处），那么这个图被称为平面图。
平面图一般是指无向图。
一个图可以重排结构画成平面图，则称为可平面图。

1、平面图性质

• 欧拉公式：$V-E+F=2$
  • 对于任何连通的平面图，其顶点数 $V$，边数 $E$，和面数 $F$（包括外部区域，相当于环形复杂度）满足的关系式。
  • 我们可以用最简单的两个结点一个结点指向另一个结点。

2、Kuratowski定理

根据Kuratowski定理，一个图是可平面的当且仅当它不包含可以缩减为 $K_5$（完全五部图）或
$K_{3,3}$（完全二部图，每部分有三个顶点）的子图。

在图论中，$K_5$ 和 $K_{3,3}$ 是两种特殊的图，它们通常用来作为测试图的平面性的基准。

注意，这里的K下标的表示并不固定，我们只需要知道它是一个什么样的图就行。

（1）$K_5$：完全五部图

• 定义：$K_5$ 是一个完全图，包含5个顶点，每一对顶点之间都有一条边相连。
• 性质：
  • 顶点数 $V=5$。
  • 每个顶点都与其他四个顶点相连。
  • 边数 $E=10$。这是因为每个顶点的度数为4，总共有5个顶点，所以总度数是20。由于每条边被两个顶点共享，所以实际的边数是总度数的一半。
• 平面性：根据图论的定理，任何包含 $K_5$ 作为子图的图都不能是平面图，因为无法在平面上绘制 $K_5$ 而不让任何边相交。

（2）$K_{3,3}$：完全二部图

• 定义：$K_{3,3}$ 是一个完全二部图，包含两个顶点集，每个集合有3个顶点，集合间的每个顶点对都有一条边相连，但集合内的顶点之间没有边。
• 性质：
  • 顶点数 $V=6$。
  • 边数 $E=9$。这是因为集合A中的每个顶点都必须与集合B中的每个顶点相连，因此边数是两个集合大小的乘积，即 $3\times 3$。
  • 没有顶点是相邻的，这意味着图中没有形成三角形的边。
• 平面性：根据Kuratowski定理，任何包含 $K_{3,3}$ 作为子图的图都不能是平面图。与 $K_5$ 一样，$K_{3,3}$ 无法在平面上绘制而不让边相交。

三、操作系统

（1）进程间通信方式

• 管道
• 共享内存
  • 可能需要同步机制来避免竞争条件
• 消息队列
• 异步信号
• 套接字

（2）进程调度：先到先服务，短作业优先，最高响应比，最高优先级，多级反馈队列，时间轮转

（3）磁盘调度：先到先服务，最短寻道时间优先，扫描算法，电梯算法，循环电梯

• 最短寻道时间优先存在磁道歧视
• 电梯算法和扫描算法存在地域差别

（4）动态内存分配：首次适应，最佳适应，最坏适应

（5）页面置换算法（淘汰页表中的页）：LRU、先进先出

（6）文件锁

• 共享锁：允许多个进程读文件，但是不允许写
• 排他锁：只允许一个进程读入或写入文件

（7）每个进程都有一个页表

• 因为一个虚拟地址对应了一个虚页号，如果不同进程共享一个页表，则不同进程必须有不同虚拟地址才能区分页表项，与每个地址由一个虚拟地址空间相违背。

（8）死锁避免
银行家算法：这是一个著名的死锁避免算法，通过模拟资源分配，判断资源分配后是否会导致系统进入不安全状态。只有在不会导致不安全状态时，才允许资源分配。

安全状态一定非死锁状态；
非安全状态不一定是死锁状态

（9）冯诺依曼结构

• 特点：程序和数据存储在同一个内存空间中，使用同一套总线来传输数据和程序。

（10）指令系统

• 指令格式：操作码 - 操作数1 - 操作数2 - 地址字段
• 常见寻址方式：操作数存储方式
  • 立即数寻址：在指令中就有操作数
    • lw $t0,#5
  • 直接寻址：直接通过地址找到操作数
    • lw $t0,1000
  • 间接寻址：通过寄存器中的地址找到操作数
    • lw $to,( $r0)
  • 寄存器寻址：操作数就在寄存器中
    • lw $t0, $r0
  • 基址寻址：就像数组一样，寄存器当作首地址
    • lw $t0,100( $r0)
  • 变址寻址：俩寄存器中的值相加作为地址
    • lw $t0,( $r0+$r1)

（11）流水线技术

• 概念：为了提高CPU执行指令的效率，将指令执行过程分为多个阶段，每个阶段由不同的硬件模块并行处理不同的指令。
• 五级流水线：取指（IF）、译码（ID）、执行（EX）、存储（MEM）、写回（WB）
• 阻塞问题：
  • 数据相关：后续指令需要前一指令的计算结果
    • 解决办法：旁路技术
  • 控制相关：条件跳转指令导致的流水线停顿，比如执行之后产生跳转可能需要重新取指令。
    • 解决办法：动态分支预测，假定分支不发生，缩短分支时间，延迟槽
  • 结构相关：多个指令同时访问同一个存储器，比如取指和写回都是访问同一个存储器，我们使用前半个周期写回，后半个周期取指来解决。
    • 解决办法：增加硬件资源

（12）I/O控制方式

• 程序查询方式：CPU定期检查输入输出设备的状态，发现设备准备好后执行相应的 I/O操作
  • 缺点：效率低，CPU大量时间用于查询设备状态
• 中断方式：I/O设备准备好后向CPU发送中断请求，CPU暂停当前任务，处理中断请求，完成I/O操作后恢复原任务。
• DMA方式：CPU只需要传输初始化参数，剩余工作由DMA控制器完成。DMA直接管理数据在内存和I/O设备间的传输。

四、数据结构

（1）动态数组
动态数组是一种可以在运行时自动调整大小的数组，通过复制现有元素到新分配的更大或更小的内存块来实现动态调整。比如vector

（2）传统二叉搜索树——关键词互异
左子树的所有结点的值都小于该结点的值，右子树的所有结点的值都大于该结点的值。传统BST关键词是互异的

• 在插入琪琪的小妹妹的时候，如果原来已经有了，那就直接return了，不会插入相同的。
  
  AVL，红黑树，B树这些搜索树的关键词通常情况下都是互异的。

（3）红黑树——一种自平衡二叉搜索树

• 每个节点都是红色或黑色
• 根结点是黑色，叶节点是黑色
• 从根结点到所有叶节点的路径上，黑色节点的数量相同
• 不能有两个连续的红色节点
• 实现：重新着色和旋转来保持平衡

（4）哈希冲突解决方法

• 拉链法
• 开放定址法
  • 线性探查法
    • $d=h(key)+i$，d表示放的位置，i是线性探查的值，从0开始
  • 平方探测法
    • $d=h(key)+i^2$
  • 伪随机序列法
    • $d=h(key)+rand()$，其中$rand()$表示随机序列按顺序取。
• 再散列法（多重散列）
  • 比如双重散列，$d=(h1(key)+i\ast h2(key))\%m$，i是冲突次数。

（5）B树和B+树

• B树：所有叶子结点都在同一层，每个结点可以有多个子节点和多个键值。
• B+树：内部节点只存储键值，所有数据都存储在叶子节点中，叶子结点还存储指向下一个叶子节点的指针形成一个有序链表。
• 通过特点可以发现，B+树内部节点的“键值”也一点会出现在叶子节点中，B树的“键值”各结点各不相同。
  
  
  

（6）排序算法的稳定性

• 稳定性指的是排序前后对于任意两个相等的元素而言它们的相对位置不变。
• 稳定排序：归并排序、插入排序、冒泡排序
  • 这些都是可以实现成稳定的排序算法。
• 不稳定排序：快速排序和堆排序