[2010],74.5(+5+7-5), 市排10-
[2007],49(+24+3+4), 過線8分
[2006],75.5(+8), 市排0, 省排29
[2009], 76.5, 市排10-
[2008], 79(+17), 市排10-, 省排70+
有兩套題是按照初賽模式模擬的, 連續思考還是有一些影響, 不妨在考場上先休息一下.
1. 小數進制轉換
(1) n進制 -> 10進制
(A1.2)16 = 10*16^1 + a^16^0 + 2*16^-1
[長除法格式]例如，1020304從10進制轉到7進制：
1020304 / 7 = 145757 r 5 ↑ => 11446435
145757 / 7 = 20822 r 3 │
20822 / 7 = 2974 r 4 │
2974 / 7 = 424 r 6 │
424 / 7 = 60 r 4 │
60 / 7 = 8 r 4 │
8 / 7 = 1 r 1 │
1 / 7 = 0 r 1 │
http://zh.wikipedia.org/wiki/%E8%AE%B0%E6%95%B0%E7%B3%BB%E7%BB%9F#.E8.BF.9B.E5.88.B6.E8.BD.AC.E6.8D.A2
(2) 10進制 -> n進制
除n取余, 乘n取整
http://www.cnblogs.com/keycode/archive/2010/10/26/1861265.html
2. 邏輯表達式
(1)考慮四種情況代值
(2)利用邏輯代數公式化簡
http://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E4%BB%A3%E6%95%B0
http://202.201.48.18/jpkc/2006/szdzjs/shoukejiaoan/0001.htm
3.數據結構
(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)二叉樹中根遍歷
根據先根遍歷和后根遍歷畫出樹, 找到樹中的不變部分, 分析不確定部分的情況(任意與否).
4.計算機史
[計算機領域先驅者]
http://zh.wikipedia.org/wiki/Category:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%A2%86%E5%9F%9F%E5%85%88%E9%A9%B1%E8%80%85
5.常識
[面向對象程序設計]http://zh.wikipedia.org/wiki/%E9%9D%A2%E5%90%91%E5%AF%B9%E8%B1%A1%E7%9A%84%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1
[ALU]http://zh.wikipedia.org/wiki/ALU
[Hash]http://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E8%A1%A8
[IPv6]http://zh.wikipedia.org/wiki/Ipv6
[RAM]http://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E5%AD%98%E5%8F%96%E5%AD%98%E5%82%A8%E5%99%A8
[CPU]http://zh.wikipedia.org/wiki/CPU
[寄存器]http://zh.wikipedia.org/wiki/%E5%AF%84%E5%AD%98%E5%99%A8
[馮諾依曼結構]http://zh.wikipedia.org/wiki/%E8%8C%83%E7%B4%90%E6%9B%BC%E6%9E%B6%E6%A7%8B
[標記語言]http://zh.wikipedia.org/wiki/%E7%BD%AE%E6%A0%87%E8%AF%AD%E8%A8%80
[自然語言]http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E8%AF%AD%E8%A8%80
6.運算符優先級
http://hi.baidu.com/xyh2007/blog/item/b2cd4b60c5dfa145eaf8f8b3.html
[記憶]去掉一個最高的，去掉一個最低的，剩下的是一、二、三、賦值。雙目運算符中，順序為算術、關系(> >= < <=高于== !=)和邏輯(&& ||)，移位和邏輯位(&^|)插入其中。
7.遞推關系
(1)第二類stirling數 s(n,k) = s(n-1, k-1) + k*s(n-1, k)
[直觀解釋]前面一種就是新開一組, 后面一種是前面分了k組, 我隨便找一組丟進去.
（提示：先固定一個數，對于其余的5個數考慮S(5,3)與 S(5,2)，再分這兩種情況對原固定的數進行分析）-> 討論一個數
8.補碼表示法
[內容]http://www.cnblogs.com/tenghoo/archive/2008/06/01/1211663.html
[動機]http://blog.163.com/fan_yishan/blog/static/476922132008697421719/
a-b = a+(b % 2^n), 即對2^n取模.
N * = 2^n - N = [2^4](base10) - 0101 = 10000(base2) - 0101 = 1011
[補碼/二補數]http://zh.wikipedia.org/wiki/%E4%BA%8C%E8%A3%9C%E6%95%B8
9.排序算法
[穩定]插入排序、冒泡排序、歸并排序、分配排序(桶式、基數)
[不穩定的]直接選擇排序、堆排序、shell排序、快速排序都是不穩定的排序算法。
[穩定排序]http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/chapter7/01/05.html
[排序原理]http://hi.baidu.com/cuifenghui/blog/item/0587932b039557f9e7cd4051.html
[5個數7次比較]
1. [構造排序樹]http://topic.csdn.net/t/20031207/21/2537867.html
2. 歸并排序(拆分為2 - 3)
3. 從排列角度考慮, log2(n!)上取整
http://zhidao.baidu.com/question/71416468.html
10.圖論
(1)二分圖判定
[定理]無向圖G為二分圖的充要條件是, G至少有兩個頂點, 且其所有回路的長度均為偶數.
(2)哈密頓圖
[定義]由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次.
http://zh.wikipedia.org/wiki/%E5%93%88%E5%AF%86%E5%B0%94%E9%A1%BF%E5%9B%BE
11.閱讀程序注意事項
(1)對程序段進行等價變換
(2)看清if的條件(比較符號看翻, 忽略括號)
(3)兩位數以上乘法豎式計算兩遍(即改變順序) -> 特別注意!!!!!!!!!
(4)注意函數名縮寫(hpsrt)和特征語句(j = k + k) -> 07的堆排(不斷更新大根堆)沒看出來
(5)對于很惡心的模擬題: 列表法(三維可以在水平方向在加列, 不妨用其他顏色的筆, 或者鉛筆指出指針)
12.完善程序注意事項
(1)注意區別遞歸函數參數的0和1,以及遞歸是參數是否需要改變(如果在函數中改變了, 很可能不用)
(2)注意邊界條件(通過交換確定, 還是通過枚舉確定)
(3)遇到比較熟悉, 但是忘得差不多的算法, 一開始不要糾纏, 最后再斟酌
(4)注意函數類型, 比如void main(), 不要寫return 0;
(5)對于for循環, 弄清楚循環變量i或j代表什么(結合題目分析)
13.負數取模
[定義]x % y = x - y*(x/y);
需要注意, 下取整的定義和數學取整的定義不同.
[這里是分析]http://chinakite.iteye.com/blog/25142
14.指針(參照<C++ Primer Plus>)
(1)定義
int a, *b; //這里表示的都是值, &a 和 b 都是地址
int *a = &k; //這么解釋 int * a = &k; 即先對地址a賦值
(2)分析
因而兩種swap可以解釋(只有交換值才有效):
void swap(int &x, int &y){int k = x; x = y; y = k;} //傳入地址, 交換值
void swap(int *x, int *y){int k = *x; *x = *y; *y = k;} //傳入值, 交換值
void swap(int *x, int *y){int *k = *x; *x = *y; *y = *k;} //傳入值, 交換值, 但k是隨機地址, 可能寫到不能寫的位置上
void swap(int *x, int *y){int *k = x; x = y; y = k;} //傳入值, 交換地址
(3)注意事項
int * fellow; //這里的fellow是隨機地址, 必須使用int *fellow = new int;來初始化
*fellow = 123456;
(4)應用: 動態數組(略)