数据结构第9章答案.pptx

数据结构第9章答案.pptx 本资源主要涉及数据结构的拓扑排序、单源最短路、折半查找、ASL、二叉排序树和 Hash 表等知识点。 1. 拓扑排序 拓扑排序是一种将有向无环图（DAG）转换为线性序列的算法。该算法可以用于解决许多问题，如项目调度、编译顺序等。拓扑排序的关键在于找到图中的所有关键路径，即从源点到达所有节点的最短路径。拓扑排序的算法可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。 2. 单源最短路 单源最短路问题是指从一个节点到达所有其他节点的最短路径问题。该问题可以通过Floyd算法来解决。Floyd算法是一种动态规划算法，通过不断地更新距离矩阵来找到所有节点之间的最短路径。该算法的时间复杂度为O(n^3)，其中n为节点的数量。 需要注意的是，Floyd算法与Dijkstra算法的区别在于Floyd算法可以处理负权边，而Dijkstra算法不能。在实际应用中，Floyd算法广泛应用于交通网络、通信网络等领域。 3. 折半查找 折半查找是指在有序表中查找元素的算法。该算法的思想是不断地折半查找，直到找到目标元素。折半查找的时间复杂度为O(logn)，其中n为表的长度。 在本资源中，要求画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。该问题可以通过构建折半查找树来解决，具体步骤如下： 构建折半查找树，树的每个节点代表一个查找步骤。然后，计算每个节点的查找概率，并求出平均查找长度。通过折半查找树来找到目标元素。 4. ASL ASL（Average Search Length）是指在折半查找中查找成功的平均查找长度。ASL是衡量折半查找算法性能的重要指标。ASL越小，表示折半查找算法的性能越好。 在本资源中，ASL的值为2.9，该值表示在折半查找中查找成功的平均查找长度为2.9。 5. 二叉排序树 二叉排序树是一种特殊的二叉树，满足以下三个条件： （1）左子树中的所有节点的关键字都小于根节点的关键字。 （2）右子树中的所有节点的关键字都大于根节点的关键字。 （3）左子树和右子树都是二叉排序树。 在本资源中，要求写一个判别给定二叉树是否为二叉排序树的算法。该问题可以通过递归的思想来解决，具体步骤如下： 判断树是否为空，如果为空则直接返回TRUE。否则，判断左子树和右子树是否为二叉排序树，如果有一个不是则直接返回FALSE。如果左右子树都是二叉排序树，则判断左子树中的最大关键字是否小于根节点的关键字，右子树中的最小关键字是否大于根节点的关键字。如果满足这两个条件则返回TRUE，否则返回FALSE。 6. Hash 表 Hash 表是一种常用的数据结构，可以用于快速查找、插入和删除元素。Hash 表的平均查找长度是衡量其性能的重要指标。 在本资源中，要求写分数即可：17/8，该分数表示Hash 表的平均查找长度为17/8。 本资源涉及了数据结构的多个知识点，包括拓扑排序、单源最短路、折半查找、ASL、二叉排序树和Hash 表等。通过对这些知识点的学习和掌握，可以更好地应用数据结构来解决实际问题。