科目代码：842

科目名称：数据结构与操作系统

本门课程由数据结构和操作系统两门课程组成，两门课程各占75分，具体要求如下：

第一部分：数据结构

一、考试的总体要求

掌握数据结构中常用的逻辑结构、存储结构和基本操作，灵活运用所学的数据结构解决实际问题;掌握典型的查找和排序算法，并能够针对不同特征的数据集进行有效应用;能够分析算法的时间复杂度，设计具有较高时空性能的算法。

二、考试的内容

1、基本概念和术语

2、线性表

线性表的定义;线性表的逻辑结构;线性表的存储结构(顺序存储、链式存储);不同存储方式下操作的实现;线性表的应用。

3、栈与队列

栈：栈的定义;栈的逻辑结构;栈的存储结构(顺序存储，链式存储);不同存储方式下操作的实现;栈的应用。

队列：队列的定义;队列的逻辑结构;队列的存储结构(顺序，链式);不同存储方式下操作的实现;队列的应用。

4、树和二叉树

二叉树：二叉树的概念;二叉树的基本性质;二叉树的逻辑结构;二叉树的存储结构(顺序、链式);各存储结构上的基本操作实现;二叉树的应用。

树和森林：树(森林)的基本概念;树(森林)的逻辑结构;树(森林)的存储结构(双亲表示法，孩子链表表示法，孩子兄弟链表表示法);树(森林)的基本操作实现;树(森林)的应用。

树(森林)与二叉树之间的相互转换;

哈夫曼树(最优二叉树)：哈夫曼树的定义、哈夫曼树的存储与应用。

5、图

图的定义与基本术语;图的逻辑结构;图的存储结构(邻接矩阵，邻接表及逆邻接表);不同存储结构上的基本操作实现;图的应用。

6、查找

基本概念与术语;静态查找(顺序查找、折半查找、分块查找);动态查找(二叉排序树、二叉平衡树和B-树的查找、插入和删除);哈希查找(哈希表的概念、常用的哈希函数、解决冲突的方法);查找性能分析(平均查找长度);

7、排序

插入类排序(直接插入排序、折半插入排序、希尔排序)、交换类排序(冒泡排序、快速排序)、选择类排序(简单选择排序、堆排序)、归并类排序(二路归并排序)、基数排序;各种排序方法的稳定性和时间性能分析。

8.综合应用：根据实际问题，设计有效的数据结构和算法，并进行时间复杂度分析。

三、考试的题型

选择题、填空题、综合题、算法设计题

第二部分：操作系统

一、考试的总体要求

要求考生熟练掌握计算机操作系统中的基本概念、基本原理; 从资源管理角度掌握计算机操作系统的主要功能及设计思想;了解和掌握现代计算机系统对其各种软硬资源的管理方法及实现技术;了解当代计算机操作系统的新技术与发展趋势。

二、考试的内容

1.操作系统概述：

包括操作系统的定义;操作系统的发展过程;操作系统的分类;操作系统的特征和服务;操作系统的功能;常用操作系统的结构特点。

2.进程管理：

包括进程的基本概念;进程控制(进程的状态机转换);进程同步;经典的进程同步互斥问题;进程通信;线程的定义及实现。

3.处理机调度与死锁：

包括处理机调度的基本概念;调度方式及算法;死锁的基本概念;死锁的概念; 死锁的处理策略。

4.存储器管理：

包括程序的装入和链接;连续分配存储管理方式;覆盖与交换;分页存储管理方式;分段存储管理方式。虚拟存储器的基本概念;请求分页存储管理方式;页面置换算法;请求分段存储管理方式。

5.设备管理：

包括I/O系统的组成;I/O控制方式;I/O软件层次结构;设备独立性;缓冲管理;假脱机技术;设备分配;设备处理。

6.文件管理：

包括文件和文件系统;文件逻辑结构;目录管理;文件共享;文件保护。

7.磁盘管理：

包括磁盘I/O;外存分配方法;空闲存储空间的管理;磁盘容错技术。

三、考试的题型

单向选择题、填空题、应用题