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

数据结构与操作系统考试大纲做与不做的最大区别是：后者拥有对前者的评论权。数据结构与操作系统考试大纲课程名称：数据结构与操作系统一、 考试的总体要求数据结构要求掌握数据结构的基本术语，线性表、树、图等几种基本数据结构的特点、存储结构、基本操作以及在计算机科学中最基本的应用；掌握常用的排序与查找的方法；了解对算法的时间复杂度分析技术。要求学生能对给定的实际问题，建立准确的问题模型，选择合理的数据结构及其运算集，设计有效的算法。操作系统要求了解操作系统在计算机系统中的作用、地位、发展和特点。理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。能够运用所学的操作系统原理、方法与技术分析问题和解决问题。二、 考试内容及比例：数据结构部分：1、绪论（）：（1）理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；（2）掌握算法的时间复杂度和空间复杂度的概念和分析方法。2、线性表（）：（1）理解线性表的概念、逻辑结构特性以及两种存储结构特性；（2）掌握线性表的顺序存储结构、链式存储结构、各种运算及其应用。、栈和队列（）：（1）掌握栈和队列的定义、表示、实现和应用；（2）掌握栈的顺序存储结构和链式存储结构以及相应操作的实现及其应用；（3）掌握队列的顺序存储结构和链式存储结构的实现及其应用。、串（）：（1）掌握串的顺序存储结构与链式存储结构；（2）掌握串的各种基本运算及其应用。、数组和广义表（）：（1）了解稀疏矩阵的表示法；（2）理解稀疏矩阵和特殊矩阵进行压缩的方法；（3）掌握数组的两种存储表示方法和地址计算方法。、树和二叉树（30）：（1）掌握二叉树的定义、性质及其存储结构；（3）掌握二叉树的各种遍历算法；（4）掌握二叉树与树、森林之间的转换；掌握树和森林的遍历算法；（5）掌握线索二叉树的概念、存储结构及线索化算法；（6）掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。、图（）：（1）掌握图的基本概念和性质；（2）掌握图的存储结构；（3）掌握图的深度优先搜索和广度优先搜索方法及其实现；（4）掌握最小生成树的生成方法；（5）掌握最短路径的求解方法；（6）理解拓扑排序及关键路径。、查找（）：（1）理解查找及其算法的时间复杂度。（2）掌握顺序查找、折半查找与分块查找算法，能对其性能进行分析。（3）掌握二叉排序树与二叉平衡树的定义、建立和实现。（4）掌握哈希表的基本概念，哈希函数和哈希表的构造方法，解决冲突的开放地址法与链地址法。排序（）：（1）掌握插入类排序算法，直接插入排序，希尔排序；（2）掌握交换类排序算法，冒泡排序，快速排序；（3）掌握选择类排序算法，简单选择排序，堆排序；（4）理解归并排序算法和基数排序算法。操作系统部分：1、 操作系统概述（0 5）：（1）操作系统的概念、特征、功能和提供的服务；（2）操作系统的发展与分类；（3）操作系统的运行环境。2、进程管理（2 5 4 0）：（1）掌握进程概念及进程的状态与转换；（2）掌握进程控制，理解进程组织；（3）理解进程通信：共享存储系统；消息传递系统；管道通信；（4）掌握线程概念与多线程模型；（5）理解调度的基本概念，调度时机、切换与过程；（6）理解调度的基本准则及调度方式；（7）掌握典型调度算法：先来先服务调度算法；短作业优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法；（8）掌握进程同步的基本概念；（9）理解实现临界区互斥的基本方法：软件实现方法；硬件实现方法。（10）掌握信号量概念及使用信号量解决进程同步问题； （11）掌握经典同步问题：生产者-消费者问题；读者-写者问题；哲学家进餐问题； （12）掌握死锁概念及处理策略； （13）理解死锁预防，死锁避免，死锁检测和解除；掌握银行家算法。 3、内存管理（2 5 4）：（1）掌握内存管理概念：程序装入与链接；逻辑与物理地址空间；内存保护。；（2）了解交换与覆盖；（3）理解连续分配管理方式：单一连续分配；分区分配；（4）掌握非连续分配管理方式：分页管理；分段管理；段页式管理；（5）掌握虚拟内存基本概念；请求分页管理方式；（6）掌握页面置换算法：最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK）；（7）了解页面分配策略；抖动现象；工作集；（8）理解请求分段管理方式；请求段页式管理方式。4、文件管理（ 2 0）：（1）理解文件概念；文件系统功能；文件系统接口；（2）理解文件的逻辑结构和物理结构；（3）掌握文件目录结构以及目录管理；掌握索引文件的目录结构；Unix文件系统空闲块组织方法-成组链接法；（4）理解文件共享与保护机制；（5）理解磁盘的相关概念和参数，磁盘结构；了解RAID；（5）掌握磁盘调度算法的特点和优缺点对比；5、输入输出（I/O）管理（ 55）：（1）了解操作系统I/O子系统结构；（2）理解I/O管理目标、I/O