[去TMD考试] 数据结构中的相关概念

1. 数据结构包含哪三方面的内容

   1. 数据的逻辑结构
   2. 数据的存储结构
   3. 施加于数据上的操作

2. 数据的存储结构有哪些种类

   1. 顺序存储结构
      优点: 基于下标的随机检索效率高
      缺点: 插入, 删除成本高, 空间利用率低, 会出现存储碎片
   2. 连接存储结构
      优点: 插入删除效率高, 空间利用率高, 可以避免存储碎片
      缺点: 基于下标或者关键字的检索效率低
   3. 索引存储结构
      优点: 是顺序存储和链接存储的结合, 具有两者的优点
   4. 散列存储结构
      优点: 对基于关键字的随机检索, 插入, 删除均非常高效
   5. 组合存储结构
      将以上4种结构组合使用

3. 算法与数据结构的关系
   密切相关, 算法依赖于具体的数据结构, 数据结构影响算法的效率.
   1976年, 沃森提出: 算法 + 数据结构 = 程序

4. 算法的特性

   1. 有限性
   2. 确定性
   3. 输入(0个或多个)
   4. 输出(1个或多个)
   5. 可行性

算法和计算过程的区别: 后者不需要满足有限性

5. 算法的评价准则
   1. 正确性
   2. 时间复杂度
   3. 空间复杂度
   4. 可读性
   5. 坚固性(健壮性, 鲁棒性, robustness)