考研计算机真题解析：栈、二叉树、哈夫曼树与图算法

"这是一份2015年考研计算机专业基础综合真题的解析资料，主要涵盖计算机考研的相关知识，包括数据结构、操作系统、计算机网络和计算机组成原理等多个方面。" 1. **栈与函数调用**：题目涉及到栈在函数调用中的应用。在C++或类似的高级语言中，当函数被调用时，相关信息会被压入栈中，如返回地址、局部变量等。题目中`s(1)`调用会先压入栈，接着是`s(0)`，最后是`main()`函数的调用信息。因此，栈从栈底到栈顶依次对应`S(1)->S(0)->main()`，答案是D。这部分知识要求考生理解栈的后进先出（LIFO）特性以及递归调用的原理。 2. **二叉树**：二叉树题目询问了先序序列不同的二叉树个数。先序遍历顺序是根-左-右，根据给定的序列，可以推断出不同的构建方式。答案C表示有15种不同的二叉树，考生需要熟悉二叉树的各种遍历方法和构造原则。 3. **哈夫曼树**：哈夫曼树是一种最优的二叉树，用于数据压缩。题目考察的是两个叶节点路径上的权值序列是否可能属于同一棵哈夫曼树。答案C表明权值序列24, 10, 10和24, 14, 11可以共存于一棵哈夫曼树中，考生需掌握哈夫曼树的构造规则。 4. **AVL树**：AVL树是一种特殊的二叉搜索树，保持平衡。在AVL树的中序遍历下，得到的序列是有序的。题目指出树是降序的，因此树中最小元素一定是叶节点，答案B。这要求考生理解AVL树的性质和中序遍历的定义。 5. **图的深度优先遍历**：深度优先遍历是一种图的遍历策略，从一个顶点出发，尽可能深地搜索图的分支。题目给出的图有4个顶点，从V0开始遍历，可能得到5种不同的序列，答案是D。考生需要掌握深度优先遍历的规则和实现。 6. **最小生成树**：最小生成树算法包括Prim和Kruskal。题目询问了两种算法在构建最小生成树时可能的选择。Kruskal通常按边的权重升序添加，而Prim从一个顶点开始扩展。答案A表示(V1, V3)可能是Kruskal算法第二次选择但不是Prim算法（从V4开始）的第二条边。考生需要了解这两种算法的差异和操作步骤。 这些题目涵盖了计算机科学的基础知识，包括数据结构（栈、二叉树、哈夫曼树、AVL树）、图论（深度优先遍历、最小生成树）和算法（递归、搜索）。对于准备计算机考研的学生来说，理解和熟练掌握这些概念至关重要。