操作系统与数据结构复习大纲

《操作系统与数据结构复习大纲》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、操作系统与数据结构复习大纲注：操作系统、数据结构各占50%操作系统：【考査目标】1、了解操作系统在计算机系统屮的作用、地位、发展和特点。2、理解操作系统的基木概念、原理，掌握操作系统设计方法与实现技术。3、能够运用所学的操作系统原理、方法与技术分析问题和解决问题。一、操作系统概述1、操作系统的概念、作用和彫响2、操作系统的形成和发展3、操作系统的基本功能、特征、运行环境和提供的服务4、操作系统的类型5、了解DOS、UNIX、LINUX、WINDOWS>OS/2类型及特点二、进程管理（一）进程与线

2、程1、进程的概念2、进程的状态及其转换3、进程的构成4、进程状态的扩充-挂起状态5、进程控制原语及其应用6、线程概念与多线程模型（二）进程的同步和互斥1、同步和互斥的基本概念2、实现临界区耳斥的锁操作法3、信号量及其应用4、经典同步问题5、牛产者-消费者问题；读者-写者问题；哲学家进餐问题（三）进程调度（四）死锁1、死锁的概念2、死锁处理策略3、死锁预防4、死锁避免5、系统安全状态：银行家算法。6、死锁检测和解除三、作业与进程调度1、作业的概念2、调度的基本概念3、调度的层次、作业调度和进程调度

3、4、用户与操作系统的接口5、调度时机、切换与过程6、调度的基本准则7、典熨调度算法8、先來先服务调度算法：短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。四、存储器管理（一）内存管理基础1、存储器管理的基本任务2、逻辑地址与物理地址空间3、重定位4、程序装入与链接（二）连续分配管理方式1、单-•连续分配2、固定分区3、可变分区（三）覆盖与交换技术（1川）虚拟存储器管理1、虚拟内存的基木概念2、分页存储管理3、页面置换算

4、法:OPT、FIFO、LRU、LFU4、页面抖动5、分段存储管理6、段页式存储管理五、设备管理（一）设备管理概述1、设备的分类2、设备管理的目标和任务3、I/O应用接口4、I/O控制方式（二）设备分配与处理1、设备分配方法与过程2、缓冲区技术3、虚拟设备和SPOOL系统4、I/O处理过程六、文件管理1、文件及文件系统2、文件的纟［I织形式和结构3、文件冃录4、辅存空间的管理5、文件的可靠性和安全性6、文件的AFT的作用7、文件基木操作的实现七、UNIX简介1、UNIX的特点2、UNIX进程的构成

5、3、UNIX进程的状态及其转换数据结构：第一章绪论［目的与要求］:深刻理解数据结构的概念，掌握数据结构的要素；掌握数据兀素的逻辑结构；掌握数据兀素的存贮结构；理解数据结构与算法的联系；了解算法的效率及存贮空间的度量。［本章主要内容］:1.1什么是数据结构1.2基木概念和术语1.3数据结构的发展简史及它在计算机科学中所处的地位1.4算法的描述和算法分析1.4.1算法的描述1.4.2算法设计的耍求1.4.3算法效率的度址1.4.4算法的存储空间需求［本章重点］:1.基木概念和术语2.算法的描述和算法

6、分析［本章难点］:1.算法的描述和算法分析第二章线性表［目的与要求］:掌握线性表顺序存贮和链式存贮的特点；理解线性表的操作规律；了解线性表的应用。［本章主要内容］:2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表链式存储结构2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加［本章重点］:1.几种常用链表的特点和运算2.从不同角度比较线性表在顺序和链式两种存储结构的优缺点［本章难点］:1.儿种常用链表的特点和运算第三章栈和队列［目的与要求］:掌握栈、队列

7、的定义及其相关数据结构的概念；了解栈的特征；掌握栈的表示和实现方法；了解栈空间的共用和栈的应用；掌握队列的实现、链队列及其操作；理解顺序队列的假溢出；掌握循环队列的操作特点。［本章主要内容］:3.1.2栈的表示和实现3.2表达式求值3.4队列1.4.1抽彖数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.4.3循环队列——队列的顺序表示和实现［本章重点］:1.顺序栈和链栈上的进栈和退栈的算法2.在顺序队列上实现入队和出队的算法［本章难点］:1.顺序栈和链栈上的进栈和退栈的算法2.在链

8、队列上实现入队和出队的算法第四章树和叉树［目的与要求］:掌握树、二叉树的圧义；掌握树、二叉树的存贮方法；掌握二叉树的先序、屮序和示序遍历观则及算法；了解线索二叉树及其操作；掌握树和二叉树传换的唯一性、森林与二义树的传换规则;学握哈夫曼树及哈夫曼编码。［本章主要内容］:4.1树的定义和基本操作4.2二叉树2.2.1二叉树的操作4.2.2二叉树的性质4.2.3二叉树的存储结构4.3遍历二叉树和线索二叉树4.3.2线索二叉树4.4树和森林4.4.1树的存储结构4.4.2森林与二叉树的转换4.4.3树的