《考研统考计算机基础班讲义.docx》由会员分享，可在线阅读，更多相关《考研统考计算机基础班讲义.docx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构【考查目标】1 .理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2 .掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3 .能够选择合适的数据结构和方法进行问题求解。-线性表大纲要求：（一）线性表的定义和基本操作（-）线性表的实现1 .顺序存储结构2 .链式存储结构3 .线性表的应用知识点：1 .深刻理解数据结构的概念，掌握数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作“运算”。2 .时间复杂度和空间复杂度的定义，常用计算语句频度来估算算法的时间复杂度。3 .线性表的逻辑结构，是指线性表的数据元素间存在
2、着线性关系。主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。在顺序存储结构中，元素存储的先后位置反映出这种逻辑关系，而在链式存储结构中，是靠指针来反映这种逻辑关系的。4 .顺序存储结构用向量（一维数组）表示，给定下标，可以存取相应元素，属于随机存取的存储结构。5 .线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。掌握顺序表上实现插入、删除、定位等运算的算法。6 .尽管“只要知道某结点的指针就可以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。要理解头指针、头结点、首元结点和元素结点的差别。头结点是在
3、插入、删除等操作时，为了算法的统一而设立的（若无头结点,则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。对链表（不包括循环链表）的任何操作，均要从头结点开始，头结点的指针具有标记作用，故头指针往往被称为链表的名字，如链表head是指链表头结点的指针是head。理解循环链表中设置尾指针而不设置头指针的好处。链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素或删除某元素，必须知道该元素的前驱结点的指针。7 .链表是本部分学习的重点和难点。重点掌握以下几种常用链表的特点和运算：单链表、循环链表、双向链表、双向循环链表的生成、插入、删除、遍历以及链表的分解和归并等操作
4、。并能够设计出实现线性表其它运算的算法。8 .从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点，即其各自适用的场合。二栈、队列和数组大纲要求：（-）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储知识点：1 .栈、队列的定义及其相关数据结构的概念，包括：顺序栈、链栈、循环队列、链队列等。栈与队列存取数据（请注意包括：存和取两部分）的特点。2 .掌握顺序栈和链栈上的进栈和退栈的算法，并弄清栈空和栈满的条件。注意因栈在一端操作，故通常链栈不设头结点。3 .如何将中缀表达式转换成前缀、后缀表达式，了解对
5、两种表达式求值的方法。4 .栈与递归的关系。用递归解决的几类问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是递归的。掌握典型问题的算法以及将递归算法转换为非递归算法，如 n!阶乘问题，fib数列问题，hanoi问题。了解在数值表达式的求解、括号的配对等问题中应用栈的工作原理。5 .掌握在链队列上实现入队和出队的算法。注意对仅剩一个元素的链队列删除元素时的处理（令队尾指针指向队头）。还需特别注意仅设尾指针的循环链队列的各种操作的实现。6 .循环队列队空及队满的条件。队空定义为队头指针等于队尾指针，队满则可用牺牲一个单元或是设标记的方法，这里特别注意取模运算。掌握循环队列中入队与出队算
6、法。7 .在后续章节中多处有栈和队列的应用，如二叉树遍历的递归和非递归算法、图的深度优先遍历等都用到栈，而树的层次遍历、图的广度优先遍历等则用到队列。这些方面的应用应重点掌握。8 .数组在机器（内存）级上采用顺序存储结构。掌握数组（主要是二维）在以行序为主和列序为主的存储中的地址计算方法。9 .特殊矩阵（对称矩阵、对角矩阵、三角矩阵）在压缩存储是的下标变换公式。三树与二叉树大纲要求：（一）树的概念（二）二叉树1 .二叉树的定义及其主要特征2 .二叉树的顺序存储结构和链式存储结构3 .二叉树的遍历4 .线索二叉树的基本概念和构造5 .二叉排序树6 .平衡二叉树（三）树、森林1 .树的存储结构2
7、.森林与二叉树的转换3 .树和森林的遍历（四）树的应用1 .等价类问题2 .哈夫曼（Huffman）树和哈夫曼编码知识点：1.二叉树的概念、性质（1）掌握树和二叉树的定义。（2）理解二叉树与普通双分支树的区别。二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的。即二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。（3）满二叉树和完全二叉树的概念。（4）重点掌握二叉树的五个性质及证明方法，并把这种方法推广到K叉树。普通二叉树的五
8、个性质：第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+l的性质，n 个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（序号i结点的左孩子为：2*i,右孩子为：2*i+l） o2 .掌握二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合，以及二叉树的顺序存储结构和二叉链表存储结构的相互转换的算法。3 .熟练掌握二叉树的先序，中序和后序遍历算法以及按层次遍历二叉树的先序、中序和后序三种遍历算法，划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握这三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算
9、法。4 .遍历是基础，重点掌握在三种基本遍历算法的基础上实现二叉树的其它算法如求二叉树叶子结点总数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点等等。5 .线索二叉树的引出，是为避免如二叉树遍历时的递归求解。递归虽然形式上比较好理解,但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险。二叉树线索化的实质是建立结点在相应序列中与其前驱和后继之间的直接联系。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树
10、中指定结点的前驱或后继结点）。6 .二叉排序树的中序遍历结果是一个递增的有序序列。二叉排序树的形态取决于元素的输入顺序，二叉排序树在最差情况下形成单支树。熟练掌握其建立、查找、插入和删除算法，以及判断某棵二叉树是否二叉排序树这一问题的递归与非递归算法。7 .平衡二叉树是二叉排序树的优化，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。掌握平衡二叉树的四种调整算法。8 .树与森林的遍历，只有两种遍历算法：先根与后根（对于森林而言称作：先序与中序遍历）。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树使用二
11、叉链表分别存放它的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。掌握树、森林和二叉树间的相互转换。9 .简单掌握等价类的生成算法。10 .哈夫曼树为了解决特定问题引出的特殊二义树结构,它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的，一般来说，哈夫曼树的形态不是唯一的。理解哈夫曼编码的基本原理，掌握基于哈夫曼树生成哈夫曼编码的方法。大纲要求：（-）图的概念（二）图的存储及基本操作1 .邻接矩阵法2 .邻接表法（三）图的遍历1 .深度优先搜索2 .广度优先搜索（四）图的基本应用及其复杂度分析1 .最小（代价）生成树2 .
12、最短路径3 .拓扑排序4 .关键路径知识点：1 .图的基本概念，包括：图的定义和特点、无向图、有向图、入度、出度、完全图、生成树、路径长度、回路、（强）连通图、（强）连通分量等概念。掌握与这些概念相联系的相关计算题。在基本概念中，完全图、连通分量、生成树和邻接点是重点。2 .图的存储形式。图是复杂的数据结构，有顺序和链式两种存储结构：数组表示法（重点是邻接矩阵），邻接表与逆邻接表，这两种存储结构对无向图和有向图均使用。3 .熟练掌握图的两种遍历算法：深度遍历和广度遍历。深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。掌
13、握图的两种遍历算法的应用，图章的算法设计题常常是基于这两种基本的遍历算法而设计的。例如，在（强）连通图中，主过程一次调用深（广）度优先遍历过程（DFS/BFS）,即可遍历全部顶点，故可以用此方法求出连通分量的个数，要会画出遍历中形成的深（广）度优先生成树和生成森林。又如，“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就用到了广度遍历和深度遍历算法。4 .最小生成树的概念。连通图的最小生成树通常是不唯一的，但最小生成树边上的权值之和是唯一的。掌握最小生成树的构造方法：PRIM算法和KRUSKAL算法，根据这两种算法思想用图示法表示出求给定网的一棵最小生成树的过程。5 .
14、拓扑排序是在有向图上对入度（先、后）为零的顶点的种排序，通常结果不唯一。拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。后一种排序出来的结果是“逆拓扑有序”的。用拓扑排序和深度优先遍历都可判断图是否存在环路。6 .关键路径问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间的含义及求解方法，三是最晚时间的含义及求解方法。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都一经求出来之后才能进行。熟练掌
15、握求解的过程和步骤。关键路径问题是工程进度控制的重要方法,具有很强的实用性。理解“减少关键活动时间可以缩短工期”是指该活动为所有关键路径所共有，且减少到尚未改变关键路径的前提下有效。7 .最短路径问题也是为图一章的难点问题。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。解决第一个问题用 DIJSKTRA算法，解决第二个问题用FLOYD算法，注意区分。掌握这两个算法，并能手工熟练模拟。掌握用求最短路径问题来解决的应用问题（如旅游景点及旅游路线的选择问题）。五查找大纲要求：（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树（五）散列
16、（Hash）表及其查找（六）查找算法的分析及应用知识点:1 .线性表上的查找。对于顺序表采用顺序查找方法，逐个比较，顺序表设置了监视哨使查找效率大大提高。对于有序顺序表采用折半查找法，其判定树是唯一的。对于索引结构,采用索引顺序查找算法，此算法综合了上述两者的优点，既能较快速地查找，又能适应动态变化的要求。注意这三种查找的平均查找长度。掌握顺序查找和折半查找算法的实现，其中，折半查找还要特别注意适用条件以及其递归实现方法。2 . B-树是多路平衡外查找树，用于文件系统。要能手工模拟B-树插入和删除关键字使B-树增高和降低，会推导B-树的平均查找长度。3 .散列表的查找算法。基本思想是：根据当前
17、待查找数据的特征，以记录关键字为自变量,设计一个散列函数，该函数对关键字进行转换后，其解释结果为待查的地址。熟练掌握散列函数的设计，冲突解决方法的选择及冲突处理过程的描述。散列表中关键字的查找只能用散列函数来计算，不能顺序查找，也不能折半查找。在闭散列法解决冲突的情况下，元素删除也只能做标记，不能物理地删除。理想情况下，散列表的平均查找长度是0（1）,优于其他查找方法。六内部排序大纲要求：（一）排序的基本概念（二）插入排序1 .直接插入排序2 .折半插入排序（三）起泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（八）二路归并排
18、序（merge sort）（九）基数排序（十）各种内部排序算法的比较（十一）内部排序算法的应用知识点：1 .插入类排序的基本思想是假定待排序文件第一个记录有序，然后从第二个记录起，依次插入到排好序的有序子文件中，直到整个文件有序。从减少比较次数和移动次数进行了各种改进，在插入排序中有直接插入、折半插入、希尔排序。直接插入是依次寻找，折半插入是折半寻找，希尔排序是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。2 .交换类排序基于相邻记录比较，若逆序则进行交换。起泡排序和快速排序是交换排序的例子，在起换排序的基础上改进得到快速排序，快速排序是目前最好的内部排序法。快速
19、排序的思想：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。3 .选择类排序，可以分为：简单选择排序、堆排序。这两种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序较为重要，其最差性能比快速排序的最差性能好。4 .归并排序是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并，算法思想比较简单。5 .基数排序
20、，是一种特殊的排序方法，分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，在排序的过程中，只要按照基数排序的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。6 .掌握各种排序方法的算法思想以及算法实现。掌握在最好、最坏、平均情况下各种排序方法的性能分析。归并排序、基数排序及时间复杂度为0（/）的排序是稳定排序，而希尔排序、快速排序、堆排序等时间性能好的排序方法是不稳定排序（但特别注意，简单选择排序是不稳定排序）。操作系统【考查目标】1 .了解操作系统在计算机系统中的作用、地位、发展和特点。2 .理
21、解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。3 .能够运用所学的操作系统原理、方法与技术分析问题和解决问题。-操作系统概述大纲要求：（一）操作系统的概念、特征、功能和提供的服务（二）操作系统的发展与分类（三）操作系统的运行环境知识点：1.了解操作系统在计算机系统中的作用，操作系统的设计目标。牢固掌握操作系统的定义。记忆要点：操作系统是什么是核心系统软件；操作系统管什么控制和管理系统内各种资源：操作系统有何用扩充硬件功能，方便用户使用。了解操作系统所处的地位：是裸机之上的第一层软件，是建立其他所有软件的基础。2 .牢固掌握操作系统的五大主要功能：存储帮管理、处理机管理、设备管理、
22、文件管理、用户接口管理。3 .记住操作系统的基本特征：并发、共享、虚拟和异步性。操作系统性能衡量标准。4 .关于多道程序设计，掌握什么是多道程序设计；多道程序设计利用系统与外围设备的并行工作能力，提高系统的利用率；多道程序设计与单道程序设计的比较。5 .记住并理解操作系统的主要类型：批处理系统、分时系统、实时系统、个人机系统、网络系统和分布式系统。理解批处理系统、分时系统和实时系统的设计目标及特点，其中， UNIX系统是著名的分时系统。区分网络操作系统与分布式操作系统的特点。几种操作系统特点的比较及各自的使用场合。6 .了解现代操作系统为用户提供的三种使用界面：命令界面、图形界面和系统调用界面
23、。了解计算机系统的层次结构。7 .理解以下相关概念：CPU状态（管态和目态）及状态转换、存储系统、中断系统、I/O 结构、通道、直接存储器存取（DMA）技术、缓冲技术、时钟。二进程管理大纲要求：（一）进程与线程1 .进程概念2 .进程的状态与转换3 .进程控制4 .进程组织5 .进程通信共享存储系统；消息传递系统；管道通信。6 .线程概念与多线程模型（二）处理机调度1 .调度的基本概念2 .调度时机、切换与过程3 .调度的基本准则4 .调度方式5 .典型调度算法先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队
24、列调度算法。（三）进程同步1 .进程同步的基本概念2 .实现临界区互斥的基本方法软件实现方法；硬件实现方法.3 .信号量4 .管程5 .经典同步问题生产者-消费者问题：读者-写者问题；哲学家进餐问题。（四）死锁1.2.3.4.死锁的概念死锁处理策略死锁预防死锁避免系统安全状态；银行家算法。6 .死锁检测和解除知识点:1 .牢固掌握进程的概念，深入理解进程最基本的特征是动态性和并发性，掌握进程与程序的主要区别。理解进程的生存过程。理解进程的一般组成，应深入理解进程控制块的作用。每个进程有惟一的进程控制块。掌握进程的基本状态，在什么条件下发生状态转换？2 .掌握进程临界资源和临界区的概念，理解进入
25、临界区的原则。掌握进程同步与互斥的概念。理解信号量概念，P、V操作执行的动作。3 .能用信号量和PV操作实现简单的进程互斥或同步。解决此类问题的一般方式：（1）根据问题给出的条件，确定进程有几个或几类；（2）确定进程间的制约关系是互斥，还是同步；（3）各相关进程间通过什么信号量实现彼此的制约，标明信号量的含义和初值。（4）用P、V操作写出相应的代码段。（5）验证代码的正确性：设以不同的次序运行各进程，是否能保证问题的圆满解决。4 .进程通信的含义，它与P、V操作的比较，理解进程通信机制共享内存、消息传递、管道文件。5 .理解线程的概念与基本状态，线程与进程的比较。6 .掌握作业调度和进程调度的
26、功能。理解作业调度与进程调度的关系，理解作业的几种状态。7 .掌握常用调度算法的评价指标：吞吐量、周转时间、平均周转时间、带权周转时间和平均带权周转时间。8 .掌握基本调度算法的实现思想，包括先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法：时间片轮转调度算法；优先级调度算法：高响应比优先调度算法；多级反馈队列调度算法。并能进行评价指标的计算，如可以利用图表形式列出各作业或进程的有关时间值，如到达时间、运行时间、结束时间等，利用评价公式计算出各指标的值。9 .掌握死锁的概念和产生死锁的根本原因。理解产生死锁的必要条件：互斥条件、不可抢占条件、占有并等待资源条件、循环等待条件。1
27、0 .记住解决死锁的一般方法，掌握死锁的预防和死锁的避免二者的基本思想。11 .掌握死锁的预防策略中资源有序分配策略。12 .理解进程安全序列的概念，理解死锁与安全序列的关系。13 .理解银行家算法。了解资源分配图。14 .了解死锁的检测及解除的思想。三内存管理大纲要求：（-）内存管理基础1 .内存管理概念程序装入与链接；逻辑地址与物理地址空间；内存保护。2 .交换与覆盖3 .连续分配管理方式单一连续分配；分区分配。4 .非连续分配管理方式分页管理方式；分段管理方式；段页式管理方式。（-）虚拟内存管理1 .虚拟内存基本概念2 .请求分页管理方式3 .页面置换算法最佳置换算法（OPT）;先进先出
28、置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK）。4 .页面分配策略5 .抖动抖动现象；工作集。6 .请求分段管理方式7 .请求段页式管理方式知识点：1 .存储管理的基本目的一是充分发挥内存的利用率，二是为用户使用存储器提供方便。比较完善的内存管理系统，应包括四个方面的功能：内存分配、地址重定位、内存保护、内存扩充。2 .理解覆盖技术和交换技术。3 .存储分配是设法解决多道程序之间划分主存的空间问题。存储分配方式一般有三种：（1）直接方式。程序员在编制程序时，或编译程序对源程序编译时，所用的是实际存储地址。（2）静态分配方式。不由程序员在编程时指定实际存储地址，
29、而是在装配程序把一个或一组目标模块进行链接装入时确定它们在主存中的相应位置。一旦程序装入内存，将不允许它在存储空间中移动。（3）动态分配方式。作业在存储空间中的位置是在装入时确定的，但在运行过程中允许它在存储空间中移动，并且允许作业临时申请附加的存储空间。4 .地址重定位。地址变换的目的既是为了方便用户编程，也是内存分配的需要。为了实现静态或动态存储分配，必须采用地址重定位技术。所谓地址重定位，就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程，即将地址空间给出的逻辑地址映射到内存的物理地址。地址重定位有静态重定位和动态重定位两种方式。5 .耍重点理解虚拟存储器的有关概念。扩
30、充内存的目的是为了增强系统的处理能力和方便用户。虚拟存储技术是实现内存扩充的主要手段。实现虚拟存储器的关键是硬件能提供快速有效的地址变换机构，软件采用相应的算法。6 .理解分区存储管理的基本思想。熟练应用可变分区存储管理的分配算法：最先适应、最优适应、最坏适应算法。7 .理解分页存储管理技术的实现原理，掌握页表的作用。重点要掌握分页存储管理的地址变换方法及过程。8 .请求分页存储管理，重点掌握先进先出法（FIFO）、最佳置换法（OPT）和最近最少使用置换法（LRU）的基本思想和实现方法。重点掌握请求分页存储管理系统中缺页中断次数和缺页中断率的计算方法。9 .内零头（或内碎片）。分页存储管理方式
31、无须移动信息而能较好地解决分区存储方式造成的存储器“碎片”问题，但依然存在“内碎片”现象。“内碎片”是指由于分配给作业的页面是整数块，而一个作业的地址空间不一定是页的整数倍，因而最后一页可能不满，这最后一页中的空闲区称为内碎片。“内碎片”的多少与页面大小有关，平均而言,“内碎片”为半页大小。10 .理解分段存储管理技术的实现思想，采用段式存储管理的地址转换过程。理解段式存储管理的各项优点。理解分页和分段管理的主要区别。11 .掌握段页式存储管理的基本思想、实现方法和地址变换过程。四文件管理大纲要求：（-）文件系统基础1 .文件概念2 .文件结构顺序文件；索引文件；索引顺序文件。3 .目录结构文
32、件控制块和索引节点；单级目录结构和两级目录结构；树形目录结构；图形目录结构。4 .文件共享共享动机；共享方式；共享语义。5 .文件保护访问类型；访问控制。（二）文件系统实现1 .文件系统层次结构2 .目录实现3 .文件实现（三）磁盘组织与管理1 .磁盘的结构2 .磁盘调度算法3 .磁盘的管理知识点：1.牢固掌握文件、文件系统概念以及文件分类。2 .了解文件系统的功能。文件系统的功能包括：文件的目录管理、文件存储空间的分配与回收，文件名与文件存储空间的映射，提供文件共享以及保护与保密措施，实现各种文件操作。3 .文件的存储介质，磁带结构、磁盘结构以及磁盘地址、块的概念。4 .掌握文件的结构分为逻
33、辑结构和物理结构。文件的逻辑结构是用户从使用角度组织的文件，-一般有两种形式：有结构的记录式文件和无结构流式文件。文件的物理结构是指文件在存储介质上的组织方式，一般有三种类型：连续文件、链接文件和索引文件。其中，文件的物理结构是重点。5 .掌握目录的基本组织方式。文件目录是文件系统的关键数据结构，用来组织文件卷上的文件以及对文件进行检索。文件目录的组织有三种形式：简单的文件目录、二级目录和多级结构。其中树型目录是使用最广泛的目录结构，它能有效地提高对目录的检索速度，允许文件重名，便于实现文件共享。在文件目录表中的每个目录项是一个文件控制块（也称为文件说明）。一个文件控制块包括如下信息：文件的标
34、识信息、文件的结构信息、文件存取控制信息、文件的管理信息。理解路径名（绝对路径名和相对路径名）和文件链接的概念。6 .文件存储空间的管理是实现连续空间或非连续空间的分配与回收。三种基本的管理方法是：位示图、空闲块表、空闲块链。7 .文件的存取控制。文件的保护保密与文件的共享是同一个问题的两个方面，保护保密的实质是有条件的共享。常用的文件的存取控制方法有：存取控制矩阵、口令和密码技术。存取控制矩阵方式集保护与保密于一体，口令和密码则是用于保密。8 .磁盘的地址是三维的（柱面号、磁头号、扇区号）。掌握执行一次信息传输的时间寻找时间+延迟时间+传送时间。熟练掌握常用的移臂调度算法的应用先来先服务、最
35、短寻找时间优先、电梯调度、单向扫描算法。五输入输出（I/O）管理大纲要求：（一）I/O管理概述1. I/O设备2. I/O管理目标3. I/O管理功能4. I/O应用接口5. I/O控制方式（二）I/O核心子系统1 . I/O调度概念2 .高速缓存与缓冲区3 .设备分配与回收4 .假脱机技术（SPOOLing）5 .出错处理知识点：1 .了解设备的分类。从存储介质物理特性角度看，分为存储设备（块设备），输入/输出设备（字符设备）。从使用角度看，有独占设备、共享设备、虚拟设备。2 .设备管理的基本任务是必须按照用户的要求来控制I/O设备工作，完成用户所希望的 I/O操作，以减轻用户编制程序的负担
36、。其另一个重要任务是按照一个的算法把某I/O 设备分配给对该设备提出请求的进程，以保证系统有条不紊地工作。如何充分而有效地使用设备，尽可能提高它们的并行操作程度是设备管理的第三个任务。掌握设备管理功能是进行设备的分配、实现真正的I/O操作、实现其他功能。3 .通道技术。通道的引入是为了建立独立的I/O操作系统。通道不仅使数据传送独立于 CPU,而且希望I/O操作的组织、管理和结束等尽量独立，以保证CPU有更多的时间去从事计算。通道有自己的指令（称为通道命令），并可构成通道程序。设置通道后，就可把原来由CPU完成的I/O操作交给通道完成。根据信息交换的方式，可将通道分为三种类型：字节多路通道、数
37、据选择通道、数组多路通道。4 .设备的分配和设备处理程序。逻辑设备与物理设备的概念，设备管理所用的数据结构，设备分配的原则，常用的设备分配算法，设备分配的过程和设备处理程序的功能。5 .理解使用缓冲技术的目的和缓冲区的设置方式。引入缓冲的原因主要有三点：（1）使CPU和I/O设备之间速度不匹配的情况得到改善；（2）提高CPU、通道和I/O设备的并行操作程度；（3）减少中断CPU的次数，放宽CPU对中断的响应时间。根据缓冲的数量及组织形式，缓冲分为：单缓冲、双缓冲、多缓冲和缓冲池。6 .理解虚拟设备的实现原理SPOOLing系统的功能和实现思想。SPOOLing技术的核心思想使利用可共享的外存设备来模拟独享设备的操作，是一台独享设备变成若干虚拟设备。SPOOLing系统主要由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。文都祝你考研成功