数据结构习题：Dijkstra与KMP算法应用

一、单项选择题 1.3 题目询问将二叉树转化为图并进行深度优先遍历，这涉及数据结构中树和图的转换。在图的深度优先搜索（DFS）中，通常用于遍历二叉树的方法是前序遍历，因为DFS的第一步是访问根节点，然后递归地遍历左子树和右子树。因此，正确答案是**A、前序遍历**。 1.4 本题考察关于树的数据结构特性： - A选项错误，用指针方式存储二叉树，只需一个指向根节点的指针，其余每个节点最多有两个指针（一个指向左子节点，一个指向右子节点），所以不一定需要n+1个指针。 - B选项错误，m阶B-树的性质指出，每个内部节点至少有k/2个键（对于k > m/2的情况），而不是k-1个键值。 - C选项正确，m阶B-树中，每个非叶子节点至少有[m/2]个子节点，保证了树的平衡。 - D选项错误，平衡树是指每个节点的左右子树高度差不超过1，不一定为丰满树（丰满树是指每个节点除了满足B树的定义外，所有分支都尽可能扩展，非叶子节点至少达到最大可能的分支数，而平衡树并非如此）。 1.5 题目寻找在最好和最坏情况下时间复杂度均为O(nlog2n)且稳定的排序方法。**D、归并排序**在这些条件上符合，因为它是一种稳定的排序算法，且在最坏情况下（输入已经部分有序或逆序）和最好情况下（输入完全有序）的时间复杂度都是O(nlog2n)。 二、解答题 2.1 题目涉及KMP算法，这是一种字符串匹配算法，用于在文本串中查找模式串。KMP算法的核心是预计算出一个失效函数f[]，它记录了模式串中每个位置的最大“不成功”偏移量。在给出的代码片段中，当模式串中当前字符与目标串不匹配时，会根据失效函数跳过部分目标串，以减少无效的比较。在匹配过程中的失效函数值为-1，0，-1，-1对应于目标串的位置1，2，3，4，表示模式串中分别从第0，1，2，3个字符重新开始匹配。最终，通过循环，当找到完整匹配或者模式串遍历完时，返回匹配的位置。在给定例子中，模式串aabc在目标串abaabcc中的匹配过程终止于位置1，因为模式串已经完全匹配。