中国科学院大学硕士研究生入学考试《计算机学科综合 ( 专业 ) 》考试大纲一、考试形式闭卷，笔试，考试时间 180 分钟，总分 150 分二、试卷结构题型，如：概念题（填空、选择、判断、简答），应用题（计算、画图、分析、设计）等三、考试科目数据结构、计算机组成原理、操作系统、计算机网络四门课程，每门课程各占 25%四、数据结构（一）考试大纲1、绪论（1）数据结构的基本概念，数据的逻辑结构、存储结构2）算法的定义、算法的基本特性以及算法分析的基本概念2、线性表（1）线性表的定义、基本操作2）线性表的实现及应用，包括顺序存储结构、链式存储结构 ( 单链表、 循环链表和双向链表) 的构造原理， 在两种存储结构上对线性表实施的主要的操作 ( 三种链表的建立、 插入和删除、检索等 ) 的算法设计与实现3、堆栈与队列（ 1）堆栈与队列的基本概念、基本操作 2）堆栈与队列的顺序存储结构、链式存储结构的构造原理 3）在不同存储结构的基础上对堆栈、队列实施基本操作（插入与删除等）对应的算法设计与实现4、数组和广义表（ 1）数组的概念、多维数组的实现 2）对称矩阵和稀疏矩阵的压缩存储 3）广义表的基本概念。
5、树与二叉树（ 1）树的概念和性质 2）二叉树的概念、性质和实现 3）二叉树的顺序存储结构和链式存储结构 4）遍历二叉树 5）线索二叉树的 基本概念和构造 6）树和森林的 存储结构、遍历 7）二叉排序树 8）平衡二叉树 9）哈夫曼 (Huffman) 树和哈夫曼编码6、图（ 1）图的基本概念 2）图的存储，包括 邻接矩阵法、邻接表法 3）图的遍历操作，包括 深度优先搜索、广度优先搜索 4）最小生成树，最短路径，关键路径、拓扑排序算法的原理与实现7、文件及查找（ 1）数据文件的基本概念、基本操作 2）顺序查找法、分块查找法、折半查找方法的原理与实现 3） B 树及其基本操作、 B+树的基本概念 4）散列 (Hash) 表 5）字符串模式匹配的算法原理与实现8、排序（ 1）排序的基本概念 2）直接插入排序、折半插入排序、气泡排序、简单选择排序、快速排序、堆排序、二路归并排序、基数排序、外部排序算法的原理、复杂度 3）排序算法的应用二）考试要求1. 掌握数据结构的基本概念、基本原理和基本方法2. 掌握数据的逻辑结构、 存储结构及基本操作的实现， 能够对算法进行基本的时间复杂度与空间复杂度的分析。
3. 能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C 或C++语言设计与实现算法的能力1、数据结构（C 语言版）.（三）主要参考书目严蔚敏，吴伟民 编著，北京：清华大学出版社，2007 年五、计算机组成原理（一）考试大纲1、计算机系统概论（ 1）计算机发展历史（ 2）计算机系统层次结构计算机系统的基本组成，计算机硬件的基本组成，计算机软件和硬件的关系，计算机的工作过程（ 3）计算机性能指标2、数据的表示和运算(1) 数制与编码进位计数制及其相互转换，真值和机器数，BCD码，字符与字符串，校验码(2) 定点数的表示和运算定点数的表示，定点数的运算 （定点数的位移运算，原码定点数的加减运算，补码定点数的加 / 减运算，定点数的乘除运算，定点数运算器组成）(3) 浮点数的表示和运算浮点数的表示， IEEE754 标准，浮点数的加 / 减运算，浮点运算器(4) 算术逻辑单元 ALU串行加法器和并行加法器，算术逻辑单元 ALU的功能和结构3、存储器系统(1) 存储器概述(2) 存储器的层次化结构(3) 半导体随机存取存储器SRAM 存储器， DRAM存储器，只读存储器， Flash 存储器(4) 主存储器与 CPU的连接(5) 双口 RAM和多模块存储器(6) 高速缓冲存储器 (Cache)Cache 的基本工作原理， Cache 和主存之间的映射方式， Cache 中主存块的替换算法， Cache 写策略(7) 虚拟存储器虚拟存储器的基本概念，页式虚拟存储器，段式虚拟存储器，段页式虚拟存储器4、指令系统(1) 指令格式指令的基本格式，定长操作码指令格式，扩展操作码指令格式(2) 操作数类型(3) 指令的寻址方式有效地址的概念，数据寻址和指令寻址，常见寻址方式(4) CISC 和 RISC的基本概念5、中央处理器 (CPU)(1) CPU 的功能和组成(2) 指令执行过程(3) 数据通路的功能和基本结构(4) 控制器的功能和工作原理硬布线控制器，微程序控制器(5) 指令流水线指令流水线的基本概念，指令流水线的基本实现，超标量和动态流水线的基本概念(6) RISC CPU6、总线系统(1) 总线概述总线的基本概念，总线结构形态，总线的组成及性能指标(2) 总线仲裁集中仲裁方式，分布仲裁方式(3) 总线操作和定时同步定时方式，异步定时方式(4) 总线标准7、输入输出 (I/O) 系统(1) I/O 系统基本概念(2) 外部设备输入设备：键盘、鼠标，输出设备：显示器、打印机，外存储器：硬盘存储器、磁盘阵列、光盘存储器(3) I/O 接口 (I/O 控制器 )I/O 接口的功能和基本结构， I/O 端口及其编址(4) I/O 方式程序查询方式，程序中断方式， DMA方式，通道方式（二）考试要求1、 掌握计算机的层次结构及软硬件组成等概念。
2、 掌握计算机中数据的格式、机器数的表示方法和特点，熟练掌握定点加减的运算方法和特点，掌握浮点运算方法和特点3、 掌握存储系统的分类、分级结构与主存储器的技术指标，了解 SRAM、DRAM、 EPROM、闪速存储器、相联存储器的工作原理，掌握 Cache 存储器、虚拟存储器的功能和基本工作原理4、 熟练掌握指令格式、指令和数据的寻址方式，理解 RISC 和 CISC 的特点5、 掌握 CPU的功能、基本组成和各个部分的工作流程，了解微程序控制器的基本工作原理，了解微程序控制技术和硬布线控制技术，了解流水 CPU的工作原理及特点6、 掌握总线系统的基本概念和基本技术以及总线仲裁方式的基本工作原理和特点，了解PCI 总线的特点7、 了解 I/O 系统基本概念、 I/O 接口的工作原理和特点，理解程序查询方式、程序中断方式和 DMA方式工作原理三）主要参考书目1、计算机组成原理（第五版） . 白中英，戴志涛编著 ; 科学出版社， 2013 年六、操作系统（一）考试大纲1、操作系统概述（1）计算机基本构成、处理器的内部结构、高速缓冲存储器 CACHE（ 2）操作系统的概念、演变历程、特性、分类、运行环境、功能（ 3）存储器的层次结构2、进程进程、进程描述及进程状态转换3、线程、对称多处理 SMP和微内核（ 1）线程的概念，定义线程的必要性和可能性；（ 2）线程的功能特性与实现方式；（ 3）对称多处理 SMP体系结构；（ 4）操作系统的体系结构（微内核与巨内核）及其性能分析。
4、并发性（ 1）并发性问题及相关概念，如临界区、互斥、信号量和管程等；（ 2）进程互斥、同步和通信的各种算法；（ 3）死锁的概念、死锁的原因和条件（ 4）死锁的预防、避免和检测算法5、存储器管理（ 1）分区存储管理、覆盖与交换；（ 2）页式管理及段式管理；（ 3）段、页式存储管理方法及实现技术；（ 4）虚存的原理及相关的各种算法和数据结构6、单处理器调度（ 1）处理器的三种调度类型；（ 2）进程调度的各种算法及其特点7、多处理器调度和实时调度（ 1）多处理器对进程调度的影响（ 2）多处理器环境下的进程和线程调度算法；（ 3）实时进程的特点；（ 4）限期调度和速率单调调度方法8、设备管理和磁盘调度（ 1）操作系统中输入 / 输出功能的组织；（ 2）中断处理；（ 3）设备驱动程序、设备无关的软件接口和spooling 技术；（ 4）缓冲策略；（ 5）磁盘调度算法；（ 6）磁盘阵列9、文件系统（ 1）文件系统特点与文件组织方式；（ 2）文件系统的数据结构；（ 3）目录的基本性质及其实现方法；（ 4）磁盘空间的管理10、分布式系统（ 1）分布式处理的特点、类型；（ 2）多层体系结构、中间件技术；（ 3）机群系统；（ 4）分布式进程管理相关的操作系统设计问题。
二）考试要求1、 了解操作系统所管辖的软、硬件资源；了解操作系统的关键概念，从整体上把握操作系统的特性与功能等概念；建立操作系统的资源管理和应用接口的职能概念2、 掌握进程的本质特征，明确进程的动态特性，熟悉进程状态间转换的原因，建立进程是资源分配单元和一种运行实体的基本理念3、 理解引入线程作为基本运行实体的必要性和可能性；掌握线程各种实现方式及其特点；熟悉 SMP体系结构、操作系统的体系结构4、 灵活运用信号量、管程等技术解决互斥合同步问题；理解死锁的概念和产生死锁的充分必要条件；熟练掌握死锁的预防、避免和检测算法；了解处理死锁问题时避免饥饿的方法5、 理解存储管理的功能及存储管理对多道程序设计的支持；掌握段、页式存储管理方法及实现技术；掌握虚存的原理及相关的各种算法和数据结构6、 了解长程、 中程和短程三种调度类型； 重点掌握进程调度的各种算法及其适用环境7、 熟悉掌握多处理器环境下进程和线程调度算法，了解实时进程的本质，掌握限期调度和速率单调调度方法8、 理解输入输出设备及操作系统中输入 / 输出功能的组织、 掌握中断处理、 设备驱动程序、设备无关的软件接口和 spooling 等技术， 重点掌握各种用于提高性能的缓冲策略和磁盘调度算法；了解可提高性能和可靠性的各种磁盘阵列配置方式。
9、 理解文件系统特点与文件组织，掌握文件系统的基本数据结构，了解文件、目。