中科院研究生院2012年程序设计考研大纲

　　中科院研究生院硕士研究生入学考试《计算机软件基础》考试大纲

　　本《计算机软件》考试大纲适用于中国科学院研究生院计算机科学与技术等专业的硕士研究生入学考试。计算机软件是计算机科学与技术及相关学科的重要基础，主要内容包括数据结构、编译原理和操作系统三大部分。要求考生对计算机科学与技术及相关学科的基本概念有较深入、系统的理解，掌握各种数据结构的定义和实现算法，掌握操作系统和编译原理所涉及的关键内容，并具有综合运用所学知识分析问题和解决问题的能力。

　　一、考试内容

　　数据结构

　　1、绪论

　　(1)数据结构的基本概念，数据的逻辑结构、存储结构。

　　(2)算法的定义、算法的基本特性以及算法分析的基本概念。

　　2、线性表

　　(1)线性关系、线性表的定义，线性表的基本操作。

　　(2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的比较主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。

　　3、堆栈与队列

　　(1)堆栈与队列的基本概念、基本操作。

　　(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理。

　　(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。

　　4、串

　　(1)串的基本概念、串的基本操作和存储结构。

　　(2)串的模式匹配算法和改进的KMP算法

　　5、数组和广义表

　　(1)数组的概念、多维数组的实现

　　(2)对称矩阵和稀疏矩阵的压缩存储

　　(3)广义表的基本概念

　　6、树与二叉树

　　(1)树的定义和性质

　　(2)二叉树的概念、性质和实现

　　(3)遍历二叉树和线索二叉树

　　(4)树和森林

　　(5)赫夫曼树及其应用

　　(6)树的计数

　　7、图

　　(1)图的定义，基本概念，图的分类，常用名词术语。

　　(2)图的邻接矩阵存储方法、邻接表存储方法的构造原理。

　　(3)图的遍历操作。

　　(4)比较小生成树，比较短路径，AOV网与拓扑排序。

　　8、文件及查找

　　(1)数据文件的基本概念和基本术语，数据文件的基本操作。

　　(2)顺序文件、索引文件、散列(Hash)文件。

　　(3)顺序文件的顺序查找方法、排序连续顺序文件的折半查找方法以及其他文件的基本查找方法。

　　9、内排序

　　(1)排序的基本概念，排序方法的分类。

　　(2)插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度简单分析。

　　操作系统

　　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、引论

　　(1)编译器的基本概念

　　(2)编译阶段和编译器伙伴

　　2、词法分析

　　(1)词法分析器

　　(2)正规式

　　(3)有限自动机和扫描器生成器

　　3、语法分析

　　(1)上下文无关文法

　　(2)各种语法分析技术，如自上而下分析和自下而上分析，LR分析器