云南大学2016考研-831-《数据结构与操作系统》考试大纲
2016-07-06 10:35:43   来源：   评论：0 点击：

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

一、考查目标

数据结构和操作系统是计算机类专业的核心课程。《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，能够灵活应用相关的方法和技术解决实际问题。

二、考试形式与试卷结构

（一）试卷成绩及考试时间

本试卷满分为150分，考试时间为180分钟。

（二）答题方式

答题方式为闭卷、笔试。

（三）试卷内容结构

各部分内容所占分值为：

  数据结构    75分

  操作系统    75分

（四）试卷题型结构

1．数据结构

选择题：15小题，每小题2分，共30分

简答题：3小题，每小题10分，共30分

算法题：1小题，每小题 15分，共15分

2.操作系统

三、考查范围

数据结构

一、考查目标

1、掌握数据结构的基本概念、方法和技术。

2、掌握程序设计的基本方法和技巧。

3、能够应用相关知识解决一些有实际背景的问题。

二、考查内容

1. 绪论

 数据结构的概念；基本概念与术语；算法的概念，算法的特性，以及算法设计的要求，算法效率的度量。

2. 线性表

线性表相关的基本概念和结构特点；线性表的顺序存储方式以及两种不同的实现方法：表空间的静态分配和动态分配；线性表的链式存储方式的实现；链表与顺序表的相似及不同之处，优缺点比较，各自适用的场合；线性表的各种实现方式能够实现指定的操作。

3.栈和队

    栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队列等；栈与队列插入删除操作的特点；栈和递归的关系；栈和队列各种实现方式。

4. 串

 串的基本概念，朴素的模式匹配算法。

5.数组

数组的定义；数组的存储，行序和列序；     特殊矩阵的定义；特殊矩阵的压缩存储。

6.树和二叉树

  二叉树的概念；二叉树的五个性质；二叉树的存储结构：顺序存储和二叉链表存储的各自优缺点及适用场合；二叉树的三种遍历方法：先序，中序和后序；线索二叉树，线索化后二叉树的遍历方法；哈夫曼树概念，哈夫曼树的构造方法，前缀码概念，哈夫曼编码。树的存储表示方法，树与森林转化为二叉树，树和森林的遍历问题。

7. 图

图的基本概念，图的定义和特点；图的几种存储形式，重点是邻接矩阵和邻接表；深度遍历和广度遍历是图的两种基本的遍历算法；生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法；有向无环图，拓扑排序和关键路径问题；最短路径问题：DIJSKTRA算法和FLOYD算法。

8. 查找

   关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果；顺序表的查找，折半查找，索引顺序表；二叉排序树，平衡二叉树，B树；哈希表的概念，哈希函数的设计，冲突解决方法的选择及冲突处理过程。

9. 内排序

要求掌握各种排序方法的思想和算法实现，排序算法稳定性的概念，以及各自的特点。插入排序：直接插入、折半插入、2路插入、希尔排序；冒泡排序，快速排序；选择排序：简单选择、树选择、堆排序；归并排序；基数排序。

操作系统

一、考查目标

1、了解操作系统在计算机系统中的作用、地位、发展和特点。

2、了解操作系统的基本概念、原理，掌握操作系统实现技术。

3、能够运用所学的操作系统原理、方法与技术分析和解决问题。

二、考查内容

1.操作系统概述

操作系统的概念、特征、功能和提供的服务；操作系统的发展与分类。

2．用户界面

作业的概念及作业的建立过程、SPOOLING系统；命令控制界面接口

3．CPU管理

（1）.进程与线程，进程的概念，进程的状态与转换，进程控制，进程互斥与同步和经典问题，死锁的概念，处理策略，死锁的预防，死锁的避免

（2）.处理机调度

调度的基本概念，调度的目标、功能与性能衡量指标，典型调度算法：先来先服务、短作业（短进程）优先、时间片轮转、优先级、最高响应比优先、多级反馈轮转调度。

4、存储管理

存储管理的功能：虚拟存储器、地址变换、内外存数据传输的控制、内存的分配与回收、内存信息的共享与保护；分区存储管理，覆盖与交换技术，请求页式管理，请求页式管理中的置换算法：先进先出置换算法（FIFO）、最近最少置换算法（LRU）、最佳置换算法（OPT）、时钟置换算法（CLOCK），段式与段页式管理， 局部性原理和抖动问题

5、文件管理

文件系统的概念、功能，常用的文件的逻辑结构与存取方法，文件的物理结构与存取设备：连续文件、串联文件、索引文件，磁盘组织与管理:磁盘调度算法，文件存储空间管理：空闲文件目录、空闲块链、位示图，单级目录、两级级目录、多级目录，文件存取控制，文件系统的层次模型

6、设备管理

设备管理的目的、设备管理的功能和任务，数据传输控制方式：DMA技术、通道技术与Ｉ/Ｏ中断处理技术，中断技术：中断的概念、中断的分类、软中断、中断的处理过程，缓冲技术：缓冲的种类、缓冲池的管理，设备分配：设备分配的数据结构、分配原则和分配算法，Ｉ/Ｏ进程控制：Ｉ/Ｏ进程控制功能与实现