記得去年在紙上寫過一份這樣的東西，迎來的是exhaustive fail.需要明確復(fù)習(xí)重點是數(shù)據(jù)結(jié)構(gòu)和算法, 考場上要注意出題規(guī)律和草稿的清晰性. 簡單復(fù)習(xí)大概用了6個番茄鐘.
1.表達式樹
[中綴] (a + b) * c + d * c
(((a + b) * c) + (d * c))
[前綴] +(*(+(a b) c) * (d c))
+ * + a b c * d c
[計算方法1] 壓棧(前綴 -> 從后向前)
[計算方法2] 括號(opt后) -> 中綴
2.二分查找的平均次數(shù) log(n+1)-1
3.heap的實現(xiàn)
[up] while(k > 1) 比較 交換(h[k], h[k/2])
[down] while(2 * k <= n) 比較 交換(h[k], h[2k + 1(小于n的話)])
4.排序算法的穩(wěn)定性
[穩(wěn)定]插入排序、冒泡排序、歸并排序、分配排序(桶式、基數(shù))
[不穩(wěn)定的]直接選擇排序、堆排序、shell排序、快速排序都是不穩(wěn)定的排序算法。
[穩(wěn)定排序]http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/chapter7/01/05.html
[排序原理]http://hi.baidu.com/cuifenghui/blog/item/0587932b039557f9e7cd4051.html
5.出棧序列
一個數(shù)列滿足條件，當(dāng)且僅當(dāng)每一段單調(diào)遞減數(shù)列要么不存在空缺（即為公差-1的等差數(shù)列），要么它的空缺在之前全部已經(jīng)出現(xiàn)。
[充要條件]若出棧序列合法，則一定不存在1<=i<j<k<=n，使s[j]<s[k]<s[i]
6.鄰接表的插入操作(鏈表的插入)
next[e] = first[u[e]]; first[u[e]] = e;
7.邏輯表達式恒值
注意符號, 轉(zhuǎn)化為分情況表示的函數(shù)
8.叉積的計算(特別注意第二個負號)
|i j k|
|a1 a2 a3|=i|a2 a3|-j|a1 a3|+k|a1 a2|
|b1 b2 b3| |b2 b3| |b1 b3| |b1 b2|
9.閱讀程序注意意圖, 草稿的清晰度(減少亂劃)
[RAM]http://baike.baidu.com/view/3558.htm
隨機存儲: 訪問時間與位置無關(guān)
[Hash]http://www.nocow.cn/index.php/%E6%95%A3%E5%88%97%E8%A1%A8
[拓撲排序(DAG)]http://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F\