1、最新计算机考研大纲解析打印版2012计算机考研大纲解析之数据结构一、线性表 （一）线性表的定义和基本操作（二）线性表的实现 1.顺序存储结构 2.链式存储结构3.线性表的应用二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树 （一）树的基本概念 （二）二叉树 1.二叉树的定义及其主要特性 2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用 1. 二叉排序树2
2、. 平衡二叉树3.哈夫曼（Huffman）树和哈夫曼编码四、图 （一）图的概念 （二）图的存储及基本操作1. 邻接矩阵法 2. 邻接表法（三）图的遍历1. 深度优先搜索2. 广度优先搜索（四）图的基本应用1. 最小（代价）生成树2. 最短路径3. 拓扑排序4. 关键路径五、查找 （一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树及其基本操作、B+树的基本概念 （五) 散列(Hash)表及其查找（六）查找算法的分析及应用六、内部排序 （一）排序的基本概念 （二）插入排序 1. 直接插入排序2. 折半插入排序（三）起泡排序（bubble sort） （四）简单选择排序 （五）希尔排序
3、（shell sort） （六）快速排序（七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）外部排序 *（十一）各种内部排序算法的比较 （十二）内部排序算法的应用 1.线性表: 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 2.栈、队列和数组: 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式
4、存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。 一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。 3、树与二叉树: 二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是
5、一种典型的应用。 在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。 多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。 最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。 4、图: 在数据结构中，图的结构是最复杂的，这里的概念也是最多的。我们要掌握图的基本概念(有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等)。 图的存储及
6、基本操作主要有邻接矩阵法和邻接表法，我们要掌握这有向图和无向图的这2种存储方法，要清楚图的连通和存储方法之间的关系。例如，一个顶点的出度和临界矩阵中1的个数有什么关系，等等。 图的遍历方法有深度优先搜索和广度优先搜索，我们要掌握这2种遍历方法的算法实现。给出一个具体的图，要能知道它的遍历次序。 在数据结构课程中，图的基本应用是最多的，也是最复杂的，我们要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小(代价)生成树、最短路径、拓扑排序、关键路径。在给出的一个具体的图中，我们要会利用已知条件，求出上述应用的结果。 5、查找: 在给定的数据集合中查找某个关键值就是查找，查找的基本方法主要有顺
7、序查找法、折半查找法、B-树、散列(Hash)表及其查找。考的比较多的是折半查找和散列表，我们要掌握它们的基本概念和方法，例如散列表的碰撞如何解决，装载因子的概念等。 另外，我们要掌握各种查找算法的分析及应用，最好能把各种查找在查找成功、查找失败的情况下的最好、平均、最坏的平均查找次数的计算方法搞清楚。 6、内部排序: 根据考试大纲，只考查内部排序。所谓内部排序，就是在内存中进行排序。在这一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、简单选择排序、希尔排序(shell sort)、快速排序、堆排序、二路归并排序(merge sort)、基数排序的基本概念和
8、方法。搞清楚这些排序方法的流程，以及它们之间的区别。 在这个知识点，一个很重要的考查点就是各种内部排序算法的比较，一般的书上都会有这样的一个表格，列出了所有排序在各种情况下(最好、最坏、平均)的时间复杂度和空间复杂度，这个表是需要我们记下来的。当然，如果我们能掌握复杂度的计算方法，自己能推算出来，那就更好了。 最后，就是要掌握内部排序算法的基本应用，以及算法的实现。线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈、队列和数组可以考查的知
9、识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序 列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队 列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行 的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支 持实际问题求解算法的设计，例如用栈解决递归问题，用队
10、列解决图的遍历问题等等。树和二叉树。这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉 树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方 式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计 算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平 衡二叉
11、树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操作 (比如结点数统计、左右子树对换等等)，判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归的算法，线索化后 二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。图。在这一章中需要识记的是图以及基于图的各种定义，存储方式。要熟练掌握图的深度遍历和广度遍历算法，这是用图来解决应用问题时常用的算法基 础。需要掌握基于图的多个算法，能够以手工计算的方式在一个给定的图上执行特定的算法求解问题
12、。常见的应用问题直接给出或经过抽象，会成为下列问题：最小生成树求解(PRIM算法和KRUSKAL算法，两种方法思想都很简单，但要注意不要混淆这两种方法)，拓扑排序问题(这里会用到数组实现的链表，可以注 意一下)，关键路径问题(数据结构的较大难点，要把概念理解透，能做出表格找出关键路径)，最短路径问题(有重要的应用背景，也是贪心法不多的能给出最优 解的典型问题之一)。查找。这一章，需要识记关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念念及在各种查找算法中的 计算方法和计算结果，特别是一些典型结构的ASL值，B-树的概念和基本操作冲突解决方法的选择和冲突
13、处理过程的描述，B+树的概念(新增考点)，特别要 注意B-树和B+树概念的对比，以及Hash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法，特别要注意顺序查找、二分查找的适用条件(比如 链表上用二分查找就不合适)和算法复杂度。排序。2012最新的大纲将去年的内部排序范围扩展为排序，排序既是重点，又是难点。排序算法众多，今年大纲还加上了外部排序，总共10种，各 种不同算法还有相应的一些概念定义需要记住。选择题常见的问题包括：给定数列要求给出某种特定排序方法运行一轮后的排序结果，或者给出初始数列和一轮排序 结果要求选择采用的排序算法，给定时间、空间复杂度要求以及数列特征要求选择合适的排序
14、算法等等。如果排序这一考点出现在综合应用题中则常与数组结合来考 查。2012年考研计算机操作系统大纲解析一、操作系统概述（一）操作系统的概念、特征、功能和提供的服务（二）操作系统的发展与分类 (三) 操作系统的运行环境 1. 内核态与用户态 2. 中断、异常 3. 系统调用(四) 操作系统体系结构二、进程管理（一）进程与线程1. 进程概念2. 进程的状态与转换3. 进程控制4. 进程组织5. 进程通信：共享存储系统；消息传递系统；管道通信。6. 线程概念与多线程模型（二）处理机调度1. 调度的基本概念2. 调度时机、切换与过程3. 调度的基本准则4. 调度方式5. 典型调度算法：先来先服务调度
15、算法；短作业(短进程、短线程)优先调度算法；时间片轮转度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。（三）进程同步与互斥1. 进程同步的基本概念2. 实现临界区互斥的基本方法：软件实现方法；硬件实现方法。3. 信号量4. 管程5. 经典同步问题：生产者-消费者问题；读者-写者问题；哲学家进餐问题。 （四）死锁 1. 死锁的概念 2. 死锁处理策略 3. 死锁预防 4. 死锁避免：系统安全状态；银行家算法。5. 死锁检测和解除三、内存管理 （一）内存管理基础1. 内存管理概念：程序装入与链接；逻辑地址与物理地址空间；内存保护。2. 交换与覆盖3. 连续分配管理方式 4. 非
16、连续分配管理方式：分页管理方式；分段管理方式；段页式管理方式。 （二）虚拟内存管理1. 虚拟内存基本概念2. 请求分页管理方式3. 页面置换算法：最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK）。4. 页面分配策略5. 抖动：抖动现象； 6. 工作集。 6. 请求分段管理方式7. 请求段页式管理方式四、文件管理 （一）文件系统基础1. 文件概念2. 文件结构：顺序文件；索引文件；索引顺序文件。3. 目录结构：文件控制块和索引节点；单级目录结构和两级目录结构；树形目录结构；图形目录结构。4. 文件共享5. 文件保护（二）文件系统实现
17、 1. 文件系统层次结构2. 目录实现 3. 文件实现（三）磁盘组织与管理 1. 磁盘的结构 2. 磁盘调度算法3. 磁盘的管理五、输入输出（I/O）管理* （一) I/O管理概述 1. I/O控制方式2. I/O软件层次结构(二) I/O核心子系统 1. I/O调度概念2. 高速缓存与缓冲区3. 设备分配与回收4. 假脱机技术(SPOOLing)操作系统学科是围绕操作系统的功能来展开的，包括进程管理、存储管理、文件管理、作业管理和设备管理(输入/输出管理)。 1、操作系统概述: 在操作系统的基础知识方面，我们要掌握操作系统的概念、特征、功能和提供的服务，操作系统的发展与分类，以及操作系统的运
18、行环境。 2、进程管理: 进程管理是操作系统的核心功能，也是考试的重点，这部分的考试分数将在10分以上。对进程管理知识点的细化，可以包括4个考点，分别是进程与线程的基本概念、处理机调度、进程同步与互斥、死锁。 在进程与线程的基本概念方面，我们要掌握进程的概念、进程的状态与转换(三态模型、五态模型)、进程控制、进程组织、进程通信(共享存储系统、消息传递系统、管道通信)，以及线程的概念与多线程模型。 在处理机调度方面，我们要掌握调度的基本概念、调度时机、切换与过程、调度的基本准则、调度方式，特别是要掌握几种典型的调度算法，包括先来先服务调度算法、短作业(短任务、短进程、短线程)优先调度算法、时间片
19、轮转度算法、优先级调度算法、高响应比优先调度算法、多级反馈队列调度算法等，搞清楚这些算法的基本原理和调度过程，以及每种调度算法的优点和缺点。 进程同步与互斥是进程管理的重点，也是操作系统学科的一个难点。这个考点的知识，一般都会出现在考试试题中。具体包括进程同步的基本概念、实现临界区互斥的基本方法(包括软件实现方法、硬件实现方法)、信号量(PV操作)、管程、经典同步问题(包括生产者-消费者问题、读者-写者问题、哲学家进餐问题等)。我们一定要掌握PV操作的概念、流程，以及PV操作在同步问题、互斥问题中的应用。 如果进程调度算法不合适，或者进程同步与互斥处理机制不好，就会产生死锁。死锁是进程之间“互
20、相等待、互相不放弃”的一种僵持状态，我们要理解死锁的概念，知道死锁发生的根本原因和有关条件，死锁处理策略和死锁的预防、死锁的避免(系统安全状态、银行家算法)，以及死锁检测和解除。在这个知识点中，特别是要掌握死锁产生的条件，因为知道了条件，就知道了解决办法。比较常考的内容是银行家算法。 3、内存管理: 这部分内容与计算机组成原理考试模块有一定的交叉和重叠，主要考查内存管理基础和虚拟内存管理。 在内存管理基础知识点，需要我们掌握内存管理的基本概念(程序装入与链接、逻辑地址与物理地址空间、内存保护)、交换与覆盖，以及连续分配管理方式(单一连续分配、分区分配)和非连续分配管理方式(分页管理方式、分段管
21、理方式、段页式管理方式)。理解这些管理方式的基本原理和工作过程，搞清楚它们之间的关系和区别，以及各种方式的优点和缺点。 在虚拟内存管理方面，我们要掌握虚拟内存的基本概念、请求分页管理方式和页面置换算法，包括最佳置换算法(OPT)、先进先出置换算法(FIFO)、最近最少使用置换算法(LRU)、时钟置换算法(CLOCK)。理解这些算法的基本工作原理和置换过程，所产生的缺页次数(缺页率)。与置换算法相关的是页面分配策略，包括最佳适应、最差适应等策略。不管采用哪一种策略和算法，都要防止抖动现象的发生。与抖动相关的概念是工作集和程序局部性原理，这也是要掌握的内容。 另外，还要掌握请求分段管理方式、请求段
22、页式管理方式的基本概念、工作流程。 4、文件管理 首先，我们要掌握文件系统的基础知识，包括文件的概念、文件结构(顺序文件、索引文件、索引顺序文件)、目录结构(文件控制块和索引节点、单级目录结构和两级目录结构、树形目录结构、图形目录结构)、文件共享(共享动机、共享方式、共享语义)、文件保护(访问类型、访问控制)。 其次，我们要掌握操作系统中文件系统的实现，包括文件系统层次结构、目录实现和文件实现。 最后，我们要掌握磁盘的组织与管理，包括磁盘的结构、磁盘调度算法(先来先服务调度算法FCFS、最短寻道时间优先调度算法SSTF、扫描算法SCAN等)、磁盘的管理等内容。 5、输入输出管理 输入输出管理(
23、I/O)的功能是进行设备的分配和实现真正的I/O操作，在这个知识点，我们要理解和熟悉I/O设备、I/O管理目标、I/O管理功能、I/O应用接口和I/O控制方式等基本概念，要掌握I/O核心子系统的基本功能和工作原理，包括I/O调度的概念、高速缓存与缓冲区、设备分配与回收、假脱机技术(SPOOLing)、出错处理等。这部分知识与计算机组成原理的考查知识点有一定的交叉。总的来看，操作系统部分2012年新大纲变动有增有减，总的来看依然是偏的，不重要的或者简单的知识点删除，而重要的难度较大的知识点有所增 加。甚至在考查目标上都有所删减和增加，特别增加了掌握操作系统进程、内存、文件和I/O管理的策略、算法
24、、机制以及相互关系部分。操作系统和计算机组成原理的部分内容是相关的，甚至是重叠的，例如虚拟存储器、输入输出等，大家在复习时，可对照计算机组成原理一起复习，加深理解。操作系统课程是理论性和实践性都很强的课程，概念多、抽象、涉及面广，复习时，我们应该注意哪些重点呢?第一：操作系统概述 操作系统概述这部分内容不会出现大题。一般是以基本原理和概念的形式为主，属于识记形式的题目。重点是操作系统的定义、操作系统的特征和主要功能等。第二：进程管理 进程管理是考试的热门，考点即可以出现在选择题中，也可出在综合应用题中。重点是要掌握进程的基本特征、进程的状态及其相互转换的条件和过程;进程与线程 的区别和联系;进
25、程通信的基本类型;调度的基本概念、时机、切换过程，掌握各种调度算法及其环境，并会用算法进行计算;进程同步相关概念、同步互斥机制; 死锁的定义、死锁产生的四个必要条件、熟练掌握死锁的预防、死锁的避免，死锁解除的原理与方法。从往年试题来看，在综合应用题中，考了一道信号量机制的应用题，这部分是操作系统科目的难点，也是考试的热点。第三：内存管理 内存管理这部分内容也要作为重点进行复习，这部分内容的考查方式也很灵活。建议重点复习内存连续分配算法、非连续分配管理方式、虚拟内存请求分页的基本原理，页面置换算法等。虚拟内存这部分内容可以结合计算机组成原理科目中虚拟存储器来进行复习。第四：文件管理 文件管理这部
26、分内容的重点是文件的几种逻辑物理结构，目录的管理和磁盘管理，重点掌握磁盘管理各种调度算法的基本原理及其应用。第五：输入/输出管理 输入/输出管理这部分重点掌握四种输入/输出控制方式特点及相互比较、中断处理、SPOOLing技术，提高性能的缓冲策略等。跨考辅导班能提供很多模拟试题，由学员在线测试，老师进行批改和试题讲解。这些模拟试题是老师根据考试大纲来命题的，符合考试要求，对考生进行考前练习，起到十分关键的作用。因为研究生考试基本上是靠我们自己学习，那么学习完之后，如何知道学习的效果呢?这就需要多参加测试，特别是跨考教育的四轮五阶教学法，会定期 安排测试，对我们有很大的帮助。计算机考研专业课中有
27、80分的单项选择题，这是与软考的考法一致的，从考试大纲来看，所考查的知识点比软考要窄一些，要求 也低一些。因此，在没有看到真实试题之前，建议考生拿软考上午试题(操作系统部分)作为模拟测试。2011年大纲2012年大纲变动考查目标二、数据的表示和运算无变化1.了解操作系统在计算机系统中的作用、地位、发展和特点。删除2.理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。1.掌握操作系统的基本概念、基本原理和基本功能，掌握操作系统设计方法与实现技术。理解变掌握，加上基本功能，难度加大2.掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系新增加3.能够运用所学的操作系统
28、原理、方法与技术分析问题和解决问题。3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题。并能利用C语言描述相关算法增加能利用C语言描述相关算法一、操作系统概述一、操作系统概述无变化(三)操作系统的运行环境(三)操作系统的运行环境无变化1.内核态与用户态2.中断、异常增加详细的小点3.系统调用增加详细的小点(四)操作系统体系结构新增加三、内存管理三、内存管理无变化(二)虚拟内存管理(二)虚拟内存管理无变化4.页面分配策略4.页面分配策略无变化5.抖动抖动现象，工作集5.工作集1小点变2小点6.抖动6.请求分段管理方式删除7.请求段页式管理方式删除五、输入输出(I/O)管理五、输入输出(
29、I/O)管理无变化(一)I/O管理概述(一)I/O管理概述无变化1.I/O设备删除2.I/O管理目标删除3.I/O管理功能删除4.I/O应用接口删除5.I/O控制方式1.I/O控制方式无变化6.I/O设备2.I/O软件层次结构新增加(二)I/O核心子系统(二)I/O核心子系统无变化1.I/O调度概念1.I/O调度概念无变化2.高速缓存与缓冲区2.高速缓存与缓冲区无变化3.设备分配与回收3.设备分配与回收无变化4.假脱机技术(spooling)4.假脱机技术(spooling)无变化5.出错处理删除2012计算机考研大纲解析之计算机组成原理2012年计算机统考大纲已经公布，我们第一时间来解析一下
30、计算机统考大纲的第二部分计算机组成原理及相关知识点：计算机组成原理部分也占了45分，是分值最高的两部分之一，可见计算机专业研究生选拔对计算机组成原理课程的要求之重。一、计算机系统概述（一）计算机发展历程（二）计算机系统层次结构1. 计算机硬件的基本组成2. 计算机软件的分类3. 计算机的工作过程（三） 计算机性能指标吞吐量、响应时间；CPU时钟周期、主频、CPI、CPU执行时间；MIPS、FLOPS。二、数据的表示和运算（一）数制与编码1. 进位计数制及其相互转换2. 真值和机器数3. BCD码4. 字符与字符串5. 校验码（二）定点数的表示和运算1. 定点数的表示2.无符号数的表示；有符号数
31、的表示。2. 定点数的运算；定点数的位移运算；原码定点数的加/减运算；补码定点数的加/减运算；定点数的乘/除运算；溢出概念和判别方法。（三）浮点数的表示和运算1. 浮点数的表示浮点数的表示范围；IEEE754标准2. 浮点数的加/减运算（四）算术逻辑单元ALU1. 串行加法器和并行加法器2. 算术逻辑单元ALU的功能和机构三、存储器层次结构（一）存储器的分类 （二）存储器的层次化结构 （三）半导体随机存取存储器1. SRAM存储器的工作原理2. DRAM存储器的工作原理 3.只读存储器4.Flash存储器*（五）主存储器与CPU的连接 （六）双口RAM和多模块存储器 （七）高速缓冲存储器（Cache）1. 程序访问的局部 2. Cache的基本工作原理3
