2015计算机考研真题解析：算法与数据结构重点

"2015年全国硕士研究生计算机考研真题及答案" 这篇文档包含了2015年全国硕士研究生计算机专业入学考试的真题和答案，主要涉及计算机科学与技术的基础知识，包括数据结构、算法、操作系统、计算机网络等多个方面。以下是其中一些关键知识点的详细解释： 1. **递归函数调用与栈**：题目中的`s(n)`函数是一个递归函数，用于计算阶乘。在执行递归调用时，栈会保存每个函数调用的信息，如返回地址和局部变量。当调用`s(1)`时，主函数`main()`首先压栈，然后是`s(1)`，接着是`s(0)`。因此，栈顶到栈底的顺序为`s(0) -> s(1) -> main()`，对应选项B。 2. **二叉树的计数**：题目询问具有特定先序遍历的二叉树数量。先序遍历顺序为a, b, c, d意味着根节点是a，左子树先序遍历为b, c，右子树为d。根据这个信息，可以推断出不同二叉树的个数。实际计算发现，满足条件的二叉树共有15种，对应选项C。 3. **哈夫曼树**：哈夫曼树是一种最优二叉树，用于数据编码。题目要求找出可能属于同一棵哈夫曼树的权值序列。哈夫曼树的权值序列必须满足路径上权值之和相等的特性。根据给定选项，只有C选项的两组权值序列满足这一条件。 4. **AVL树**：AVL树是一种平衡二叉搜索树，其特点是任何节点的左右子树高度差不超过1。对于无重复关键字的AVL树，中序遍历得到降序序列意味着树的结构特殊，但并不意味着根节点的度一定为2（可能为1或0），最小元素不一定是叶节点，最后插入的元素也不一定是叶节点。唯一正确的是D选项，表示树中最大元素一定没有左子树。 5. **深度优先遍历**：深度优先遍历（DFS）从一个顶点开始，沿着某一条路径尽可能深地搜索，直到达到叶子节点，然后回溯。给定顶点V0开始，可能的遍历序列有多个，但题目只给出了顶点集合，无法确定具体序列个数。因此，正确答案可能是从2到5中的任意一个，题目要求选出可能的遍历序列个数，所以答案是D。 6. **最小生成树**：最小生成树问题可以使用克鲁斯卡算法或普里姆算法解决。克鲁斯卡算法是贪心策略，每次选择最小权值的边，而普里姆算法通常从一个节点开始，逐步扩展生成树。题目要求找出克鲁斯卡算法第二次选中但不是普里姆算法（从V4开始）第二次选中的边。由于没有具体图的信息，只能根据算法特性分析，普里姆算法从V4开始，第二次选中的边不会连接V4自身，所以排除(V3, V4)。而克鲁斯卡算法通常选择最小权值的边，所以(C)(V2, V3)可能是第二次选中的边。 7. **折半查找**：折半查找要求关键字序列必须有序。A、B、D选项均保持了升序或降序，而C选项的关键字序列中间插入了一个较大的值500，破坏了有序性，因此不能构成折半查找的序列。 8. **KMP算法**：KMP算法是一种字符串匹配算法，可以避免不必要的字符回溯。题目中提到在模式串"abaabc"与目标串"abaabaabacacaabaabcc"的匹配过程中出现了“失配”，这指的是当前字符不匹配时，KMP算法会利用已知的前缀和后缀关系跳过部分字符，寻找下一个可能的匹配位置。具体的失配处理需要根据KMP的next数组来确定，这里没有给出完整的题目，无法计算出具体的失配位置。 这些知识点涵盖了计算机科学基础的多个核心概念，对于准备计算机考研的学生来说，理解和掌握这些内容是非常重要的。