数据结构考研 第一章 绪论

1.数据结构的基本概念

1.1基本概念和术语

1. 数据
   信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
2. 数据对象
   具有相同性质的数据元素的集合， 是数据的一个子集
3. 数据元素
   数据的基本单位， 通常作为一个整体进行考虑和处理。
4. 数据项
   构成数据元素的不可分割的最小单位

1.2数据结构的三要素

1. 逻辑结构
   线性结构：线性表、栈、队列
   集合
   树形结构
   图状结构
2. 存储结构
   顺序存储
   链式存储
   索引存储
   散列存储
3. 数据的运算
   运算的定义针对逻辑结构
   运算的实现针对存储结构

2.算法和算法评价

2.1算法的基本概念

1. 算法
   对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令
   表示个或多个操作。
2. 算法的五个特性
   有穷性
   确定性
   可行性
   输入
   输出
3. 算法和程序的区别
   有穷性
   算法必须是有穷的，程序可以是无穷的
   正确性
   算法必须是正确的，程序可以是错误的
   描述方法
   信算法可以用伪代码、程序语言等描述，程序只能用程序语言编写并可以运行

2.2算法效率的度量

1. 时间复杂度
   T(n) = O(f(n))，其中0表示T(n)与f(n)在n->正无穷时为同阶无穷大
2. 空间复杂度
   除本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操
   作的工作单元和存储为实现算法所需的一些信息的辅助空间。
   ★算法原地工作时指算法所需辅助空间为常量，O(1)