页表是把所有的逻辑页面放到一起，但随着进程的增加，逻辑页面会迅速增长，有多少页面页表就会有多少项。那么不变的是物理内存。为什么不给物理内存编号记录每一块存放了哪个进程呢？

第三层 网络层协议  网络层是干什么的？ 传输层tcp把数据传给下一级网络层ip，ip将数据报分片加上自己的头部。就可以发送到目的地址。 ip分片以8字节为单位。  ◼ IP协议 ◼ Internet控制协议ICMP ◼ 内部网关路由协议OSPF ◼ 外部网关路由协议BGP  第四层 传输层    传输层：提供从源端主机的进程到目的端主机的进程的可靠的、与实际使用的网络无关的数据传输；消除网络层的不可靠性。 TCP （Transmission Control Protocol ）是什么？                                                      ...

目录 tournament tree： loser tree：   tournament tree：  删除过程中交替访问沿途节点及其兄弟； 感觉像n/2路组归并，一轮需要的时间，n轮需要n的时间；    loser tree：  删除过程中只与父节点比较； 参考资料：https://www.iteye.com/blog/kenby-1017532

指令的功能和分类 1.算术与逻辑运算指令  加、减、乘、除、变符号 等算术运算 与、或、非、异或 等逻辑运算  2.移位操作指令  算术移位（一般只右移）、逻辑移位、循环移位  3.数据传送指令  通用寄存器之间传送 通用寄存器与主存储器存储单元之间传送 主存储器不同存储单元之间传送  4.输入输出指令  通用寄存器与输入输出设备（接口）之间传送  5.转移指令 结构冲突 互斥  变动程序中指令执行次序的指令，分为无条件转移指令和条件转移指令  6.子程序调用与返回指令  调用指令与返回指令二者要配合使用，子程序的最后一条指令一定是返回指令，执行结束后返回主程序断点  7.堆栈操作指令  堆栈...

网络设备：网桥交换机路由器 物理层设备：集线器中继器 集线器的主要功能是对接收到的信号进行再生整形放大，以扩大网络的传输距离，同时把所有节点集中在以它为中心的节点上。采用CSMA/CD（即带冲突检测的载波监听多路访问技术)介质访问控制机制。集线器每个接口简单的收发比特，收到1就转发1，收到0就转发0，不进行碰撞检测。 集线器（Hub）是指将多条以太网双绞线或光纤集合连接在同一段物理介质下的设备。集线器是运作在OSI模型中的物理层。它可以视作多端口的中继器，若它侦测到碰撞，它会提交阻塞信号。 [1]  集线器通常会附上BNC and/or AUI转接头来连接传统10BASE2或10BASE5网络...

相容：每一顶点都不会通过边，指向其在此序列中的前驱顶点。 topological sorting（拓扑排序）：这样的一个线性序列。 有向无环图一定存在拓扑排序。拓扑排序存在的一定是有向无环图。 dfs应用：是否是dag。 空间复杂度&时间复杂度：O(n+e)。 出，入栈 n次 入队，n 递减邻接顶点的入度，e 删除0入度顶点，n

     

高速缓冲存储器Cache

32静态存储器及高速缓冲存储器： Cache命中率和哪些因素有关？如何提高Cache的命中率？ Cache写有许多策略，试进行比较。

通用寄存器 2020   addu $1,$2,$3 $1=$2+$3 无符号数加法       addu   $1,$2,$3  $1=$2+$3  无符号数加法                          2019    

       create 插入 删除 查找      B-树            红黑树           AVL树     О（ log n ）     tournament О（ n ） О（ log n ） О（ log n ）     loser            CBP完全二叉堆   О（ log n ）平均О（ 1 ） О（ log n ）     SKIPLIST       О（ log n ）      BFS:O(n(n+e)) 

  Null Path Length（NPL）   左倾性: npl( lc(x) ) >= npl ( rc(x) )  左子堆的规模是否总是大于右子堆，左子堆的高度是否总是大于右子堆？ 

CBT（完全二叉树）：要么不要子节点，要么左右节点都要！ FBT（满二叉树）：强迫症患者，左右孩子都得有！ BST（二叉搜索树）：强迫症晚期，中序遍历从小到大排序 BBST（平衡二叉搜索树）：  AVL：强迫症早期，任意节点的左右子树高度差小于2； B-TREE RB-TREE     一个普通的树变成完全二叉树；