935891269《数据结构与操作系统》科目考查的内容范围

PA08055671342

一、数据结构

（一）概述

1、数据、数据对象、数据结构、数据类型

2、算法及算法描述

3、算法的时间复杂度和空间复杂度

（二）线性表

1、线性表的概念和基本操作

2、线性表类的定义和实现

3、线性表的应用及算法

（三）栈

1、栈的概念和基本操作

2、栈类的定义和实现

3、栈的应用及算法

（四）队列

1、队列的概念和基本操作

2、队列类的定义和实现

3、队列的应用及算法

（五）递归

1、理解递归的概念以及与栈的关系

2、理解递归的工作原理

3、递归算法的设计

（六）字符串

1、串的概念、术语和基本操作

2、串类的定义和实现

3、朴素模式匹配算法

（七）数组

1、数组的定义和运算

2、数组的按行、按列存储

3、特殊矩阵的压缩存储

（八）二叉树

1、二叉树的概念和相关术语

2、二叉树的先序、中序、后序三种遍历方法

3、线索二叉树

4、哈夫曼树的概念和建立方法

（九）树

1、有关树、森林的概念和术语

2、森林、树与二叉树的转换方法

3、森林、树的遍历方法

（十）图

1、图的定义和相关术语

2、计算机表示

3、图的遍历及算法

4、拓扑排序概念及算法

5、最短路径求解算法

6、最小生成树求解算法

（十一）查找

1、有关查找的基本概念

2、顺序查找算法实现及性能分析

3、二分查找算法实现及性能分析

4、二叉查找树的基本概念

5、二叉查找树下的查找、插入、删除算法

6、二叉查找树建立算法

7、AVL树定义

8、哈希查找的概念、哈希函数的选择及冲突解决方法

9、哈希查找算法实现及性能分析

10、不同查找算法的性能比较

（十二）排序

1、掌握有关排序的基本概念

2、插入排序算法实现及性能分析

3、选择排序算法实现及性能分析

4、希尔排序算法基本原理

5、归并排序算法实现及性能分析

6、快速排序算法实现及性能分析

7、堆和堆排序算法实现及性能分析

8、基数排序算法的基本原理

9、各种排序算法在时间、空间、程序效率等方面的比较

二、操作系统

（一）操作系统及其相关概念

1、操作系统的概念、发展、类型；

2、操作系统的功能、结构。

（二）进程管理

1、进程概念、调度算法、进程间通信；

2、进程同步机制、应用；

3、死锁概念、处理。

（三）内存管理

1、内存分配的策略及其分类；

2、页式管理、请求式页式管理、分段管理、段页式管理；

3、虚存管理的性能分析。

（四）文件管理

1、文件系统概念、功能、结构和实现；

2、磁盘结构及其调度算法。

（五）输入/输出管理

1、概念、功能、接口的基本含义及其相关实例。

872《数据结构与操作系872统》科目考查的内容范围