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

一、考查目标

数据结构和操作系统是计算机类专业的核心课程。《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，能够灵活应用相关的方法和技术解决实际问题。

二、考试形式与试卷结构

（一）试卷成绩及考试时间

本试卷满分为150分，考试时间为180分钟。

（二）答题方式

答题方式为闭卷、笔试。

（三）试卷内容结构

各部分内容所占分值为：

数据结构    75分

操作系统    75分

（四）试卷题型结构

选择题，简答题，综合题，程序设计题

三、考查范围

数据结构

一、考查目标

1、掌握数据结构的基本概念、方法和技术。

2、掌握程序设计的基本方法和技巧。

3、能够应用相关知识解决一些有实际背景的问题。

二、考查内容

1. 数据结构概述

数据结构的概念；

基本概念与术语；

算法的概念，算法的特性，以及算法设计的要求，算法效率的度量。

2. 线性表

线性表的基本概念和结构特点；

线性表的顺序存储方式以及两种不同的实现方法，线性表存储空间的静态分配和动态分配；

线性表的链式存储方式的实现，链表与顺序表的相似及不同之处，优缺点比较，各自适用的场合；

线性表的各种实现方式下能够实现指定的操作。

3.栈和队

栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队列等；

栈与队列插入删除操作的特点；栈和递归的关系；栈和队列各种实现方式。

4. 串

 串的基本概念，朴素的模式匹配算法。

5.数组

数组的定义，数组的存储，行序和列序；

特殊矩阵的定义；特殊矩阵的压缩存储。

6.树和二叉树

二叉树的概念，二叉树的五个性质；

二叉树的存储结构：顺序存储和二叉链表存储的各自优缺点及适用场合；

二叉树的三种遍历方法：先序，中序和后序，线索二叉树，线索化后二叉树的遍历方法；

哈夫曼树概念，哈夫曼树的构造方法，前缀码概念，哈夫曼编码。

树的存储表示方法，树与森林转化为二叉树，树和森林的遍历问题。

7. 图

图的基本概念，图的定义和特点；

图的几种存储形式，重点是邻接矩阵和邻接表；

深度遍历和广度遍历是图的两种基本的遍历算法；

生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法；

有向无环图，拓扑排序和关键路径问题；

最短路径问题：DIJSKTRA算法和FLOYD算法。

8. 查找

关键字、主关键字、次关键字的含义；

静态查找与动态查找的含义及区别，平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果；

顺序表的查找，折半查找，索引顺序表；

二叉排序树，平衡二叉树，B树；

哈希表的概念，哈希函数的设计，冲突解决方法的选择及冲突处理过程。

9.排序

要求掌握各种排序方法的思想和算法实现，排序算法稳定性的概念，以及各自的特点。

插入排序：直接插入、折半插入、2路插入、希尔排序；

冒泡排序，快速排序；

选择排序：简单选择、树选择、堆排序；

归并排序；

基数排序。

操作系统

一、考查目标

1、了解操作系统在计算机系统中的作用、地位，操作系统的发展历史，各类型操作系统的特点。

2、掌握操作系统资源管理的原理、机制、策略和关键技术，理解操作系统的运行过程。

3、能够运用所学的操作系统原理、方法与技术分析和解决问题。

二、考查内容

1、操作系统概述

操作系统的概念、特征、功能和提供的服务；

操作系统的发展历史与分类；

操作系统的运行环境

2、用户界面

作业的概念及作业的建立过程；

命令控制界面接口；

系统调用

3、处理机管理

(1)进程管理

进程与线程，进程的状态与转换，进程控制，进程间通信；

进程同步与互斥，信号量机制与P、V操作，经典的同步互斥模型；

死锁的预防、避免、检测和解除

(2)处理机调度

调度的基本概念，调度的目标，功能与性能衡量；

典型调度算法：先来先服务、短作业（短进程）优先、时间片轮转、基于优先级、最高响应比优先、多级反馈轮转等调度算法。

4、存储管理

存储管理的功能：虚拟存储器、地址变换、内存的分配与回收、内存信息的共享与保护；

覆盖与交换技术；

分区存储管理：基本原理、分区的分配与回收；

页式存储管理：基本原理和实现，请求页式管理中的页面置换算法：先进先出置换算法（FIFO）、最近最少使用置换算法（LRU）、最佳置换算法（OPT）、时钟置换算法（CLOCK）等；

段式与段页式管理：基本原理和实现；

工作集、局部性原理和抖动问题

5、文件管理

文件和文件系统的基本概念；

文件逻辑结构与物理结构；

文件存储管理：文件存储空间管理，文件目录管理，文件存取控制，文件系统层次结构；

磁盘组织与管理:磁盘调度算法

6、设备管理

设备管理的目的、设备管理的功能和任务；

数据传输控制方式：程序直接控制、中断、DMA、通道；

中断技术：中断的概念、中断的分类、软中断、中断的处理过程；

缓冲技术：缓冲的种类、缓冲池的管理；

设备分配与回收：设备分配用数据结构、分配原则和分配算法；

虚拟设备，Spooling技术