各种面试题

标签（空格分隔）： 数据结构 二叉树

---

根据守恒定律，智商和情商的总和是守恒的。你的高情商高智商和我的低情商低智商维持了世界和平。

##二叉树

一颗只有左右子节点的数。n层二叉树节点最大个数：2^n-1

###完全二叉树
n层二叉树，n-1层节点全满，第n层节点满足从左往右依次排列。

###平衡二叉树
左右2棵子数高度差小于等于一。

###前序遍历，中序遍历，后序遍历
前序遍历：父节点–>左节点–>右节点
中序遍历：左节点–>父节点–>右节点
后序遍历：左节点–>右节点–>父节点

例：

前序遍历：ABCDEGF
中序遍历：CBEGDFA
后序遍历：CGEFDBA

笔试过程中经常遇到知道2个遍历求第三个遍历
解题思路上，抓住父节点所在的位置，能够画出二叉树，求出第三种遍历。

平衡二叉树面试题
n个节点二叉树，理想二叉树的操作时间是O(logn)，但是极限状态下二叉树变成一条直线时时间变成O(n)，平衡二叉树能够稳定时间在o(logn)

插入新节点，调整二叉树：
(1)LL型。插入位置为左子树的左结点，进行向右旋转

(2)RR型。插入位置为右子树的右孩子，进行向左旋转

(3)LR型。插入位置为左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树，第二次再调整最小不平衡子树。

(4)RL型。插入位置为右子树的左孩子，进行两次调整，先右旋转再左旋转。

哎嘿嘿，发现md语法不支持解析带中文名的img url！！！

哈夫曼树与哈夫曼编码
哈夫曼树：带权路径最短树。
对于给定权值w=（w1，w2…wn）的n个节点哈夫曼树。
从n个节点中选取最小的2个节点wa，wb.计算wa+wb得到新的节点，将wa,wb从w集合中删除，wab插入集合w中
重复进行上述步骤。
假设w = {5,4,3,2,1}构造哈夫曼树
1:

2:

3:

4:

那么，D的霍夫曼编码：011

#DOS攻击。
denial of service.
攻击者向服务器发送大量http请求，阻塞其他用户正常http请求。
好理解：我派一帮流氓堵住了饭店门口，正常客人就进不来吃饭了。
DDOS攻击
由于攻击者势单力薄，单个攻击服务器很难对拥有较大带宽的服务器发送足够多的http攻击，于是采用分布式方式，来，先搞100000台服务器。

cookie vs localStorage vs sessionStorage

特点	cookie	localStorage	sessionStorage
生命周期	由服务器设置时间，默认在浏览器关闭后失效	永久存储	当前页面关闭页面失效
大小	4K	5M	5M
与服务器通信	每次http请求都携带cookie	无通信，仅存储于客户端	无通信，仅存储于客户端

综上，通常生命周期时间：sessionStorage < cookie < localStorage
因为cookie每次都要携带在http中，所以4K也挺大了。性能优化上可以控制cookie大小。
吐槽一句，md画表格还真是奇葩啊

#javascript模块化开发
js发展状态，代码多了，需要模块化
CommadJS vs AMD
Asynchronous Module Definition 浏览器段开发规范
CommadJS服务端开发规范