一、概念。
1、数据结构研究的内容；数据逻辑结构和数据存储结构及其分类；时间复杂度和空间复杂度。
2、线性表定义、特性及两种存储结构的的类的描述。
3、队列、栈的定义及特点，栈（链栈与顺序栈）及循环队列（循环顺序队列和循环链队列）的判空、判满条件。
4、树的有关概念。
树、二叉树、满二叉树、完全二叉树；
二叉树的基本形态、二叉树的性质；
二叉链表的存储结构及类的描述；
森林、树、二叉树的遍历及其对应关系；
哈夫曼树（最优二叉树）。
5、串的几种基本操作的定义(截子串、串的连接、串的定位（查找）等)
6、数组、特殊矩阵、稀疏矩阵及其压缩存储。
数组的顺序存储；
重点掌握以行为主序的存储结构中的地址计算方法；
掌握对特殊矩阵进行压缩存储时的下标变换公式；
稀疏矩阵的压缩存储结构： 顺序存储 （三元组顺序表）
链接存储 (十字链表)
7、排序的有关概念。
排序算法效率衡量的主要标准是什么？
（时间、空间及稳定性）
各种排序的思想及其性能分析。
（注意各种排序方法的特殊性）
8、查找有关概念。
平均查找长度（衡量一个查找算法好坏的依据）；
二叉排序树（二叉查找树）、二叉平衡树；
哈希函数、哈希地址、冲突、哈希表及解决冲突的方法；
静态查找表和动态查找表及其上的各种查找方法的思想。
重点掌握顺序查找，二分查找，二叉排序树的查找，哈希查找）。
9、图的有关概念。
图的相关术语；
图的存储结构（重点掌握邻接矩阵及邻接表）；
图的深度优先和广度优先遍历思想；
注：树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。
图的最小生成树。
二、应用与分析。
1、写出二叉树的各种遍历结果。
2、由先序、中序遍历序列要能确定一棵二叉树；
由中序、后序遍历序列要能确定一棵二叉树；
3、树、森林与二叉树的转换；
4、哈夫曼树的构造、哈夫曼编码的确定及带权路径长度的计算（wpl）；
如：以10,15 20,5,1,30,23为权值构造一棵哈夫曼树并求出wpl，最后确定叶子结点的哈夫曼编码。
5、哈希表的构造及在哈希表上查找的效率分析；
6、拆半查找的性能分析（通过判定树）；
7、二叉排序树的构造及其查找的性能分析；
8、二叉平衡树的构造及其查找性能分析；
9、写出各种排序下的数据变化过程；
重点掌握希尔排序、快速排序和归并排序。
10、根据一个图分别给出深度优先和广度优先的遍历结果；
11、用普里姆和克鲁斯卡两种方法构造图的最小生成树。
三、算法。1、线性表(包括有序表)在顺序表和链表上的插入、删除、逆置操作算法；
2、求线性表的长度和线性表上的查找算法；
2、栈（链栈及顺序栈）的入栈、出栈操作算法；
3、循环顺序队列和循环链队列的入队、出队操作算法；
4、求二叉树的深度算法；
5、求二叉树中叶子结点个数的算法或求二叉树中结点个数的算法；
6、判断两棵二叉树是否相等的算法；
7、二叉树上的查找算法。
8、二叉树上的复制算法。
9、几种简单的排序算法；
如直接插入排序、简单选择排序、冒泡序）
10、几种重要的查找算法。
如顺序查找、折半（二分）查找、二叉排序树上的查找）
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...