《数据结构及操作系统》考试大纲

命题方式  招生单位自命题  科目类别  初试
满分  150
考试性质
《数据结构及操作系统》课程主要包含数据结构和操作系统两块内容。该课程的考试是为招收工学类硕士研究生而设置的选拔考试。它的主要目的是测试考生对该课程的把握程度，包括对课程中的概念、基本原理和方法的理解和掌握，及能够运用所学的原理和方法分析、判断及解决有关理论问题和实际问题。
考试方式和考试时间
考试采用闭卷笔试形式，试卷满分为150分（数据结构和操作系统各占75分），考试时间为3小时。
考试内容和考试要求
一、数据结构
（一）数据结构概论
考试内容：
1． 概念：数据结构，数据元素，数据项，数据的四种经典逻辑结构，数据的物理存储结构，数据结构研究的三个方向，算法，算法的时间复杂度、空间复杂度
2． 理解和应用：
（1）数据的四种经典逻辑结构之间的区别和联系
（2）算法的特性和设计的要求
（3）时间复杂度和空间复杂度的关系
考试要求
（1）掌握基本概念
（2）能计算出给定程序的时间复杂度

（二）线性结构
考试内容：
1. 概念：线性结构的特点，线性表，线性表的顺序存储特点，顺序表中元素存储位置之间的关系，线性链表， 循环链表，双向链表，栈，队列，循环队列，串，子串，模式匹配算法
2.  理解与应用：
（1） 线性表、栈、队列与线性结构的关系
（2） 线性表的顺序存储结构表示
（3） 顺序表中的插入、删除、合并操作算法的思想及实现方法
（4）线性表的链式存储结构表示
（5）单链表的创建、查找、插入、删除、合并算法的思想及实现方法
（6）双向链表的插入和删除算法的思想及实现
（7）栈中栈顶、栈底的含义，栈中元素操作的特点
（8）栈顶指针的作用及意义
（9）栈的进栈、出栈算法的思想及实现方法
（10）栈的应用
（11）队列中队头、队尾的含义，队列的基本特点
（12）循环队列的设计思路及实现方法
（13）队列的入队列、出队列算法的思想及实现方法
（14）子串的位置及模式匹配
（15）子串的定位算法及KMP算法
考试要求：
（1）掌握基本概念
（2）对算法的思想能进行文字描述
（3）了解栈与队列的操作特点

（三）树
考试内容：
1. 概念：树，子树，二叉树，结点的度，分支结点，双亲、兄弟、堂兄、祖先、子孙结点，树的深度，无序树，有序树，森林，满二叉树，完全二叉树，线索二叉树，最优二叉树，树的带权路径长度
2. 理解与应用
（1）二叉树的性质
（2）满二叉树与完全二叉树的区别与联系
（3）二叉树的存储结构及实现
（4）二叉树的三种遍历算法的思想及实现方法
（5）二叉树的线索过程
（6）树的存储结构及表示
（7）树、二叉树、森林间的相互转换
（8）树、森林的遍历与二叉树的遍历之间的联系
（9）线索二叉树的存储结构
（10）二叉树的线索化算法
（11）赫夫曼树的构造算法及实现方法
考试要求：
（1）掌握基本概念
（2）掌握算法的思想，能对算法代码实现
（3）了解树、二叉树、森林的存储结构、遍历关系

（四）图
考试内容：
1. 概念：图，顶点，弧，有向图，无向图，完全图，子图，顶点的度，路径，简单路径，回路，连通图，连通分量，强连通图，强连通分量，生成树，生成森林 ，有向无环图，拓扑排序，关键路径，AOV网，AOE网，最短路径
2. 理解与应用：
（1）图的特点
（2）图的存储结构及实现
（3）图的遍历算法思想及实现方法
（4）图的最小生成树构造算法思想及实现方法
（5）拓扑排序算法的思想及实现方法
（6）最短路径的构造算法
考试要求：
（1）掌握基本概念
（2）掌握算法的思想，能对算法代码实现
（3）了解各种算法的应用范围和解决的实际问题

（五）查找
考试内容：
1. 概念：查找表，关键字，静态查找，动态查找，平均查找长度，二叉排序树，平衡因子，平衡二叉树，B-树，B+树，键树，TRIE树，哈希表，
2. 理解与应用：
（1）理解静态查找和动态查找的区别
（2）静态查找的三种方法及实现，三种方法的特点及适用范围
（3）二叉排序树的构造和插入算法的思想及实现方法
（4）二叉排序树构造过程中的平衡处理算法的思想
（5）各种查找方法的ASL计算
（6）B-树上的查找、插入、删除算法的思想
（7）哈希函数的构造方法
（8）哈希构造中处理冲突的方法
考试要求：
（1）掌握基本概念
（2）掌握算法的思想，能对算法代码实现
（3）掌握哈希表的构造方法
（4）了解各种算法的应用范围和解决的实际问题
（六）排序
1. 概念：排序，稳定，内排序，外排序
2. 理解与应用：
（1）排序算法的分类，重要指标
（2）各种排序算法的思想及实现方法
（3）各种算法的稳定性、时间复杂度、空间复杂度
（4）各种排序算法的特点和适用范围
考试要求：
（1）掌握基本概念
（2）掌握各种排序算法的思想，能对算法代码实现
（3）理解各种排序方法的优缺点和适用范围
（4）了解稳定性、时间复杂度和空间复杂度对排序的影响

二、操作系统原理
（一）操作系统概论
考试内容：
1． 概念：操作系统的定义、功能和地位，操作系统的发展，操作系统基本特征
2． 理解和应用：
（1）批处理多道系统、分时系统和实时系统三个基本操作系统的工作原理及特征
（2）分时系统与实时系统的区别
（3）基本操作系统的特征
考试要求
（1）掌握基本概念
（2）理解操作系统在计算机系统中的地位和三个基本特征

（二）进程管理
考试内容：
1．概念：前趋图，进程的定义、特征、三种基本状态（就绪、阻塞和运行），进程控制块，临界资源，临界区，同步机制应遵循的原则，管程的定义，条件变量，进程通信的类型，线程，线程的属性，处理机的三级调度，进程的两种调度方式，周转时间，带权周转时间，常用的几种调度算法（先来先服务、短作业（进程）优先、高优先权优先、高响应比优先、时间片轮转法、多级反馈队列调度），优先权，响应比，死锁，产生死锁的原因、必要条件及处理死锁的基本方法，死锁定理
2． 理解与应用：
（1）进程与程序的区别
（2）进程三个基本状态之间的转换及引起转换的原因
（3）进程的两种制约关系，并能进行辨别
（4）能够辨别临界资源
（5）常用的几种信号量机制及每种机制的原理
（6）利用信号量实现进程的互斥、同步和前趋关系
（7）理解经典的进程同步问题（生产者-消费者问题；读者-写者问题；哲学家进餐问题）
（8）利用管理解决生产者和消费者问题
（9）消息传递通信的实现方法
（10）消息缓冲队列通信的实现方法
（11）理解什么是内核支持线程和用户级线程
（12）进程与线程的区别
（13）进程调度方式中抢占式的抢占原则
（14）理解每种调度算法的算法思想、优缺点，并能根据算法思想完成相应计算
（15）预防死锁的各种方法
（16）银行家算法的思想
（17）能够根据银行家算法和安全性检测算法判断系统的安全状态及决定是否分配资源
（18）死锁检测的方法
（19）死锁解除的方法
考试要求：
（1）掌握基本概念及基本原理
（2）重点：进程的概念和进程的并发特征；进程与程序的区别；进程状态及转换；相关临界区问题和临界资源；用信号量解决进程的同步与互斥问题；进程调度算法；死锁的概念与解决死锁的方法。
（3）难点：进程的相互制约；相关临界区的概念；进程通信；用信号量解决进程的互斥与同步；

（三）存储管理
考试内容：
1. 概念：相对地址，绝对地址，重定位，静态重定位，动态重定位，碎片，拼接，页表，快表，段表，虚拟存储器的概念及特征，抖动（颠簸）
2. 理解与应用
（1）固定分区的内存分配原理
（2）动态（可变）分区的内存分配原理，及常用数据结构
（3）动态（可变）分区常用的三种分配算法（首次适应算法、循环首次适应算法、最佳适应算法）
（4）引入分页和分段的原因
（5）基本分页的实现原理及和机制
（6）基本分段的实现原理及和机制
（7）分页与分段的主要区别
（8）请求分页管理的实现原理和机制
（9）缺页中断的处理过程及缺页中断与一般中断的区别
（10）掌握常用的页面置换算法（最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK）），并能根据算法思想完成相应计算
（11）请求分段管理的实现原理和机制
考试要求：
（1）掌握基本概念和原理
（2）重点：虚拟存储器的概念；静态与动态重定位及其区别；可变分区的管理算法；分页管理的实现原理和机制；基本分段的实现原理和机制；典型的页面替换算法；分页与分段的区别。
（3）难点：虚拟存储器的概念；页面替换算法；分页与分段的区别。

（四）设备管理
考试内容：
1. 概念：I/O设备的分类，通道，设备无关性，虚拟设备，SPOOLing技术，寻道时间，旋转延迟时间
2. 理解与应用：
（1）设备管理的功能
（2）设备控制器的功能
（3）通道的分类
（4）I/O的几种控制方式（程序I/O方式、中断控制方式、DMA方式、通道控制方式）的工作原理及特点
（5）缓冲技术的引入目的和缓冲区的分类
（6）设备无关性；
（7）设备分配中常用的数据结构
（8）独占设备的分配与释放。
（9）SPOOLing系统的组成及实现
（10）磁盘调度常用的几种调度算法（先来先服务、最短寻道优先、扫描算法、循环扫描算法），并能根据算法思想完成相应计算
考试要求：
（１）掌握基本概念和原理
（２）重点：I/O控制方式；缓冲技术的引入目的和缓冲区的种类；虚拟设备的概念和SPOOLING系统的组成和实现；磁盘调度算法。
（3）难点：设备无关性；虚拟设备；I/O控制方式。

（五）文件管理
考试内容：
1. 概念：文件、文件的分类，文件逻辑结构，文件物理结构，目录，文件控制块，按名存取，位示图
2. 理解与应用：
（１）文件和文件系统的概念；
（２）文件的基本操作
（3）文件逻辑结构中的顺序文件、索引文件和索引顺序文件的形式和特点
（4）文件物理结构中涉及的连续分配、链接分配和索引分配如何实现一个文件在外存上的存放及每种分配方式的特点
（5）二级和多级文件目录的形式及特点
（6）管理文件存储空间的常用方法
（7）通过位示图如何实现盘块的分配和回收
考试要求：
（１）掌握基本概念和原理
（２）重点：文件的逻辑结构和物理结构；二级和多级文件目录；管理文件存储空间的方法。
（3）难点：文件的逻辑结构；文件的物理结构。
主要参考书目
《数据结构C语言版》，严蔚敏著，清华大学出版社
《计算机操作系统（第三版）》汤小丹著，西安电子科技大学出版社