2015年计算机考研真题与解析

"2015年计算机真题及解析" 这篇文档包含了2015年全国硕士研究生入学统一考试的计算机学科专业基础综合试题，主要涉及计算机科学和技术的基础知识，包括数据结构、算法、操作系统、计算机网络等多个方面。试题以单项选择题的形式出现，每个题目2分，总分80分。 1. 题目涉及到递归函数的调用顺序。在C++中，函数调用会使用栈来存储返回地址和局部变量。递归调用`s(n)`会在栈上依次压入`s(n-1)`，直到基本情况`n<=0`。因此，正确的调用顺序应该是从栈底到栈顶：main() -> s(1) -> s(0)，对应答案B。 2. 这是一道关于二叉树组合的题目。根据题目描述，需要计算先序序列为a,b,c,d的不同二叉树个数。这个问题可以通过计算排列组合来解决，由于先序遍历的顺序是根节点-左子树-右子树，所以a作为根节点，b,c,d作为子节点，可以形成14种不同的二叉树，对应答案B。 3. 哈夫曼树是一种最优二叉树，用于数据编码。题目要求找出可能属于同一棵哈夫曼树的权值序列。哈夫曼树的特性是任意两个叶子节点的路径上不会经过其他叶子节点，所以只有24,10,5和24,14,6这两个序列满足条件，因为它们在构建哈夫曼树时可以合并成相同的路径，对应答案D。 4. AVL树是一种自平衡二叉搜索树，对于任何节点，其左右子树的高度差不超过1。题目中提到进行中序遍历得到降序序列，这意味着树的形状是右斜的。在AVL树中，插入操作可能导致树的不平衡，但最后插入的元素不一定是叶节点，根节点的度也不一定是2，最小元素可能是叶节点也可能不是，最大元素一定是无左子树。所以正确答案是D。 5. 图的深度优先遍历（DFS）是从一个顶点开始，尽可能深地搜索图的分支。给定的有向图G包含4个顶点和4条边，从V0开始的DFS可能产生的不同遍历序列有3种，分别是V0, V1, V2, V3, V0, V1, V3, V2, V0, V2, V1, V3。答案是B。 6. 克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法都是用于寻找图的最小生成树的。克鲁斯卡尔算法按照边的权重升序选择，而普里姆算法通常从一个顶点开始，逐次加入相邻的最小权重边。这里没有具体的边权重，但可以推断，克鲁斯卡尔第二次选择的边可能不是普里姆算法第二次选择的边，因为普里姆算法更注重局部最优。答案可能是C。（V2,V3）这条边，具体取决于其他边的权重。 7. 折半查找的关键字比较序列需要保持有序性，以便每次比较都能有效地减少查找范围。选项A、B、C都满足这一条件，而D中的180, 200, 500, 450在前三个元素后没有保持有序，所以D不能构成有效的折半查找比较序列。 8. KMP算法是一种改进的字符串匹配算法，它可以避免回溯。在给定字符串S和模式串t的匹配过程中，KMP算法会利用部分匹配表来减少不必要的字符比较。当第一次出现模式串t的前缀与S的某个子串匹配失败时，KMP算法会跳过已经比较过的部分，继续匹配。对于这个题目，需要具体的部分匹配表来确定第一次出现"abaabc"时的具体位置，这部分信息在提供的内容中未给出。 这些题目涵盖了计算机科学中的基本概念，如递归、二叉树、哈夫曼编码、平衡二叉树、图的遍历、最小生成树算法以及字符串匹配等。解答这些问题需要扎实的理论基础和对算法的理解。