（八）排序

插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序等排序方法排序的原理、规律和特点；

各种排序算法的时空复杂度的简单分析。

（九）索引结构与散列

线性索引结构、倒排表、静态搜索树的结构和特点；

B树的结构；

散列的实现原理和各种操作的实现算法。

三、试卷结构

考试题型：填空题、选择题、简答题、编程题

第二部分  操作系统（60/150）(与第三部分二选一)

一、考试要求

要求考生比较系统地理解和掌握操作系统的基本概念、主要功能、主要组成部分、各个主要组成部分的不同实现方法；从资源管 理和应用程序与硬件系统接口的观点掌握操作系统设计的基本思想，掌握现代计算机系统对其各种软硬资源的管理技术。要求考生具备综合运用所学知识分析问题和 解决问题的能力。

二、考试内容

（一）基本概念

计算机基本构成、处理器的内部结构、高速缓冲存储器CACHE；

操作系统的概念、演变历程、特性、分类、运行环境、功能；

存储器的层次结构。

（二）进程

进程的概念和特点；

进程状态转换。

（三）线程、对称多处理SMP和微内核

线程的概念，定义线程的必要性和可能性；

线程的功能特性与实现方式；

对称多处理SMP体系结构；

操作系统的体系结构（微内核与单内核）及其性能分析。

（四）并发

并发性问题及相关概念，如临界区、互斥、信号量和管程等；

进程互斥、同步和通信的各种算法；

死锁的概念、死锁的原因和条件；

死锁的预防、避免和检测算法。

（五）存储器管理

分区存储管理、覆盖与交换；

页式管理及段式管理；

段、页式存储管理方法及实现技术；

虚存的原理及相关的各种算法和数据结构。

（六）单处理器调度

处理器的三种调度类型；

进程调度的各种算法及其特点。

（七）多处理器调度和实时调度

多处理器对进程调度的影响；

多处理器环境下的进程和线程调度算法；

实时进程的特点；

限期调度和速率单调调度方法。

（八）设备管理和磁盘调度

操作系统中输入/输出功能的组织；

中断处理；

设备驱动程序、设备无关的软件接口和spooling技术；

缓冲策略；

磁盘调度算法；

磁盘阵列。

（九）文件系统

文件系统特点与文件组织方式；

文件系统的数据结构；

目录的基本性质及其实现方法；

磁盘空间的管理。

（十）分布式系统

分布式处理的特点、类型；

多层体系结构、中间件技术；

机群系统；

分布式进程管理相关的操作系统设计问题。

三、试卷结构

考试题型：填空题、选择题、简答题、计算题

第三部分  数据库系统原理（60/150）(与第二部分二选一)

一、考试要求

要求考生熟悉数据库系统的基本概念、原理和基础理论，熟悉关系数据模型、关系代数、关系系统、关系数据库设计方法，以及数据库恢复、并发控制、安全性、完整性等数据库系统技术；能够熟练使用SQL，具备使用数据库管理系统和设计数据库的能力。

二、考试内容

（一）概论

数据、数据库、数据库管理系统、数据库系统、数据库系统的特点等基本概念的定义；

数据管理的三个阶段；数据模型：概念模型、关系模型、面向对象等的构造形式及特点；数据库系统结构：三级结构、两级映像。

（二）关系数据库

关系模型、关系模式、关系数据库等基本概念以及关系代数理论；

能够运用关系代数（并、交、差、除、笛卡尔积、选择、投影、连接）完成关系运算。

（三）SQL语言

SQL特点、SQL标准；

各类SQL语句的语法构成、语义与功能，能够运用标准SQL完成数据存取；

视图的概念、视图的定义、视图操纵、视图的更新；

存储过程、触发器。

（四）关系存储和查询优化