2010年计算机考研专业课知识点分析：数据结构[3]

树与二叉树

二叉树和树是两种不同的概念这一点是必须要搞清楚的在这个部分我们要掌握树的定义二叉树的定义及主要特征(特殊的二叉树二叉树的性质)在二叉树的顺序存储结构和链式存储结构方面特别是链式存储结构因为很多应用都是建立在链式存储基础上例如二叉树的遍历(前序遍历中序遍历后序遍历)就是一种典型的应用

在特殊的二叉树中完全二叉树的概念是必须要搞清楚的其次线索二叉树的基本概念和构造二叉排序树平衡二叉树的基本概念和应用特别是二叉排序树的基本性质和特点要能很好地理解

多棵独立的树就组成了森林树的存储结构和遍历森林的遍历树和二叉树的转换森林和二叉树的转换等知识也要有了了解

最后就是树的应用通常会作为综合应用类试题出现包括等价类问题哈夫曼(Huffman)树和哈夫曼编码等

图

在数据结构中图的结构是最复杂的这里的概念也是最多的我们要掌握图的基本概念(有向图无向图连通路径子图出度入度生成树最短路径关键路径等)

图的存储及基本操作主要有邻接矩阵法和邻接表法我们要掌握这有向图和无向图的这种存储方法要清楚图的连通和存储方法之间的关系例如一个顶点的出度和临界矩阵中的个数有什么关系等等

图的遍历方法有深度优先搜索和广度优先搜索我们要掌握这种遍历方法的算法实现给出一个具体的图要能知道它的遍历次序

在数据结构课程中图的基本应用是最多的也是最复杂的我们要掌握这些应用的复杂度分析要掌握的具体应用主要包括最小(代价)生成树最短路径拓扑排序关键路径在给出的一个具体的图中我们要会利用已知条件求出上述应用的结果

[] [] [] [] [] []