HUST 2015 887数据结构真题回忆版1

【数据结构】是计算机科学的重要组成部分，主要研究如何在计算机中高效地组织和存储数据，以便于进行各种操作。在2015年华中科技大学887数据结构与算法分析的真题中，涉及了多个核心知识点，下面将详细阐述。 **一、名词解释** 1. **（图的）广度优先搜索 (BFS)**：一种图遍历算法，按照从起点出发，先访问离起点近的顶点，再访问远的顶点的顺序进行搜索。 2. **二叉搜索树 (BST)**：二叉树的一种，其中每个节点的左子树只包含小于当前节点的元素，右子树只包含大于当前节点的元素。 3. **（二叉树结点的）平衡因子**：在AVL树中，平衡因子是节点的左子树高度减去右子树高度的差，用于保持树的平衡。 4. **有向完全图**：每个顶点与其他所有顶点都有一条有向边相连的图。 5. **空间复杂度**：衡量算法在执行过程中临时占用存储空间大小的度量。 **二、单项选择题** 这部分题目涉及了算法的时间复杂度分析和排序算法等概念，例如： - 后续表达式求值：考察了中缀表达式到后缀表达式的转换和后缀表达式的计算。 - 时间复杂度：如选项B，O(log n)，表示算法的时间复杂度与问题规模n成对数关系。 - 排序算法：稳定性，冒泡排序是稳定的排序算法，选择排序和插入排序是不稳定的，归并排序是稳定的。 - 时间复杂度分析：题目给出的时间复杂度形式暗示了平方级的时间复杂度，即C选项的n^2。 - 查找时间复杂度：在有序数组中查找，最好情况是第一项找到，时间复杂度为O(1)，最坏情况是最后一项找到，时间复杂度为O(n)。 **三、大题** 1. **二叉树的构造**：通过中序遍历和后序遍历，可以唯一确定一棵二叉树，这是构建二叉树的一个基本问题。 2. **哈夫曼树和编码**：哈夫曼树是一种带权路径长度最短的二叉树，用于数据压缩。构建哈夫曼树并给出编码需要根据权值进行构造。 3. **小根堆的构造**：小根堆是一种特殊的完全二叉树，其中每个父节点的值都小于或等于其子节点。通过插入和调整操作，可以将一组数构造成小根堆。 4. **有向图的邻接矩阵和Dijkstra算法**：邻接矩阵表示图中节点之间的连接关系；Dijkstra算法用于求解单源最短路径问题，从0V节点开始，逐步扩展找到所有节点的最短路径。 5. **数组中寻找元素i使得i = a[i]**：这是一个线性查找问题，时间复杂度为O(n)。 **四、算法设计** 1. **计算二叉树叶子结点个数**：可以通过遍历二叉树，统计没有子节点的结点数量。 2. **计算逆序对**：利用分治策略和排序，可以在O(n log n)的时间复杂度内计算数组中的逆序对数量。 这些知识点涵盖了数据结构的基础概念、操作和算法，对于理解数据结构和优化算法至关重要。学习这些内容有助于解决实际问题，提高程序性能。