2022年燕山大学数据库与操作系统考研复习大纲 3.pdf

《2022年燕山大学数据库与操作系统考研复习大纲 3.pdf》由会员分享，可在线阅读，更多相关《2022年燕山大学数据库与操作系统考研复习大纲 3.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、注：操作系统、数据结构各占50%操作系统：【考查目标】1、了解操作系统在计算机系统中的作用、地位、发展和特点。2、理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。3、能够运用所学的操作系统原理、方法与技术分析问题和解决问题。一、操作系统概述1、操作系统的概念、作用和影响2、操作系统的形成和发展3、操作系统的基本功能、特征、运行环境和提供的服务4、操作系统的类型5、了解 DOS 、UNIX 、 LINUX、WINDOWS、OS/2 类型及特点二、进程管理（一）进程与线程1、进程的概念2、进程的状态及其转换3、进程的构成4、进程状态的扩充 - 挂起状态5、进程控制原语及其应用6、线程

2、概念与多线程模型（二）进程的同步和互斥1、同步和互斥的基本概念名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 2、实现临界区互斥的锁操作法3、信号量及其应用4、经典同步问题5、生产者 - 消费者问题；读者 - 写者问题；哲学家进餐问题（三）进程调度（四）死锁1、死锁的概念2、死锁处理策略3、死锁预防4、死锁避免5、系统安全状态：银行家算法。6、死锁检测和解除三、作业与进程调度1、作业的概念2、调度的基本概念3、调度的层次、作业

3、调度和进程调度4、用户与操作系统的接口5、调度时机、切换与过程6、调度的基本准则7、典型调度算法8、先来先服务调度算法：短作业（短任务、短进程、短线程）优先调度算法；时间调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 四、存储器管理（一）内存管理基础1、存储器管理的基本任务2、逻辑地址与物理地址空间3、重定位4、程序装入与链接（二）连续分配管理方式1、单一连

4、续分配2、固定分区3、可变分区（三）覆盖与交换技术（四）虚拟存储器管理1、虚拟内存的基本概念2、分页存储管理3、页面置换算法： OPT 、FIFO、LRU 、LFU 4、页面抖动5、分段存储管理6、段页式存储管理五、设备管理（一）设备管理概述1、设备的分类2、设备管理的目标和任务名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 3、I/O 应用接口4、I/O 控制方式（二）设备分配与处理1、设备分配方法与过程2、缓冲区技术3、虚

5、拟设备和 SPOOL 系统4、I/O 处理过程六、文件管理1、文件及文件系统2、文件的组织形式和结构3、文件目录4、辅存空间的管理5、文件的可靠性和安全性6、文件的 AFT的作用7、文件基本操作的实现七、 UNIX简介1、UNIX的特点2、UNIX进程的构成3、UNIX进程的状态及其转换数据结构：第一章绪论名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 目的与要求 ：深刻理解数据结构的概念，掌握数据结构的要素；掌握数据元素的逻

6、辑结构；掌握素的存贮结构；理解数据结构与算法的联系；了解算法的效率及存贮空间的度量。 本章主要内容 ：1.1 什么是数据结构1.2 基本概念和术语1.3 数据结构的发展简史及它在计算机科学中所处的地位1.4 算法的描述和算法分析1.4.1 算法的描述1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间需求 本章重点 ：1基本概念和术语2算法的描述和算法分析 本章难点 ：1算法的描述和算法分析第二章线性表 目的与要求 ：掌握线性表顺序存贮和链式存贮的特点；理解线性表的操作规律；了解线性表的应 本章主要内容 ：2.1 线性表的逻辑结构名师资料总结 - - -精品资料欢迎下

7、载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 2.2 线性表的顺序存储结构2.3 线性表链式存储结构2.3.1 线性链表2.3.2 循环链表2.3.3 双向链表2.4 一元多项式的表示及相加 本章重点 ：1几种常用链表的特点和运算2从不同角度比较线性表在顺序和链式两种存储结构的优缺点 本章难点 ：1几种常用链表的特点和运算第三章栈和队列 目的与要求 ：掌握栈、队列的定义及其相关数据结构的概念；了解栈的特征； 掌握栈的表示和实了解栈空间的共用和栈的应用；掌握队列的

8、实现、链队列及其操作；理解顺序队列出；掌握循环队列的操作特点。 本章主要内容 ：3.1 栈3.1.1 抽象数据类型栈的定义3.1.2 栈的表示和实现3.2 表达式求值3.4 队列名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 3.4.1 抽象数据类型队列的定义3.4.2 链队列队列的链式表示和实现3.4.3 循环队列队列的顺序表示和实现 本章重点 ：1顺序栈和链栈上的进栈和退栈的算法2在顺序队列上实现入队和出队的算法 本章难点

9、 ：1顺序栈和链栈上的进栈和退栈的算法2在链队列上实现入队和出队的算法第四章树和叉树 目的与要求 ：掌握树、二叉树的定义；掌握树、二叉树的存贮方法；掌握二叉树的先序、中序和历规则及算法；了解线索二叉树及其操作；掌握树和二叉树转换的唯一性、森林与的转换规则；掌握哈夫曼树及哈夫曼编码。 本章主要内容 ：4.1 树的定义和基本操作4.2 二叉树4.2.1 二叉树的操作4.2.2 二叉树的性质4.2.3 二叉树的存储结构4.3 遍历二叉树和线索二叉树4.3.1 遍历二叉树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

10、- - - - - - 第 7 页，共 11 页 - - - - - - - - - 4.3.2 线索二叉树4.4 树和森林4.4.1 树的存储结构4.4.2 森林与二叉树的转换4.4.3 树的遍历4.6 哈夫曼树及其应用4.6.1 最优二叉树4.6.2 哈夫曼编码 本章重点 ：1二叉树的性质与各种遍历算法2哈夫曼树 本章难点 ：1遍历二叉树和线索二叉树2哈夫曼树及其应用第五章图 目的与要求 ：掌握图的基本概念，掌握图的存贮方法、图的深度优先算法和广度优先遍历规则及最小生成树的构造、拓扑排序、关键路径和最短路径。 本章主要内容 ：5.1 图的定义和术语5.2 图的存储结构5.2.1 数组表示法

11、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 5.2.2 邻接表5.3 图的遍历5.3.1 深度优先搜索5.3.2 广度优先搜索5.4 图的连通性问题5.4.1 无向图的连通分量和生成树5.4.3 最小生成树5.5 有向无环图及其应用5.5.1 拓朴排序5.5.2 关键路径 本章重点 ：1图的存储结构2图的遍历3有向无环图及其应用 本章难点 ：1关键路径2最短路径第六章查找 目的与要求 ：掌握顺序表的查找及其效率； 理解折半

12、查找的两个条件； 掌握二叉树和平衡二叉树四种类型的不平衡调整；理解哈希函数与哈希表；掌握冲突与冲突的解决方法；掌表的插入与删除方法。会推导B-树的平均查找长度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 本章主要内容 ：6.1 静态表的查找6.1.1 有序表的查找6.1.2 静态树表的查找6.1.3 静态树表的查找6.1.4 索引顺序表的查找6.2 动态查找表6.2.1 二叉排序树和平衡二叉树6.3 哈希表6.3.1 什么

13、是哈希表6.3.2 哈希函数的构造方法6.3.3 处理冲突的方法6.3.4 哈希表的查找及其分析 本章重点 ：1静态表2哈希表 本章难点 ：1动态表第七章内部排序 目的与要求 ：理解排序定义；了解排序的分类；掌握插入排序方法及效果；掌握集合的划分及快方法；掌握堆的构造及堆选排序方法；掌握归并的效率及归并排序方法；了解基数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 其特点。 本章主要内容 ：7.1 概述7.2 插入排序7.2.1 直接插入排序7.2.2 其它插入排序7.2.3 希尔排序7.3 快速排序7.4 选择排序7.4.1 简单选择排序7.4.2 树形选择排序7.4.3 堆排序7.5 归并排序7.6 基数排序7.6.1 多关键字的排序7.6.2 链式基数排序7.7 各种内部排序方法的比较讨论 本章重点 ：1各种排序方法的算法思想2各种排序方法的算法实现 本章难点 ：1各种排序方法的算法实现名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -