哈工大计算机考研2013、2014年原版真题

### 哈工大计算机考研2013年真题知识点解析 #### 数据结构部分 **一、单项选择题** 1. **完全二叉树的结点数计算** - 完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层的结点都是满的，而最后一层的结点都集中在左侧。对于高度为\(h\)的完全二叉树，最少的结点数取决于最后一层是否有结点。 - 高度为6的完全二叉树，最少的情况是第6层只有一个结点，此时该二叉树可以看作是由高度为5的满二叉树加上一个结点构成。 - 高度为5的满二叉树的结点数为\(2^5-1=31\)，再加上第6层的一个结点，总共32个结点。因此正确答案为B.32。 2. **非连通无向图中的树的数量** - 在非连通的无向图中，每增加一条边会减少一个连通分量（即树的数量），直到图变为连通图。 - 设有\(n\)个结点的非连通无向图，若有\(k\)条边，且该图是森林，则意味着该图不包含环。因此，每增加一条边，都会将两个连通分量合并成一个，所以连通分量的数量减少了1。 - 因此，树的数量为\(n-k\)。正确答案为C. n-k。 3. **邻接矩阵的压缩存储** - 对于无向图来说，邻接矩阵是对称的，因此可以只存储上三角或下三角部分来节省空间。 - 如果存储下三角部分，那么第一行不需要存储，第二行存储1个元素，第三行存储2个元素，依此类推，直到第n行存储n-1个元素。总的存储单元数为\(1 + 2 + ... + (n-1) = \frac{n(n-1)}{2}\)。 - 正确答案为D. \(\frac{n(n-1)}{2}\)。 4. **排序算法的特性** - 在所有给出的排序算法中，只有插入排序可以在最后一趟开始之前所有元素都不在其最终位置上。 - 堆排序、冒泡排序和选择排序在排序过程中，至少有一个元素会被放到最终位置上。 - 插入排序则是逐步将未排序的部分插入到已排序的部分中，因此直到最后一趟开始之前，所有元素都可能不在其最终位置上。 - 正确答案为D. 插入排序。 5. **多路归并的趟数** - 多路归并是指将多个已经排序的小文件合并成一个大文件的过程。如果有\(m\)个初始归并段，采用\(k\)路归并，那么归并的趟数可以通过计算\(\lceil\log_km\rceil\)来确定。 - 这是因为每次\(k\)路归并可以将\(k\)个文件合并为一个文件，所以需要的趟数就是将\(m\)个文件通过每次\(k\)个文件合并成一个文件所需的步骤数。 - 正确答案为C. \(\lceil\log_km\rceil\)。 6. **前缀码的判断** - 前缀码是指在所有编码中，没有任何一个编码是另一个编码的前缀。选项B中的编码“0”，“1”，“00”，“11”中，“00”是以“0”为前缀的，因此不是前缀码。 - 正确答案为B. （0，1，00，11）。 7. **二叉树的结点数量计算** - 对于只有度为0和度为2的结点的二叉树，可以根据递推关系式计算结点数。 - 设这样的二叉树的高度为\(h\)，那么它包含的结点数\(N\)满足关系式\(N = 2^{h} - 1\)。 - 正确答案为B. \(2^h-1\)。 8. **二叉树与森林之间的转换** - 当二叉树转换为森林时，每个子树都会成为一个独立的树。 - 结点M和N是结点P的第i和i+1个孩子，在转换后的森林中，M和N仍然是兄弟结点，但由于二叉树的性质，M总是作为N的左兄弟（即左孩子）出现。 - 正确答案为D. N是M的右孩子。 9. **二分查找中的失败结点** - 在二分查找中，查找失败时会指向一个不存在的外部结点，称为失败结点。 - 对于n个结点的二分查找树，失败结点的数量为n+1，这是因为除了n个内部结点外，还需要一个额外的结点来表示查找失败的情况。 - 正确答案为C. n+1。 10. **最小堆中的最大关键字位置** - 最小堆是一种特殊的完全二叉树结构，其中每个父结点的值不大于其孩子结点的值。 - 最大关键字位于堆的下半部分，即从\(\left\lfloor\frac{n}{2}\right\rfloor + 1\)到n的结点之间。 - 正确答案为D. \(\left\lfloor\frac{n}{2}\right\rfloor+2\)。 **二、填空题** 11. **顺序存储线性表插入操作的时间复杂度** - 在长度为n的顺序存储的线性表中，在第一个元素前插入元素的时间复杂度为\(O(n)\)，因为需要移动n个元素。 - 平均时间复杂度为\(O(n)\)，因为无论在何处插入，都需要移动一半左右的元素。 12. **稀疏矩阵的存储方法** - 稀疏矩阵中大部分元素为0，因此通常采用更高效的存储方法来节省空间。 - 常见的存储方法包括三元组表和十字链表。 13. **后缀算数表达式的计算** - 后缀算数表达式923+-82/-的值为\(9 + 2 - 3 = 8\)；中缀算数表达式(3+4×X)-2×Y/3对应的后缀算数表达式为3 4 X ×+2 Y ×3 ÷-。 14. **完全二叉树的结点度数** - 具有2n个结点的完全二叉树中，度为1的结点数量为0，度为2的结点数量为n-1。 15. **B树的插入位置查找** - 在高度为h的B树中，叶子结点处于第h层，查找插入位置时最多需要读取h个结点。 **三、简答题** 16. **二叉树的构建及遍历** - 根据给定的前序遍历序列和中序遍历序列，可以构建出唯一的二叉树。 - 前序遍历的第一个结点是根结点，从中序遍历中找到根结点的位置，可以将中序遍历分为左子树和右子树两部分。 - 左子树的前序遍历序列是前序遍历序列中根结点之后直到左子树最后一个结点的部分，右子树的前序遍历序列是前序遍历序列中左子树之后的部分。 - 通过递归地应用这一过程，可以构建出整棵二叉树。 17. **图的最短路径计算及中心选择** - 使用Floyd算法可以求出图中每对顶点间的最短距离，从而得到最短路径矩阵。 - 求每个顶点的偏心度，即该顶点到达其他所有顶点的最大距离。 - 选择偏心度最小的顶点作为娱乐中心的位置，这是因为偏心度最小的顶点能够最方便地到达图中的所有其他顶点。 **四、算法设计题** 18. **寻找两个数使它们的和等于给定的数** - 可以采用双指针法，一个指针从数组的起始位置开始，另一个指针从数组的末尾开始。 - 根据两个指针所指的数之和与目标数的比较结果，移动指针直到找到符合条件的两个数或者两个指针相遇为止。 - 时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)。 19. **森林的叶子结点计数** - 可以遍历森林中的每一个结点，对于每个结点，检查它的左右子结点是否存在。 - 如果一个结点没有左右子结点，则它是叶子结点，累加计数器。 - 时间复杂度为\(O(n)\)，空间复杂度为\(O(h)\)，其中\(h\)为森林的高度。