1中国科学院大学硕士研究生入学考试计算机专业综合考试大纲一、考试方法和考试时间闭卷，笔试，考试时间 180 分钟，总分 150 分。试卷共 16 道大题，每题 15 分，共 240 分，考生可以任意选择其中 10 道大题回答，并在答题纸的该题答案前标明“选做本题” 。如果选做的题目多于 10 道，则判卷将按照所选做试题的题号顺序选择前 10 道大题计分，后续所做视为无效考试内容。二、试卷结构题型：概念题（填空、选择、判断、简答） ，应用题（计算、画图、分析、设计）等。三、考试科目数据结构、计算机体系结构、操作系统、编译原理四门课程，每门课程各占 25%左右。四、考试内容I、计算机体系结构部分（一）考试大纲1、计算机体系结构概论（1）计算机体系结构的发展（2）计算机系统层次结构计算机系统的基本组成，计算机硬件的基本组成，计算机软件和硬件的关系，计算机的工作过程（3）衡量计算机的指标（4）计算机体系结构的设计原则2、指令系统结构（1）指令系统设计原则（2）指令系统的演变指令集分类，存储管理，运行级别（3）指令集结构2指令集的分类，指令操作数的存储，指令操作数的特征，指令操作和编码，C 语言的机器表示（4）异常与中断异常分类，异常处理，中断机制（5）存储管理MIPS 处理器对虚存系统的支持，LINUX 操作系统的存储管理3、计算机硬件结构（1）计算机组成原理和结构冯诺依曼结构，计算机硬件结构的演进，处理器与 IO 间的通信，计算机系统主要组成部件（2）计算机总线接口技术片上总线，内存总线，IO 总线（3）计算机系统启动过程处理器核初始化，总线接口初始化，设备探测及驱动加载4、CPU 微结构（1）二进制与逻辑电路计算机中数的表示，CMOS 逻辑电路（2）简单运算器设计定点补码加法，减法，比较，移位（3）定点补码乘法器（4）指令流水线处理器数据通路，五级流水处理器，解决指令相关（二）计算机体系结构部分考试要求1、掌握从外部 I/O 与上层应用交互的整体软硬件过程 2、掌握基于 MIPS 处理器的 Linux 操作系统 TLB 例外过程3、掌握 C 语言与指令系统的关系4、掌握系统初始化时 PCI 设备的探测过程5、掌握 I/O 通信中 DMA 传输过程6、能读懂 CMOS 电路，根据晶体管电路给出逻辑表达式7、掌握先行进位加法器结构及其 verilog 实现8、掌握 Booth 编码和华莱士树9、掌握指令流水线原理，了解解决相关的方法，能够用时空图表达流水线的运行（三）主要参考书目1、计算机体系结构基础、胡伟武等著;机械工业出版社，2017 年。II、 数据结构（一）考试大纲31、绪论（1）数据结构的基本概念，数据的逻辑结构、存储结构。（2）算法的定义、算法的基本特性以及算法分析的基本概念。2、线性表（1）线性表的定义、基本操作。（2）线性表的实现及应用，包括顺序存储结构、链式存储结构（单链表、循环链表和双向链表）的构造原理，在两种存储结构上对线性表实施的主要的操作（三种链表的建立、插入和删除、检索等）的算法设计与实现。3、堆栈与队列（1）堆栈与队列的基本概念、基本操作。（2）堆栈与队列的顺序存储结构、链式存储结构的构造原理。（3）在不同存储结构的基础上对堆栈、队列实施基本操作（插入与删除等）对应的算法设计与实现。4、数组和广义表（1）数组的基本概念、多维数组的实现。（2）对称矩阵和稀疏矩阵的压缩存储。（3）广义表的基本概念。5、树与二叉树（1）树的基本概念和性质。（2）二叉树的基本概念、性质。（3）二叉树的存储，包括顺序存储、链式存储结构。（4）二叉树的遍历。（5）线索二叉树的基本概念和构造。（6）树和森林的存储结构、遍历。（7）哈夫曼（Huffman）树和哈夫曼编码。6、图（1）图的基本概念和性质。（2）图的存储，包括邻接矩阵法、邻接表法。（3）图的遍历操作，包括深度优先搜索、广度优先搜索。（4）最小生成树、最短路径、关键路径、拓扑排序算法的原理、实现和应用。7、查找（1）顺序查找法、分块查找法、折半查找方法的原理、实现和应用。（2）二叉排序树、平衡二叉树、键树的原理、实现和应用。（3）B 树及其基本操作、B+树的基本概念。（4）哈希（Hash）表的原理、实现和应用。（5）字符串模式匹配算法的原理和实现。8、排序4（1）排序的基本概念。（2）直接插入排序、折半插入排序、气泡排序、简单选择排序、快速排序、堆排序、二路归并排序、基数排序、外部排序算法的原理、实现和复杂度。（3）排序算法的应用。（二）考试要求1、掌握数据结构的基本概念、基本原理和基本方法。2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用 C 或 C+语言设计与实现算法的能力。（三）主要参考书目1、数据结构（C 语言版） 、 严蔚敏，吴伟民 编著，北京：清华大学出版社，2007 年。III、 编译原理（一） 考试大纲1、编译系统的概念和架构（1）编译的概念、分类、编译系统的组成（2）程序设计语言的基础知识、作用域、参数传递等（3）四类形式文法的相关概念（4）构建编译系统的相关科学以及编译技术的应用等2、词法分析（1）词法分析器的作用（2）词法符号的描述（包括正则式、正则定义等内容）（3）基于状态转换的词法分析实现（4）有限状态自动机概念，正则表达式、NFA、DFA 间的转换，DFA 的化简3、语法分析（1）语法分析基础，上下文无关文法、二义性文法（2）文法的设计：二义性的消除、消除左递归、提取左因子等（3）自上而下的分析方法、递归下降分析和非递归的预测分析器等（4）自下而上的分析方法、LR 分析4、语法制导的翻译（1）属性文法、继承属性和综合属性（2）语法制导定义、求值顺序5（3）语法制导翻译的应用（4）语法制导的翻译方案（5）实现 L 属性的 SDD5、中间代码生成（1）语法树的变体、DAG（2）三地址代码（3）类型和声明的处理（4）表达式的翻译（5）静态类型检查（6）控制流的处理等6、运行时环境（1）存储组织、静态分配、栈式分配的基本概念等（2）作用域的运行时实现、非局部名字的访问等7、目标代码生成简介（1）代码生成器设计中的问题（2）目标代码中的地址处理（3）基本块和流图（4）基本块的优化（5）代码生成器的简单实现（6）窥孔优化（7）寄存器分配和指派（8）指令调度等（二）考试要求1、掌握编译系统构成的基本概念和相关原理2、熟悉词法分析的基础理论，明晰正则式、正则定义、有限状态自动机等基本概念以及相关转换的方法，能够按照要求构造简单的有限状态自动机，并实施必要的变换3、熟悉语法分析的基本理论，掌握上下文无关文法的基本概念、推导等，明晰文法、句子、语言之间的关系；能够根据需要对文法进行必要的改写（如消除二义性、消除左递归、提取左因子等） ；对自上而下和自下而上的典型分析方法能够熟悉其流程、构建相关的分析表等4、熟悉语法制导翻译的典型方法（如语法制导定义、翻译方案）及其基本概念（如继承属性、综合属性等） ，掌握 S 属性和 L 属性定义，并理解在语法分析框架中实现翻译的方法和过程5、能够利用语法制导翻译的理论指导中间代码生成，对三地址代码有基本了解，熟悉对典型语句的翻译处理、理解类型检查的原则和典型的静态类型检查的方法6、熟悉运行时环境、存储组织等的基本概念、熟悉对非局部名字访问的处理方法7、熟悉代码生成的基本概念，对基本块、流图等有充分认识，对简单的优化方法（如 DAG的优化、窥孔优化、寄存器分配、指令调度等）有初步了解6（三）主要参考书目1、英文原版：Compilers Principles, Techniques and ToolsAlfred V、 Aho, Monica S、 Lam, Ravi Sethi, Jeffrey D. Ullman, second edtion,机械工业出版社有影印版2、英文原版的中译本编译原理 ；赵建华、郑滔、戴新宇译，机械工业出版社 2009 年 1月，2015 年 10 月第二次印刷IV操作系统（一） 考试大纲1、操作系统概述（1）计算机基本构成、处理器的内部结构、高速缓冲存储器 CACHE（2）操作系统的概念、演变历程、特性、分类、运行环境、功能（3）系统调用的功能和过程。2、进程进程、进程描述、进程地址空间分布及进程状态转换3、线程、对称多处理 SMP 和微内核（1）线程的概念，定义线程的必要性和可能性；（2）线程的功能特性与实现方式；（3）操作系统的体系结构（微内核与巨内核）及其性能分析。4、处理器调度（1）处理器的三种调度类型；（2）进程调度的各种算法及其特点。（3）多处理器对进程调度的影响（4）实时进程的特点，限期调度和速率单调调度方法。5、并发性（1）并发性问题及相关概念，如临界区、互斥、信号量和管程等；（2）进程互斥、同步和通信的各种算法；（3）死锁的概念、死锁的原因和条件（4）死锁的预防、避免和检测算法。6、存储器管理（1）分区存储管理、覆盖与交换；（2）页式管理及段式管理；（3）段、页式存储管理方法及实现技术；（4）虚存的原理及相关的各种算法和数据结构。7、设备管理和磁盘调度（1）操作系统中输入/输出功能的组织；（2）中断处理；（3）设备驱动程序、设备无关的软件接口和 spooling 技术；（4）缓冲策略；7（5）磁盘调度算法；（6）磁盘阵列。8、文件系统（1）文件系统特点与文件组织方式；（2）文件系统的数据结构；（3）目录的基本性质及其实现方法；（4）磁盘空间的管理。（5）分布式文件系统9、分布式系统（1）分布式处理的特点、类型；（2）机群系统。10、操作系统安全（1）操作系统安全保护目标及相关技术（2）常见操作系统攻击方法的原理和防护（二）考试要求1、了解操作系统所管辖的软、硬件资源；了解操作系统的关键概念，从整体上把握操作系统的特性与功能等概念；建立操作系统的资源管理和应用接口的职能概念。理解系统调用的执行过程。2、掌握进程的本质特征，明确进程的动态特性，理解进程的地址空间分布，熟悉进程状态间转换的原因，建立进程是资源分配单元和一种运行实体的基本理念。3、理解引入线程作为基本运行实体的必要性和可能性；掌握线程各种实现方式及其特点；熟悉 SMP 体系结构、操作系统的体系结构。4、了解批处理、交互式、实时三种调度类型；重点掌握进程调度的各种算法及其适用环了解实时进程的本质，掌握限期调度和速率单调调度方法。5、灵活运用信号量、管程等技术解决互斥合同步问题；理解死锁的概念和产生死锁的充分必要条件；熟练掌握死锁的预防、避免和检测算法；了解处理死锁问题时避免饥饿的方法。6、理解存储管理的功能及存储管理对多道程序设计的支持；掌握段、页式存储管理方法及实现技术；掌握虚存的原理及相关的各种替换算法和数据结构。7、理解输入输出设备及操作系统中输入/输出功能的组织、掌握中断处理、设备驱动程序、设备无关的软件接口和 spooling 等技术，重点掌握各种用于提高性能的缓冲策略和磁盘调度算法；了解可提高性能和可靠性的各种磁盘阵列配置方式。8、理解文件系统特点与文件组织，掌握文件系统的基本数据结构，了解文件、目录的基本性质及其实现方法；重点掌握磁盘空间的管理、文件系统的性能及可靠性、文件系统的安全性及保护机制，分布式文件系统的问题和特点等。9、了解分布式处理的特点、类型；掌握多层体系结构和机群系统的基本概念和特点。10、了解操作系统安全保密性、完整性和可用性的基本概念及保护方法。了解常用的攻击和防御技术的原理。（三）主要参考书目1、 现代操作系统（第三版） Andrew S、 Tanenbaum ， 2008 8编制单位：中国科学院大学编制日期：2018 年 6 月 8 日