2020年云南大学831数据结构与操作系统考研大纲

云南大学 1
《数据结构与操作系统》硕士研究生入学考试大纲
一、考查目标
数据结构和操作系统是计算机类专业的核心课程。《数据结构和操
作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，
要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，
能够灵活应用相关的方法和技术解决实际问题。
二、考试形式与试卷结构
（一）试卷成绩及考试时间
本试卷满分为 150 分，考试时间为 180 分钟。
（二）答题方式
答题方式为闭卷、笔试。
（三）试卷内容结构
各部分内容所占分值为：
数据结构 75 分
操作系统 75 分
（四）试卷题型结构
1．数据结构
选择题：15 小题，每小题 2 分，共 30 分
简答题：3 小题，每小题 10 分，共 30 分
算法题：1 小题，每小题 15 分，共 15 分
2.操作系统
三、考查范围
数据结构
一、考查目标
1、掌握数据结构的基本概念、方法和技术。
2、掌握程序设计的基本方法和技巧。
3、能够应用相关知识解决一些有实际背景的问题。
二、考查内容
1. 绪论
数据结构的概念；基本概念与术语；算法的概念，算法的特性，以
及算法设计的要求，算法效率的度量。
2. 线性表
2
线性表相关的基本概念和结构特点；线性表的顺序存储方式以及两
种不同的实现方法：表空间的静态分配和动态分配；线性表的链式存储
方式的实现；链表与顺序表的相似及不同之处，优缺点比较，各自适用
的场合；线性表的各种实现方式能够实现指定的操作。
3.栈和队
栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链
栈，共享栈，循环队列，链队列等；栈与队列插入删除操作的特点；栈
和递归的关系；栈和队列各种实现方式。
4. 串
串的基本概念，朴素的模式匹配算法。
5.数组
数组的定义；数组的存储，行序和列序； 特殊矩阵的定义；特殊矩
阵的压缩存储。
6.树和二叉树
二叉树的概念；二叉树的五个性质；二叉树的存储结构：顺序存
储和二叉链表存储的各自优缺点及适用场合；二叉树的三种遍历方法：
先序，中序和后序；线索二叉树，线索化后二叉树的遍历方法；哈夫曼
树概念，哈夫曼树的构造方法，前缀码概念，哈夫曼编码。树的存储表
示方法，树与森林转化为二叉树，树和森林的遍历问题。
7. 图
图的基本概念，图的定义和特点；图的几种存储形式，重点是邻接
矩阵和邻接表；深度遍历和广度遍历是图的两种基本的遍历算法；生成
树、最小生成树的概念以及最小生成树的构造：PRIM 算法和 KRUSKAL
算法；有向无环图，拓扑排序和关键路径问题；最短路径问题：
DIJSKTRA 算法和 FLOYD 算法。
8. 查找
关键字、主关键字、次关键字的含义；静态查找与动态查找的含
义及区别；平均查找长度 ASL 的概念及在各种查找算法中的计算方法
和计算结果；顺序表的查找，折半查找，索引顺序表；二叉排序树，平
3
衡二叉树，B 树；哈希表的概念，哈希函数的设计，冲突解决方法的选
择及冲突处理过程。
9. 内排序
要求掌握各种排序方法的思想和算法实现，排序算法稳定性的概念，
以及各自的特点。插入排序：直接插入、折半插入、2 路插入、希尔排
序；冒泡排序，快速排序；选择排序：简单选择、树选择、堆排序；归
并排序；基数排序。
操作系统
一、考查目标
1、了解操作系统在计算机系统中的作用、地位、发展和特点。
2、了解操作系统的基本概念、原理，掌握操作系统实现技术。
3、能够运用所学的操作系统原理、方法与技术分析和解决问题。
二、考查内容
1.操作系统概述
操作系统的概念、特征、功能和提供的服务；操作系统的发展与分
类。
2．用户界面
作业的概念及作业的建立过程、SPOOLING 系统；命令控制界面接
口
3．CPU 管理
（1）.进程与线程，进程的概念，进程的状态与转换，进程控制，进
程互斥与同步和经典问题，死锁的概念，处理策略，死锁的预防，死锁
的避免
（2）.处理机调度
调度的基本概念，调度的目标、功能与性能衡量指标，典型调度算
法：先来先服务、短作业（短进程）优先、时间片轮转、优先级、最高
响应比优先、多级反馈轮转调度。
4、存储管理
存储管理的功能：虚拟存储器、地址变换、内外存数据传输的控制、
内存的分配与回收、内存信息的共享与保护；分区存储管理，覆盖与交
换技术，请求页式管理，请求页式管理中的置换算法：先进先出置换算
法（FIFO）、最近最少置换算法（LRU）、最佳置换算法（OPT）、时钟
4
置换算法（CLOCK），段式与段页式管理， 局部性原理和抖动问题
5、文件管理
文件系统的概念、功能，常用的文件的逻辑结构与存取方法，文件
的物理结构与存取设备：连续文件、串联文件、索引文件，磁盘组织与
管理:磁盘调度算法，文件存储空间管理：空闲文件目录、空闲块链、
位示图，单级目录、两级级目录、多级目录，文件存取控制，文件系统
的层次模型
6、设备管理
设备管理的目的、设备管理的功能和任务，数据传输控制方式：DMA
技术、通道技术与Ｉ/Ｏ中断处理技术，中断技术：中断的概念、中断
的分类、软中断、中断的处理过程，缓冲技术：缓冲的种类、缓冲池的
管理，设备分配：设备分配的数据结构、分配原则和分配算法，Ｉ/Ｏ
进程控制：Ｉ/Ｏ进程控制功能与实现