2015计算机专业408考研试题完整版无水印

"这是一份2015年的计算机专业408考研试题完整版，无水印，来源于王道计算机复习真题资料。试题经过优化，去除了多余页面，便于考生进行全真模拟考试。试题与答案分开，方便打印和答题。" 以下是试题中的部分知识点详解： 1. 此题考察递归调用时栈的存储顺序。在C++程序中，调用函数时，信息会被压入栈中。根据题目中给出的递归函数`s(n)`，`S(1)`调用会先执行，然后是`S(0)`，最后回到`main()`函数。因此，栈顶到栈底的顺序应该是`S(1)→S(0)→main()`，答案是D。 2. 本题考查二叉树的构造。根据先序遍历（根-左-右）的特点，我们知道构建具有不同结构的二叉树时，先序序列可以提供一定的线索。例如，对于先序序列`a,b,c,d`，根节点为`a`，`b`和`c`、`d`是`a`的两个子节点。但是由于没有更多信息，无法确定具体结构。答案为B，表示可能有14种不同的二叉树结构。 3. 哈夫曼树是一种最优二叉树，其特点是最小带权路径长度最短。两个叶节点路径上的权值序列如果能属于同一棵树，必须满足两序列中各元素之和相等。只有选项C满足这个条件，两序列的权值和均为35。答案为C。 4. 平衡二叉树（AVL树）在中序遍历后得到降序序列，意味着所有左子树的元素都小于其父节点，所有右子树的元素都大于其父节点。选项A，根结点的度不一定为2，因为AVL树允许度为1；B，最小元素不一定是叶结点，它可能在树的任意位置；C，最后插入的元素成为新叶结点，满足平衡条件；D，最大元素可能有左子树，但没有右子树。答案为C。 5. 深度优先遍历（DFS）是从一个顶点开始沿着某条分支深入搜索，直到所有相邻顶点都被访问。在给定的有向图G中，从顶点`V0`出发，所有可能的遍历序列如下：`V0->V1->V3`，`V0->V1->V3`，`V0->V2`，`V0->V3`。共有3个不同的遍历序列。答案为B。 6. 克鲁斯卡算法和普里姆算法都是求最小生成树的方法。克鲁斯卡算法是按边的权重从小到大选择，而普里姆算法是从一个顶点开始逐步扩大树的范围。从`V4`开始，第二条边的选择，普里姆算法会优先选择与已选顶点相连的最小权重边。因此，不是普里姆算法第二次选择的边可能是克鲁斯卡算法第二次选择的边。在选项中，`(V3,V4)`的权重未知，但`(V1,V3)`的权重显然大于`(V1,V4)`和`(V2,V3)`，所以`(V1,V3)`可能是克鲁斯卡算法第二次选中的边，但不会是普里姆算法的。答案为A。 7. 折半查找是一种在有序数组中查找元素的算法。比较序列必须保持升序或降序。选项C中的序列`180,500,200,450`不是有序的，因此不能构成折半查找的关键字比较序列。答案为C。 8. KMP算法在模式匹配过程中，利用部分匹配表避免了不必要的字符比较。在给定的字符串`s`和模式`t`中，第一次失配发生在`s[7]`和`t[3]`，即`s`中的`a`与`t`中的`c`不匹配。根据KMP算法，此时模式串的下一个字符是`t[0]`，即`a`，因此我们需要找到在`s`中下一次出现`t[0]`的位置，即`s[1]`处的`a`，而`t[1]`是`b`，所以失配发生在`s[8]`和`t[1]`。答案为`s[8] != t[1]`。 以上就是试题中涉及的一些核心计算机科学概念，包括递归、二叉树、哈夫曼树、平衡二叉树、图的遍历、最小生成树算法、折半查找以及字符串匹配的KMP算法。这些知识点是计算机科学基础的重要组成部分，对于准备408计算机专业基础综合考试的考生来说，理解和掌握这些内容至关重要。