1、数据结构与操作系统考试大纲科目代码：830科目名称：数据结构与操作系统I. 考查目标计算机科学与技术专业课程考试包括数据结构和操作系统两科专业基础课程。要求考生系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。II. 考试形式和试卷结构1、试卷满分及考试时间本试卷满分为 150 分，考试时间为 180 分钟2、答题方式答题方式为闭卷、笔试3、试卷内容结构数据结构 80 分（从选择题、填空题、简答题、算法设计与分析题题型中任意选择或组合）操作系统 70 分（包括选择题、判断题、简答题、综合分析设计题等）III. 考试范围数据
2、结构考查目标：1、熟悉线性表、栈、队列、串、树和二叉树以及图等基本类型的数据结构及其特点，学会根据实际问题要求选用及设计数据结构； 2、理解数据的逻辑结构、存储结构以及各种基本操作的实现；3、掌握基本的算法分析和设计方法；4、掌握数据结构在排序和查找等常用算法中的应用，学会一般问题的算法设计。考查内容：（一）线性表（1）线性表的定义和基本操作（2）线性表的实现 顺序存储 链式存储 线性表的应用（二）栈和队列（1）栈和队列的基本概念。（2）栈和队列两种存储结构表示（顺序存储和链式存储）中基本操作的实现算法。（3）栈和队列的应用。（三）字符串（1）字符串的基本概念。（2）字符串在顺序存储表示中基本
3、操作的实现算法。（3）字符串匹配的 KMP 算法，字符串特征向量的计算方法。（四）树和二叉树（1）二叉树的定义及其主要性质。（2）二叉树的顺序存储结构和链式存储结构。（3）二叉树的遍历。（4）二叉树线索化的实质和线索化的过程。（5）树和森林与二叉树的转换。（6）树和森林的遍历。（7）二叉树的应用：二叉搜索树、堆、Huffman 树和 Huffman 编码。（五）图（1）图的基本概念。（2）图的存储（相邻矩阵表示和邻接表表示）及基本操作。（3）图的两种遍历策略：深度优先搜索和广度优先搜索。（4）图的基本应用：拓扑排序、最短路径、最小代价生成树。（六）查找（1）查找基本概念（2）顺序查找与折半查找
4、。（3）哈希表及其查找。（4）查找算法的分析与应用。（七）内排序（1）内排序的基本概念。（2）插入排序、起泡排序、简单选择排序、希尔排序、快速排序、堆排序、归并排序和基数排序。（3）各种内部排序算法的比较与应用。参考书：1张铭，王腾蛟，赵海燕。数据结构与算法，高等教育出版社，2008 年 6 月。2严蔚敏、吴伟民编著数据结构（C 语言版），清华大学出版。操作系统考查目标1.掌握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。2.掌握操作系统进程、内存、文件和 I/O 管理的策略、算法、机制以及相互关系。3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用
5、C 语言描述相关算法。考试内容一、操作系统概述(一)操作系统的概念、特征、功能和提供的服务(二)操作系统的发展与分类二、进程管理(一)进程与线程1.进程概念2.进程的状态与转换3.进程控制4.进程组织5.进程通信共享存储系统，消息传递系统，管道通信。6.线程概念与多线程模型(二)处理机调度1.调度的基本概念2.调度时机、切换与过程3.调度的基本准则4.调度方式5.典型调度算法先来先服务调度算法，短作业(短进程、短线程)优先调度算法，时间片轮转 调度算法，优先级调度算法，高响应比优先调度算法，多级反馈队列调度算法。(三)同步与互斥1.进程同步的基本概念2.实现临界区互斥的基本方法软件实现方法，硬
6、件实现方法。3.信号量4.管程5.经典同步问题生产者-消费者问题，读者-写者问题，哲学家进餐问题。(四)死锁1.死锁的概念2.死锁处理策略3.死锁预防4.死锁避免系统安全状态，银行家算法。5.死锁检测和解除三、内存管理(一)内存管理基础1.内存管理概念程序装入与链接，逻辑地址与物理地址空间，内存保护。2.连续分配管理方式3.非连续分配管理方式分页管理方式，分段管理方式，段页式管理方式。(二)虚拟内存管理1.虚拟内存基本概念2.请求分页管理方式3.页面置换算法最佳置换算法(OPT)，先进先出置换算法(FIFO)，最近最少使用置换算法(LRU)，时钟置换算法(CLOCK)。4.页面分配策略5.工作
7、集6.抖动四、文件管理(一)文件系统基础1.文件概念2.文件的逻辑结构顺序文件，索引文件，索引顺序文件。3.目录结构文件控制块和索引节点，单级目录结构和两级目录结构，树形目录结构，图形目录结构。4.文件共享(二)文件系统实现1.文件系统层次结构2.目录实现3.文件实现(三)磁盘组织与管理1.磁盘的结构2.磁盘调度算法3.磁盘的管理五、输入输出(I/O)管理(一)I/O 管理概述1.I/O 控制方式2. I/O 软件层次结构(二)I/O 核心子系统1.I/O 调度概念2.高速缓存与缓冲区3.设备分配与回收4.假脱机技术(SPOOLing)参考书：计算机操作系统（第四版），汤小丹等，西安电子科技大学出版社
