硕士研究生入学考试部分专业课复习大纲
《计算机基础(Ⅰ)》
参考书目：
1《现代操作系统》陈向群、马洪兵译 机械工业出版社2005
2《编译原理》，侯文永，电子工业出版社，2002
3《数据结构与算法（C＋＋）》窦延平、张同珍、姜丽红、陈玉泉编著，上海交通大学出版社
复习大纲：
一. 操作系统
复习大纲：
1.引论：
设置操作系统的目的：操作系统分类、功能、特性和性能；UNIX的发展历史、操作系统的发展历史 、特点和体系结构。
2、进程管理
程序和进程；并发与并行；进程的表示及状态；进程模型、线程模型；进程的创建、终止和父、子进程同步；进程虚地址空间管理。进程调度；进程间通信；UNIX操作系统中的进程管理。
3、中断和陷入
中断及其一般处理过程；UNIX系统中的中断处理；操作系统的程序设计界面和陷入处理；系统调用处理。
4、存储管理
存储管理的早期技术；虚拟存储器的基本思想、组织和管理；UNIX存储管理。
5、信号和跟踪
信号和跟踪机构的基本工作原理。
6、设备管理
设备管理概要；UNIX设备管理的主要数据结构；缓冲存储区管理；块设备驱动；块设备读、写技术。
7、文件管理系统
概述；文件系统的用户界面；目录结构；文件的结构和存取方法文件存储空间管理；文件的共享、保护保密和文件系统的完整性，UNIX文件系统的主要结构和算法：UNIX文件系统的实施。
8、进程间通信与死锁
进程间通信的经典问题；UNIX 进程间通信的机制；死锁。
9、系统初起和再生
系统初起的一般过程。
10、shell、命令控制语言及其解释程序
UNIX中基本的shell命令； UNIX命令程序设计语言Shell的基本特征；Shell解释程序的基本结构和工作原理。
二．编译原理
引论、文法和语言、词法分析、语法分析、语法制导翻译、运行时的存储空间管理、中间代码的生成、代码优化、代码生成、并行编译基础。
（一）引论
1、编译程序是一种特定的翻译程序
2、编译程序的结构
3、编译程序的生成
4、编译程序的学习
（二）文法和语言
1、基本概念
2、分析树和二义行
3、形式语言分类
（三）词法分析
1、构造一个简单的词法分析器
2、正规表达式与正规集
3、有限自动机
4、正规式与有限自动机
5、词法分析的自动生成
（四）语法分析
1、语法分析概述
2、递归下降分析方法
3、非递归的预测分析方法
4、算符优先分析法
5、LR分析器
6、二义文法的应用
7、分析表的自动生成
（五）语法制导翻译
1．语法制导定义
2．L—属性定义
3．属性的自下而上计算
4．属性的自上而下计算
（六）运行时的存储空间管理
1．变量及存储分配
2．静态分布
3．栈式分配
4．堆分配
5．参数传递
6．符号表
（七）中间代码的生成
1、中间语言
2、说明语言
3、赋值语句
4、布尔表达式
5、控制转移中的回填方法
6、过程调用
（八）代码优化
1、优化概念
2、局部优化
3、控制流分析及循环的查找
4、数据流分析
5、循环优化
（九）代码生成
1、目标代码
2、一个简单的代码生成器
3、存储器分配
4、窥孔优化
5、由DAG生成代码
（十）并行编译基础
1、并行计算机及其编译系统
2、基本概念
3、并行编译概述
三．数据结构
1、 数据结构与算法的基本概念
算法、算法正确性、复杂性
算法的时间与空间复杂性级别
抽象数据类型、数据结构和表示、实现
2、线性表、栈和队列
顺序分配、链接分配的表示及实现
各种链表：单链、双链、多链、循环链表等
栈、队列、双向队列等
表达式计算
3、 串的存储及模式匹配算法
存储、基本运算、模式匹配算法等
4、 树及二叉树
遍历、存储、基本概念、性质、树的应有举例
二叉树：遍历、线索树、分类二叉树、树与二叉树的转换、最优二叉树
最优叶子查找树及HUFFUMAN算法
堆及优先队列的实现等等
各种树操作特性、性质、实现
5、图的各种操作及算法分析比较
遍历：DFS、BFS、PFS、方法以及存储、基本概念、性质
连通分量的求法
最小生成树、最短路径
拓扑排序的求法及实现等
各种图的算法的分析及比较、算法复杂性的级别等
6、查找技术
顺序查找、有序表的查找、索引顺序查找、二分查找法等
排序二叉树及其实现
平衡二叉排序树的实现、插入、删除、查找实现及时间代价等
HASHING技术
查找速度的分析及比较、算法复杂性的级别等等
7、排序技术
各种排序方法：插入排序、快速排序、堆及选择排序、合并排序、基数排序法
最好、最坏、平均排序的时间复杂性分析
《计算机基础(Ⅱ)》
参考书目：
1《计算机组成与系统结构》胡越明编 电子工业出版社2002
2《数据结构与算法（C＋＋）》窦延平、张同珍、姜丽红、陈玉泉编著，上海交通大学出版社
复习大纲：
一．计算机组成与系统结构
计算机系统概论、数据编码和数据运算、存储系统、指令系统、控制器、系统总线、输入输出系统、流水技术、并行计算机的互联网络、并行计算机系统。
1、 计算机系统概论
1） 计算机系统的基本构成
2） 计算机系统结构及其分类
3） 计算机的性能评价
4） 计算机系统的可靠性
2、数据编码和数据运算
1）数据编码
2）定点数加减法运算
3）定点数乘除法运算
4）逻辑运算
5）浮点数运算
6）运算器的组成和结构
3、存储系统
1）存储器芯片的工作原理
2）存储器的基本构成
3）访存局部性原理和高速缓存
4）虚拟存储器与存储保护
4、指令系统
1）指令格式与指令编码
2）寻址方式
3）数据类型及其存储方式
4）指令格式与指令集
5）指令系统分类
5、控制器
1）中央处理单元的功能和组成
2）指令的执行过程
3）硬布线控制器
4）微程序控制
5）门阵列控制器
6、系统总线
1）总线的基本概念
2）总线控制
3）总线接口
7、输入输出系统
1）输入输出设备的类型
2）程序查询方式
3）中断方式
4）DMA传递方式
5）通道方式
8、流水技术
1）流水线工作原理
2）标量指令流水技术
3）向量流水处理技术
9、并行计算机的互联网络
1）静态互联网络
2）单级动态互联网络
3）多级动态互联网络
10、并行计算机系统
1）阵列并行计算机系统
2）多处理机系统
3）分布式计算机系统
二．数据结构
1、 数据结构与算法的基本概念
算法、算法正确性、复杂性
算法的时间与空间复杂性级别
抽象数据类型、数据结构和表示、实现
2、线性表、栈和队列
顺序分配、链接分配的表示及实现
各种链表：单链、双链、多链、循环链表等
栈、队列、双向队列等
表达式计算
3、 串的存储及模式匹配算法
存储、基本运算、模式匹配算法等
4、 树及二叉树
遍历、存储、基本概念、性质、树的应有举例
二叉树：遍历、线索树、分类二叉树、树与二叉树的转换、最优二叉树
最优叶子查找树及HUFFUMAN算法
堆及优先队列的实现等等
各种树操作特性、性质、实现
5、图的各种操作及算法分析比较
遍历：DFS、BFS、PFS、方法以及存储、基本概念、性质
连通分量的求法
最小生成树、最短路径
拓扑排序的求法及实现等
各种图的算法的分析及比较、算法复杂性的级别等
6、查找技术
顺序查找、有序表的查找、索引顺序查找、二分查找法等
排序二叉树及其实现
平衡二叉排序树的实现、插入、删除、查找实现及时间代价等
HASHING技术
查找速度的分析及比较、算法复杂性的级别等等
7、排序技术
各种排序方法：插入排序、快速排序、堆及选择排序、合并排序、基数排序法
最好、最坏、平均排序的时间复杂性分析
