福州大学数学与计算机学院2006年研究生入学考试《数据结构与操作系统》专业课考试大纲
（一） 课程性质《算法与数据结构》与《计算机操作系统》是计算机学科的技术基础和主干必修课。
（二） 课程结构
第一部分：算法与数据结构
1、绪论（4学时）
知识点：数据与数据类型、数据结构、抽象数据类型、算法及其描述、算法复杂性分析
重点: 数据类型、数据结构、用c＋＋语言描述算法与数据结构、算法复杂性分析
难点: 抽象数据类型
2、表（12学时）
知识点: adt表的概念、表的各种实现方法、循环链表和双链表、栈及其各种实现方法、队列及其各种实现方法、映射及其各种实现方法
重点: 表的数组和链接实现、栈和队列的概念及实现
难点: 表的链接实现、栈的队列的综合应用
3、串（4学时）
知识点: 串的基本概念、串所支持的9种基本运算、表示串的数据结构
重点: 串的基本运算、串的匹配算法
难点: kmp算法
4、排序与选择（12学时）
知识点: 冒泡排序方法、插入排序方法、选择排序方法、快速排序方法、堆排序方法、计数排序方法、桶排序方法、基数排序方法、找第k小元素的方法
重点: 冒泡排序方法、快速排序方法、堆排序方法、基数排序方法
难点: 快速排序方法、堆排序方法、基数排序方法、桶排序方法
5、树（8学时）
知识点: 树的基本概念、二叉树的概念、树的前序遍历、中序遍历和后序遍历、adt树的概念、树的父亲数组表示法、树的儿子链表表示法、树的左儿子右兄弟表示法、二叉树的顺序存储结构、二叉树的结点度表示法、二叉树的链式存储结构、二叉树的应用
重点: 树与二叉树的存储结构、二叉树性质、二叉树遍历、线索化二叉树
难点: 线索二叉树、二叉树的应用、二叉树生成算法
6、图（16学时）
知识点: 图的基本概念与基本术语、图的邻接矩阵表示法、图的邻接表表示法、图的深度优先搜索、图的广度优先搜索、深度优先生成森林、无圈有向图、有向图的强连通分枝、最小生成树的概念与性质、最小生成树的prim算法、最小生成树的kruskal算法、单源最短路算法、所有顶点对间最短路算法、图匹配方法
重点：图的邻接矩阵和邻接表表示法、图的深度和广度优先搜索、prim和kruskal算法、dijkstra和floyd算法
难点：prim和kruskal算法、dijkstra和floyd算法
7、集合（16学时）
知识点: 集合的基本概念、集合的基本运算、集合的简单表示法、字典的概念、实现字典的简单方法、散列表的概念、用散列表实现字典的方法、有序字典的概念、用数组实现有序字典的方法、顺序搜索方法、二分搜索方法、插值搜索方法、二叉搜索树的概念、用二叉搜索树实现有序字典的方法、二叉搜索树的效率分析、优先队列的概念、优先队列的字典式实现方法、优先级树和堆的概念、用数组实现堆的方法、检索树的概念、用数组表示检索树的方法、用链表表示检索树的方法
重点:字典的实现方法（简单实现和散列表实现）、有序字典的实现方法（二分搜索方法和二叉搜索方法）、优先队列概念及实现方法
难点: 优先队列的字典或实现方法、检索树的实现方法
第二部分：计算机操作系统
1. 操作系统概论（4学时）
知识点：操作系统的定义、视点及认识；操作系统的基本类型及其特点；操作系统的形成与发展。
重点：掌握操作系统的基本特征和操作系统的地位、作用和效果。
教学难点：虚拟机概念的讲解；
2. 处理器管理（12学时）
知识点：中断、多道程序设计、并发程序设计、进程的概念；进程管理功能；进程的控制及调度；处理器基本工作单位的控制粒度；进程并发性的含义；进程的同步机制；进程通信；死锁。
重点及难点：处理器管理是操作系统的核心之一，是操作系统课程的教学重点也是难点。
3．存储器管理（12学时）
知识点：存储器管理的基本概念；连续存储空间存储管理的原理实现；非连续存储空间存储管理的原理及实现；虚拟存储空间的概念及实现
重点及难点：存储管理是操作系统的核心之一，是操作系统课程的教学重点和难点。
4．文件系统管理（8学时）
知识点：文件及文件系统的概念；文件目录；文件的共享、保护和保密
重点：文件的组织与存储
难点：文件操作的执行过程
5．设备管理（8学时）
知识点：i/o操作与设备和概念；缓冲技术及pnp技术；中断处理及驱动程序
重点：设备的分配和调度
难点：i/o控制方式及具有通道的i/o系统管理；虚拟设备、设备一致性、设备无关性的概念。
6．作业管理（6学时）
知识点：作业及作业管理功能；交互式作业的控制
重点：批处理作业的控制及调度；作业的变迁。
难点：作业控制。
7．现行主流操作系统实例分析（4学时）
知识点：msdos系统实例分析；unix系统实例分析；minix或linix操作系统实例分析（可选内容）。
重点及难点：以os的理论分析几种操作系统。
（三） 课程资料
教材：
1. 《算法与数据结构》王晓东编，电子工业出版社；
2. 《计算机操作系统教程》，张尧学，史美林编，清华大学出版社
主要教学参考资料：
页:
[1]