2014燕山大学数据库与操作系统考研复习大纲

注：操作系统、数据结构各占50%操作系统：【考查目标】1、了解操作系统在计算机系统中的作用、地位、发展和特点。2、理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。3、能够运用所学的操作系统原理、方法与技术分析问题和解决问题。一、操作系统概述

1、操作系统的概念、作用和影响2、操作系统的形成和发展3、操作系统的基本功能、特征、运行环境和提供的服务4、操作系统的类型5、了解DOS、UNIX、LINUX、WINDOWS、OS/2类型及特点二、进程管理

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

1、作业的概念2、调度的基本概念3、调度的层次、作业调度和进程调度4、用户与操作系统的接口5、调度时机、切换与过程6、调度的基本准则7、典型调度算法8、先来先服务调度算法：短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。四、存储器管理

（一）内存管理基础1、存储器管理的基本任务2、逻辑地址与物理地址空间3、重定位4、程序装入与链接（二）连续分配管理方式1、单一连续分配2、固定分区3、可变分区（三）覆盖与交换技术（四）虚拟存储器管理

1、虚拟内存的基本概念

2、分页存储管理3、页面置换算法：OPT、FIFO、LRU、LFU4、页面抖动5、分段存储管理6、段页式存储管理五、设备管理

（一）设备管理概述1、设备的分类2、设备管理的目标和任务3、I/O应用接口4、I/O控制方式（二）设备分配与处理1、设备分配方法与过程2、缓冲区技术3、虚拟设备和SPOOL系统4、I/O

处理过程六、文件管理

1、文件及文件系统2、文件的组织形式和结构3、文件目录4、辅存空间的管理5、文件的可靠性和安全性6、文件的AFT的作用7、文件基本操作的实现

七、UNIX简介1、UNIX的特点2、UNIX进程的构成3、UNIX进程的状态及其转换

数据结构：第一章绪论[目的与要求]：深刻理解数据结构的概念，掌握数据结构的要素；掌握数据元素的逻辑结构；掌握数据元素的存贮结构；理解数据结构与算法的联系；了解算法的效率及存贮空间的度量。[本章主要内容]：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线性表的逻辑结构

2.2线性表的顺序存储结构

2.3线性表链式存储结构

2.3.1线性链表

2.3.2循环链表

2.3.3双向链表

2.4一元多项式的表示及相加[本章重点]：1．几种常用链表的特点和运算2．从不同角度比较线性表在顺序和链式两种存储结构的优缺点[本章难点]：1．几种常用链表的特点和运算第三章栈和队列[目的与要求]：掌握栈、队列的定义及其相关数据结构的概念；了解栈的特征；掌握栈的表示和实现方法；了解栈空间的共用和栈的应用；掌握队列的实现、链队列及其操作；理解顺序队列的假溢出；掌握循环队列的操作特点。

[本章主要内容]：3.1栈

3.1.1抽象数据类型栈的定义

3.1.2栈的表示和实现

3.2表达式求值

3.4队列

3.4.1抽象数据类型队列的定义

3.4.2链队列——队列的链式表示和实现

3.4.3循环队列——队列的顺序表示和实现[本章重点]：1．顺序栈和链栈上的进栈和退栈的算法2．在顺序队列上实现入队和出队的算法[本章难点]：1．顺序栈和链栈上的进栈和退栈的算法2．在链队列上实现入队和出队的算法第四章树和叉树[目的与要求]：掌握树、二叉树的定义；掌握树、二叉树的存贮方法；掌握二叉树的先序、中序和后序遍历规则及算法；了解线索二叉树及其操作；掌握树和二叉树转换的唯一性、森林与二叉树的转换规则；掌握哈夫曼树及哈夫曼编码。[本章主要内容]：4.1树的定义和基本操作

4.2二叉树

4.2.1二叉树的操作

4.2.2二叉树的性质

4.2.3二叉树的存储结构

4.3遍历二叉树和线索二叉树

4.3.1遍历二叉树

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数组表示法

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．最短路径第六章查找[目的与要求]：掌握顺序表的查找及其效率；理解折半查找的两个条件；掌握二叉树和平衡二叉树的构造、四种类型的不平衡调整；理解哈希函数与哈希表；掌握冲突与冲突的解决方法；掌握哈希表的插入与删除方法。会推导B-树的平均查找长度。[本章主要内容]：6.1静态表的查找

6.1.1有序表的查找

6.1.2静态树表的查找

6.1.3静态树表的查找

6.1.4索引顺序表的查找

6.2动态查找表

6.2.1二叉排序树和平衡二叉树

6.3哈希表

6.3.1什么是哈希表

6.3.2哈希函数的构造方法

6.3.3处理冲突的方法

6.3.4哈希表的查找及其分析[本章重点]：1．静态表2．哈希表[本章难点]：1．动态表第七章内部排序[目的与要求]：理解排序定义；了解排序的分类；掌握插入排序方法及效果；掌握集合的划分及快速排序方法；掌握堆的构造及堆选排序方法；掌握归并的效率及归并排序方法；了解基数排序及其特点。[本章主要内容]：7.1概述

7.2插入排序

7.2.1直接插入排序

7.2.2其它插入排序

7.2.3希尔排序

7.3快速排