数据结构复习关键问题解析

"数据结构复习提纲包含了多项关于数据结构的核心概念和算法，涉及二叉树、排序、图论、链表、矩阵压缩存储、树的性质、深度优先搜索、广义表等知识点。" 1. 二叉树形态：具有三个结点的二叉树共有五种不同的形态，包括单支树、左分支树、右分支树、满二叉树和完全二叉树。每种形态代表了不同的节点关系。 2. 二叉树遍历：根据前序遍历ABECDFGHIJ和中序遍历EBCDAFHIGJ，可以恢复出二叉树的形态，并通过后序遍历进一步确认。这是一个经典的树遍历问题，涉及到递归或栈的应用。 3. 简单选择排序：它不是稳定的排序方法。在比较元素时，可能会改变相同元素的相对顺序，例如在序列[3, 1, 4, 1, 5]中，第一个1被第二个1提前交换，破坏了稳定性。 4. 最小生成树：普里姆和克鲁斯卡尔算法都是用于构建图的最小生成树。普里姆从一个顶点开始逐步添加边，而克鲁斯卡尔则是按边的权重从小到大加入，两者都需避免形成环。 5. 希尔排序：增量序列(8, 4, 2, 1)用于希尔排序，每一步会按照增量将序列分为若干个子序列进行插入排序，最后达到完全排序。 6. 稀疏矩阵存储：稀疏矩阵的三元组表和十字链表是压缩存储方法，用于节省存储空间，便于矩阵操作。 7. 循环链表连接：将两个循环链表首尾相接需要处理好头尾节点的关系，确保形成一个完整的循环链表。 8. 树的属性：计算树的叶子节点、非终端节点、各节点的度、树的度和树深，需要掌握树的基本概念和计算规则。 9. 中根线索链表：在二叉树上建立线索，用于便捷地进行中序遍历。 10. 深度优先搜索：从顶点v1出发，沿着边进行遍历，直到所有可达顶点都被访问，返回路径取决于图的结构。 11. 折半插入排序：结合二分查找的效率，改进插入排序，降低比较次数，提高排序速度。 12. 稀疏矩阵的三元组表和十字链表存储同样适用于其他矩阵，简化表示，提高操作效率。 13. 希尔排序的稳定性：希尔排序不是稳定的排序方法，同样举例说明。 14. 二叉树的顺序存储和遍历：根据给定的顺序存储结构，画出对应的二叉树，并给出遍历结果，同时找到节点c的双亲和孩子。 15. 有向图的表示：画出有向图，计算每个顶点的入度和出度，然后用邻接矩阵和邻接表表示。 16. 二叉树的先根、中根序列恢复：利用给定的先根和中根序列，构建二叉树，并找出后序序列。 17. 线性表的存储结构：顺序存储和链式存储，各有优劣，顺序存储访问效率高但插入删除操作复杂，链式存储反之。 18. 克鲁斯卡尔算法构建最小生成树：根据图的边和权重，逐步选择最小权重的边，避免形成环，直至连接所有顶点。 19. 希尔排序过程：希尔排序的每趟排序后，序列会逐渐接近有序，直至完全有序。 20. 权重集构建最小生成树：给定权集，应用克鲁斯卡尔算法逐步构造最小生成树。 以上知识点覆盖了数据结构中的关键概念和算法，适合复习准备。