一、名词解释

1、 数据对象

是具有相同性质的数据元素的集合，是数据的一个子集。

数据对象是一种运行时的概念，可以是外界实体（例如，产生或使用信息的任何事物）、事物（例如，报表）、行为（例如，打电话），总之可以由一组属性来定义的实体都可以被认为是数据对象。

1.1、 数据元素与数据对象

• 数据元素：组成数据的基本单位，与数据的关系是 “集合的个体”。
• 数据对象：性质相同的数据元素的集合，与数据的关系是 “集合的子集”。

2、KMP算法

3、顺序栈

顺序栈是栈的顺序存储结构，它通过一组地址连续的存储单元（通常为一维数组）实现栈的逻辑结构，借助两个指针管理元素存储：base指针固定指向栈底位置，top指针动态指示栈顶元素的位置。

其核心特点为：结构简单、操作便捷，存储密度高（无额外指针开销），但受限于数组容量，栈的大小固定，灵活性较差。

使用中需注意两类异常：

• 上溢：当栈已满（top指向数组最后一个元素）时执行入栈操作，会导致元素溢出；
• 下溢：当栈为空（top与 base指向同一位置）时执行出栈操作，会引发非法访问。

针对栈满的处理方案包括：一是通过扩容（定义更大数组并复制原元素）调整容量；二是入栈前先判断栈是否已满，提前规避上溢。

4、B和B+树

4.1、B + 树与 B 树的差异

B + 树是 B 树的一种变形体，它与 B 树的差异在于：

• 有 k 个子树的节点必有 k 个关键码；
• 非叶节点仅具有索引作用，元素信息均存放在叶节点中；
• 树的所有叶节点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

4.2、B + 树的优势

• 由于 B + 树在内部节点上不包含数据信息，因此在内存页中能够存放更多的 key，数据存放更加紧凑，具有更好的空间局部性；
• B + 树的叶子节点都是相继连接的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而且由于数据按序排列并且相连，所以便于区间查找和搜索，而 B 树则需进行每一层的遍历操作。

5、外部排序

• 定义：需要将待排序的记录存储在外存上，排序时把数据按部分调入内存进行排序，过程中需多次进行内存和外存之间的交换。

• 常用方法：归并排序

  该方法分两个阶段完成：

  1. 划分归并段（顺串）
     根据内存缓冲区大小，将外存中的文件分成若干长度为 l的子文件，依次读入内存并通过内部排序方法排序，再将有序子文件写回外存，这些有序子文件称为归并段（顺串）。
  2. 逐趟归并
     对归并段进行逐趟归并，使有序文件逐渐由小到大，直到得到整个有序文件。

• 归并排序的性能指标

  • 时间效率：O(nlog₂n)
  • 空间效率：O(n)
  • 稳定性：稳定

---

二、简答题