北航考研数据结构历年试题

### 数据结构知识点解析 #### 一、算法分析的前提条件与主要方面 - **前提条件**：进行算法分析之前，需要明确算法解决的问题及其输入范围、数据类型等基本要素。此外，还需要了解算法的基本结构和执行流程，以便进行精确的分析。 - **主要分析方面**： - **时间复杂度**：评估算法执行所需的时间资源，通常用大O符号表示。例如，O(1) 表示常数时间复杂度，O(n) 表示线性时间复杂度。 - **空间复杂度**：评估算法执行过程中所需的额外内存资源。 - **稳定性**：如果一个排序算法能保持相同值元素原有的相对顺序不变，则称此排序算法是稳定的。 - **适应性**：算法对不同输入规模或特定数据分布的性能变化情况。 #### 二、线性表的存储结构选择 - **频繁插入删除操作**：当需要频繁地对线性表进行插入和删除操作时，建议采用**链式存储结构**。因为链式存储结构（如单链表、双链表）可以在O(1)时间内完成插入和删除操作，而顺序存储结构（如数组）则需要移动大量元素，时间复杂度较高，通常为O(n)。 #### 三、双向循环链表中的插入操作 - **插入步骤**：在双向循环链表中，向节点`q`后插入节点`p`的操作分为四步： 1. `llink(p) ← q`：设置新节点`p`的前驱指针指向`q`。 2. `rlink(p) ← rlink(q)`：设置新节点`p`的后继指针指向原`q`的后继节点。 3. `rlink(q) ← p`：更新`q`的后继指针指向`p`。 4. **第四步**：更新`p`的后继节点的前驱指针，即`llink(rlink(p)) ← p`。 #### 四、对称矩阵的压缩存储 - **压缩存储**：对称矩阵可以利用其对称性进行压缩存储，只存储矩阵的下三角部分或上三角部分即可。假设存储下三角部分，采用行优先顺序存储。 - **计算公式**：对于下三角矩阵中的任意元素`aij` (i ≥ j)，其在一维数组`B`中的下标位置`k`可以通过以下公式计算得出：\[k = \frac{(2n-i-1)i}{2} + j - 1\] 其中，`n`为矩阵的大小，`i`和`j`为矩阵元素的位置索引。 #### 五、稀疏矩阵的三元组表示 - **定义**：稀疏矩阵是指非零元素较少的矩阵。当稀疏矩阵中非零元素的数量`t`远小于矩阵元素总数`m×n`时，使用三元组表示才显得有意义。 - **阈值**：一般认为当`t < (m×n) / 10`时，使用三元组表示较为经济有效。 #### 六、多堆栈存储方案比较 - **方案1**：分别使用多个顺序存储空间建立多个独立堆栈。 - **优点**：管理简单，容易实现。 - **缺点**：可能会浪费存储空间。 - **方案2**：多个堆栈共享一个顺序存储空间。 - **优点**：更高效利用存储空间。 - **缺点**：实现相对复杂，可能需要动态调整堆栈的空间分配。 - **方案3**：分别建立多个独立的链式堆栈。 - **优点**：灵活性高，易于扩展。 - **缺点**：需要额外的指针空间，可能导致一定的空间开销。 #### 七、图的遍历序列多样性 - **因素**：图的遍历序列受到多种因素的影响，包括： - 起始顶点的选择。 - 遍历策略的不同（深度优先搜索DFS vs. 广度优先搜索BFS）。 - 图的具体结构（连通性、环路等）。 - 访问顶点的具体规则（如访问顺序）。 #### 八、线性表的折半查找条件 - **条件**：进行折半查找的前提是线性表必须是有序的，并且通常采用顺序存储结构。 #### 九、哈希表及其查找机制 - **定义**：哈希表是一种根据键值(Key value)来直接访问内存存储位置的数据结构。通过哈希函数将键值映射到表的一个位置来访问记录，加快查找速度。 - **查找机制**：将待查找键值通过哈希函数转换为哈希地址，然后在哈希表中查找对应位置上的记录。 #### 十、排序算法的选择 - **排序方法比较**：对于堆积排序法、快速排序法和归并排序法，它们各有优势： - **节省存储空间**：归并排序需要额外的存储空间用于合并操作，因此从节省空间的角度考虑，首选快速排序，次选堆积排序。 - **排序稳定性**：归并排序是稳定的排序算法，而堆积排序和快速排序不稳定。 - **平均情况下的排序速度**：快速排序在平均情况下的时间复杂度为O(n log n)，是这三种算法中最快的。 #### 十一、AOE网的十字链表存储方法 - **顶点结点与边结点结构**：顶点结点包含名称、入度、出度等信息；边结点表示活动，包含活动的权值、最早开始时间、最晚开始时间等属性。 - **存储映射**：通过列指针和行指针关联顶点结点和边结点，形成网络结构。 #### 十二、多表结构分析 - **物理结构与逻辑结构映射**： - 物理结构：顺序存储、链式存储。 - 逻辑结构：DEPT表可视为线性表，OFFICE表和TEACHER表则可以看作是树形结构。 - **存储映像示意图**：绘制DEPT表、OFFICE表和TEACHER表之间的关联关系图，展示它们之间的指针连接情况。 以上知识点总结了《北航考研数据结构历年试题》中关于数据结构的基本概念、算法分析方法、不同存储结构的应用场景、矩阵的压缩存储、稀疏矩阵的表示、多堆栈存储方案的优缺点比较、图的遍历、折半查找的适用条件、哈希表的原理与查找机制以及几种常见排序算法的特性等内容。这些知识点不仅涵盖了理论基础，还涉及实际应用案例，有助于深入理解数据结构领域的核心知识和技术。