P5

211275022田昊东

6.6

1. 
2. 
3. 

6.9: (1)

• 0	1	2	3	4	5	6	7	8	9	10	11	12
  78		15	03		57	45	20	31		23	36	12

• 成功的平均搜索长度：\(\frac1{10}(1+1+1+1+1+1+1+4+1+2)=1.400\)

• 不成功的平均搜索长度：\(\frac1{13}(2+1+3+2+1+5+4+3+2+1+5+4+3)=2.769\)

6.10

• \[ 设表的大小至少为x\\ \alpha=150/x\\ (1+1/(1-150/x))/2<=2\\ x>=225 \]

• 即至少为 \(225\)

6.12

• 平均读盘1.5次就是说查询一次平均检查记录的数目为\((30/2+30+(60-30)/2)/2=30\)
• 至少设置桶的数目 \(15000/30=500\)

7.2

• 
• 成功：\((1+2+\dots+14)/14=7.5\)
• 失败：\((1+2+\dots+14+14)/15=7.933\)

7.3

• 
• 成功：\((1+2*2+4*3+7*4)/14=3.214\)
• 失败：\((3+14*4)/15=3.933\)

7.8

• 初始的二叉搜索树：
• 
• 删除for之后的二叉搜索树：
• 
• 重新插入for的二叉搜索树（不相同）：
• 

7.15

• 
• 
• 
• 最终结果

7.16

• 删除MAY：叶子节点可以直接删除
• 
• 删除FEB：用中序遍历前继替代
•