[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+
有兩套題是按照初賽模式模擬的, 連續(xù)思考還是有一些影響, 不妨在考場上先休息一下.
1. 小數(shù)進(jìn)制轉(zhuǎn)換
(1) n進(jìn)制 -> 10進(jìn)制
(A1.2)16 = 10*16^1 + a^16^0 + 2*16^-1
[長除法格式]例如，1020304從10進(jìn)制轉(zhuǎn)到7進(jìn)制：
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進(jìn)制 -> n進(jìn)制
除n取余, 乘n取整
http://www.cnblogs.com/keycode/archive/2010/10/26/1861265.html
2. 邏輯表達(dá)式
(1)考慮四種情況代值
(2)利用邏輯代數(shù)公式化簡
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.數(shù)據(jù)結(jié)構(gòu)
(1)表達(dá)式樹
[中綴] (a + b) * c + d * c
(((a + b) * c) + (d * c))
[前綴] +(*(+(a b) c) * (d c))
+ * + a b c * d c
[計(jì)算方法1] 壓棧(前綴 -> 從后向前), 即彈出順序
[計(jì)算方法2] 括號(opt后) -> 中綴
(2)二叉樹中根遍歷
根據(jù)先根遍歷和后根遍歷畫出樹, 找到樹中的不變部分, 分析不確定部分的情況(任意與否).
4.計(jì)算機(jī)史
[計(jì)算機(jī)領(lǐng)域先驅(qū)者]
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.常識
[面向?qū)ο蟪绦蛟O(shè)計(jì)]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
[馮諾依曼結(jié)構(gòu)]http://zh.wikipedia.org/wiki/%E8%8C%83%E7%B4%90%E6%9B%BC%E6%9E%B6%E6%A7%8B
[標(biāo)記語言]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.運(yùn)算符優(yōu)先級
http://hi.baidu.com/xyh2007/blog/item/b2cd4b60c5dfa145eaf8f8b3.html
[記憶]去掉一個(gè)最高的，去掉一個(gè)最低的，剩下的是一、二、三、賦值。雙目運(yùn)算符中，順序?yàn)樗阈g(shù)、關(guān)系(> >= < <=高于== !=)和邏輯(&& ||)，移位和邏輯位(&^|)插入其中。
7.遞推關(guān)系
(1)第二類stirling數(shù) s(n,k) = s(n-1, k-1) + k*s(n-1, k)
[直觀解釋]前面一種就是新開一組, 后面一種是前面分了k組, 我隨便找一組丟進(jìn)去.
（提示：先固定一個(gè)數(shù)，對于其余的5個(gè)數(shù)考慮S(5,3)與 S(5,2)，再分這兩種情況對原固定的數(shù)進(jìn)行分析）-> 討論一個(gè)數(shù)
8.補(bǔ)碼表示法
[內(nèi)容]http://www.cnblogs.com/tenghoo/archive/2008/06/01/1211663.html
[動機(jī)]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
[補(bǔ)碼/二補(bǔ)數(shù)]http://zh.wikipedia.org/wiki/%E4%BA%8C%E8%A3%9C%E6%95%B8
9.排序算法
[穩(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個(gè)數(shù)7次比較]
1. [構(gòu)造排序樹]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至少有兩個(gè)頂點(diǎn), 且其所有回路的長度均為偶數(shù).
(2)哈密頓圖
[定義]由指定的起點(diǎn)前往指定的終點(diǎn)，途中經(jīng)過所有其他節(jié)點(diǎn)且只經(jīng)過一次.
http://zh.wikipedia.org/wiki/%E5%93%88%E5%AF%86%E5%B0%94%E9%A1%BF%E5%9B%BE
11.閱讀程序注意事項(xiàng)
(1)對程序段進(jìn)行等價(jià)變換
(2)看清if的條件(比較符號看翻, 忽略括號)
(3)兩位數(shù)以上乘法豎式計(jì)算兩遍(即改變順序) -> 特別注意!!!!!!!!!
(4)注意函數(shù)名縮寫(hpsrt)和特征語句(j = k + k) -> 07的堆排(不斷更新大根堆)沒看出來
(5)對于很惡心的模擬題: 列表法(三維可以在水平方向在加列, 不妨用其他顏色的筆, 或者鉛筆指出指針)
12.完善程序注意事項(xiàng)
(1)注意區(qū)別遞歸函數(shù)參數(shù)的0和1,以及遞歸是參數(shù)是否需要改變(如果在函數(shù)中改變了, 很可能不用)
(2)注意邊界條件(通過交換確定, 還是通過枚舉確定)
(3)遇到比較熟悉, 但是忘得差不多的算法, 一開始不要糾纏, 最后再斟酌
(4)注意函數(shù)類型, 比如void main(), 不要寫return 0;
(5)對于for循環(huán), 弄清楚循環(huán)變量i或j代表什么(結(jié)合題目分析)
13.負(fù)數(shù)取模
[定義]x % y = x - y*(x/y);
需要注意, 下取整的定義和數(shù)學(xué)取整的定義不同.
[這里是分析]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是隨機(jī)地址, 可能寫到不能寫的位置上
void swap(int *x, int *y){int *k = x; x = y; y = k;} //傳入值, 交換地址
(3)注意事項(xiàng)
int * fellow; //這里的fellow是隨機(jī)地址, 必須使用int *fellow = new int;來初始化
*fellow = 123456;
(4)應(yīng)用: 動態(tài)數(shù)組(略)