数据结构复习大纲.doc

《数据结构复习大纲.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构复习大纲第1章：理解数据、数据元素、数据对象、数据类型等基本概念；理解数据类型和抽象数据类型区别；掌握数据四种逻辑结构、2种存储结构、逻辑结构和存储结构的联系和区别；理解算法的概念，算法5个特性和设计要求，掌握算法时间复杂度分析。第2章：掌握线性结构定义、特点。掌握顺序表的定义和存储实现，插入和删除时候的平均移动次数。掌握链表的定义和存储实现，链表插入和删除时候的指针应该如何修改。掌握循环链表、单链表和双向链表的区别。头结点、首元结点、头指针区别。顺序表和链表的优缺点对比。一定要会进行本章相应的算法设计。第3章：栈和队列的定义及和线性操作的区别。栈的递归应用。顺序栈的出栈

2、、进栈操作；空栈的表示。循环队列的队列初始化条件表示、队满表示、队空表示、队列长度表示。链队列的空队表示，插入和删除操作。第4章：串的定义，空串、空格串。串的每个基本操作参数的含义和实现的功能。第5章：二维数组的定义数组中第i行、第j列元素在内存中存储的具体位置。（公式）特殊矩阵的第i行、第j列元素在内存中存储的具体位置。（公式）广义表的定义。广义表的取表头和表尾操作。第6章：树相关基本概念：如结点的度，树的度和深度等二叉树的定义，二叉树5个性质，以及5个性质的简单应用。（课堂例题）二叉树的三种遍历，有两种遍历序列还原二叉树。二叉树的线索化的概念。为什么要加线索？在树的孩子兄弟表

3、示法的基础上掌握树、森林和二叉树之间相互转化。哈夫曼树的定义、创建和编码。一定要会进行本章相应的递归算法设计。（课本例题和课后有关递归算法设计题）第7章图的定义、相关概念图的邻接矩阵和邻接表两种存储结构是重点，掌握他们各自特点，给你图为写出两种存储结构。根据图或者邻接矩阵和邻接表会写出深度优先、广度优先、拓扑排序线性序列。根据图会利用克鲁斯卡尔和prim算法画出最小生成树根据图会利用迪杰斯特拉求出一个顶点到其余各个顶点的最短路径。第8章查找概念，什么是平均查找长度。顺序查找和折半查找算法以及时间复杂度和ASL。根据具体的折半查找判定树，求出它的ASL。二叉排序树的概念。给你一组数

4、据会画出这个二叉排序树，进行插入删除操作时，会重新画出二叉排序树。同一组数据二叉排序树的形态与数据输入状态有关。会根据具体树的形状求出ASL。哈希表的概念、哈希函数种类、处理冲突有哪些办法。根据具体的哈希函数和解决冲突的办法画出哈希表，求出查找成功和不成功时候的ASL。给你一棵二叉排序树，会判定是否为平衡二叉排序树。算法：必须掌握折半查找、二叉树排序树的创建，插入，和查找。哈希表的查找.(都是课本上的算法)第9章各个排序方法的算法思想，和时间复杂度、空间复杂度分析，掌握他们之间的优缺点。特别是很多小的结论。给你一组数据，给你一种排序算法，会写出每一趟的排序结果。（如快速和堆）给你

5、一组数据，会判断是否能构成堆。快速排序正序时候反而最差。简单选择排序的比较次数永远不变等，这些小的结论记牢。算法：会写出直接插入、冒泡，简单选择算法的代码备注：整个考试共十套试卷，随机抽提，知识点覆盖率很高，请同学们根据我写复习大纲认真复习。祝考试顺利！