数据结构部分

考试内容范围:

绪论

1. 了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。

线性表

1. 了解线性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。

2. 熟练掌握顺序存储结构和链式存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。

3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

栈和队列

1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2. 熟练掌握栈类型的两种实现方法。

3. 熟练掌握循环队列和链队列的基本操作实现算法。

4. 理解递归算法执行过程中栈的状态变化过程。

串

1. 理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。

2. 理解串类型的各种存储表示方法。

数组和广义表

1. 理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”和“以列为主”的存储表示中的地址计算方法。

2. 掌握特殊矩阵的压缩存储表示方法。

3. 理解稀疏矩阵的压缩存储方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。

树和二叉树

1. 领会树和二叉树的类型定义，理解树和二叉树的结构差别。

2. 熟记二叉树的主要特性，并掌握它们的证明方法。

3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。

4. 理解二叉树的线索化过程以及在线索化树上找给定结点的前驱和后继的方法。

5. 熟练掌握二叉树和树的各种存储结构及其建立的算法。

6. 学会编写实现树的各种操作的算法。

7. 了解哈夫曼树的特性，掌握建立哈夫曼树和哈夫曼编码的方法。

图

1. 领会图的类型定义。

2. 熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。

3. 熟练掌握图的两种遍历算法。

4. 理解各种图的应用问题的算法及其应用场合。

查找

1. 理解查找表的结构特点以及各种表示方法的适用性。

2. 熟练掌握以顺序表或有序表表示静态查找表时的查找方法。

3. 熟练掌握二叉排序树的构造和查找方法。

4. 理解平衡二叉排序树的构造过程。

5. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的查找表的实质性的差别。

6. 掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

内部排序

1. 理解排序的定义和各种排序方法的特点，并能加以灵活应用。

2. 掌握各种排序方法的时间复杂度和空间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。

3. 理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

文件

1. 熟悉各类文件的特点、构造方法以及如何实现检索、插入和删除等操作。

2. 了解各种文件的适用场合。

考试总分：90分     考试时间：1.8小时    考试方式：笔试

考试题型：选择题（30分）

判断题（10分）

填空题（10分）

计算题（30分）

算法题（10分）

参考书目（材料）

严蔚敏  吴伟民编著，数据结构（C语言版），北京：清华大学出版社

操作系统部分

考试内容范围:

一、操作系统概述

1．理解操作系统的概念、特征、功能和提供的服务。

2．了解操作系统的发展与分类。

3．了解操作系统的运行环境。

二、进程管理

1．理解进程概念、进程的状态与转换、进程控制、进程组织、进程通信、线程概念与多线程模型。

2．掌握处理机调度的基本概念、调度时机、切换与过程、调度的基本准则、调度方式。

3．熟练掌握典型调度算法：先来先服务调度算法；短作业（短进程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。

4．理解进程同步的基本概念、实现临界区互斥的基本方法、信号量、管程、经典同步问题。

5．熟练掌握死锁的概念、死锁处理策略、死锁预防、死锁避免（系统安全状态、银行家算法）、死锁检测和解除。

三、内存管理

1．理解内存管理概念、程序装入与链接、逻辑地址与物理地址空间、内存保护。

2．熟练掌握交换与覆盖、连续分配管理方式、非连续分配管理方式。

3．理解分页管理方式、分段管理方式、段页式管理方式。

4．理解虚拟内存基本概念、请求分页管理方式，并熟练掌握页面置换算法（OPT、FIFO、LRU、CLOCK）。

5．理解页面分配策略、抖动、工作集。

6． 理解请求分段管理方式、请求段页式管理方式。

四、文件管理

1．理解并熟悉文件概念、文件的逻辑结构、目录结构、文件控制块和索引节点、文件共享、文件保护。

2．理解并熟悉文件系统层次结构、目录实现、文件实现。

3． 熟练掌握磁盘的结构、磁盘调度算法、磁盘的管理。

五、输入输出（I/O）管理

1．理解I/O管理，I/O 设备、I/O 管理目标、I/O 管理功能、I/O 应用接口、I/O 控制方式。

2．熟练掌握I/O调度，高速缓存与缓冲区、设备分配与回收、假脱机技术（SPOOLing）、出错处理。

考试总分：60分     考试时间：1.2小时    考试方式：笔试

考试题型： 选择题（10分）

           填空题（10分）

应用题（40分）