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

一、考试的基本要求

要求考生比较系统地理解数据结构的基本概念和基本知识，从数据结构的逻辑结构、存储结构和数据的操作三个方面掌握线性表、树、图等常用的数据结构。掌握在各种常用数据结构上实现高效的查找和排序算法，并对算法的时间和空间复杂性有一定的分析能力。针对简单的应用问题，能够选择合适的数据结构设计有效的算法。

另一方面，要求考生比较系统地掌握操作系统各要素的基本概念、基本原理和方法，对操作系统如何管理和控制计算机系统的所有硬件和软件资源以达到方便用户、提高资源的使用效率有较深入的了解。

要求考生具有较强的抽象思维能力、逻辑推理能力、软件设计和实现能力以及综合运用所学的知识分析问题和解决问题的能力。

二、考试方式和考试时间

闭卷考试，总分150(数据结构90+操作系统60)，考试时间为3小时。

三、参考书目(仅供参考)

《数据结构与算法》(第四版)，廖明宏，郭福顺，张岩，李秀坤，高等教育出版社，2007年

《计算机操作系统》(第三版)，汤小丹，梁红兵，哲凤屏，汤子瀛，西安电子科技大学出版社，2007年

四、试题类型：

主要包括选择题 、编程题、计算题、综合题等类型，并根据每年的考试要求做相应调整。

五、考试内容及要求

第一部分 数据结构-线性表

掌握：线性表的逻辑结构、存储结构及描述方式;顺序表的定义、插入、删除;单链表、双向链表和循环链表的定义、插入、删除;顺序栈、链栈的表示、入栈和出栈操作;顺序队列、链队列的表示、入队和出队操作;循环队列的队空和队满的判断;串的定义、逻辑结构和存储结构，串的KMP模式匹配方法;广义表的定义;矩阵的压缩存储的概念以及有关计算方法;稀疏矩阵的三元组表示方法;

熟悉：线性结构的定义和特点;顺序表和单链表的组织方法、特点、算法和性能分析;单链表、双向链表和循环链表之间的区别;栈和队的特点;栈和队列的定义;顺序栈和链栈上基本运算的实现和简单算法设计;链队上基本运算的实现和简单算法设计;串的基本运算，串的传统匹配方法;多维数组的定义以及逻辑结构;广义表的链表表示和算法;特殊矩阵的非零元下标与数组下标的对应关系。

第二部分 数据结构-树

掌握：树的逻辑结构;二叉树的定义以及性质;二叉树的不同表示方法;二叉树的构建方法;二叉树的三种遍历算法;线索二叉树的定义及构造方法;树的存储结构;哈夫曼树的构建及其应用，哈夫曼编码;表达式树的构建及其应用;集合树的表示以及集合等价分类算法;

熟悉：树的常用术语和含义;二叉树性质的证明;利用二叉树的遍历设计有关算法解决简单应用问题;线索二叉树的插入、删除结点算法，利用线索二叉树确定结点的前驱和后继结点;森林与二叉树的转换;利用表达式树求表达式的值。

第三部分 数据结构-图

掌握：图的逻辑结构特征;图的两种表示方法;图的深度优先搜索的算法及实现;最小生成树的概念，用Prim算法和Kruskal算法构造连通图的最小生成树的方法和复杂度;对给定的有向图，给出其中一个拓扑排序;AOE网的基本原理和实现方法;单源最短路径Dijkstra算法的基本思想和性能分析;

熟悉：图的定义和术语;图的广度优先搜索的算法及实现;图的遍历和树的遍历之间的关系;生成树概念，用两种方法构建最小生成树的实现;拓扑排序算法的实现;单源最短路径的实现方法;Floyd算法的基本思想和性能分析;Warshall的算法实质;利用Floyd算法求有向图的中心点。

第四部分 数据结构-查找和排序

掌握：二分查找的基本条件和方法;分块查找的基本思想和性能分析;二分查找和分块查找的实现方法;二叉查找树和平衡二叉树的构建、插入结点和删除结点的方法;哈希表技术的相关概念、哈希函数的构造方法和原则以及产生冲突的原因;插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序基本原理和性能分析;快速排序、归并排序的算法实现;

熟悉：顺序查找、二分查找和分块查找、二叉排序树和平衡二叉树、哈希查找的概念、性质及性能;顺序查找、二叉排序树的实现方法;哈希函数的构造方法和处理冲突的方法;插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想;希尔排序、基数排序的实现方法;排序算法的稳定性分析。

第五部分 操作系统-进程管理

掌握：进程的基本概念;进程的特征与状态;进程的创建、终止、堵塞与唤醒、挂起与激活;进程的同步;几个经典的进程同步问题;消息缓冲队列通信机制;线程的同步与通信;

熟悉：程序顺序执行及其特征;程序并发执行及其特征;进程控制块;进程通信类型;消息传递通信的实现方法。

第六部分 操作系统-处理机调度与死锁

掌握：调度队列模型以及选择调度算法的若干准则;高优先权优先调度算法、时间片轮转调度算法、最高响应比调度算法;利用银行家算法避免死锁;死锁的检测与解除;

熟悉：处理机调度的基本概念;先来先服务调度算法、短作业优先调度算法;产生死锁的原因和必要条件;系统安全状态。

第七部分 操作系统-存储器管理

掌握：程序的装入和连接;页面与页表;地址变换机构;两级和多级页表;段页式存储管理方式;虚拟存储器的特征;请求分页存储管理中的内存分配策略、分配算法和调页策略;最佳置换算法和FIFO算法LRU置换算法;Clock置换算法;

熟悉：存储器的层次结构;连续分配方式：固定分区、动态分区、可重定位分区、对换;反向页表;分段存储的基本原理;信息共享;虚拟存储器的实现方法;请求分页中的硬件支持;请求分段中的硬件支持;分段的共享与保护。

第八部分 操作系统-设备管理

掌握： 程序I/O方式;中断驱动I/O控制方法;DMA I/O控制方法;循环缓冲、缓冲池;中断驱动程序;设备驱动程序;独立型设备的分配与去配;共享型设备的分配与去配;磁盘高速缓存;提高磁盘I/O速度的其它方法;

熟悉：I/O设备;总线系统; I/O通道控制方法;I/O软件的设计目标与原则;设备独立性软件;用户层软件;设备分配的相关数据结构;磁盘调度;廉价磁盘冗阵列。

第九部分 操作系统-文件管理与接口命令

掌握：索引文件、索引顺序文件、直接文件和哈希文件;连续分配、链接分派、索引分配;文件存储的空闲表法、空闲链表发、位示图法、成组链接法;基于索引结点的共享方式、利用符号链实现文件共享;数据一致性控制;Shell命令语言;

熟悉： 文件、记录和数据项的基本概念;文件类型和文件系统模型;文件的基本操作;文件逻辑结构的类型;顺序文件;文件控制块与索引结点、目录结构、目录查询技术;重复数据的数据一致性问题;联机用户接口、联机命令类型、键盘终端处理程序;系统调用概念及基本类型;图像界面接口。