07NOV2009 GRE Subject Computer Science 总结+复习材料

首先要说明，我很弱，从不好好学习，没有好好复习。这次能上 80% 的话就谢天谢地了。其次，这个主要是自己的总结，有很大的个人因素（实在写不出来足够 General 的东西）

UPDATE @ 19 NOV 2009 - Raw Score=62, Correct 63, Incorrect 5, Omit 2

0 关于考试难度
这次难度貌似不大，但是有些计算（包括用人脑跑程序的两个）太麻烦，偏偏我在这方面又是短板（相信我，这是能力问题），所以有几道题属于放弃了。

1 关于考试范围

我的复习基本上都是在 05-06NOV2009 两天搞定的，大约 20 小时。在考场上感觉复习的东西基本覆盖了。复习材料很少，Booklet + 20031010.pdf。后面那个 pdf 在附件里（现在已经不太好下载了），虽然内容比较老，但是也能用。

最 General 的一句话：好好复习基本知识，考试的时候依靠基本知识与其上的推理。

复习的时候集中了两个地方，排序和图论。从用处、原理、分析（主要是时间复杂度，空间复杂度应该会极少）三个方面压结识了。排序的 Bubble/Merge/Quick/Heap/Shell，图论的 Prim/Kruskal/Dijkstra/BFS/DFS/MincutMaxflow 这些，个人感觉 Wikipedia 上的知识就够了，而且很清晰。要着重于最常用、最基本的东西，CS Sub 不会有太深的。数据结构上，Graph+HashTable+LinkedList(Bi/Single)+Array+BinaryTree+一般的 Tree（比如给你一个 x-ary tree 让你回答几个性质） 差不多就够了，附带一些软知识比如 hash 函数的特点。

国内很多人都花很多时间复习 theory，不过我的感觉就是 exclusively theory cs 的内容都是基本概念，语言类的只有 regular language = finite automata, cfg=push down automata，感觉经常有语言间的包含关系、判定子集是什么语言这类题目，复杂性类的只有 np-complete, reduction, np, p 和不同 class 里面常见的一些 problem。其他的 theory 基本上就是数学，尤其是 number theory。这次有个 fermat 定理的我忘记了……f*ck me，除了 fermat, 还有 gcd 和 lcm，算术基本定理（唯一分解）。

程序语言涉及 C/PASCAL/Java，本身就学计算机的话没什么好复习的（到考 Sub 的时候对程序语言基本特性不熟悉的，别说自己还想学计算机）。递规调用、迭代调用、各种条件判断要熟悉，考试的时候会有实例让你算（比较恶心的题目会有让你用人脑跑程序，which is my weak point，这个我不会干，希望有人教教我哈）。

编译器知识我觉得可以分成两类，一类是可以深入了解语言特性后自己明白的（比如这次考得虚函数 dynamic dispatch table，写程序的时候寻思寻思会变成什么底层代码就可以很容易的想到这个数据结构），另一类是跟 theory 部分 automata 很近的东西（比如 abstract syntax tree）。有些 high level 的软知识要知道，比如解释语言和编译语言的区别。主要是把常见概念搞懂，比如本段说的两个。

数字逻辑很简单，主要是卡诺图和化简。知识点本身没什么难度，但是“考试的时候依靠基本知识与其上的推理”，今天的考试有一个是，判断什么输入时输出内容不确定，其实就是化简表达式然后简单带入。其他的硬件知识，要了解一些机器的设计，比如堆栈型计算机。

系统上，了解一些 FIFO(Belady 特征),LRU, LFU 等 Cache/VM 替换算法，FIFS, SJF 和其他的调度算法，以及 并发和 PV 操作，内存分页、分段以及与 VM 的关系，差不多就够了。

然后还有 Performance 一类。比如 Amdahl 定律和 Availability 的定义等等。记住概念、公式，到时候随机应变。如果记不住怎么办？猜（Well, 考场上 Amdahl 定律我就是自己拼凑出来的……）。
.--
其他的就不好总结了，比较琐碎。比如高性能计算的一些……如果具备一些“软知识”会容易很多（软知识就是一些 Understanding 的东西，有这个你就可以猜很多东西了）。

2 没了，所以给点儿建议

平时多积累一些软知识，这些是永久性的积累，任何复习都无法代替（其实这牵扯另一个问题：你对计算机有爱么？如果有的话，这些软知识太容易具备了）。
算法的细节到时可以考前突击，相信我，细节永远是适合突击的。
Subject 拼体力，考前两天的集中复习更拼体力，如果你敢考前突击 20 小时，你就能明白什么叫脑子累了，那叫完全没反应的呆子。该带红牛带红牛，该吃巧克力吃巧克力。

附件里有我收集的复习资料， CS Sub 的资料不太好找。历年的 Recall 题目我就不放了，没啥用，建议用 Booklet 作模考（我 87%，提前半小时完成……主要是因为复习过程可能会不小心碰到里面的题目，所以会比较快）。 资料没有必要都看完。嗯，谢谢 Warald 提供这么个地方可以放这么大的附件，方便所有人，哈哈，如果开放一下后缀就更好了（.7z）。

加油啊

sub开考了?

good luck!

加油加油~~唉想当年我也考过sub，结果成绩……惨不忍睹……

加油啊！！！

已编辑为总结+复习材料。

。。。。只复习了两天，膜拜一下

哇 这个不错

这次人脑跑程序里面 有fork的那题太恶心了 跑死。。

哇，这个要顶，虽说我估计不会去考sub，好像不是必须的吧。。。

这个帖子牛！大牛。。。