408需要背诵的知识点
数据结构
数据结构常用公式
(一)栈：
1.出栈顺序，卡特兰数：
1
n
+
1
C
2
n
n
\frac{1}{n+1}{\rm C}_{2n}^{n}
n+11C2nn
C(1)=1，C(2)=2，C(3)=5，C(4)=14，C(5)=42
(二)树：
1.树的总结点数=1+度：
度为m的树(
n
m
n_m
nm为度为m的结点个数)：
n
0
+
n
1
+
n
2
+
n
3
+
n
4
+
.
.
.
+
n
m
=
1
+
1
n
1
+
2
n
2
+
3
n
3
+
4
n
4
+
.
.
.
m
n
m
n₀+n₁+n₂+n₃+n₄+...+n_m=1+1n₁+2n₂+3n₃+4n₄+...mn_m
n0+n1+n2+n3+n4+...+nm=1+1n1+2n2+3n3+4n4+...mnm
2.n个结点的AVL树最大深度 / 高度为h的AVL树最少结点数：
n
h
=
n
h
−
1
+
n
h
−
2
+
1
n_h=n_{h-1}+n_{h-2}+1
nh=nh−1+nh−2+1
n
1
=
1
,
n
2
=
2
，
n
3
=
4
，
n
4
=
7
n_1=1,n_2=2，n_3=4，n_4=7
n1=1,n2=2，n3=4，n4=7，
n
5
=
12
，
n
6
=
20
n_5=12，n_6=20
n5=12，n6=20
(三)图：
1.连通图最少有n-1条边。则最小生成树恰好有n-1条边。
2.n个结点的无向非连通图 最多有
C
n
−
1
2
=
(
n
−
1
)
(
n
−
2
)
2
{\rm C}_{n-1}^2=\dfrac{(n-1)(n-2)}{2}
Cn−12=2(n−1)(n−2) 条边。若是任何情况下都是连通的，则至少需要
C
n
−
1
2
+
1
{\rm C}_{n-1}^2+1
Cn−12+1条边
(四)排序：
1.归并排序，需要增加的虚归并段：
k
−
u
−
1
=
k
−
(
n
0
−
1
)
%
(
k
−
1
)
−
1
k-u-1=k-(n_0-1)\%(k-1)-1
k−u−1=k−(n0−1)%(k−1)−1
单链表
1.单链表结点的数据结构定义
typedef struct Node{
int data; //数据域
struct Node *next; //指针域
}LNode,*LinkList;
2.单链表结点的插入：
3.单链表结点的删除：
q = p->next; //令p指向被删除结点
p->next = q->next; //将*q结点从链中断开
free(q); //释放结点的存储空间
数组
1.C++语法：申请一个长度为n的辅助数组A，并初始化为空
int * A = new int[n]; //申请辅助计数数组
for(int i=0;i<n;i++) A[i]=0; //计数数组清零
二叉树
1.二叉树结点的数据结构定义
C写法二叉树
typedef struct BiTNode{
char data; //数据域
struct BiTNode *lchild,*rchild; //左、右孩子指针
}BiTNode,*BiTree;
C++写法二叉树(C++更简单)
struct TreeNode{
int data; //数据域
TreeNode * leftChild; //左子树
TreeNode * rightChild; //右子树
};
2.二叉树的遍历： 递归(栈) / 非递归的while循环(队列)
(1)先序遍历
void PreOrder(BiTree T){
if(T != NULL){
visit(T); //1.根:访问根结点
PreOrder(T->lchild); //2.左:递归遍历左子树
PreOrder(T->rchild); //3.右:递归遍历右子树
}
}
(2)中序遍历
void InOrder(BiTree T){
if(T != NULL){
InOrder(T->lchild); //1.左:递归遍历左子树
visit(T); //2.根:访问根结点
InOrder(T->rchild); //3.右:递归遍历右子树
}
}
(3)后序遍历
void PostOrder(BiTree T){
if(T != NULL){
PostOrder(T->lchild); //1.左:递归遍历左子树
PostOrder(T->rchild); //2.右:递归遍历右子树
visit(T); //3.根:访问根结点
}
}
(4)层序遍历
void LevelOrder(BiTree T){
InitQueue(Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //根结点入队
while(! IsEmpty(Q)){ //队列不空则循环
DeQueue(Q,p); //队头结点出队
visit(p); //访问出队结点
if(p->lchild != NULL)
EnQueue(Q,p->lchild); //左子树非空，则左子树根结点入队
if(p->rchild != NULL)
EnQueue(Q,p->rchild); //右子树非空，则右子树根结点入队
}
}
B树
| m阶B树结点 | 子树 | 关键字 |
|---|---|---|
| 最多 | m m m | m − 1 m-1 m−1 |
| 最少 | ⌈ m 2 ⌉ ⌈\dfrac{m}{2}⌉ ⌈2m⌉ | ⌈ m 2 ⌉ − 1 ⌈\dfrac{m}{2}⌉-1 ⌈2m⌉−1 |
B树根结点：最少有2棵子树，1个关键字
计算机组成原理
数据的表示与运算
1.8位补码所能表示的取值范围：
−
2
7
∼
2
7
−
1
-2^7\sim 2^7-1
−27∼27−1，即-128~127
2.算术移位与逻辑移位：
算术移位：操作对象是 有符号数
| 码制 | 添补代码 |
|---|---|
| 正数的原码、补码 | 0 |
| 负数原码 | 符号位仍为1，其余添0 |
| 负数补码 | 符号位仍为1，左移添0，右移添1 |
逻辑移位：操作对象是 无符号数，逻辑左右移均添0
3.符号扩展：
| 类型 | 符号扩展的方法 |
|---|---|
| 1.正数的符号扩展 | 高位全补0 |
| 2.负数原码的符号扩展 | 最高位为符号位1，其他扩展位补0 |
| 3.负数补码的符号扩展 | 最高位为符号位1，其他位补1 (整数补1，小数补0) |
无论移位还是符号扩展：正数全补0，负数原码保持符号位是1不动，其他补0。负数补码，高位补1，低位补0
指令
1.计算机指令系统最多的指令条数 = 最多有多少种不同的操作码 =
2
指令操作码
O
P
的位数
2^{指令操作码{\rm OP}的位数}
2指令操作码OP的位数
2.一行微指令序列代表一个时钟周期
3.①存储字长：存储单元的位数，看编址方式
②机器字长：CPU一次能处理的位数 = 内部数据通路位数 = 寄存器位数
③指令字长：一条指令的长度
4.PC = (PC) + 指令长度 + 偏移量
5.基址寻址与变址寻址
| 基址寻址 | ①多道程序设计 ②基址寄存器BR内容不可变 (由操作系统决定) |
| 变址寻址 | ①编制循环程序、数组 ②变址寄存器IX内容可变 (由用户决定) |
CPU
1.寄存器：
MAR位数：2MAR位数 =
主存空间大小
编址方式
\dfrac{主存空间大小}{编址方式}
编址方式主存空间大小 = 存储单元的个数
MDR位数：机器字长
寄存器
| 程序员可见寄存器 | 程序员不可见寄存器 |
|---|---|
| ①程序计数器：PC | ① 存储器地址寄存器：MAR 存储器数据寄存器：MDR |
| ②程序状态字寄存器：PSW | ②指令寄存器：IR 微指令寄存器：μIR |
| ③通用寄存器GPRS：R0、R1、R2、R3 | ③运算部件：移位寄存器SR、乘法器、先行进位链 |
| ④暂存器、锁存器DR |
数据通路
1.控制信号由控制部件CU产生
2.取指周期的控制信号序列
PCout,MARin //PC→MAR
Read //M(MAR)→MDR
MDRout，IRin //MDR→IR
五大技术
| 技术 | 作用 |
|---|---|
| Cache技术 | 解决CPU与主存速度不匹配 |
| 缓冲技术 | 解决CPU与外设速度不匹配 |
| 虚拟存储技术 | 解决内存容量不足 |
| 通道技术 | 减少外设对CPU的I/O操作控制请求，提高了CPU效率 |
| 并行技术 | 提高整机的运行效率和吞吐率 |
操作系统
文件系统
1.磁盘索引块是由地址项组成的，可以不存满。
2.索引块(磁盘块)大小 / 地址项大小 = 每个索引块最多拥有多少个地址项
3.索引库的每一个地址项，指向一个磁盘块
计算机网络
各层协议一览
链路层：PPP、HDLC、CSMA
网络层：IP、ARP、ICMP、OSPF
传输层：TCP、UDP
应用层：DNS、FTP、SNMP、POP3、MIME、HTTP、DHCP、RIP、BGP
特殊IP地址
1.直接广播地址：目的网络号 + 主机号全1
2.本地广播地址(受限广播地址)：255.255.255.255
TCP拥塞控制
(1)慢开始、拥塞避免
①慢开始(从1开始double，乘法增大)
②拥塞避免(从门限值ssh开始cwnd++，加法增大)
发生拥塞条件：超时
发生拥塞时的处理：
s
s
h
新
=
c
w
n
d
拥塞时
2
，
c
w
n
d
新
=
1
\rm ssh_新= \dfrac{cwnd_{拥塞时}}{2}，cwnd_新 =1
ssh新=2cwnd拥塞时，cwnd新=1（慢开始）
(2)快重传、快恢复
③快重传：收到3个上一条的ACK帧(3个冗余ACK)，立刻重传该数据帧，不等超时
④快恢复：优化拥塞时的处理，
s
s
h
新
=
c
w
n
d
拥塞时
2
=
c
w
n
d
新
\rm ssh_新= \dfrac{cwnd_{拥塞时}}{2}=cwnd_新
ssh新=2cwnd拥塞时=cwnd新（快恢复，直接进入拥塞避免的加法增大阶段，跳过从1开始慢开始的阶段）
发生拥塞的条件：收到3个冗余ACK
发生拥塞的处理：
s
s
h
新
=
c
w
n
d
拥塞时
2
=
c
w
n
d
新
\rm ssh_新= \dfrac{cwnd_{拥塞时}}{2}=cwnd_新
ssh新=2cwnd拥塞时=cwnd新
(3)门限值ssthesh的变化
刚开始，拥塞前：
s
s
h
旧
=
\rm ssh_旧=
ssh旧= 慢开始和拥塞避免的分界线
拥塞后：
s
s
h
新
=
c
w
n
d
拥塞时
2
\rm ssh_新= \dfrac{cwnd_{拥塞时}}{2}
ssh新=2cwnd拥塞时
(4)总结：
在TCP连接建立和网络出现超时时，采用慢开始和拥塞避免算法。
在发送方收到冗余ACK时，采用快重传和快恢复算法。
帧、报文
1.DHCP报文都是广播报文，目的IP：255.255.255.255，目的MAC：ff-ff-ff-ff-ff-ff，源IP：0.0.0.0
2.广播MAC帧：ff-ff-ff-ff-ff-ff
3.TTL（最大生存时间，Time to live）
数据报每经过一个路由器，TTL减1。是经过的路由器的个数，而不是路径费用。
4.路由表项的下一跳：下一跳的是路由器接口名称 或者 路由器接口IP地址 或是 下一跳网络地址，而不是路由器本身的名字！
5.因特网Internet
若因特网Internet没有给出具体的IP地址，则可以将其视为默认路由 0.0.0.0/0
相关文章
- 【知识点】Umsin修仙
- 第二十七节：Java基础面向对象-静态，单例模式，继承详情知识点
- Android Service用法知识点的讲解
- xml_MathML的基本知识点__这东西要自己实践最好
- 今天加班做了昨天晚上要写的页面，用到了一些之前用过但还不熟悉需要上网搜索才能用的知识点：
- SSH三大框架面试知识点
- Vue知识点总结(15)——匿名插槽（超级详细）
- Vue知识点总结(8)——filter过滤器（超级详细）
- 计网 | 【三 数据链路层】知识点及例题
- 计网 | 一文解析TCP协议所有知识点
- 计算机网络知识点
- Python 基础 之 多任务 yield/greenlet/gevent 协程知识点的简单整理，以及对应的使用（迭代器、协程、进程线程和协程的区别等）
- Unity 使用教程 之 Unity3D常用的知识点归纳
- C# 知识点汇总整理 -- 附思维导图
- Zabbix知识点
- 读metronic文档学到的几个知识点
- 移动端前端开发的知识点总结