大学数据结构复习要点.doc

《大学数据结构复习要点.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.第一章复习要点是：    数据、数据元素、数据结构(包括逻辑结构、存储结构)以及数据类型的概念、数据的逻辑结构分为哪两大类，及其逻辑特征、数据的存储结构可用的四种基本存储方法。时间复杂度与渐近时间复杂度的概念，如何求算法的时间复杂度。可能出的题目有选择题、填空题或简答题。第二章复习要点是：    线性表的逻辑结构特征、常见的线性表的基本运算，并可以根据这些基本运算组合得到更复杂的运算。顺序表的特征、顺序表中结点地址的计算。顺序表上实现的基本运算(算法)：主要是插入和删除的算法。顺序表的算法应该掌

2、握。算法时间复杂度要记住。单链表的特征、图形表示法。单链表的各种算法实现，并能运用这些算法解决一些简单问题；循环链表的特征、双链表的特征以及它们的主要算法实现。可能出的题型有：填空题、简答题、应用题和算法题。第三章复习要点是：    栈的定义、其逻辑结构特征、栈的基本运算、栈的上溢、下溢的概念。队列的逻辑结构，队列的基本运算；循环队列的边界条件处理；以上各种基本运算算法的实现。算法的简单应用。可能出的题型有填空、选择、简答、算法等。第四章复习要点是：    串是一种特殊的线性表，它的结点仅由一个字

3、符组成。空串与空白串的区别：空串是长度为零的串，空白串是指由一个或多个空格组成的串。串运算的实现中子串定位运算又称串的模式匹配或串匹配。串匹配中，一般将主串称为目标(串),子串称为模式(串)。本章可能出的题型多半为选择、填空等。第五章复习要点是：    多维数组和广义表的逻辑结构特征：它们是复杂的非线性结构。一个数据元素可能有多个直接前趋和多个直接后继。多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。几种特殊矩阵的特征及其压缩存储地址对应关系。稀疏矩阵的三元组表

4、示(画图形表示)。广义表是线性表的推广，也是树的推广。能画出广义表的图形表示法。广义表的取表头运算与取表尾运算要注意，表头是广义表的第一个元素，它不一定是原子，表尾则必是子表。第六章复习要点是：    本章是重点章，二叉树又是本章的重点容。据分析，本章在试题中所占分数达到20%左右，如加上其他章节与二叉树有关的二叉排序树等容，则占有四分之一以上的分值，可见树是十分重要的容，务必仔细掌握各个知识点。    首先是树的概念，包括与树有关的各个名词的意义要能够完全领会，在这方面可能出的题目多是填空、选择

5、等题型。树的四种表示方法：树(图)..形表示法、嵌套集合表示法、凹入表示法和广义表表示法。二叉树的定义、二叉树的五种基本形态、为什么二叉树不是树的特殊情形，这里要注意二叉树与度为二的有序树的区别所在。二叉树的四个性质，如果理解了二叉树，应该能够推导出来。多会出填空题。对于两种特殊情形的二叉树(完全二叉树和满二叉树的定义)应该十分清楚。二叉树的顺序存储适宜用于完全二叉树。第七章复习要点是：    图的概念中主要记忆连通图、连通分量、强连通图和强连通分量的定义和应用(填空、选择、应用)。图的邻接矩阵表

6、示法和邻接表表示法应熟练掌握，根据表示法画出图或者根据图写出邻接矩阵表示或画出邻接表(应用)。注意一个图的邻接矩阵表示是唯一的，而邻接表表示则不是唯一的。稀疏图及稠密图的概念及适用的表示法(填空或选择等)。在图中求顶点的度，在邻接表和邻接矩阵中如何计算(填空题)。图的遍历一定要掌握，对图的深度优先遍历和广度优先遍历的遍历序列应能正确写出(填空或选择)。两种遍历生成树的作图(选择、应用)。最小生成树的两种算法思想(Prim算法、Kruskal算法)要掌握，就是要能在给定的图中分别用两种算法作出最小生

7、成树(包括生成过程)(应用)。最短路径树的生成画图(应用)。拓扑排序的两种方法(无前趋的顶点优先和无后继的顶点优先)应注意到使用DFS遍历算法是后一种方法所排出的拓扑序列(填空、选择)。第九章复习要点是：       查找的基本概念应明确动态查找表和静态查找表的含义、查找和外查找的含义，平均查找长度的定义及计算。线性表的查找有三种方法：顺序查找、二分查找和分块查找。二分查找对线性表的要求。什么是判定树?对于给定的序列，画出二叉判定树。二分查找的平均查找长度，其在最坏情况下查找成功的比较次数也不超过

8、判定树的深度。为什么在链表上无法实现二分查找？分块查找的算法思想。分块有序，块无序。又称索引顺序查找。三种查找方法各自的优缺点。树上的查找，是重点（这里有二叉排序树、平衡二叉排序树）。    什么是二叉排序树?二叉排序树的插入和生成，给定一个序列，请画出二叉排序树的生成过程。二叉排序树中结点的删除。其中要注意的是第三种情况，删除的结点若有两个孩子，则用删除结点的中序后继结点来替换要删的结点。二叉排序树的查找就是从根结点出发走一条从根到待查结点的路径，应能判断某一序列是否是二叉排序树