数据结构习题解析：冒泡排序与二叉树算法

"数据结构复习题目及答案" 在数据结构的学习中，这些题目涉及了排序算法、二叉树的操作和图的属性等多个重要知识点。以下是这些题目的详细解析： 第一题：冒泡排序算法的改进 传统的冒泡排序算法通过交换相邻的两个元素来逐步排序。这里提出了一种改进方法，将控制交换的布尔变量`change`改为整型变量`lastChange`，它记录每趟排序中最后进行交换的位置。在新算法中，`lastChange`在每趟排序结束后更新为上一次交换发生的位置，作为下一次排序循环的终止条件。这样可以减少不必要的比较，提高效率。 ```cpp void BubbleSort_0306(RcdSqList2& L) { int lastChange = L.length; int change, i, j; for (i = L.length; i > 1 && lastChange != 0; i--) { change = 0; for (j = 1; j < lastChange; j++) { if (GT(L.rcd[j], L.rcd[j+1])) { Swap(L.rcd[j], L.rcd[j+1]); change = j; } } lastChange = change; } } ``` 第二题：判断两棵二叉树是否同构 同构的二叉树是指可以通过交换它们的子节点而相互转换的树。在这个问题中，我们需要编写一个函数`isIsomorphic`，输入为两棵二叉树的根节点，返回它们是否同构。基础情况是两棵树都为空或其中一棵为空，另一棵不空，此时返回false。若两棵树都不为空，我们递归地比较它们的左右子树，如果对应位置的子树同构，才返回true。 ```cpp Status isIsomorphic(BiTree T1, BiTree T2) { if (T1 == NULL && T2 == NULL) return TRUE; else if (T1 == NULL || T2 == NULL) return FALSE; // ... 递归比较T1和T2的左右子树 } ``` 第三题至第六题：二叉树操作 1. 交换二叉树所有节点的左右子树：这个操作涉及到递归，对每个节点执行交换操作，同时也要考虑空节点的情况。 2. 复制二叉树：同样使用递归，为每个节点创建一个新的节点，并复制其值，然后分别复制左右子树。 3. 计算二叉树中度为1的节点数目：遍历所有节点，累加度为1的节点数。 4. 判断是否为正则二叉树：正则二叉树是指所有非叶节点都有两个子节点，或者没有子节点。遍历检查每个非叶节点的子节点数量即可。 第七题至第十题：孩子兄弟链表表示的树和邻接表存储的有向图 1. 统计孩子兄弟链表表示的树的叶子个数：通过遍历树的节点，检查是否有子节点，若无子节点则为叶子节点。 2. 求孩子的度：遍历每个节点，计算其子节点的数量。 3. 计算树的深度：使用深度优先搜索（DFS）或广度优先搜索（BFS）计算。 4. 计算有向图中某顶点的出度：遍历该顶点的所有邻接边，计数即可。 以上是这些题目的详细解析，涵盖了数据结构中的核心概念，如排序算法、二叉树操作、图的属性等，对于理解和掌握数据结构非常有帮助。