2010年考研北京航空航天大学计算机学科专业基础综合(408)重难点解析

考研全程辅导专家2010年考研北京航空航天大学计算机学科专业基础综合（408）重难点解析跨考专业课特别奉献，为广大考研学子加油助力！1、操作系统今天我们来解析一下计算统考大纲操作系统部分的知识点。操作系统的研发能力很能够体现计算机软件发展的水平，因此操作系统是计算机课程体系里很重要的一门专业核心基础原理课程。在考研大纲里，操作系统占了35分，次于数据结构和组成原理，但高于计算机网络。总的来说，操作系统实际上是四门考察课程里最简单的。除了PV操作这一大难点，基本没有其它特别难的原理或复杂的算法。重要的是区分清楚各个不同的算法，不要混淆。复习参考书推荐国内系统课程的教材或者课内参考书，计算机考研统考大纲也和这本书的目录比较一致，建议大家复习时采用。操作系统在大纲中的考查目标是了解操作系统在计算机系统中的作用、地位、发展和特点；理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术；能够运用所学的操作系统原理、方法与技术分析操作系统最经典的教材，西电汤子瀛版的《操作系统》。很多高校都在使用这本书做操作问题和解决问题。这些和09年大纲相比都没有发生变化。事实上，大纲操作系统部分列出要考查的知识点的变化也很小，只是做了一些微小的调整。操作系统概述这一章出现大题的可能性微乎其微。选择题中常出现的点主要是这些：操作系统的定义，引入单道批处理系统、多道批处理、分时系统、实时系统的原因，这些不同阶段的操作系统共的特征如何，相互之间的差别在什么地方；操作系统的基本特征和功能；操作系统的运行环境。进程管理是重点和难点之所在。考点既可以出现在选择题中，又可以出在综合应用题中。按照大纲考点的顺序，诸如进程的概念、基本特征、组成结构，进程与程序的区别与联系，进程的状态及其相互转换的条件及过程，进程间的通信方式，线程的定义以及和进程的区别与联系，调度的基本概念、时机、切换过程和各种调度算法，进程同步相关的概念，实现同步与互斥的机制，信号量和PV操作，管程的基本组成结构和运行过程，死锁的基本概念，死锁产生的四个必要条件，预防、避免、检测和解除死锁的原理与方法，这些点都可以出现在选择题中进行考查。对于综合应用题，重点应该放在PV操作，调度算法和银行家算法。其中，用PV操作实现经典同步问题及其变形是整个操作系统考试的最难点，也是最大的热点。要注意收集往年各校考过的PV操作应用题，把常见的经典题型做会做熟，力求看到题目就能想到相关的解题套路。调度算法的难点在于计算不同调度算法下调度的效率，建议使用时间轴的方法解决相关的调度时间计算问题。银行家算法是系统做资源分配的时候防止发生死锁的一种方法，该算法的难点在于搞清楚各种不同表格的含义，能够看懂并且会做出相关的表格，由表格推出结果。内存管理可考的点也很多，同样也可以有灵活的考查方法。但是相比进程管理来说，这一部分理解起来要相对简单，各种存储管理的算法的思想都是比较直接的，难点在于要记住解决某一个问题的算法有那几个，每一个算法的运行过程是怎么样的。这一章典型的综合应用题出现在：内存的连续分配算法，比如给出内存的申请和释放序列，要求解空闲块列表；非连续分配管理方式下虚拟地址和物理地址的转换，这一点可以和组成原理中的虚拟存储器结合来看；各种页面置换算法产生的缺页数的统计，经典的解法是表格法。至于选择题的点，这一章有比较多，除了上述综合题点都可以简化后出现在选择题中外，还需要注意内存管理的基本概念，如装入、链接、逻辑地址、物理地址、交换、覆盖等等，各种主存分配方式的工作过程以及优缺点对比，虚存的基本概念，抖动、工作集、程序局部性原理以及请求分段请求分页的基本原理。文件管理的重点在于文件的顺序和索引结构。这一部分最重要的应用题点在于索引文件的目录结构，要熟练掌握计算给定目录树结构下单文件的最大文件大小；其次是Unix系统的文件系统空闲块的组织方法——成组链接法，要能说清楚空闲块是怎么分配给申请空闲块的文件的，以及释放的空闲块如何加入到空闲块组里；最后是磁盘的调度算法，要熟练掌握不同调度算法寻道数的计算。文件系统其它需要了解的知识点包括：文件的相关概念，文件的逻辑结构和物理结构，目录结构以及目录管理，文件共享与保护机制，隐式链接和显式链接，空闲块的三种不同组织方法，磁盘的相关概念和参数，磁盘的结构以及调度优缺点对比等。输出管理这一章是非重点。需要注意的地方是五种I/O控制方式和它们之间的对比，SPOOLING技算法的特点和输入第1页共11页考研全程辅导专家术以及缓冲策略。可能的选择题点包括I/O设备的分类，I/O管理的目标与功能，应用结构，控制方式，I/O调度的相关概念，设备独立性相关的概念和原理，容错技术等。2、数据结构线性表。这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈、队列和数组。可以考查的进栈出栈序列的问题常出现在选择题中。其次，是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，是栈和队列的序顺和链式存储结构，这里一个常考点一章可能的计，例如用栈解决递归问题，用队列解决图的遍历问题等等。树和二叉树。这一章中我们从顺不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用Huffman树），重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及问题。常见的综合应用题：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操作（比如结点数统计、左右子树对换等等），判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。图。在这一章中需要识记的是图以及基于图的各种定义，存储方式。要熟练掌握图的深度遍历和广度遍历算法，图来解决应用问题时常用的算法基础。需要掌握基于图的多个算法，能够以算的方式在一个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过抽象，会成为下：最小生成树求解（PRIM算法和KRUSKAL算法，两种方法思想都很简单，但要注意不要混淆这两种方法），拓扑排序问题（这里会用到数组实现的链表，可以注意一下），关键路径问题（数据结构的较大难点，要把概念理解透，能做出表格找出关键路径），最短路径问题要的应用背景，也是贪心法给出最优解的典型问题序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的（二叉排序树、平衡二叉树和算法设考点包括：满二叉回溯法相关的考点包括这是用手工计列问题（有重不多的能之一）。查找。这一章，需要识记关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，B-树的概念和基本突解决方法的选择和冲突处理过程的描述，B+树的概念（新增考点），特别要注意B-树和B+树概念的操作冲对比，以及Hash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法，特别要注意顺序查找、二分查找的适用条件（比如链表上用二分查找就不合适）和算法复杂度。内部排序。内部排序既是重点，排序算法众多，光大纲上列出的就有9种，各种不同算法还有相应的一些概念定义需要记住。选择题常见的问题包括：不同排序算法的复杂度，给定数列要求给出某种特定排序方法运行一轮后的排序结果，或者给出初始数列和一轮排序结果要求选择采用的排序算法，给定时间、空间复杂度要求以及数列特征要求选择合适的排序算法等等。如果排序这一考点出现在综合应用题中则常与数组结合来考又是难点。第2页共11页考研全程辅导专家查。3、组成原理计算机系统概述一章几乎没有出综合应用题的可能，大部分知识点只要了解就可以了。数据的表示与运算一章可考的点多，但单独出现在综合应用题中的可能性不大。数在机器中的不同表示方法及其相互转换时选择题的一个常考点。存储器层次结构是组成原理这门课的重点，大家在复习这一章的时候要注意Cache-主存-外存的层次结构，对比Cache-主存和虚拟存储器的相关思想、原理和方法。本章是综合应用题常考点，典型的考题包括Cache的三种不同映像方式的相关计算，主存芯片的字扩展和位扩展方案设计以及虚存相关地址转换的内容。第3页共11页考研全程辅导专家指令系统历来都是考试的常考点，这一章相对简单，要拿高分就要确保这章相关考点的分数。第4页共11页考研全程辅导专家中央处理器这一章是重点和难点，组成原理考试几乎必考的章节。总线一章不是考试的重点，需要识记的内容较多，相对的重点在于总线仲裁和定时。第5页共11页考研全程辅导专家输入输出系统也不属于考试的热点。主要是记忆一些概念，知道不同的设备以及一些相关的参数，需要熟练掌握的是硬盘读写过程和一些参数的计算，中断相关的概念和原理，以及DMA方式的原理，相应的硬件结构和工作过程。4、计算机网络计算机网络体系结构。这一章基本上不会出大题，主要是要求考生建立对网络协议栈结构的印象。在这一章需要对各层协议的功能有一个大致的了解，比较重要的是协议、接口和服务的概念，以及带宽、时延、往返时延RTT和时延带宽积的概念和物理意义。物理层。不是考试的热门。这一章更多的是通信学科的内容，重点在于对基本概念的识记，奈奎斯特定理和香定农理的的相关计算，电路交换、报文交换与分组交换的运行机制以及相互之间的比较，数据报和虚电路的运行机制以及相互之间的比较，以及中继器和集线器与交换机的比较。第6页共11页考研全程辅导专家数据链路层。也考试的热点，在这一章中我们要掌握数据链路层的三大功能：组帧、差错控制、流量控制与可靠传输机制，以太网协议与IEEE802.3，介质访问控制协议CSMA/CD、CSMA/CA和ALOHA，数据链路层设备网桥、交换机运行原理。难点在于滑窗机制与三种停等协议、CSMA/CD的二进制指数退避机制，以及交换机帧转发过程和转发表的构建过程。第7页共11页考研全程辅导专家网络层。第8页共11页考研全程辅导专家是计算机网络的重点与热点，这部分可考的内容非常多，需要考生重点把握。这与TCP/IP网络体系结构“EverytingoverIP,IPoverEveryting”的特点是相符合的。本章需要重点的掌握的知识点包括：路由算法（距离-向量路由，链路状态路由）原理及其具体实现（RIP和OSPF），IPv4的数据包结构，头部各字段的含义，