中科院研究生院硕士研究生入学考试

《中科院研究生院硕士研究生入学考试》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学院大学硕士研究生入学考试《计算机学科综合(非专业)》考试大纲本《计算机学科综合(非专业)》考试大纲适用于中国科学院大学非计算机科学与技术一级学科下各专业的硕士研究生入学考试。《计算机学科综合(非专业)》主要内容包括数据结构、操作系统和计算机网络三大部分。要求考生对计算机科学与技术及相关学科的基本概念有较深入、系统的理解；掌握各种数据结构的定义和实现算法；掌握操作系统和计算机网络所涉及的关键内容，并具有综合运用所学知识分析问题和解决问题的能力。一、考试内容数据结构1、绪论（1）数据结构的基本概念，数据的逻辑结构、存储结构。（2）算法的定义、算法的基本特性以

2、及算法分析的基本概念。2、线性表（1）线性关系、线性表的定义，线性表的基本操作。（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。3、堆栈与队列（1）堆栈与队列的基本概念、基本操作。（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理。（3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。4、串（1）串的基本概念、串的基本操作和存储结构。（2）串的模式匹配算法和改进的KMP算法5、数组和广义表（1）数

3、组的概念，以及表示和实现（2）矩阵（对称矩阵和稀疏矩阵）的压缩存储（3）广义表的基本概念6、树与二叉树（1）树的定义和性质（2）二叉树的概念、性质和实现（3）遍历二叉树和线索二叉树（4）树和森林（5）赫夫曼树及其应用（6）回溯法与树的遍历（7）树的计数7、图（1）图的定义，基本概念，图的分类，常用名词术语。（2）图的邻接矩阵存储方法、邻接表存储方法的构造原理。（3）图的遍历操作。（4）图的连通性、最小生成树（5）最短路径的计算（6）AOV网与拓扑排序。8、查找（1）静态查找表：顺序表、有序表、静态树表以及索引表的查找。（2）动态查找表：二叉排序树和平衡二叉树，以

4、及B树和B+树的基本概念和操作。（3）哈希表：基本概念和构造方法，冲突处理方法和查询及性能分析。9、内排序（1）排序的基本概念，排序方法的分类。（2）插入排序法(含折半插入排序法)、选择排序法、快速排序法、堆排序法、归并排序、基数排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度简单分析。操作系统1、操作系统概述（1）计算机基本构成、处理器的内部结构、高速缓冲存储器CACHE；（2）操作系统的概念、演变历程、特性、分类、运行环境、功能（3）存储器的层次结构2、、进程进程、进程描述及进程状态转换3、线程、对称多处理SMP和微内核（1）线程的概念，定

5、义线程的必要性和可能性；（2）线程的功能特性与实现方式；（3）对称多处理SMP体系结构；（4）操作系统的体系结构（微内核与巨内核）及其性能分析。4、并发性（1）并发性问题及相关概念，如临界区、互斥、信号量和管程等；（2）进程互斥、同步和通信的各种算法；（3）死锁的概念、死锁的原因和条件（4）死锁的预防、避免和检测算法。5、存储器管理（1）分区存储管理、覆盖与交换；（2）页式管理及段式管理；（3）段、页式存储管理方法及实现技术；（4）虚存的原理及相关的各种算法和数据结构。6、单处理器调度（1）处理器的三种调度类型；（2）进程调度的各种算法及其特点。7、多处理器调度

6、和实时调度（1）多处理器对进程调度的影响（2）多处理器环境下的进程和线程调度算法；（3）实时进程的特点；（4）限期调度和速率单调调度方法。8、设备管理和磁盘调度（1）操作系统中输入/输出功能的组织；（2）中断处理；（3）设备驱动程序、设备无关的软件接口和spooling技术；（4）缓冲策略；（5）磁盘调度算法；（6）磁盘阵列。9、文件系统（1）文件系统特点与文件组织方式；（2）文件系统的数据结构；（3）目录的基本性质及其实现方法；（4）磁盘空间的管理。10、分布式系统（1）分布式处理的特点、类型；（2）多层体系结构、中间件技术；（3）机群系统；（4）分布式进程管

7、理相关的操作系统设计问题。计算机网络1、绪论　　（1）计算机网络的概念、分类、标准、组成与功能　　（2）计算机网络分层结构，协议、接口、服务等概念，ISO/OSI模型和TCP/IP模型2、物理层　　（1）通信信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念，电路交换、报文交换与分组交换，数据报与虚电路　　（2）双绞线，物理层接口的特性，中继器，集线器3、数据链路层　　（1）数据链路层的功能，组帧，差错控制（检错与纠错编码）  （2）流量控制、可靠传输与滑轮窗口机制，停止-等待协议，后退N帧协议(GBN)，选择重传协议(SR)　　（3）CSMA/CA协议、

8、令牌传递协议　　（4）局