《 数 据 结 构 》 期 末 复 习 复习要点： 第一章 1.相 关 基 本 概 念 ： 数 据 、 数 据 元 素 （ 基 本 单 位 ）、 数 据 项 （ 最 小 单 位 ）、 算 法 及其 特 征 等 ； ◎ 数 据 ： 所 有 能 输 入 到 计 算 机 中 并 被 计 算 机 程 序 处 理 的 符 号 总 称 。 ◎ 数 据 元 素 ： 基 本 单 位 。 ◎ 数 据 项 ： 最 小 单 位 。 ◎ 算 法 特 征 （ 5 点 ）： 有 穷 性 ； 确 定 性 ； 可 行 性 ； 输 入 ； 输 出 。 2.逻 辑 结 构 、 存 储 结 构 （ 物 理 结 构 ） 及 其 类 型 ； ◎ 逻 辑 结 构 有 四 种 基 本 类 型 ： 集 合 、 线 性 结 构 、 树 形 结 构 和 网 状 结 构 。 ◎ 数 据 元 素 之 间 的 关 系 有 两 种 不 同 的 表 示 方 法 ： 顺 序 映 象 和 非 顺 序 映 象 ， 并 由此 得 到 两 种 不 同 的 存 储 结 构 ： 顺 序 存 储 结 构 和 链 式 存 储 结 构 。 ◎ 注 ： 期 中 考 题 目 数 据 结 构 分 为 两 大 类 ， 即 为 逻 辑 结 构 和 存 储 结 构 。 其 中 逻 辑 结 果 又 分 为 线 性 结构 和 非 线 性 结 构 ， 存 储 结 构 一 共 有 四 种 （ 顺 序 、 链 接 、 索 引 、 散 列 ）。 3.算 法 分 析 ： 语 句 频 度 （ 执 行 次 数 ） 计 算 、 时 间 和 空 间 复 杂 度 分 析 。 表 示 方 法 ◎ 语 句 频 度 ： 直接 写次 数 。 ◎ 时 间 复 杂 度 ： O(执 行 次 数 ),如： O(n)。 ◎ 空 间 复 杂 度 ： O(所 需空 间 ) 第二章 1.顺 序 表 （ 数 组） 插入 、 删除、 有 序 表 合 并 算 法 及 其 移动次 数 计 算 ； 数 据 元素 序 号 1 2 3 4 5 6 7 8 表 示 L.elem[0] [1] [2] [3] [4] [5] [6] [7] ◎ 顺 序 表 插入 算 法 思想： 如果 要在序 号 5 前插入 元 素 e， 需要将序 号 5～8 向后移动一 个位 置。 ▲移动次 数 为 4 次 ， 公式 n-i+1 12 13 21 24 28 30 42 77 ◎顺序表删除 算法思想：如果要删除序号5 ...
