专业课复习指南.docx

专业课复习指南一：专业课:先说离散数学，很多朋友看到东大初始考离散数学就心凉了一半，的确离散数学是计算机学科中一门极其重要又较为晦涩难懂的科目，但庆幸的是东大的离散数学还考的比较正常，题目也不算难，卷面分值为40分，仅次于数据结构,其重要性可见一斑。离散数学也是我专业课考完唯一感到放心的一门，甚至认为40分全拿也问题不大。先看看东大推荐的复习书目：工、离散数学朱一清编，电子工业出版社;2、离散数学耿素云、屈婉玲编著，高等教育出版社。东大本校用的是朱一清的本子，我在书店里面大致翻过，也不错，但我没有买，因为我看到耿素云、屈婉玲的本子，是清华大学出版社出的，比朱的本子要薄整整84页，内容却相差不大，而且还有一本对应的题解，感觉更值一些，就买了耿、屈的本子，现在看来二者并无本质区别，大家可以根据个人喜好来买。这里我就拿手头的耿素云、屈婉玲的本子来谈复习要点。第一章命题逻辑重点！一定要看，这是离散的基础，要熟练掌握公式以及推理证明的解题过程。一定要掌握等值演算和主析取（主合取）范式判断证明的方法，不要动不动就用真值表证明。第二章一阶逻辑重点！必看，尤其掌握一阶逻辑推理理论，今年考题就有证明，分值不低，需要熟练掌握，其实离散数学前面的部分真不算难，这部分的分千万别轻易丢掉。第三章集合和基本概念和运算非重点，单独出题的可能性不大，大致看看就行了，但一定弄清楚本章的课后题，文式图一般都能搞定的，还有就是幕集的概念。第四章二元关系和函数重点中的重点！什么都不说了，好好掌握吧人人第五章代数系统的一般性质重点中的重点！直接关系到你后面几章的理解程度，这章概念很多，一定要区分清楚!第六章几个典型的代数系统重点中的重点！前面学的都在这章能体现出来，首先要区分若干个容易混淆的概念，我清楚的记得今年就有一道考题问到''域"的概念及其在计算机领域的应用。大家非常值得自己好好总结一下本章的众多知识点。从第一章到第六章是最容易出考题的地方，大家要特别予以重视。第七章图的基本概念这章很难讲，按常理推断图论部分是离散数学的重点和难点，但东大历年却考的很少，尤其这章有许多部分与数据结构相应章节有重复的部分，大家大致看看就行了，充其量巩固一下数结的知识。第八章一些特殊的图这章很难，现在回想起来我都晕晕糊糊的，但确实是离散数学图论的重点，可惜东大很少考到，复习不复习，大家酌情考虑吧，反正去年没考。大家如果要复习，也把重点放到概念上，我认为不会出太偏太难的题目打击各位。第九章树跟第七章情况类似，大家翻翻就行了，数据结构中的Tree才是重中之重啊！第十章组合分析初步不用看第十一章形式语言和自动机初步不用看，当然如果看看对编译原理的复习有好处。都说完了，现在看看离散数学的复习，其实内容并不多,课本的课后题目就足够大家做的了，当然如果你属于那种不做题就难受的人，你还可以买相应的题集，但我个人认为用处不大，毕竟离散是东大考的四门中最简单的一门，可以说都很基础，大家好好复习拿40分都极有可能，但再次提醒大家东大的专业课试卷不考小题（包括填空、判断、选择etc）,全部是解答题的形式，所以大家要有心里准备。二：接下来我们再看看另一个复习起来相对容易的专业科目操作系统（以下简称。S）。在专业课试卷中所占的分值为30分，不多而且相对而言比较好拿分。还是先看看东大推荐的复习书目：工、现代操作系统教程滕至阳，高等教育出版社；2、ModernOperatingSystemTnenbaumAS,机械工业出版社。这两本书我都有，但我本科用的却是清华的本子，据我了解东大本校用的是ModernOperatingSystem»授课，这本书也是我们常说的''恐龙书，很厚也很经典，但我认为这样的书仅适合平日学习，不适合应对考试，因此不推荐大家在这本书上花功夫，实事上我复习期间也就没有翻过这本书，另外考试的时候题目都为中文，没必要为了30分去啃那么厚的一本影印版的书，而且如果语言不过关的话无疑是在自寻烦恼，也看不出个重点来。东大的滕至阳教授写的现代操作系统教程我觉得还是不错的，虽然很多人觉得那本书有些乱，我估计那是因为本科时所用教材先入为主的原因。其实OS的基础东西就那么几点，任何教材都会包括，建议大家可以先过一遍自己曾经用过的教材，熟悉一下OS中的核心知识，然后再认真阅读滕的本子，你会发现腾的本子不少独到的地方,此外这本书还配有教学光盘，懒惰的同学可以连书都不用翻了，唯一的遗憾是这本书不太好买，大家自己想办法吧。这里我就拿腾的本子谈谈OS复习的要点，供大家参考：第一章引言大致看看，起码知道什么是OSA_乐课后题重点看一下1,3,6。说到课后题，腾的本子有相应的课后题答案，但我也不清楚哪里有卖，是朋友帮忙复印的，大家自己想办法吧，不行的话就自己从书里找，自己总结，效果我想更好。第二章作业管理这是腾的本子比较独到的一个地方，把作业的地位拔的很高,需要大家认真看一下尤其是24节。重点掌握"系统调用、"SPOOLING“、”虚拟设备等若干概念，至于书中大段的程序大家就量力而行吧，我认为可以不看，但看绝对没有坏处。课后题重点看一下，4,5o第三章存储管理重点认真理解”虚存的含义和实现方法，熟悉逻辑地址与物理地址的映射，能区分静态重定位和动态重定位的不同，熟悉请求页式的地址变换方法，了解页面置换算法（尤其是FIFO和LRU）。课后题重点看8,10,14,17,19,28o第四章进程管理在任何教材中都是重点中的重点深刻理解掌握进程的同步、互斥、死锁以及在计数信号量上的PV操作。一重点掌握三个算法,这也是OS中最重要的三个算法：1生产者与消费者、2读者与写者、3银行家算法。另外还有许多概念也需要认真理解记忆，譬如“原语、”微内核等。本章的实例设计到大段的代码，我觉得可以跳过，抓住最核心的知识就可以了。课后题重点掌握2,4,11,13,14,17,21,27,30。第五章线程的概念与应用如题所言，重点了解线程的概念即可，如果你有一定JaVa编程的基础，可能了解OS多线程执行更容易些，本章不是重点，了解即可。课后题看看2,5,6足矣。第六章文件管理不算是重点，但很容易涉及考到，还是要看的。重点了解这几个概念和知识点：''文件、'、文档点、'成组与分解、''打开与关闭，要明白文件分为流式和记录式，另外还要小心''文件卷''和''超级块''的概念。课后题以9,10,19,25为主。第七章设备管理不算重要,其实OS大多将设备按照文件处理，所以并不难理解。重点就看看IO队列调度和IO进程工作原理，另外明白设备文件和普通文件的区别即可。课后题着重看一下10,14,20,29,34o至于第七章以后的内容，我认为不用看了，因为考到的可能性为零，讲这个话我还是要对大家负责任的。另外，大家在认真复习前面的内容的同时非常有必要关注一下OS的发展趋势和最新成果，因为05年就考到了嵌入式操作系统的概念，课本里面没有，需要的是自己平日对IT的关注和日积月累（譬如64位时代的到来意味着什么？）o东大的OS考的比较正常,大家放心复习就是,BT的科目我们最后再说。三：下面接着谈谈令不少人头疼的编译原理，恐怕如果投票评选计算机专业最难的科目，编译原理十有八九要高票当选。东大的今年编译就考的令我抓狂，甚至考场上有种撕卷子的冲动（幸好最终忍住了人人），3道大题30分，除了第一道题还算正常，剩下的两道出题的方式我绝对没想到，后面讲到相应的章节的时候我会提到。先看看东大的推荐书目：工、编译原理（第三版）陈火旺，国防工业出版社；2、编译原理及编译程序构造秦振松，东南大学出版社。陈的本子是很多学校都在用的教材，很经典，值得一看，而秦的本子是东大学生用的教材，我感觉也不错，大家可以根据自己的情况酌情考虑。我复习用的是秦的本子，原因很简单,他的本子比陈的本子要薄好多。实事上核心的知识就那么多，书薄说明他废话少，大家时间都很宝贵，我当然选薄的了。当然如果你两本书都有，可以选一本书为主，重要的知识点可以交叉的看一下。不过，说实话，编译就30分，按照05东大出题的思路并不好拿分，旦愿06年东大能良心发现，出题稍微正常些，这样大家还是在编译原理上还是能拿到不少分的，因为编译的考题的类型还是相对比较死板的，远不如数据结构那么灵活多变。这里我就拿秦的本子谈谈编译原理复习的要点，供大家参考。此外，我列出的课后题是东大老师给学生布置的作业，我个人认为是一定要认真做一下的。第一章引论读一遍足矣，没什么大用。第二章编译的基础知识需要认真看一下，基础的东西总是重要的，本章尤其是23节非常重要，今年就考到一个由语言构造文法的大题，可谓''会者不难，难者不会，需要一些技巧在里面的，建议大家找些题集专门练习一下，总结一下做题的思路。课后题重点做24、25、2-9o第三章词法分析非常重要，要好好复习，但特别注意本章3.2节和3.3节不用看，只有3节要认真学习，本节的好多知识点贯穿编译原理全书。课后题32、3-4.3-7.3-9o第四章自上而下语法分析极其重要，很多思想和知识点都与后面的章节息息相关，需要认真掌握。4.1节主要掌握一些基本的概念，4.2.1主要掌握间接左递归的处理方法,4.2.2大致了解，4.3.1要会算，43.2重点掌握表4.2,4.3.3可以不看，4.4我个人认为不是很重要，有时间再看吧。课后题着重看一下43,4-4,4-7o第五章优先级分析，我个人认为考的可能性不大，如果非要看的话，着重在5.2节吧，掌握一下基本的思想以及5.2.2的几道例题。课后题就会做59足矣！第六章LR分析法及分析程序自动构造每年都会出考题的章节，可以说是编译中最核心的章节，必看！书中每道例题都要看！只有6.7节分析表的自动生成不用看。特别要提到05年的考题中考到了用LR分析法,分析二义文法的问题，大致6.6节的内容，但令人头疼的是二义文法没有给你,让你自己举例，然后再分析，让人感觉很不痛快，所以大家在复习这章时一定要认真，真正弄懂，另外要多做练习，书上的例题最好自己能亲手做一遍，不要光看！此外，适当做些课外的题目，一定要熟练并且准确，这种类型的题目，是一步一步完成分析的，前面做错后面就全错了，大家千万仔细再仔细啊！课后题62,6-6,6-10o第七章语法制导翻译并产生中间代码这章并非重点，但不难掌握，还是建议大家看一下，以防万一。特别提醒大家的是类似P130页的那种语义过程，不需要掌握，很麻烦的也不会考，这章关键是掌握例题：诸如Pl35、P工41、P143的例子一定要会，此外还有一个知识点就是P153的那个数组及其下标变量地址的计算公式以及P157的例题，剩下的内容全部是了解性的，如果时间不够，可以跳过的。课后题以73和78为主。第八章不用看，呵呵第九章第十章建议结合起来看。优化是编译中非常重要的步骤和思想，但很多学校教学时都简单略过，甚至布置成课后完成，确实对学生很不负责任。05年就考到了优化的大题，但令我及其郁闷的是，考的太空泛了，题目要求谈谈优化的思想和策略，并没有给出具体的中间代码，很笼统，一下子就蒙了，不知从何说起，瞎写了一堆，缺乏条理，希望大家要好好对待这最后的两章。其中9.2.4可以不看。M九章有很多例题，要认真研读。课后题重点就是9-1。第十章前面都可以跳过，关键是10.4DAG结点的一种启发式排序，这个还是比较重要的。至此编译原理就介绍完了，其实平心而论，编译原理在专业课试卷中所占分数不高，但由于不出小题，所以可能出到知识点是非常有限的，大家需要的只是对总体的把握，尤其一些核心的考点一定要熟练掌握，做题的时候一定要细心，只要东大出题正常一些，编译拿分并非难事。这里只能祝大家好运了，因为05年考的编译我感觉知识难度不大，但拿分却非常困难，是四门中我个人考的最不舒服的一门AA_o四：最后我谈谈专业课的重头戏数据结构。数结在计算机科学体系中的重要性毋庸置疑，属于研究生入学考试必考科目，我个人感觉东大的数据结构出题充分体现出数据结构考点多，出题活的特点，需要大家花一些时间认真准备。至于复习用的教材，今年的考试说明还未正式对外公布,我仍然以去年为准，我这里就拿清华大学殷人昆的C+版的本子为例，谈数结复习的要点，供各位参考。其实我个人认为，对于数据结构这门课，教材之间差别不是很大，因为本质的东西都一样，更多的是描述语言选择的不同，随着OOP的流行，C+和Java这类语言越来越成为数据结构描述首选语言，按照东大的要求C+无疑是大家应该优先采用的描述语言，当然如果你确实不习惯用C+,用C也可以的（我考前曾问过东大的老师）。其实描述语言和数据结构知识点并没有直接的联系，语言只是大家交流思想的一个通用工具，从这个角度讲C其实通用性更好，话虽如此，但还是强烈大家使用东大指定教材选用的描述语言来答题，以求判卷老师更容易看懂你解决问题的思路，而不是在语言上就出现沟通困难。第一章绪论如果你有C+基础可以直接跳过。看清楚，我写是''基础二字，换句话讲，不需要你精通C+,你只要能读懂简单并且典型的C+源程序就足矣。不要因为数据结构教材是C+的本子就非捧着一本BjarnesStroustrupTheC+Programming来看，那纯粹是件徒劳无益的事情，对你考研没有任何帮助。本章唯一一个知识点就是算法分析中的复杂度的概念：考试的时候不会给你个算法让你说出它的复杂度，但可能让你就某个问题写一个算法，要求该算法的复杂度为XX,这个心里有数就是了。第二章数组这里有个东大考了好多次的热点问题KMP算法（带*号的内容），04年和05年都考到了，大家还是需要注意一下，失效函数计算的时候仔细些，实际并不难。另外本章需要掌握的还有2,2节顺序表（侧重看2.2.1和2.2.3）,最后要把2.4稀疏矩阵看看，尤其是242稀疏矩阵的压缩表示，05年考到一道大题,涉及到稀疏矩阵的知识。总的来说，本章的重点突出，其它部分酌情看一下即可。第三章链表数据结构中的核心概念，用途极为广泛，主要掌握单链表（其中游标和静态链表可以跳过不看），大致了解循环链表双向链表。至于3.5稀疏矩阵和3.6C+中的虚函数和动态联编可以跳过。第四章栈和队列又是数据结构中的核心概念，首先一定要把它们的定义和思想弄清楚，单独考它们的可能性不大，但它们是解决好多问题的最佳工具模型和有效思路，应用很频繁。另外本章还有一个可能考到的知识点就是表达式的计算，4.22和4.2.3的问题要学会手动转换，而且要熟练。本章4.L3链式栈和4.5事件驱动模型可以跳过。第五章递归递归是计算机解决很多问题不得不采用的算法，但让人脑去模拟计算机执行递归的每一个步骤还是很令人头疼的，毕竟人脑不是电脑。所以本章侧重了解递归的概念和思想，太复杂的应用应该不会考到。另外广义表的问题也是一个可能的考点，譬如表头表尾是如何定义计算的，其实是很简单的。本章知识点不多，复习起来也不难的。第六章树和森林数据结构必考的章节，重点中的重点,一定要认真仔细的复习本章。正因为都是考点和重点，所以反而也没什么谈的了，好好复习就是了。非要找出一些不考知识点的话，我认为6.8二叉树的计数可以跳过，其它知识希望大家多花些时间认真掌握。第七章集合和搜索7.1集合及其表示和7.2等价类和并查集可以不看，7.3节也只需看看7.3.3顺序搜索和7.3.4折半搜索。重点精力放在后面几节：74二叉搜索树除了7.4.5涉及到游标类不需要看以外其他几节都要认真看一下，7.5最优二叉搜索树我觉得还是以概念和定义为主，关键在于76AVL树,尤其是平衡化旋转非常容易考到，另外关于AVL树的算法也可能有所涉及。第八章图数据结构复习的重点，虽然离散中有关于图论大量的知识，但实际考到的不多，倒是数据结构中的图的知识，考点极其多而且非常灵活。希望大家能像复习树那样认真复习准备，其中本章可以略过的是&5.2和8.5.3,其它都需要大家认真看，并且书上的例题最好能自己亲自动笔做做。第九章排序数据结构知识中常见的考题，强烈建议大家复习的时候把多种排序算法总结比较一下，通过比较它们适用的情况及算法的时间和空间复杂度的不同来加深对本章的理解。其中可以跳过不看的是9.4.2锦标赛排序，9.5.3递归的表归并排序，9.6基数排序，9.7.3,9.74,9.7,5关于外排序较深的后面三节，但9.7.2k路平衡归并却要仔细的看一下。第十章索引结构与散列这张知识点很突出，一个是B树，注意与AVL树结合看；另一个就是散列，散列关键是掌握解决散列冲突的几种效率比较高的方法。其它内容都可以跳过。到此，数据结构复习要点就过完了，也许很多人会觉得数据结构如此重要，为何我给大家提的复习要点却又如此空泛，原因其实很简单，因为数据结构是专业课四门中出题最为灵活，最不好预测的一门，我没有那个把握也没有那个能力给大家细细指出复习要点，那样没准会害了大家。就05年的考题看，东大更侧重问题的解决，而不是书上算法的记忆，很多同学准备数结考试就像背文章一样将大段的算法背下来，但如果不认真理解，死背只会死用，上了考场十有八九是不行。当然书上一些重要的算法思路还是要牢记的，譬如树叶子结点个数，总结点个数，树的高度等等（05年一道大题就涉及到这些知识点），但希望大家能活学活用，这样上了考场才会应对自如。我多少有些武断的认为数据结构才是专业课中真正能考察一个人专业素质的课程，也是以后进一步学习中最可能用到的知识，非常值得大家下功夫。