1.1 基本概念与术语
数据 (Data)
信息的载体，是描述客观事物的数、字符及所有能输入到计算机中被程序处理的符号集合。数据元素 (Data Element)
数据的基本单位，在计算机程序中通常作为一个整体考虑。如一个学生记录。数据项 (Data Item)
构成数据元素的、不可分割的最小单位。如学生的学号、姓名。数据对象 (Data Object)
性质相同的数据元素的集合，是数据的一个子集。关系：数据 > 数据对象 > 数据元素 > 数据项。一个数据元素可由若干数据项组成。
1.2 数据结构三要素
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包括三个方面的内容：
1. 逻辑结构
数据元素之间的逻辑关系，与存储无关，分为四类基本结构：
- 集合：各元素同属一个集合，无其他关系。
- 线性结构：一对一关系，如线性表、栈、队列。
- 树形结构：一对多关系，如二叉树、树。
- 图状结构：多对多关系，如有向图、无向图。
2. 存储结构（物理结构）
数据在计算机中的表示（映像），主要有：
- 顺序存储：借助元素在存储器中的相对位置表示逻辑关系，支持随机存取。
- 链式存储：借助指针指示元素逻辑关系，不要求逻辑相邻的元素物理相邻。
- 索引存储：建立附加的索引表来查找数据。
- 散列存储：根据关键字直接计算存储地址（哈希）。
3. 数据的运算
定义在逻辑结构上的操作，如查找、插入、删除、更新、排序等，其实现依赖于存储结构。
重要结论：数据的逻辑结构独立于存储结构；同一逻辑结构可对应多种存储结构，运算效率因存储结构而异。
4. 抽象数据类型 (ADT)
抽象数据类型 (Abstract Data Type)
指一个数学模型及定义在该模型上的一组操作。ADT 仅关心数据对象、数据关系和基本操作，不关心具体实现。ADT 可用三元组 (D, S, P) 表示：
- D — 数据对象（Data Object）
- S — D 上的关系集合（Structure）
- P — 对 D 的基本操作集合（Operations）
ADT 定义格式：
ADT 抽象数据类型名 {
数据对象：<数据对象的定义>
结构关系：<结构关系的定义>
基本操作：<基本操作的定义>
} ADT 抽象数据类型名；408 考点：ADT 将数据的使用（逻辑层）与实现（物理层）分离，是面向对象思想的基础。数据结构 = 逻辑结构 + 存储结构 + 数据运算，ADT 强调前三者中对「操作」的抽象。
1.3 算法与算法分析
算法 (Algorithm)
对特定问题求解步骤的一种描述，是指令的有限序列。算法的五个重要特性：
- 有穷性：步骤有限，每步在有限时间内完成。
- 确定性：每条指令有确切含义，无二义性。
- 可行性：每步操作均可通过基本运算有限次执行实现。
- 输入：有零个或多个输入。
- 输出：有一个或多个输出。
时间复杂度
衡量算法执行时间随问题规模 n 增长的趋势，用大 O 记号表示。常见的复杂度递增关系：
常见时间复杂度比较（从优到劣）：
| 复杂度 | 类型 | 示例算法 |
|---|---|---|
| O(1) | 常数阶 | 直接取下标 |
| O(log n) | 对数阶 | 折半查找 |
| O(n) | 线性阶 | 顺序查找 |
| O(n log n) | 线性对数阶 | 归并排序、快速排序 |
| O(n²) | 平方阶 | 冒泡排序、简单选择排序 |
| O(n³) | 立方阶 | 矩阵乘法 |
| O(2ⁿ) | 指数阶 | 汉诺塔递归 |
空间复杂度
算法所需存储空间随问题规模 n 增长的趋势。原地工作算法空间复杂度为 O(1)。