[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)应用: 动态数组(略)