哈工大2012秋数据结构与算法期末考试试题解析

本资源是一份哈尔滨工业大学2012年秋季学期数据结构与算法期末考试试卷，涵盖了多个关键知识点。以下是详细解读： 1. **完全二叉树结点数**：深度为6，根节点层次为1的完全二叉树，最少有2^(h-1) + 1个结点，其中h为高度，代入h=6，得出至少有31个结点，答案是C。 2. **森林的树的数量**：非连通无向图是森林，如果n个结点、k条边，因为n＞k，所以至少存在n-k棵树，因为每增加一条边都会连接两个不连通的子图，答案是C。 3. **邻接矩阵压缩存储**：邻接矩阵表示图中节点间的连接，无向图G有n个顶点，压缩存储在B数组中，需要的空间k等于最大边数，即(n-1)+1= n，因此k的最小值为n(n-1)/2，答案是D。 4. **排序算法稳定性**：冒泡排序和插入排序都是稳定的，因为它们不会改变相等元素的相对顺序；堆排序和选择排序是非稳定的，因为它们可能会改变相等元素的顺序。题目要求算法在最后一趟前元素未到位的情况，这通常发生在不稳定排序中，所以答案是A（堆排序）。 5. **归并排序趟数**：k路归并是指同时合并k个子序列，所需趟数是将m个初始归并段合并成1个所需的最小步骤，即log2k，答案是A。 6. **前缀码判断**：前缀码是一种字符串编码规则，任何字符串都不是另一个字符串的前缀。在给定的选项中，(0,1,00,11)不符合前缀码的要求，因为11是10的后缀，答案是B。 7. **二叉树结点数**：高度为h的二叉树只有度为0（叶子节点）和度为2的节点，此类二叉树的特点是除了最后一个层次外，其余各层都是满的，所以结点数为2^(h-1) * 2 + 1 = 2h - 1，答案是B。 8. **树中结点关系**：结点M和N作为结点P的孩子，且M在P的i位置，N在i+1位置，根据二叉树的性质，M和N在二叉树表示中是相邻的，且M通常是N的左孩子，答案是B。 9. **二分查找判定树的外部结点数**：二分查找判定树中，每个结点都有最多两个子结点，除根节点外，其他结点都是查找失败的外部结点，因此外部结点数为n-1，答案是A。 10. **最小堆中的最大记录**：最小堆（堆顶元素最小）中，最大记录位于堆顶，即位置n/2（向下取整），答案是C。 最后两部分是填空题，涉及插入操作的时间复杂度和稀疏矩阵的存储方式，这部分内容没有具体给出，需要根据教材或课程知识进行填充。整体而言，这份试卷涵盖了数据结构基础概念、图论、排序算法、树结构、查找算法和矩阵存储等多个方面的知识点。