新祥旭考研：十年专注考研一对一辅导！ 

考试内容包括：操作系统和数据结构

一、操作系统

1、操作系统引论

（1）设计操作系统的目标及操作系统的作用。

（2）操作系统的基本特征和操作系统的主要功能。

2、进程的描述与控制

（1）进程的概念、进程的特征及操作系统中引入进程的原因。

（2）进程与程序的区别。

（3）进程控制：进程的三种基本状态及引起进程状态转换的事件。

（4）进程同步：使用信号量机制实现进程互斥、描述前趋图。

（5）经典进程的同步问题：生产者-消费者、哲学家进餐、读者-写者问题。

3、处理机调度与死锁

（1）高级、中级及初级调度的功能。

（2）调度算法：先来先服务、短作业/进程优先、高优先权优先、高响应比优先及多级反馈队列调度算法的原理及应用。当调度算法应用于进程调度时，需要考虑系统是否采用抢占式的调度方式。

（3）死锁的定义及死锁产生的必要条件。

（4）预防死锁的方法及具体措施。

（5）避免死锁：掌握银行家算法的基本思想，并能够应用银行家算法判定是否满足某进程的资源请求，从而避免系统进入不安全状态。

4、存储器管理

（1）连续分配存储管理方式：重点掌握动态分区分配方式。

（2）分页存储管理方式：实现的基本原理及将给定的逻辑地址转换成相应的物理地址。

（3）分段存储管理方式：实现的基本原理及将给定的逻辑地址转换成相应的物理地址。

5、虚拟存储器

（1）请求分页存储管理方式：实现的基本原理及将给定的逻辑地址转换成相应的物理地址。

（2）页面置换算法：最佳置换、先进先出、最近最久未使用、简单的Clock、改进型Clock等置换算法实现的基本原理及应用。

6、输入输出系统

（1）Spooling系统的组成、特点及假脱机打印机系统的实现

（2）磁盘存储器的性能和调度：掌握先来先服务、最短寻道时间优先、扫描算法及循环扫描算法的原理与应用。

7、文件管理

（1）文件系统的层次结构

（2）文件系统中使用打开和关闭文件操作的目的

（3）文件的逻辑结构

（4）文件目录

8、磁盘存储器的管理

（1）外存的组织方式：掌握链接组织方式及索引组织方式

（2）文件存储空间的管理：掌握位示图法和成组链接法。

二、数据结构

1、绪论

（1）基本概念和术语

（2）数据结构和数据类型的区别

（3）抽象数据类型的表示和实现

（4）算法的相关概念

（5）时间复杂度和空间复杂度的概念和分析

2、线性表  

（1）线性表的类型定义

（2）顺序表，主要包括：顺序表的特点、顺序表的存储结构的定义、顺序表的常见操作、顺序表的合并、利用顺序表解决简单的应用问题。

（3）链表，主要包括：链表的定义、链表的存储结构的定义、链表的常见操作、链表的合并、顺序表和链表的比较、利用链表解决简单的应用问题。

3、栈和队列

（1）栈，主要包括：栈的定义、栈的存储结构、栈的基本操作、栈的应用。

（2）栈与递归，主要包括：递归的定义、递归算法、递归的应用。

（3）队列，主要包括：队列的定义、队列的存储结构、队列的常见操作。

4、树

（1）树的定义和术语。

（2） 二叉树，主要包括：二叉树的定义、二叉树的性质、 二叉树的遍历、二叉树的建立和应用。

（3）树和森林，主要包括：树的存储结构、树和森林与二叉树之间转换、树和森林的遍历、树和森林与二叉树之间转换。

（4）赫夫曼树，主要包括：赫夫曼树的定义、赫夫曼算法、赫夫曼树编码、赫夫曼树应用。

5、图

（1）图的定义和基本概念

（2）图的存储，主要包括：数组表示法、邻接表、图的存储结构的对比。

（3）图的常见操作，主要包括：图的建立、度的计算、深度优先遍历、广度优先遍历等。

（4）图的连通性问题，主要包括：用Prim求最小生成树、用Kruskal求最小生成树。

（5）有向无环图，主要包括：拓扑排序算法、关键路径。

（6）最短路径，主要包括：最短路径定义和算法。

6、查找

（1）静态查找，主要包括：相关概念、顺序查找、二分查找。

（2）动态查找，主要包括：二叉排序树、B树。

（3）哈希查找，主要包括：哈希表定义、哈希表的构造、哈希查找的分析。

7、排序

（1）排序的定义与相关概念。

（2）插入排序，主要包括：直接插入排序、希尔排序。

（3）交换排序，主要包括：起泡排序、快速排序。

（4）选择排序，主要包括：简单选择排序、树形选择排序、堆排序。

（5）归并排序

①初试参考书目
《数据结构（C语言版）》，严蔚敏，清华大学出版社　　

《计算机操作系统》，汤小丹，西安电子科技大学出版社

　　②复试：面试
　　复试科目：计算机专业相关知识
　　参考书目：
　　《C语言程序设计》（第四版），谭浩强，清华大学出版社
　　《数据结构（C语言版）》，严蔚敏，清华大学出版社
　　《计算机操作系统》，汤小丹，西安电子科技大学出版社

　　③同等学力加试：笔试
　　加试科目：①离散数学②微机原理
　　参考书目：
　《离散数学》，左孝凌等，上海科学技术文献出版社
　《微型计算机技术及应用》（第四版），戴梅萼等，清华大学出版

新祥旭---2018-2019年考研一对一辅导班报名中!   

咨询QQ:3390-4516-33

手机+微信咨询：133-4100-4451（新祥旭岑老师）

机构地址：北京市海淀区苏州街长远天地大厦B1座505