计算机操作系统学习指导的方法

计算机操作系统学习指导的方法

　　操作系统在大纲中的考查目标是了解操作系统在计算机系统中的作用、地位、发展和特点;能够运用所学的操作系统原理、方法与技术分析问题和解决问题。下面是学习啦小编分享给大家的计算机操作系统学习指导的方法的资料，希望大家喜欢!

　　计算机操作系统学习指导的方法

　　▶操作系统概述

　　这一章出现大题的可能性微乎其微。选择题中常出现的点主要是这些：操作系统的定义，引入单道批处理系统、多道批处理、分时系统、实时系统的原因，这些不同阶段的操作系统共的特征如何，相互之间的差别在什么地方;操作系统的基本特征和功能;操作系统的运行环境。

　　▶进程管理

　　进程管理是重点和难点之所在。考点既可以出现在选择题中，又可以出在综合应用题中。按照大纲考点的顺序，诸如进程的概念、基本特征、组成结构，进程与程序的区别与联系，进程的状态及其相互转换的条件及过程，进程间的通信方式，线程的定义以及和进程的区别与联系，调度的基本概念、时机、切换过程和各种调度算法，进程同步相关的概念，实现同步与互斥的机制，信号量和PV操作，管程的基本组成结构和运行过程，死锁的基本概念，死锁产生的四个必要条件，预防、避免、检测和解除死锁的原理与方法，这些点都可以出现在选择题中进行考查。对于综合应用题，重点应该放在PV操作，调度算法和银行家算法。其中，用PV操作实现经典同步问题及其变形是整个操作系统考试的最难点，也是最大的热点。要注意收集往年各校考过的PV操作应用题，把常见的经典题型做会做熟，力求看到题目就能想到相关的解题套路。调度算法的难点在于计算不同调度算法下调度的效率，建议使用时间轴的方法解决相关的调度时间计算问题。银行家算法是系统做资源分配的时候防止发生死锁的一种方法，该算法的难点在于搞清楚各种不同表格的含义，能够看懂并且会做出相关的表格，由表格推出结果。

　　▶内存管理

　　内存管理可考的点也很多，同样也可以有灵活的考查方法。但是相比进程管理来说，这一部分理解起来要相对简单，各种存储管理的算法的思想都是比较直接的，难点在于要记住解决某一个问题的算法有那几个，每一个算法的运行过程是怎么样的。这一章典型的综合应用题出现在：内存的连续分配算法，比如给出内存的申请和释放序列，要求解空闲块列表;非连续分配管理方式下虚拟地址和物理地址的转换，这一点可以和组成原理中的虚拟存储器结合来看;各种页面置换算法产生的缺页数的统计，经典的解法是表格法。至于选择题的点，这一章有比较多，除了上述综合题点都可以简化后出现在选择题中外，还需要注意内存管理的基本概念，如装入、链接、逻辑地址、物理地址、交换、覆盖等等，各种主存分配方式的工作过程以及优缺点对比，虚存的基本概念，抖动、工作集、程序局部性原理以及请求分段请求分页的基本原理。

　　▶文件管理

　　文件管理的重点在于文件的顺序和索引结构。这一部分最重要的应用题点在于索引文件的目录结构，要熟练掌握计算给定目录树结构下单文件的最大文件大小;其次是Unix系统的文件系统空闲块的组织方法——成组链接法，要能说清楚空闲块是怎么分配给申请空闲块的文件的，以及释放的空闲块如何加入到空闲块组里;最后是磁盘的调度算法，要熟练掌握不同调度算法寻道数的计算。文件系统其它需要了解的知识点包括：文件的相关概念，文件的逻辑结构和物理结构，目录结构以及目录管理，文件共享与保护机制，隐式链接和显式链接，空闲块的三种不同组织方法，磁盘的相关概念和参数，磁盘的结构以及调度算法的特点和优缺点对比等。

　　▶输入输出管理

　　这一章是非重点。需要注意的地方是五种I/O控制方式和它们之间的对比，SPOOLING技术以及缓冲策略。可能的选择题点包括I/O设备的分类，I/O管理的目标与功能，应用结构，控制方式，I/O调度的相关概念，设备独立性相关的概念和原理，容错技术等。

　　计算机是一门很博大精深的科目，包含的内容千变万化，能学的东西也数不胜数。操作系统是重要的科目，知识点还是很多的，考生应该牢牢掌握。

　　计算机数据结构核心考点之排序算法

　　各类排序算法的特点及比较

　　几种主要的排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、Shell排序、堆排序等。

　　冒泡排序算法思想：

　　将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。

　　选择排序算法思想：

　　选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。

　　插入排序算法思想：

　　经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。

　　快速排序算法思想：

　　快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：1. 分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。2. 递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。3. 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。

　　归并排序算法思想：

　　分而治之(divide -conquer)。每个递归过程涉及三个步骤：1.分解，把待排序的n个元素的序列分解成两个子序列，每个子序列包括 n/2 个元素。2. 治理，对每个子序列分别调用归并排序MergeSort，进行递归操作。3. 合并，合并两个排好序的子序列,生成排序结果。

　　Shell排序算法思想：

　　算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

　　堆排序算法思想：

　　用大根堆排序的基本思想：1.先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。2.再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key。3. 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。

　　计算机数据结构核心考点之二叉树

　　▶二叉树的遍历

　　遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。

　　二叉树遍历方法可分为两大类，一类是“宽度优先”法，即从根结点开始，由上到下，从左往右一层一层的遍历;另一类是“深度优先法”，即一棵子树一棵子树的遍历。

　　从二叉树结构的整体看，二叉树可以分为根结点，左子树和右子树三部分，只要遍历了这三部分，就算遍历了二叉树。设D表示根结点，L表示左子树，R表示右子树，则DLR的组合共有6种，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左后右，则只有DLR，LDR，LRD三种，分别称为先(前)序法(先根次序法)，中序法(中根次序法，对称法)，后序法(后根次序法)。三种遍历的递归算法如下：

　　1.先序法(DLR)

　　若二叉树为空，则空操作，否则：访问根结点，先序遍历左子树，先序遍历右子树。

　　2.中序法(LDR)

　　若二叉树为空，则空操作，否则：中序遍历左子树，访问根结点，中序遍历右子树.

　　3.后序法(LRD)

　　若二叉树为空，则空操作，否则：后序遍历左子树，后序遍历右子树，访问根结点。

　　▶完全二叉树中有关结点个数计算

　　完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。

　　完全二叉树的叶子数为(n + 1) / 2取下整。

　　▶森林与二叉树之间的转换以及转换过程中结点之间的关系

　　将一棵树转换为二叉树的方法是：

　　1.树中所有相邻兄弟之间加一条连线。

　　2.对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。

　　3.以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。

　　森林转换为二叉树的方法如下：

　　1.将森林中的每棵树转换成相应的二叉树。

　　2.第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。

　　树和森林都可以转换为二叉树，二者的不同是:树转换成的二叉树,其根结点必然无右孩子，而森林转换后的二叉树，其根结点有右孩子。将一棵二叉树还原为树或森林，具体方法如下：

　　1.若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、……都与该结点的双亲结点用线连起来。

　　2.删掉原二叉树中所有双亲结点与右孩子结点的连线。

　　3.整理由1、2两步所得到的树或森林，使之结构层次分明。

　　计算机是一门很博大精深的科目，包含的内容千变万化，能学的东西也数不胜数。二叉树是重要的考点，考生应该牢牢掌握。