2015年计算机考研真题与解析：选择题部分

"计算机专业基础综合真题及答案解析" 这篇文档是一份关于计算机科学与技术（cs）领域的教育/考试资料，特别是针对全国硕士研究生入学统一考试的计算机学科专业基础综合试题。试题涵盖多项选择题，涉及编程、数据结构、算法、图论等多个核心计算机科学概念。 1. 题目涉及到递归函数`s`的调用过程，考察了函数调用栈的工作原理。当调用`s(1)`时，会先计算`s(0)`，然后返回到`s(1)`，最后返回到`main()`。因此，栈中信息的顺序应为`S(0)->S(1)->main()`，选项B是正确的。 2. 这道题考察了二叉树的构造。先序遍历a,b,c,d可以构建多种不同的二叉树，总共有14种不同的排列方式，所以答案是B。 3. 这题是关于哈夫曼树（Huffman Tree）的，它是一种用于数据编码的最优二叉树。哈夫曼树中，两个叶节点的路径权值序列如果相同，那么它们可能属于同一棵哈夫曼树。选项B中的两个序列不满足这一条件，因为它们的路径权值序列不完全相同，所以答案是B。 4. AVL树是一种特殊的平衡二叉搜索树，它的特点是任何节点的左右子树高度差不超过1。题目提到进行中序遍历得到降序序列，这意味着根节点是最小元素且没有左子树，选项B和D的描述错误，而C描述的最后插入元素为叶节点在AVL树中并不总是正确。因此，正确答案是A，根节点的度一定为2。 5. 这道题考察了图的深度优先遍历。给定的有向图G有4个顶点和4条边，从V1开始的深度优先遍历可能有4种不同的序列，因此答案是C。 6. 在寻找最小生成树时，克鲁斯卡算法和普里姆算法可能会有不同的选择顺序。克鲁斯卡算法通常按照边的权重升序选择，而普里姆算法从一个顶点开始逐次添加边。这里要求的是克鲁斯卡算法第二次选择但不是普里姆算法（从V开始）第二次选择的边，根据边的权重和添加顺序，答案可能是C。（V2,V3），因为它可能是克鲁斯卡算法第二次选择的边，但不是普里姆算法从V开始的第二次选择。 7. 折半查找是一种效率较高的查找方法，要求关键字序列有序。选项C中的序列180,500,200,450不符合有序性，因此不能构成折半查找的关键字比较序列。 8. 最后一道题是关于KMP（Knuth-Morris-Pratt）算法，这是一种高效的字符串匹配算法。KMP算法利用部分匹配表避免了不必要的字符比较，提高效率。题目未提供具体的解答过程，但需要考生理解KMP算法并应用其匹配模式串t到字符串S中。 总结，这份文档是研究生入学考试的复习资料，涵盖了计算机科学基础的多个重要知识点，包括递归、二叉树、哈夫曼编码、平衡二叉树、图的遍历、最小生成树算法以及字符串匹配算法。这些内容对于准备计算机科学相关的考试或者深入理解计算机基础知识至关重要。