6、树和二叉树
基本要求:理解树和二叉树的定义及相关术语;理解二叉树的五个性质及相关 概念;理解二叉树的两种存储结构的形式、描述及特点，理解二叉树的遍历运算， 并能综合应用;理解线索二叉树及其存储结构，线索化方法和算法，以及在指定线 索二叉树中求解指定次序的前趋和后继的算法;理解树和森林的存储结构及其描述，树(森林)与二叉树的相互转换，树(森林)的遍历算法;理解树模型在软件设计 中的作用;理解赫夫曼树的有关概念、应用及构造。
考试范围:树的定义和基本术语;二叉树的定义;二叉树的性质;二叉树的存储结构;遍历二叉树;线索二叉树;树的存储结构;森林与二叉树的转换;树和森林的遍历; 最优二叉树(赫夫曼树);赫夫曼编码。
7、图
基本要求:理解图的相关概念、图的存储结构;熟练掌握图的两种遍历算法(深度优先搜索遍历和广度优先搜索遍历)，并能灵活应用;熟练掌握求解最小生成树的算法;熟练掌握拓扑排序算法和关键路径算法，并能灵活应用;熟练掌握最短路径算法并能灵活应用。
考试范围:图的定义和术语;图的数组表示法与邻接表存储结构;图的深度优先搜索与广度优先搜索;最小生成树;拓扑排序;关键路径;最短路径。
8、查找
基本要求:理解查找的相关概念，理解简单顺序查找、折半查找算法及性能分析;理解二叉排序树的定义、特性和查找算法，二叉排序树的构造、插入结点的算法和删除结点的实现方法;理解平衡二叉树的定义及构造平衡二叉树的方法;理解b-树的定义、特性和查找方法，理解在b-树中插入和删除关键字的运算实现;理
解散 列表结构的相关概念和构造散列函数的基本方法;理解冲突及其处理的基本方法; 理解哈希查找过程;掌握上述各种查找算法的时间性能分析。
考试范围:顺序表的查找;有序表的查找;索引顺序表的查找;二叉排序树和平衡二叉树; b-树和 b+树;什么是哈希表;哈希函数的构造方法;处理冲突的方法;哈希表的查找及分析。
9、内部排序
基本要求:理解排序的相关概念;理解直接插入排序、shell 排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序等算法的基本思想、算法实现、时间复杂度和空间占用情况，并能根据具体问题选择合适的算法。
考试范围:排序概述;插入排序;交换排序;选择排序;归并排序;各种内部排序方法的分析比较。
(二)操作系统
1、操作系统引论
(1)操作系统的基本概念
基本要求:理解操作系统的基本概念、作用和常见操作系统。
考试范围:操作系统的定义、目标、在计算机系统中的地位与作用，主流操作系统概况。
(2)操作系统的发展过程
基本要求:理解操作系统的发展特点，掌握发展过程中基本操作系统类型特点和其中的一些关键技术，理解现代多种操作系统类型特点。
考试范围:脱机/联机 i/o 技术、多道程序设计技术、多道批处理系统、分时系统、实时系统、微机操作系统、分布式系统、嵌入式系统。
(3)操作系统的功能与结构
基本要求:理解操作系统的主要功能及概念，掌握操作系统的特征及其含义，理解操作系统的各种结构特征。
考试范围:操作系统的主要功能及同步、地址映射、逻辑扩充内存等基本概念;操作系统的基本特征;操作系统的结构设计，微内核技术、内核态与用户态。
2、进程管理
(1)进程的基本概念
基本要求:掌握进程引入的原因和基本概念，掌握进程与程序的不同与特性;掌握进程的三状态转换模型，理解挂起状态的含义;掌握进程控制块 pcb 的作用和组成，理解pcb 的组织方法。
考试范围:程序的顺序与并发执行的特点、进程的引入、进程的概念与特性、进程与程序的比较、进程的三状态模型、五状态模型、挂起状态、进程控制块的作用、内容与组织
(2)进程的控制
基本要求:理解和掌握原语的含义、进程创建与撤销的主要工作;了解常见操作系统的进程控制方法
考试范围:原语、进程控制方法与过程
(3)进程同步
基本要求:理解进程同步要解决的制约关系，掌握同步处理的基本概念与原则，理解硬件同步方案的特点，掌握信号量机制及其解决实际同步问题的方法与实现， 掌握管程机制的思想与基本概念。
考试范围:进程的制约类型、临界资源、临界区、进程同步设计的原则，进程同步的硬件方法、信号量机制及其应用、管程机制、经典进程同步问题(生产者消费者问题、读者写者问题、哲学家就餐问题)。
(4)进程通信
基本要求:掌握进程通信的基本概念，理解进程通信的基本类型及其特点。
考试范围:进程通信的基本概念、进程通信的类型、基本进程通信类型(共享存储器、消息传递系统、管道)的实现原理与特点。
(5)线程技术
基本要求:掌握线程引入的原因，掌握线程相比进程的不同与优势，理解多线程实现的几种模型特点，理解多线程技术的应用领域。
考试范围:线程的引入、线程与进程的比较、多线程模型、线程技术的应用
3、处理机调度与死锁
(1)处理机调度及算法
基本要求:掌握处理机调度三个层次的主要任务，掌握调度算法与方式选择的原则;掌握多种调度算法的 fcfs、sjb、hpf、hrrn、rr、mlfq 的调度思想与特点，能熟练运用上述算法对实际调度问题进行调度与分析性能。
考试范围:处理机调度的层次及任务、各级调度算法选择的准则，作业调度的过程，作业调度算法 fcfs、sjb、hpf(hrrn)的调度思想与特点，进程调度实现方法，调度方式，调度算法rr/多级反馈队列 mlfq 等的思想与特点。
(2)死锁
基本要求:理解和掌握死锁的基本概念，包括定义、产生原因与必要条件;掌 握死锁预防的思想，区别破坏不同必要条件的资源分配方法;掌握死锁避免的思想，并熟练使用银行家算法进行系统安全状态判断与进程推进控制;理解死锁检测与解 除的思想。
考试范围:死锁的定义、产生原因、必要条件，死锁的几种预防方法，死锁的避免思想与银行家算法，死锁的检测和解除方法。
4、存储器管理
(1)存储器管理概述
基本要求:掌握存储器管理实现的基本功能，了解程序链接与装入各种方式的特点。
考试范围:存储器管理的功能、地址重定位、内存保护，程序的链接与装入方式。
(2)连续分配方式
基本要求:理解连续分配方式的思想，了解单一分区与固定分区分配的思想与特点;掌握动态分区分配的思想以及功能实现方法，掌握分区分配出现的碎片问题以及解决方案。
考试范围:连续分配方式思想以及单一分区、固定分区、动态分区分配思想、分配与回收过程、分配算法、碎片问题及其处理、可重定位分区分配。
(3)离散分配方式
基本要求:掌握基本分页技术的思想，掌握页表的内容与作用，熟练掌握分页系统下地址映射的基本方法;理解分页技术下越界与越权的判定方法，掌握 tlb 的作用以及性能分析方法;初步掌握多级页表的思想与基本特点;掌握分段技术的基本思想， 理解和掌握分段技术与分页技术的异同;初步掌握段页式存储管理方案的思想与地址映射方法。
考试范围:基本分页技术的思想、数据结构、地址映射方法、存储保护、tlb的引入、多级页表及其特点;基本分段技术的思想、数据结构、地址映射方法、存储保护;分段与分页技术的对比，段页式存储管理方案的思想与实现方法、地址映射过程等。
(4)逻辑扩充内存技术
基本要求:了解覆盖和交换技术的思想，掌握程序局部性原理，掌握虚拟存储技术的思想与特点。
考试范围:覆盖技术、交换技术、虚拟存储技术。
(5)虚拟存储管理方案
基本要求:掌握请求分页技术的基本思想，掌握请求分页方案的页表设计，理解缺页处理方法与特点，理解请求分页方案下分配策略、调入策略的设计;掌握请求分段技术的思想。
考试范围:请求分页技术的思想、实现的硬件支持(页表、缺页中断机构、地址映射机构) 和软件策略设计(分配策略、调入策略、调入时机)、请求分段技术的思想。
(6)页面置换算法
基本要求:理解页面置换策略的用途，掌握 opt、fifo、clock、lru、工作 集等页面置换算法的思想与特点;理解置换性能与抖动现象的影响因素;能熟练运 用 opt、fifo、clock、lru 算法进行实际页面置换问题的解决与性能分析。
考试范围:页面置换算法概述、opt、fifo、clock、lru、工作集等页面置换算法思想、效率与置换性能分析、缺页率的影响因素、抖动现象及其影响因素。
5、i/o 系统
(1)i/o 系统概述
基本要求:理解 i/o 系统的基本功能，理解并掌握 i/o 系统软件层次的设计方法;掌握 io设备的范畴与分类，掌握通道的含义与作用。
考试范围:i/o 系统的管理对象、i/o 系统功能、i/o 系统软件设计的层次、i/o 设备基本情况、分类与特点，设备控制器的功能与组成、管理方法，通道的基本概念与类型。
(2)i/o 中断与设备驱动
基本要求:理解中断技术的意义，理解中断技术的基本概念，掌握中断处理的方式与过程; 掌握设备驱动程序的功能，理解设备四种 io 控制方式及特点。
考试范围:中断技术的意义、中断向量表、中断优先级、中断处理方式、中断处理过程、设备驱动程序功能与特点、i/o 控制方式及其特点。
(3)设备独立性与用户i/o 层软件
基本要求:掌握设备独立性的含义;理解与初步掌握设备分配的数据结构与分配过程;掌握缓冲技术的引入原因、思想，理解常见缓冲技术的思想与特点;掌握
spooling 系统的组成与特点。
考试范围:设备独立性层功能，逻辑设备名与物理设备名、设备分配的数据结构、分配算法、方式与分配过程，缓冲技术的引入原因、常见的软件缓冲技术及特点，用户 i/o 层软件功能，spooling 技术。
6、磁盘磁盘管理
基本要求:掌握磁盘的结构和物理地址组成，理解磁
盘的访问过程，掌握四类磁盘调度算法的思想与特点;了解提高磁盘可靠性的方法。
考试范围:磁盘结构、磁盘物理地址，磁盘的访问过程与访问时间组成，磁盘调度算法(fcfs、sstf、scan、cscan)，磁盘可靠性的 3 级容错技术、磁盘阵列。
7、文件系统
(1)文件与文件系统
基本要求:理解文件与文件系统的基本概念;掌握文件逻辑结构的类型与特点;
掌握文件的存取方法及其特点;掌握文件的三种物理结构类型与特点;理解目录结构的功能，与基本概念，掌握目录结构的类型与特点，理解目录结构的改进方法。掌握文件空间管理的位示图法和成组链接法的思想与特点。
考试范围:文件的引入/定义、文件系统的功能及结构、文件的逻辑结构类型及 特点、文件的存取方法及特点、文件的连续/链接(显式/隐式)/索引结构及其特点，目录管理的目 标、基本概念、目录结构、目录的改进、索引节点、基于索引节点的 文件共享方法、文件空间管理的位示图法和成组链接法的思想与特点。
三、考试形式和试卷结构
1、考试时间和分值
闭卷笔试，考试时间为 180 分钟，试卷满分为 150 分。两门课程各占75。
2、考试题型结构
(1)单项选择题:每个问题都只有一个选择，根据题目内容选择正确答案。
(2)填空题:根据题目要求，填充对应位置的内容。
(3)判断题:根据题目内容判断其描述问题的正确性。
(4)应用及算法设计题:根据题目内容完成相应问题的求解，要求给出具体求解过程。
四、参考书目
1、《数据结构》(c 语言版)，严蔚敏，吴伟民主编，清华大学出版社，2018
2、《计算机操作系统》第四版，汤小丹等编著，电子科技大学出版社，2018
原标题:西南石油大学2023年硕士研究生入学考试初试校自命题科目复习大纲
文章来源:https://www.swpu.edu.cn/gs/info/1074/3906.htm