1附件 2：930 数据结构考试科目大纲一、考试性质数据结构是硕士研究生入学考试科目之一，是硕士研究生招生院校自行命题的选拔性考试。本考试大纲的制定力求反映招生类型的特点，科学、公平、准确、规范地测评考生的相关基础知识掌握水平，考生分析问题和解决问题及综合知识运用能力。应考人员应根据本大纲的内容和要求自行组织学习内容和掌握有关知识。本大纲主要包括三大常用数据结构的逻辑、物理表示与基本操作算法实现部分的知识，各种结构的经典应用和具体问题求解。考生应掌握各种数据结构及其操作，具备一定的算法设计与分析能力，能够根据实际问题选择合适的数据结构并设计算法实现。二、评价目标(1)要求考生具有较全面的数据结构表示与实现的基础知识。(2)要求考生具有较高的分析问题和解决问题的能力。(3)要求考生具有较强的综合知识运用能力。三、考试内容（一）绪论1、基本概念和术语1）基本要求了解课程的研究内容，理解数据结构的相关概念。 2）考试范围掌握数据结构的研究内容、基本概念和相关术语；理解抽象数据类型的表示与实现。2、算法和算法分析21）基本要求理解算法的含义，熟悉算法描述语言，掌握算法的性能评价指标及评价方法,并能分析常用算法的时间复杂度。2）考试范围算法的概念与特征；算法效率的度量指标；时间复杂度与空间复杂度的计算方法；常见时间复杂度类型与性能优劣比较。（二）线性表1、线性表的类型定义1）基本要求掌握线性表的逻辑结构及相关概念；理解线性表的抽象数据类型。2）考试范围线性表的概念及文件、数据项及记录的相关概念；线性表的抽象数据类型；用线性表表示集合合并的算法；合并有序线性表的算法。2、线性表的表示和实现1）基本要求掌握线性表的顺序与链式两种存储结构及其各种基本运算的的实现过程；掌握两种存储方式之间的差异及各自优缺点；能够灵活运用顺序表和链表解决实际问题。2）考试范围顺序存储结构的概念及计算第 i 个元素存储地址的公式；用类 C 描述线性表的顺序存储结构；顺序表的初始化、插入、删除、定位和有序表合并算法；线性链表及相关概念；用 C 语言描述线性表的链式存储结构；链表的访问、插入、删除和有序3合并算法；线性表的静态链表表示基本定义；循环链表的定义以及与单链表的区别；双向链表的定义和存储表示；双向链表的插入与删除算法；一元多项式的表示及相加算法实现。（三）栈和队列1、栈1）基本要求理解栈的定义、特性和运算；掌握栈的顺序存储实现及其性能分析；理解和掌握用栈实现表达式求解的过程；了解栈的链式存储结构的实现。2）考试范围栈的抽象数据类型定义；栈的先进后出特性；栈的存储表示与基本操作实现；栈的应用。2、队列1）基本要求理解队列的定义、特性和运算；理解队列的顺序存储实现及其性能分析；理解循环队列的背景和实现方法；理解队列的链式存储结构的实现及其性能分析。2）考试范围队列的抽象数据类型定义；队列的先进先出特性；队列的存储表示与基本操作实现。（四）串1）基本要求掌握串的相关概念、串的存储结构（顺序串和链式串）及基本4运算的实现；掌握 KMP 算法的基本思想及模式匹配过程；能灵活运用串的特点解决复杂的应用问题。2）考试范围：串类型的定义；串的定长顺序存储、堆分配存储、块链存储表示和实现；串的模式匹配算法；串的应用。（五）数组和广义表1）基本要求理解数组结构及其存储，理解矩阵的压缩存储方式及其映射关系；理解广义表以及子表、原子和长度等概念；理解广义表的基本运算及其存储。2）考试范围：数组的定义；二维数组的两种存储方式（以行序为主、以列序为主）及其数组元素存储位置计算公式；特殊矩阵与稀疏矩阵的压缩存储方式；广义表的定义和存储结构。（六）树和二叉树1）基本要求理解树和二叉树的定义及相关术语；理解二叉树的五个性质及相关概念；理解二叉树的两种存储结构的形式、描述及特点，理解二叉树的遍历运算，并能综合应用；理解线索二叉树及其存储结构，线索化方法和算法，以及在指定线索二叉树中求解指定次序的前趋和后继的算法；理解树和森林的存储结构及其描述，树（森林）与二叉树的相互转换，树（森林）的遍历算法；理解树模型在软件设计中的作用；理解赫夫曼树的有关概念、应用及构造。2）考试范围：5树的定义和基本术语；二叉树的定义；二叉树的性质；二叉树的存储结构；遍历二叉树；线索二叉树；树的存储结构；森林与二叉树的转换；树和森林的遍历；最优二叉树（赫夫曼树） ；赫夫曼编码。（七）图1）基本要求理解图的相关概念、图的存储结构；熟练掌握图的两种遍历算法（深度优先搜索遍历和广度优先搜索遍历） ，并能灵活应用；熟练掌握求解最小生成树的算法；熟练掌握拓扑排序算法和关键路径算法，并能灵活应用；熟练掌握最短路径算法并能灵活应用。2）考试范围：图的定义和术语；图的数组表示法与邻接表存储结构；图的深度优先搜索与广度优先搜索；最小生成树；拓扑排序；关键路径；最短路径。（八）查找1）基本要求理解查找的相关概念，理解简单顺序查找、折半查找算法及性能分析；理解二叉排序树的定义、特性和查找算法，二叉排序树的构造、插入结点的算法和删除结点的实现方法；理解平衡二叉树的定义及构造平衡二叉树的方法；理解-树的定义、特性和查找方法，理解在-树中插入和删除关键字的运算实现；理解散列表结构的相关概念和构造散列函数的基本方法；理解冲突及其处理的基本方法；理解哈希查找过程；掌握上述各种查找算法的时间性能分析。2）考试范围：6顺序表的查找；有序表的查找；索引顺序表的查找；二叉排序树和平衡二叉树；B-树和 B+树；什么是哈希表；哈希函数的构造方法；处理冲突的方法；哈希表的查找及分析。（九）内部排序1）基本要求理解排序的相关概念；理解直接插入排序、Shell 排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序等算法的基本思想、算法实现、时间复杂度和空间占用情况，并能根据具体问题选择合适的算法。2）考试范围：排序概述；插入排序；交换排序；选择排序；归并排序；各种内部排序方法的分析比较。四、考试形式和试卷结构（一）考试时间考试时间为 180 分钟。（二）答题方式答题方式为闭卷、笔试。试卷由试题和答题纸组成。答案必须写在答题纸相应的位置上。（三）试卷满分及考查内容分数分配试卷满分为 150 分。（四）试卷题型比例1、单项选择题（27）：每个问题都只有一个选择，根据题目7内容选择正确答案。2. 填空题（13）：根据题目要求，填充对应位置的内容。3. 判断题（7）：根据题目内容判断其描述问题的正确性。4. 应用题（30）：根据题目内容完成相应问题的求解，要求给出具体求解过程。5算法设计题（23）：根据题目要求，采用类 C 语言或 C语言完成算法的编写，解决实际问题。五、样卷1、单项选择题1、在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 逻辑 B 存储C 逻辑和存储 D 物理2、填空题，请在下划线上填写答案。1、若一个算法中的语句频度之和为 T(n)=3720n+4nlogn，则算法的时间复杂度为 。3、判断题（正确画，错误画× ）1、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 4、应用题5、算法设计题略