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

一、考试性质

硕士研究生入学考试是为招收硕士研究生而实施的具有选拔功能的水平考试，其指导思想是既要有利于国家对高层次人材的选拔，又要有利于促进高等学校各类课程教学质量的提高，考试对象为2006年参加硕士研究生入学考试的考生。

二、考试的基本要求

要求学生比较系统地理解数据结构的基本概念和基本知识，掌握表、栈、队列、树和图等数据结构的基本特征和在计算机上实现的方法，要求考生具有抽象思维能力、逻辑推理能力、综合运用所学的知识分析问题和解决问题的能力，以及软件设计和编程能力。

要求学生在完成程序设计语言（汇编、C、C++等）、数据结构、计算机组成原理等课程学习的基础上，系统地学习操作系统这一计算机最重要系统软件的基本概念、基本原理和方法，对操作系统如何管理和控制计算机系统的所有硬件和软件资源以达到方便用户、提高资源的使用效率有较清楚的认识，为将来在软件开发设计具有较强的分析、解决问题的能力打下坚实的基础。

三、考试方法和考试时间

硕士研究生入学专业考试为笔试，考试时间为3小时，考试分数150分。

四、考试科目、考试内容、考试要求和试卷结构

考试科目《数据结构与操作系统》

第一部分：数据结构（60%）

第一章绪论

1. 什么是数据结构

2．基本概念和术语

3．算法的描述和算法分析

基本要求：

了解《数据结构》所研究的问题，理解数据结构的基本概念，掌握算法的描述、算法设计的要求和算法效率的度量方法。

重 点：

数据的逻辑结构和存储结构；用类C（C++）语言描述算法。

第二章线性表

1．线性表的逻辑结构

2．线性表的顺序存储结构

3．线性表的链式存储结构

单向链表、循环链表、双向链表

基本要求：掌握线性表的逻辑结构、存储结构及描述方式；掌握顺序表和链表的插入、删除等操作。

重点：线性结构的定义和特点；顺序表和单链表的组织方法、特点和算法。

第三章栈和队列

1、 栈的定义、栈的表示和实现

2、表达式求值

3、队列的定义、队列的链式存储结构（链队列）、队列的顺序存储结构（循环队列）

基本要求：了解栈和队列的定义；理解线性表、栈和队列特点及区别，栈对实现递归过程的作用；掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断。

重点：栈和队的特点；顺序栈和链栈上基本运算的实现和简单算法设计；链队上基本运算的实现和简单算法设计，栈与递归。

第四章串

1、 串的逻辑结构定义及其基本操作

2、串的静态存储结构和动态存储结构

基本要求：了解串的有关定义；理解串的逻辑结构和存储结构；掌握串的模式匹配传统方法和KMP方法。

重点：串的基本运算及串的传统匹配方法和改进的KMP方法。

第五章数组和广义表

1、 数组的定义和运算

2、 数组的顺序存储结构

3、 矩阵（特殊矩阵、稀疏矩阵）的压缩存储

4、 广义表的定义

5、 广义表的存储结构及算法

基本要求：了解数组、特殊矩阵和稀疏矩阵的定义，广义表的概念、链表表示和算法；理解矩阵的压缩存储的概念；掌握矩阵的压缩存储的有关计算方法。

重点：特殊矩阵的非零元下标与数组下标的对应关系。

第六章树和二叉树

1、树的结构定义和基本操作

2、二叉树

定义与基本操作、性质、存储结构、遍历和线索化

3、树和森林。

树的存储结构、森林与二叉树的转换、树的遍历

4、哈夫曼树及其应用

基本要求：了解树的定义和二叉树的定义；理解二叉树的性质、二叉树的存储结构；掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码。

重点：利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题；哈夫曼树及其应用。

第七章图

1、图的定义和术语

2、图的存储结构：数组表示法、邻接表

3、图的遍历：深度优先搜索、广度优先搜索

4、图的连通性问题：无向图的连通分量和生成树、最小生成树

5、最短路经

6、拓扑排序

7、关键路经

基本要求：了解图的定义和术语，生成树和最小生成树的概念；理解邻接矩阵中元素的含义和邻接表中结点的含义；掌握深度优先搜索和广度优先搜索算法；

理解求最小生成树、最短路径、拓扑排序和关键路径等各种图解方法。

重点：图的两种表示，两种遍历；用Prim算法和Kruskal算法构造最小生成树；单源点、多源点的最短路径；用拓扑排序算法求关键路径等。

第八章动态存储管理

1、可利用空间表及分配方法

2、边界标识法

3、伙伴系统

基本要求：了解动态存储管理的含义及分配方法。

重点：边界标识法中可利用空间表的结构及分配算法和回收算法。

第九章查找

1、 静态查找表：顺序表的查找、有序表的查找、索引顺序表的查找

2、动态查找表：二叉排序树和平衡二叉树、B_树和B+树

3、哈希表：哈希函数的构造方法、处理冲突的方法、哈希表的查找及其分析

基本要求：了解顺序查找、二分查找和分块查找、二叉排序树和平衡二叉树、哈希查找等的概念；理解顺序查找、二分查找和分块查找算法，二叉排序树的性质；掌握哈希函数的构造方法和处理冲突的方法，平衡二叉树的查找、插入和删除操作算法及相关查找方法的成功平均查找长度ASL。

重点：二分查找的基本条件和方法；建立二叉排序树和平衡二叉树的过程；根据散列函数和解决冲突的方法建立散列表及等概率下成功平均查找长度ASL。

第十章内部排序

1、概述

2、插入排序：直接插入排序、希尔排

3、交换排序：冒泡排序、快速排序

4、选择排序：简单选择排序、树形选择排序、堆排序

5、归并排序：二路归并

6、基数排序

7、各种内部排序方法的比较讨论

基本要求：了解排序算法的稳定性问题；理解直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想；掌握直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序的算法和时间分析。

重点：对直接插入排序、简单选择排序、快速排序、堆排序、归并排序基本过程的掌握和算法的理解及评价。

第十一章外部排序

1、外存信息的存取

2、外存排序的方法

3、多路平衡归并的实现

4、置换-选择排序

基本要求：了解外排序的基本过程及方法。

重点：外部排序方法及利用“败者树”解决K路平衡归并和置换-选择排序问题

第十二章文件

1、有关文件的基本概念

2、顺序文件

3、索引文件

4、ISAM文件和VSAM文件

5、直接存取文件（散列文件）

6、多关键字文件：多重表文件、倒排文件

基本要求：熟悉各类文件的特点及构造方法。

重点：顺序文件、索引文件和散列文件。

参考教材：

严蔚敏、吴伟民《数据结构》（C语言版）清华大学出版社 1997

第二部分：操作系统（40%）

第一章操作系统概述

1.操作系统的概念

2.操作系统的历史

3.操作系统的特性

4.操作系统的功能

5.操作系统的发展

基本要求：

了解操作系统的作用、发展历史和分类等。

重 点：

操作系统的定义、分类和功能。

第二章 处理机管理

1. 多道程序设计

2．进程的引入

3．中断与中断系统

4．处理机调度

基本要求：

了解多道程序设计概念、掌握进程的基本概念、熟悉处理机调度算法。

重 点：

进程的概念、处理机调度算法。

第三章存储管理

1. 存储管理的功能

2. 内存资源管理

3. 存储管理方式

4. 虚拟存储系统

基本要求：

熟悉操作系统存储管理的方式和虚拟存储系统。

重 点：

页式、段式、段页式存储管理；虚拟存储系统。

第四章文件管理

1、文件与文件系统

2、文件的访问方式

3、文件的组织

4、文件目录

5、文件的共享

6、文件的保护、保密和安全

7、文件系统的实现

8、文件系统的界面

9、盘存储管理

基本要求：

理解文件系统的基本目的是为用户提供按名存取的功能，以使得用户能透明地存储访问文件。为了实现按名存取，需要对文件存储设备进行合理的组织、分配和管理，对存储在文件存储设备上的文件进行保护、保密和提供共享的手段。

重 点：

如何对文件存储设备进行组织、分配和管理；文件的共享和保护、保密。

第五章设备管理

1. 设备的分类

2. 设备的物理特性

3. 通道技术

4. 设备的分配和去配

5. 设备驱动

6. 缓冲技术

7. 虚拟设备

基本要求：

由于现代计算机系统外部设备的复杂性和多样性以及不同设备需要不同的处理程序，设备管理成了操作系统中最复杂、最具多样性的部分。要求了解设备管理的基本概念，理解通道技术和缓冲技术、设备驱动和虚拟设备技术。

重 点：

通道、缓冲、设备驱动、设备分配与去配。

第六章操作系统接口

1. 联机命令接口

2. 程序接口

3. 图形用户接口

基本要求：

了解操作系统的用户接口。

重 点：

了解操作系统的用户接口

第七章进程管理

1. 并发进程

2. 进程互斥

3. 进程同步

4. 进程通信

5. 进程死锁

基本要求：

掌握死锁的概念以及死锁发生的条件，熟悉发现死锁、预防或避免死锁的一些方法。

重 点：

进程的互斥和同步、死锁产生的必要条件；死锁的预防和避免。

第八章UNIX操作系统介绍

1. 历史回顾

2. 系统结构

3. 进程管理

4. 存储管理

5. 文件系统

6. 设备管理

7. 系统调用

基本要求：

了解UNIX操作系统的进程管理、存储管理、文件管理、设备管理以及系统调用。

重 点：

进程管理、存储管理和文件系统。

参考教材：

汤子瀛、哲凤屏 计算机操作系统 西安电子科技大学出版社 2002