《数据结构》考试大纲

　　一、考试性质

　　本大纲用于专科毕业生升学普通高等学校本科的选拔性考试。适用于所有需要参加《数据结构》考试的各专业考生。

　　二、考试内容

　　总要求：考生按本大纲的要求掌握本课程的基本理论、基本知识和基本分析问题的方法，以及各种数据结构(物理结构和逻辑结构)的概念及其算法;掌握线性表、树、二叉树、图等算法的时间复杂度和空间复杂度分析方法;熟练掌握各种查找和排序的算法思想，掌握各种查找和排序算法的时间复杂度和空间复杂度分析方法。掌握以抽象数据类型ADT的观点来组织线性表、树、二叉树、图等主要的数学模型，包括数据对象的逻辑结构和物理存储结构，并能够通过相关算法实现其功能;具备熟练运用各种查找和排序算法解决实际问题的能力。具备应用数据结构和算法的基本能力。

　　第一章 绪论

　　【要求】

　　了解抽象数据类型的表示与实现;了解数据结构的基本概念;掌握数据结构的相关概念及术语;掌握算法的概念及算法分析方法。

　　【重点、难点】

　　数据的逻辑结构和存储结构、抽象数据类型以及时间及空间复杂度的分析。

　　【知识范围】

　　1.1什么是数据结构

　　1.2 基本概念和术语

　　1.3 抽象数据类型的表示与实现

　　1.4 算法和算法分析

　　1.4.1 算法

　　1.4.2 算法设计的要求

　　1.4.3 算法效率的度量

　　1.4.4 算法的存储空间要求

　　第二章 线性表

　　【要求】

　　了解线性表的类型定义;掌握线性表的顺序表示和实现;掌握线性表的链式表示和实现;掌握循环链表和双向链表;了解一元多项式的表示及相加。

　　【重点、难点】

　　链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。

　　【知识范围】

　　2.1 线性表的类型定义

　　2.2 线性表的顺序表示和实现

　　2.3 线性表的链式表示和实现

　　2.3.1 线性链表

　　2.3.2 循环链表

　　2.3.3 双向链表

　　2.4 一元多项式的表示及相加

　　第三章 栈和队列

　　【要求】

　　了解栈的定义及性质;掌握栈的基本操作的算法实现;掌握栈的基本应用;了解队列定义及基本性质;掌握队列的基本操作及算法实现;了解循环队列的基本内容。

　　【重点、难点】

　　栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。

　　【知识范围】

　　3.1 栈

　　3.1.1 抽象数据类型栈的定义

　　3.1.2 栈的表示和实现

　　3.2 栈的应用举例

　　3.2.1 数制转换

　　3.2.2 括号匹配的检验

　　3.2.3 行编辑程序

　　3.2.4 迷宫求解

　　3.2.5 表达式求值

　　3.3 栈与递归的实现

　　3.4 队列

　　3.4.1 抽象数据类型队列的定义

　　3.4.2 链队列

　　3.4.3 循环队列

　　3.5 离散事件模拟

　　第四章 串

　　【要求】

　　了解串的类型定义;掌握串的表示和实现;了解串的模式匹配算法;掌握串的应用。

　　【重点、难点】

　　相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想。

　　【知识范围】

　　4.1 串的类型定义

　　4.2 串的表示和实现

　　4.2.1 定长顺序存储表示

　　4.2.2 堆分配存储表示

　　4.2.3 串的块链存储表示

　　4.3 串的模式匹配算法

　　4.3.1 求子串位置的定位函数Index(S,T,pos)

　　4.3.2 模式匹配的一种改进算法

　　4.4 串的应用举例

　　4.4.1 文本编辑

　　4.4.2 建立词索引表

　　第五章 数组和广义表

　　【要求】

　　了解数组的定义;掌握数组的顺序表示和实现;掌握矩阵的压缩存储;了解广义表的定义及存储结构。

　　【重点、难点】

　　本章重点是学习数组类型的定义及其存储表示。

　　【知识范围】

　　5.1 数组的定义

　　5.2 数组的顺序表示和实现

　　5.3 矩阵的压缩存储

　　5.3.1 特殊矩阵

　　5.3.2 稀疏矩阵

　　5.4 广义表的定义

　　5.5 广义表的存储结构

　　5.6 m元多项式的表示

　　5.7 广义表的递归算法

　　5.7.1 求广义表的深度

　　5.7.2 复制广义表

　　5.7.3 建立广义表的存储结构

　　第六章 树和二叉树

　　【要求】

　　掌握树及二叉树的定义;了解树及二叉树的相关术语;掌握二叉树的基本性质，掌握二叉树的存储结构;掌握二叉树的遍历及应用;了解线索二叉树的定义;掌握二叉树的线索化应用;掌握树的存储结构及树的遍历;掌握森林与二叉树的转换方法;掌握赫夫曼树的定义及构造过程;掌握赫夫曼树的应用。

　　【重点、难点】

　　二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。

　　【知识范围】

　　6.1 树的定义和基本术语

　　6.2 二叉树

　　6.2.1二叉树的定义

　　6.2.2二叉树的性质

　　6.2.3二叉树的存储结构

　　6.3 遍历二叉树和线索二叉树

　　6.4 树和森林

　　6.4.1 树的存储结构

　　6.4.2 森林与二叉树的转换

　　6.4.3 树和森林的遍历

　　6.5 树与等价问题

　　6.6 赫夫曼树及其应用

　　6.6.1 最优二叉树

　　6.6.2 赫夫曼编码

　　6.7 回溯法与树的遍历

　　6.8 树的计数

　　第七章 图

       新起点25/26届专升本英语VIP协议班上线，开启备考之旅！

　　专升本全科协议班上新，助力24专升本备考!

　　如果有专升本报考问题咨询，欢迎扫码关注微信公众号新起点培训学校，有专业老师免费解答。