78 = 12+15+5+32+14，上80還是很困難.
1.二分查找
設內(nèi)
部結(jié)點的總數(shù)為n=2^h-1，則判定樹是深度為h=log(n+1)的滿二叉樹(深度h不計外部結(jié)點)。樹中第k層上的結(jié)點個數(shù)為2k-1，查找它們所需的比較次數(shù)是k。因此在等概率假設下，二分查找成功時的平均查找長度為：ASLbn ≈ log(n+1)-1
二分查找在查找失敗時所需比較的關(guān)鍵字個數(shù)不超過判定樹的深度，在最壞情況下查找成功的比較次數(shù)也不超過判定樹的深度。
2.問題求解第二題
21本書中選4本，任意兩本編號不相鄰.
去掉3個間隔，C(18,4)=3060.
排列組合題總是簡單的出乎意料. = =
3.快速排序算法不熟
今天突然發(fā)現(xiàn)很多O(nlogn)級別的算法都和樹有很深的關(guān)系，遍歷的過程通常都是生成某種樹，然后查找長度和比較次數(shù)通常和樹的深度相關(guān).