数据结构复习：证明题、画图题与算法解析

"这是一份关于数据结构复习的文档，包含了证明题、画图题和算法题，涵盖了二叉树的基本性质、遍历、线索二叉树、最小生成树、哈夫曼树等重要概念，以及顺序表的动态扩展操作。" 在数据结构的学习中，二叉树是一个核心的概念，它在很多算法中起到关键作用。文档中提到的证明题主要考察了二叉树的特性： 1. 二叉树的性质表明，如果一个二叉树有n0个叶子结点（度为0的结点），n2个度为2的结点，那么节点总数n等于n0+n1+n2，其中n1是度为1的结点数。由此可以推导出n0=n2+1的关系。 2. 完全二叉树的性质指出，对于拥有n个结点的完全二叉树，其深度为log2n（向上取整）。这是因为完全二叉树每一层都是满的，除了最后一层可能不满。 3. 在二叉树的第i层上，最多可以有2^(i-1)个结点，因为每上升一层，结点数最多翻倍。 4. 二叉树的度数关系问题，已知叶子结点m，可以通过总结点数n和度为2的结点数n2来推算出度为1的结点数n1，即n=m+n1+n2，且n2=m-1，解得n1=2m-n。 画图题涉及二叉树的先序和中序遍历，这些遍历方法是构建和识别二叉树的关键。例如，给定两个遍历序列，可以使用这两种遍历的性质来唯一确定二叉树的结构。同时，题目还涉及线索二叉树的构建，这是为了方便二叉树的中序遍历而引入的一种特殊结构。 算法题部分，重点考察了顺序表的动态扩展操作。在C语言中，使用`realloc`函数可以动态调整内存分配。当顺序表满时，需要增加存储空间，这里通过`realloc`函数将原数组扩大`LISTINCREMENT`个单位，并更新指针和长度。 此外，还提到了哈夫曼树的构建，这是一种用于数据压缩的优化二叉树，通过不断合并权值最小的两棵树来构建。最后，关于森林与二叉树的转换，以及最小生成树的构造，这些都是图论中的基础概念，通常用Prim算法或Kruskal算法来求解。 这些题目覆盖了数据结构中的多个重要主题，是深入理解和掌握数据结构知识的好材料。通过解答这些题目，学生可以巩固对二叉树、顺序表、图论等相关概念的理解，并提高实际编程解决问题的能力。