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