西南石油大学2023年硕士研究生招生专业课考试大纲
考试科目名称：925计算机学科综合(数据结构+操作系统)
一、考试性质
《计算机学科综合(数据结构+ 操作系统)》是硕士研究生入学考试科目之一，是硕士研究生招生院校自行命题的选拔性考试。本考试大纲的制定力求反映招生类型 的特点，科学、公平、准确、规范地测评考生的相关基础知识掌握水平，考生分析问 题和解决问题及综合知识运用能力。应考人员应根据本大纲的内容和要求自行组织学 习内容和掌握有关知识。
本科目包含数据结构及操作系统两门课程。考试时间共 180 分钟。两门课程各75 分。
数据结构主要包括三大常用数据结构的逻辑、物理表示与基本操作算法实现部分的知识，各种结构的经典应用和具体问题求解。考生应掌握各种数据结构及其操作，具备一定的算法设计与分析能力，能够根据实际问题选择合适的数据结构并设计算法实现。
操作系统主要包括其对各种计算机硬、软件资源的管理方法的理论与应用学习。考生应掌握操作系统的基本概念、原理和基本功能，掌握操作系统中进程、内存、 文件和 I/O 管理的策略、算法、机制以及相互关系，并能够运用所学的原理、方法 与技术分析和解决实际问题以及代码实现。
二、考试主要内容
(一)数据结构
1、绪论
(1)基本概念和术语
基本要求：了解课程的研究内容，理解数据结构的相关概念。
考试范围：掌握数据结构的研究内容、基本概念和相关术语;理解抽象数据类型的表示与实现。
(2)算法和算法分析
基本要求：理解算法的含义，熟悉算法描述语言，掌握算法的性能评价指标及评价方法,并能分析常用算法的时间复杂度。
考试范围：算法的概念与特征;算法效率的度量指标;时间复杂度与空间复杂度的计算方法; 常见时间复杂度类型与性能优劣比较。
2、线性表
(1)线性表的类型定义
基本要求：掌握线性表的逻辑结构及相关概念;理解线性表的抽象数据类型。考试范围：线性表的概念及文件、数据项及记录的相关概念;线性表的抽象数据类型;用线性表表示集合合并的算法;合并有序线性表的算法。
(2)线性表的表示和实现
基本要求：掌握线性表的顺序与链式两种存储结构及其各种基本运算的的实现过程;掌握两 种存储方式之间的差异及各自优缺点;能够灵活运用顺序表和链表解决实际问题。
考试范围：顺序存储结构的概念及计算第 i 个元素存储地址的公式;用类 C 描 述线性表的顺序存储结构;顺序表的初始化、插入、删除、定位和有序表合并算法;线性链表及相关概念;用 C 语言描述线性表的链式存储结构;链表的访问、插入、 删除和有序合并算法;线性表的静态链表表示基本定义;循环链表的定义以及与单链表的区别;双向链表的定义和存储表示;双向链表的插入与删除算法;一元多项式的表示及相加算法实现。
3、栈和队列
(1)栈
基本要求：理解栈的定义、特性和运算;掌握栈的顺序存储实现及其性能分析;理解和掌握用栈实现表达式求解的过程;了解栈的链式存储结构的实现。
考试范围：栈的抽象数据类型定义;栈的先进后出特性;栈的存储表示与基本操作实现;栈的应用。
(2)队列
基本要求：理解队列的定义、特性和运算;理解队列的顺序存储实现及其性能分析;理解循环队列的背景和实现方法;理解队列的链式存储结构的实现及其性能分析。
考试范围：队列的抽象数据类型定义;队列的先进先出特性;队列的存储表示与基本操作实现。
4、串
基本要求：掌握串的相关概念、串的存储结构(顺序串和链式串)及基本运算的实现;掌握KMP 算法的基本思想及模式匹配过程;能灵活运用串的特点解决复杂的应用问题。
考试范围：串类型的定义;串的定长顺序存储、堆分配存储、块链存储表示和实现;串的模式匹配算法;串的应用。
5、数组和广义表
基本要求：理解数组结构及其存储，理解矩阵的压缩存储方式及其映射关系;理解广义表以及子表、原子和长度等概念;理解广义表的基本运算及其存储。
考试范围：数组的定义;二维数组的两种存储方式(以行序为主、以列序为主)及其数组元素存储位置计算公式;特殊矩阵与稀疏矩阵的压缩存储方式;广义表的定义和存储结构。
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
