2015年考研计算机专业基础综合真题解析.pdf

【知识点详解】 1. **栈的基本概念和函数调用的原理**：在程序运行时，每当发生函数调用，相关信息会被压入栈中。题目中给出的递归函数调用`s(1)`会先调用`s(0)`，然后是`s(1)`，最后返回到`main()`。因此，栈顶到栈底的信息顺序应为`S(1)->S(0)->main()`。 2. **二叉树的基本概念**：先序遍历顺序是`根-左-右`，题目中询问不同的二叉树数量，对于先序序列`a,b,c,d`，可以通过构造不同结构的二叉树得到不同的遍历结果，共有15种不同的二叉树。 3. **哈夫曼树的原理**：哈夫曼树是一种特殊的二叉树，用于数据压缩，具有最小带权路径长度。选项C中的两个权值序列可以构建同一棵哈夫曼树，因为它们的组合能保持权值的加权和顺序。 4. **AVL树的基本概念**：AVL树是一种平衡二叉搜索树，中序遍历得到降序序列意味着每个节点都比其左子树的所有节点大，比右子树的所有节点小。选项B正确，因为最小元素一定是叶节点。 5. **图的深度优先遍历**：深度优先遍历从一个顶点开始，沿着边尽可能深地搜索。对于图G，从V0开始有5种不同的遍历顺序。 6. **最小生成树算法**：Kruskal算法按边的权重从小到大添加边，而Prim算法从任意节点开始逐步扩展。题目中询问的是两种算法在构造最小生成树过程中可能的不同选择。 7. **二分查找算法**：折半查找需要关键字有序，选项A中序列不满足这一条件，因为500在200之前，但在450之后，导致无法进行有效的二分查找。 8. **KMP算法**：KMP算法在模式匹配时遇到失配不会立即回溯，而是根据部分匹配表确定下次比较的位置。题目中失配发生在i=5, j=5，根据KMP算法，下次匹配时i=5, j=2。 9. **排序算法**：元素移动次数与初始排列无关的排序算法是起泡排序，因为无论输入如何，每次都将最大（或最小）元素“冒泡”到正确位置。 10. **最小堆的概念和重建**：删除堆顶元素后，需要重建堆以保持最小堆性质。在这个过程中，通常需要重新调整节点以确保堆的性质，关键字之间的比较次数为2。 11. **希尔排序**：希尔排序是一种改进的插入排序，首先通过增量序列将数组分组，然后在各组内进行直接插入排序，最后增量为1时，整个序列基本有序，进行最后一次直接插入排序。 12. **计算机硬件执行程序**：计算机硬件直接执行的是机器语言程序，即二进制代码。汇编语言和硬件描述语言都需要经过编译或解释才能转换为机器语言。 这些知识点涵盖了计算机科学的基础，包括数据结构（如二叉树、堆）、算法（如排序、查找）、图论（如图的遍历）、程序设计（如递归、函数调用）以及计算机体系结构（如指令执行）。这些是计算机科学考研中的核心内容，理解和掌握这些知识点对于深入学习计算机科学至关重要。