每个主机都有一个 ARP 高速缓存,里面有本局域网上的各主机和路由器的 IP 地址到硬件地址的映射表。
14、私有地址
A类:10.0.0.0 - 10.255.255.255
B类:172.16.0.0 - 172.31.255.255
C类:192.168.0.0 - 192.168.255.255
数据结构
1、 快速排序算法,归并排序算法的复杂度
平均
最好
最坏
辅助存储
稳定性
快速排序
n
l
o
g
2
n
nlog2n
nlog2n
n
l
o
g
2
n
nlog2n
nlog2n
n
2
n^2
n2
1
1
1
不稳定
归并排序
n
l
o
g
2
n
nlog2n
nlog2n
n
l
o
g
2
n
nlog2n
nlog2n
n
l
o
g
2
n
nlog2n
nlog2n
n
n
n
稳定
2、为什么要稳定排序?
稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。
比如成绩一样的按上次成绩靠前的排在前面
3、 堆实现及应用
4、Dijkstra
5、最小生成树等
6、邻接表和邻接矩阵(如何存储大数据)
7、哪些图算法用到了动态规划思想
D
P
≈
s
u
b
p
r
o
b
l
e
m
s
+
"
r
e
u
s
e
"
DP\approx subproblems + "reuse"
DP≈subproblems+"reuse"
Floyd算法是DP思想
d
i
s
t
[
i
]
[
j
]
=
m
i
n
(
d
i
s
t
[
i
]
[
j
]
,
d
i
s
t
[
i
]
[
k
]
+
d
i
s
t
[
k
]
[
j
]
)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
8、判断链表是否有环
快慢指针法, 快指针一次走两步, 慢指针一次走一步。如果环的入口在
X
X
X处,当前慢指针走到入口处,那么快指针一定在环当中。假设他们的距离为
K
K
K那么再走
K
K
K步,慢指针就追上快指针了。
判断环的位置在哪里
首先,假设链表有环,然后还是使用快指针和慢指针,快指针一次走两步,慢指针一次走一步。假设他们在
C
C
C点相遇,
C
C
C 点距离
b
b
b 的距离为
y
y
y 。这时候让慢指针退
y
y
y 步,那么由于快指针是慢指针速度的两倍,那么快指针会退到
C
′
C^{'}
C′ 这个位置。起点
a
a
a 和
b
b
b 之间的距离为
x
x
x。
也就是说,从起点走
x
x
x 步,慢指针走到了
b
b
b 点,快指针走到了
C
′
C^{'}
C′ 点,快指针走的距离为
2
x
2x
2x 的距离。不管快指针转了几圈,从入口开始转,转
x
x
x 的距离,就会转到
C
′
C^{'}
C′ 点。 那么从
C
C
C 点出发,不管转几圈,走
x
x
x 的距离就会走到入口
b
b
b 点。
所以,从快慢指针相遇点开始,一个指针从起点出发,另一个指针从
C
C
C 点出发,两个指针一起走 他们相遇的点就是入口,恰好走了
x
x
x 步。
向量组
A
:
α
1
,
α
2
,
⋅
⋅
⋅
,
α
m
A:\alpha_1,\alpha_2,···,\alpha_m
A:α1,α2,⋅⋅⋅,αm线性相关的充分必要条件是它所构成的矩阵
A
=
(
α
1
,
α
1
,
⋅
⋅
⋅
α
m
)
A=(\alpha_1,\alpha_1,···\alpha_m)
A=(α1,α1,⋅⋅⋅αm) 的秩小于向量个数
m
m
m ;向量组
A
A
A线性无关的充分必要条件是
R
(
A
)
=
m
R(A)=m
R(A)=m.
P
(
A
∣
B
)
=
P
(
B
∣
A
)
P
(
A
)
P
(
B
)
P
(
A
)
是
先
验
概
率
P
(
A
∣
B
)
是
后
验
概
率
P(A|B)=\frac{P(B|A)P(A)}{P(B)}P(A)是先验概率 P(A|B)是后验概率
P(A∣B)=P(B)P(B∣A)P(A)P(A)是先验概率P(A∣B)是后验概率
2、 大数定律和中心极限定理的意义与作用(切比雪夫大数定律)
中心极限定理
中心极限定理指的是给定一个任意分布的总体。我每次从这些总体中随机抽取 n 个抽样,一共抽 m 次。 然后把这 m 组抽样分别求出平均值。 这些平均值的分布接近正态分布。
f
(
x
)
=
1
2
π
σ
e
−
(
x
−
μ
)
2
2
σ
2
f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\\
f(x)=2πσ1e−2σ2(x−μ)2
独立同分布
如果随机变量
X
1
X_{1}
X1 和
X
2
X_{2}
X2独立,是指
X
1
X_{1}
X1的取值不影响
X
2
X_{2}
X2的取值,
X
2
X_{2}
X2的取值也不影响
X
1
X_{1}
X1的取值且随机变量
X
1
X_{1}
X1和
X
2
X_{2}
X2服从同一分布,这意味着
X
1
X_{1}
X1和
X
2
X_{2}
X2 具有相同的分布形状和相同的分布参数,对离随机变量具有相同的分布律,对连续随机变量具有相同的概率密度函数,有着相同的分布函数,相同的期望、方差。
正态分布的和
只有相互独立两个正态分布相加才是正态分布
5、泊松分布概率密度
P
(
X
=
k
)
=
λ
k
k
!
e
−
λ
P(X=k)=\frac{\lambda^k}{k!}e^{-\lambda}\\
P(X=k)=k!λke−λ
E
(
X
)
=
λ
E(X) = \lambda
E(X)=λ
D
(
X
)
=
λ
D(X)=\lambda
D(X)=λ
6、一句话概括假设检验
假设检验:
你提出假设:说你的硬币是公平的
我提出要检验你的假设:扔十次,看实验的结果是不是和你的假设相符
P值
一般认为
p
−
v
a
l
u
e
≤
0.05
p-value\le0.05
p−value≤0.05
就可以认为假设是不正确的。0.05这个标准就是显著水平,当然选择多少作为显著水平也是主观的。
比如,上面的扔硬币的例子,如果取单侧P值,那么根据我们的计算,如果扔10次出现9次正面:
p
−
v
a
l
u
e
=
P
(
9
≤
X
≤
10
)
=
0.01
≤
0.05
p-value=P(9\le X\le 10)=0.01\le 0.05
p−value=P(9≤X≤10)=0.01≤0.05
表示出来如下图所示:
我们可以认为刚开始的假设错的很“显著”,也就是“硬币是不公平的”。
如果扔10次出现出现8次正面:
p
−
v
a
l
u
e
=
P
(
8
≤
X
≤
10
)
=
0.05
≤
0.05
p-value=P(8\le X\le 10)=0.05\le 0.05
p−value=P(8≤X≤10)=0.05≤0.05