欧拉图与汉密尔顿图，判定、性质；

    平面图，欧拉定理；

    对偶图与着色，四色定理；

    树与生成树，最小生成树；

    了解避圈法(Kruskal)求最小生成树；

    了解根树极其应用，最优树，了解前缀码。

    -----------------------------------------------

    计算机科学中的应用

    略过。

    __________________________________________

    中科院《编译原理》考查要点

    因为编译的题量较小，

    偶结合考试题型作了一些简要的总结。

    个人观点，仅作参考。

    请大家批评、补充。

    -----------------------------------------------

    1. DFA的构造：

    这是常考的题型。

    如2000年题目，

    由Pascal语言无符号数的正规定义，

    作出用状态转换图表示的DFA。

    其符号表示方式与陈火旺的书不同，

    请注意。

    可参考陈意云《编译》的p15页2.2。

    2. 给定语言，构造文法：

    通常要求文法是LR(1)，非LR(1)，或非二义等。

    参考例子：

    陈意云《编译》P86页例3.38和3.39。

    注意：

    给二义文法构造等价非二义文法的技巧。

    3. 语法制导翻译：

    为文法写语法制导定义、翻译方案。

    陈火旺的书没有作区分，

    请参考陈意云的《编译》4.2，4.3。

    注意参考书上例子，

    以及2000年的题目。

    尤其是书写格式。

    4. 写出表达式的后缀式、三元式、四元式、间接三元式：

    从往年考题答案来看，

    这一部分是参考陈火旺的书。

    参陈火旺的《编译》的5.3，5.4节，

    注意单目运算符在四元式中的表示法。

    5. 活动记录：

    几乎是必考。

    重点是陈意云《编译》6.3.2一节。

    6. 运行环境与中间代码部分：

    常用题型是C代码分析。

    近三年的试卷中都有这一类题目。

    参陈意云《编译》第六、七章的习题。

    试卷中许多考题的来源是陈意云《编译》的课后习题，

    茶余饭后不妨一做。

    ___________________________________________________________________

    中科院《计算机操作系统》考试要点

    参考书： 汤子瀛 《计算机操作系统》 1996版，498页

    以下是按照章节归纳的复习要点以及注意事项，有遗漏和不足的地方请各位指正。

    -----------------------------------------------

    第一章：

    关于操作系统的基本概念，OS基本类型、特征，OS服务；

    注意：关于系统调用和一般过程的区别的；

    了解“OS的进一步发展”一节；

    略过“1.6 OS/2操作系统简介”。

    第二章：

    前趋图，顺序执行与并发执行，Bernstein条件；

    进程概念、基本特征、基本状态，挂起状态（结合UNIX部分）；

    PCB构成、组织；

    OS内核，内核功能；

    进程创建的时机、过程（结合UNIX部分）；

    进程终止；

    进程阻塞与唤醒、挂起与激活的时机、过程（结合UNIX部分）；

    线程，线程与进程的区别；

    了解2.4.3;

    略过“2.4.4 Solaris操作系统中的线程”；

    “2.5 OS/2 操作系统中进程的描述与控制”中，了解会晤概念，其他略过。

    第三章：

    临界资源和临界区，同步机制应遵循的准则；

    信号量机制；

    整型信号量；

    记录型信号量（重点考查内容）；

    了解信号量集；

    理解经典进程同步问题中的几个算法，wait操作顺序问题；

    了解管程概念；

    进程通信类型，直接通信和间接通信；

    消息传递系统中的进程同步方式；