考完sub，心里是五味杂陈。来到gter论坛上，本以为考cs的人在诸学科里即使不是最多也是比较多，心得感受肯定不少，不容我这个大烂人置喙。却没想论坛空空，想是大家都忙于申请材料脱不开身吧。我在此论坛潜水多年，受前辈的帮助不少，虽然考得不甚理想，但是深以为有责任指点后来者几句，以免走了弯路，劳民伤财后悔莫及。

首先，我要说，在中国顶尖名校（仅限北大清华中科）就读的同学们，我深以为诸位将GPA搞高才是第一要务，sub可考可不考。考了固然是锦上添花，不考也无伤大雅，毕竟有良好的声誉诸多的校友在国外。对于其他同学，也是专业课为最重要，GT和sub都没有GPA重要，而且其他皆可弥补，GPA是无法弥补的。

（一）材料准备
下面简单说说cs sub的准备材料问题。
我准备sub，用了以下几本材料：
1．ETS寄送的材料：说明与9629真题
2．黄蔚、headlong、张涛著《GRE计算机专项》（gter上有下载）
3．《计算机专业GRE考试试题精选及详解》
4．历年真题。

第一本就不用说了，大家都知道，是基本材料，要好好看，因为后面附了P+值的表，和评分标准，是唯一的官方评分标准。在29er.51.net（已关站）的另一份材料里给出了8629，9429和9629三次考试的P+值曲线。这个文件不知现在还能不能找得到。我一直对几个cs sub网站的关站感到困惑，也为那些网站上丰富的备考材料和分析没有及时保存下来感到惋惜。但是我相信，这些材料应该在一些非公开的校内ftp上都能找得到，大家可联络清华等学校的同学，看看能不能要到一些。

关于第二本，我本无资格评判。这是一本由众多前辈汇集心血编著的一本书，我见到的最早的形式出现在网上时还只是一个压缩包，里面是理论组、数学组等四个组关于每一道题的解法的文本，甚至还有工作计划表。可以看出，这本书的作者其实不止三人。由不同的人解出不同的问题，水平自然参差不齐。可以说，这本书中的错谬确实过多，甚至有些错误还会引起误导。该书中的错误和不妥之处主要集中在以下几类：最多的是引述原题时，由于排版问题，采用了非通用的符号，造成误解。还有不少题，虽给出解答，但语焉不详，大部分人可能无法理解作者用意。还有题目归类的错误，和打字的错误，亦举不胜举。习题的解答，有些采用的解法不实用，另外，还有很多重复题。但由于重复本身就是sub的一个特点，所以这也算不上什么大错误。总之，这本书无疑是非常有价值，但是最好作为一本大纲来看，做真题的时候还是最好参照影印版。现在我看到的影印版真题，有91、94年的真题，91、96年的样题（分类过的）。很多图书馆里可以找到86年的真题，不过没有很大意义，因为据说（传闻）96年以后用的是新的题库。而且看上去，确实是近几年的题目重复率比较高（包括回忆题）。该书后面的回忆题极重要，必须看，“就是背也要背下来”。

第三册，是上面那本书的附录中提到的，清华图书馆有，可借到。同以前的诸位一样，我同样不推荐这本书，这本书其实就是所谓REA四套题的翻译，与真题相去甚远，题目偏僻且怪，大多数知识点不可能考到。但是我必须说，里面有一些关于计算机系统结构和组成原理的题，比如浮点数和磁盘存储，可以看一下，如果有功夫的话。

下面说到那个古老的问题，英文原版教材的问题。我不建议用英文原版教材，中文教材便可应付，至少从今年的情况来看是这样。将来怎么发展，会不会像三月的GRE general一样变态一回，我不敢肯定。我唯一想推荐的一本书就是Michael Sipser的《计算理论导引 Introduction to the Theory of Computation》。我相信，关于图灵机，可归约性，NP问题的内容，这本书足够了。NP的题，每次必然有，但也就一道。算法复杂度的问题，这本书似乎还比较单薄，例子较少。其实简单的问题普通教科书上一般都有。难一点的，参照一下其他书吧。Introduction to algorithms 这本书涉及考点也多，可看看目录，选看几章作为熟悉单词用。贴一下该书目录：（划★的是我认为的重点）

I Foundations
Introduction 3
l The Role of Algorithms in Computing 5
l.l Algorithms 5
l.2 Algorithms as a technology 10
2 Getting Started I5
2.l Insertion sort 15
2.2 Analyzing algorithms 21
2.3 Designing algorithms 27
3 Growth of Functions 41
3.l Asymptotic notation 41
3.2 Standard notations and common functions 51
★4 Recurrences 62
4.l The substitution method 63
4.2 The recursion-tree method 67
4.3 The master method 73
4.4 Proof of the master theorem 76
5 Probabilistic Analysis and Randomized Algorithms
5.l The hiring problem 91
5.2 Indicator random variables 94
5.3 Randomized algorithms 99
5.4 Probabi1istic analysis and further uses of indicator 106
II Sorting and Order Statistics Introduction 123
★6 Heapsort 127 （几种sort勿搞混）
6.l Heaps I27
6.2 Maintaining the heap property 130
6.3 Building a heap 132
6.4 The heapsort algorithm 135
6.5 Priority queues 138
7 Quicksort 145
7.l Description of quicksort 145
7.2 Performance of quicksort 149
7.3 A randomized version of quicksort 153
7.4 Analysis of quicksort 55
8 Sorting in Linear Time 165
8.l Lower bounds for sorting 165
8.2 Counting sort i68
8.3 Radix sort 170
8.4 Bucket sort 174
9 Medians and Order Statistics 183
9.1 Minimum and maximum 184
9.2 Selection in expected linear time 185
9.3 Selection in worst-case linear time 189
III Data Structures Introduction 197
10 Elementary Data Structures 200
l0.l Stacks and queues 200
l0.2 Linked lists 204
l0.3 Implementing pointers and objects 209
l0.4 Representing rooted trees 214
★11 Hash Tables 221
ll.l Direct-address tables 222
11.2 Hash tables 224
ll.3 Hash functions 229
ll.4 Open addressing 237
ll.5 Perfect hashing 24S
★l2 Binary Search Trees 253
l2.l What is a binary search tree? 2S3
l2.2 Querying a binary search tree 2S6
l2.3 Insertion and deletion 261
l2.4 Randomly built binary search trees 265
13 Red-Black Trees 273
l3.l Properties of red-black trees 273
l3.2 Rotations 277
l3.3 Insertion 280
l3.4 Deletion 288
14 Augmenting Data Structures 302
l4.l Dynamic order statistics 302
l4.2 How to augment a data structure 308
l4.3 Interval trees 311
IV Advanced Desthe and Analysis Techniques Introduction 321
15 Dynamic Programming J2J
l5.l Assembly--line scheduling 324
l5.2 Matrix-chain multiplication 331
l5.3 Elements of dynamic programming 339
15.4 Longest common subsequence 350
l5.5 Optimal binary search trees 356
★l6 Greedy Algorithms 370
l6.l An activity-selection problem 371
l6.2 Elements of the greedy strategy 379
l6.3 Huffman codes 385
l6.4 Theoretical foundations for greedy methods 393
16.5 A task-scheduling problem 399
17 Amortized Analysis 405
l7.1 Aggregate analysis 406
17.2 The accounting method 410
17.3 The potential method 412
l7.4 Dynamic tables 416
V Advanced Data Structures Introduction 431
18 B-Trees 434
18.l Definition of B--trees 438
l8.2 Basic operations on B-trees 44j
l8.3 Deleting a key from a B--tree 449
19 Binomial Heaps 455
l9.l Binomial trees and binomial heaps 457
19.2 Operations on binomial heaps 461
20 Fibonacci Heaps 476
20.l Structure of Fibonacci heaps 477
20.2 Mergeable-heap operations 479
20.3 Decreasing a key and deleting a node 489
20.4 Bounding the maximum degree 493
21 Data Structures for Disjoint Sets 498
2l.l Disjoint--set operations 498
2l.2 Linked-list representation of disjoint sets 501
2l.3 Disjoint--set forests 505
2l.4 Analysis of union by rank with path compression 50 VI Graph Algorithms Introduction 525
22 Elementary Graph Algorithms 527
22.l Representations of graphs 527
★22.2 Breadth-first search 531
★22.3 Depth-first search 540
22.4 Topological sort 549
22.5 Strongly connected components 552
23 Minimum Spanning Trees 561
23.l Growing a minimum spanning tree 562
23.2 The algorithms of Kruskal and Prim 567
24 Single-Source Shortest Paths 580
24.l The Bellman-Ford algorithm 588
24.2 Single-source shortest paths in directed acyclic graphs
★24.3 Dijkstra’s algorithm 595
24.4 Difference constraints and shortest paths 601
24.5 Proofs of shortest-paths properties 607
25 All-Pairs Shortest Paths 620
25.l Shortest paths and matrix multiplication 622
25.2 The Floyd-Warshall a1gorithm 629
25.3 Johnson’s algorithm for sparse graphs 636
26 Maximum Flow d43
26.l Flow networks 644
26.2 The Ford-Fulkerson method 651
26.3 Maximum bipartite matching 664
26.4 Push--relabel algorithms 669
26.5 The relabel--to-front a1gorithm 68I VII Selected Topics Introduction 701
27 Sorting Networks 704
27.l Comparison networks 704
27.2 The zero-one principle 709
27.3 A bitonic sorting network 712
27.4 A merging network 716
27.5 A sorting network 719
28 Matrix Operations 725
28.l Properties of matrices 725
28.2 Strassen’s algorithm for matrix multiplication 735
28.3 Solving systems of linear equations 742
28.4 Inverting matrices 7S5
28.5 Symmetric positive-definite matrices and least-squares approximation760
29 Linear Programming 770
29.1 Standard and slack forms 777
29.2 Formulating problems as linear programs 785
29.3 The simplex algorithm 790
29.4 Duality 804
29.5 The initial basic feasible solution 811
★30 Polynomials and the FFT 822
30.l Representation of polynomials 824
30.2 The DFT and FFT 830
30.3 Efficient FFT implementations 839
31 Number-Theoretic Algorithms 849
3l.l E1ementary numbertheoretic notions 850
31.2 Greatest common divisor 856
3l.3 Modular arithmetic 862
3l.4 Solving modular linear equations 869
3l.5 The Chinese remainder theorem 873
3l.6 Powers of an element 876
3l.7 The RSA public-key cryptosystem 881
3l.8 Primality testing 887
3l.9 Integer factorization 896
32 String Matching 906
32.l The naive string-matching algorithm 909
32.2 The Rabin-Karp algorithm 911
32.3 String matching with finite automata 916
32.4 The Knuth-Morris-Pratt algorithm 923
33 Computational Geometry 933
33.l Line--segment properties 934
33.2 Determining whether any pair of segments intersects 940
33.3 Finding the convex hull 947
33.4 Finding the c1osest pair of points 957
★34 NP-Completeness 966
34.1 Polynomial time 971
34.2 Polynomial-time verification 979
34.3 NP-completeness and reducibility 984
34.4 NP--completeness proofs 995
34.5 NP-complete problems 1003
35 Approximation Algorithms 1022
35.l The vertex-cover problem 1024
35.2 The traveling-salesman problem 1027
35.3 The set-covering problem 1033
35.4 Randomization and linear programming ]039
35.5 The subset-sum problem 1043
VH APPendir: Mathematical Background
Introduction 1057
A Summations 1058
A.l Summation formulas and properties 1058
A.2 Bounding summations 1062
B Sets, Etc. 1070
B.1 Sets 1070
B.2 Relations 1075
B.3 Functions 1077
B.4 Graphs 1080
B.5 Trees 1085
C Counting and Probability 1094
C.l Counting 1094
C.2 Probability 1100
C.3 Discrete random variables 1106
C.4 The geometric and binomial distributions 1112
C.5 The tails of the binomial distribution 1118
Bibliography 1127
Index 1145

http://mitpress.mit.edu/algorithms/ 这本书后面的题还有答案，google一下即可。

其他的问题，前面有人说OO是一个trend。没错。另外介绍一个论坛（http://www.testmagic.com/forum/forum.asp?FORUM_ID=78 ），可以去看看，有一些整理的材料，也没多大价值，但是不是可以不用自己弄了吗，像各种sort algorithm的worst，average复杂度等列了个表很方便。

（二）考试过程
我是在北语考的，一切都与GRE没有分别，唯一不同的就是再也没有了跨区做题的烦恼。两个小时50分钟的时间，尽量分配好。原来有份材料说第一个小时做30道题，第二个小时做20-25题。这样做可能会稍有些紧，因为无疑你留在后面做的题都是较难的题，除非你想omit一些题，否则肯定会有那么几道特别耽误时间的题。所以这个时间分配标准是不是应该再改一下呢？我也拿不准。

不知道为什么没有人写考试范围，我来大概写一些，请高人指正。以下都是常考知识点，概念不明的应熟记。
操作系统
生产者消费者问题、读者写者问题、调度与死锁：各种调度算法；死锁的预防避免及解除。虚拟存储器：页面置换算法FIFO，LRU
体系结构和组成原理
Amdahl定律、基本数据类型：浮点数计算。十进制到二进制的转换。RISC，流水线原理，存储体系：地址映像，虚拟存储器及管理。
数据结构
表，数组，堆栈。树与二叉树：binary search tree，各种遍历，AVL树。HASH表。插入、选择、Heap、快速、Shell、归并等各种排序及复杂度的计算。
计算方法（包括：编译原理、数理逻辑、图论、自动机理论等）
除了把《计算理论导引》这本书看一遍以外，数理逻辑的内容要简单过一遍，特别注意：永真式、重言式、等值演算、完全集（{NOT,AND}{NOT,OR}{NOT,Implication}）。

这些知识点最基本，学过的人都应该至少有印象；又是最常考，至少我见到过若干次。请大家补充。

真题这次没见大家讨论，也许在内部论坛上有讨论吧，但是我没看见。这是一个好现象。其实ETS已经把范围限得很死了，每次的题目又相差不多，没有必要大张旗鼓搞一个真题回忆，再弄得ETS反应过度取消考试，对谁都不好。

alexsmart