浙江大学mse考研计算机专业基础真题解析

"浙江大学mse考研真题，涵盖计算机专业基础，涉及数据结构、栈、二叉树、完全二叉树、B树、AVL树、哈夫曼编码、有向图等知识点。" 浙江大学硕士研究生入学考试中的计算机专业基础试题包含了多个计算机科学的基础概念和算法。以下是对这些知识点的详细解释： 1. 单向链表插入节点：题目中提到的选择题涉及到链表的插入操作。在不带头结点的单向链表头部插入新节点，需要先将新节点的`next`指向当前头节点，然后更新头节点为新节点。正确选项是A：`t->next=h; h=t;`。 2. 栈的性质：栈是一种后进先出（LIFO）的数据结构。如果第一个输出的元素是4，那么最后一个输入的元素5会最后输出，所以选项B正确。 3. 反序的二叉树：前序遍历和中序遍历序列相反的二叉树不存在，因为前序遍历总是先访问根节点，而中序遍历在根节点左侧的子树在前，右侧子树在后。所以选项D正确。 4. 完全二叉树的最近公共祖先：对于完全二叉树，节点17和19的最近公共祖先可以通过计算它们的层次得到，17在第4层，19在第5层，所以它们的最近公共祖先是它们的父节点，即下标为8的节点，选项D正确。 5. “儿子-兄弟”表示法的二叉树与森林的关系：森林可以通过“儿子-兄弟”表示法转换为二叉树，如果对应的是一个16节点的完全二叉树，意味着森林中有4棵树（完全二叉树的节点数除以2向下取整），且最大的树可能有9个节点，选项D正确。 6. B树的性质：B树的每个非叶节点至少有m/2个孩子，但最低一层节点数可以等于其他层的总和，不一定会大于。B树节点分裂后，树的高度可能不变，所以选项A和C错误，D正确。 7. AVL树的高度：AVL树是自平衡的二叉搜索树，其任何节点的两个子树的高度最多相差1。如果节点数是21，高度最大可能是5（例如，每个节点都有一个子节点，除了最底层的20个节点），选项B正确。 8. 哈夫曼编码与文本压缩：哈夫曼编码是一种最优前缀编码，用于文本压缩。给定的对象和出现次数，构建哈夫曼树后，总位数等于各对象出现次数乘以其编码长度之和。根据题目，总位数应为3*2 + 2*3 + 5*3 + 1*4 + 1*4 = 36位，选项B正确。 9. 有向图的拓扑排序：拓扑排序是将有向无环图的顶点按入度顺序排列。给定的有向图G的拓扑序列是B：v1，v3，v4，v5，v2，v6，因为v1没有前驱，可以首先输出，然后依次考虑其余节点的入度。 10. 关键路径问题：在有向图中寻找关键路径是项目管理中的重要概念，用于找出完成项目所需的最短时间。在这个问题中，寻找关键路径通常需要使用拓扑排序和松弛操作来确定各个活动的最早开始时间和最晚结束时间。 以上知识点涵盖了数据结构中的核心概念，如链表、栈、二叉树、哈夫曼编码以及图论中的拓扑排序和关键路径，这些都是计算机科学基础的重要组成部分，对备考浙江大学mse专业的学生来说，理解和掌握这些知识至关重要。