全国计算机二级之公共基础

《全国计算机二级之公共基础》由会员分享，可在线阅读，更多相关《全国计算机二级之公共基础（37页珍藏版）》请在金锄头文库上搜索。

1、第 一 章 数 据 结 构 与 算 法算 法定 义 ：指 阶 梯 方 案 的 准 确 而 完 整 的 描 述 （算 法 程 序 ）特 征 ：可 行 性 ，在 设 计 一 个 算 法 时 ，必 须 考 虑 它 的 可 行 性 。确 定 性 ，算 法 中 的 每 个 步 骤 必 须 是 明 确 定 义 的 ，不 允 许 模棱 两 可 。有 穷 性 ，算 法 必 须 在 有 限 的 时 间 内 做 完 ，必 须 在 执 行 有 限个 步 骤 之 后 终 止 。足 够 的 情 报 ，是 指 算 法 要 有 一 定 的 输 入 数 据 和 必 须 要 有 输出 结 果基 本 要 素 ：对 数 据 对 象

2、 的 运 算 和 操 作 ：算 术 运 算 、逻 辑 运 算 、关 系 运 算 、数 据 传 输算 法 的 控 制 结 构 ：1 算 法 中 各 操 作 之 间 的 执 行 顺 序2 描 述 算 法 的 工 具 ：传 统 流 程 图 、N-S 结 构 化 流 程图 、算 法 描 述 语 言 等3 一 个 算 法 一 般 可 以 用 顺 序 、选 择 、循 环 三 种 基 本结 构 组 合 而 成时 间 复 杂 度 ：是 指 执 行 算 法 所 需 要 的 计 算 工 作 量 ，可 以 用 算 法 所 执行 的 基 本 运 算 次 数 度 量空 间 复 杂 度 ：是 指 执 行 算 法 所 需

3、要 的 内 存 空 间 。包 括 算 法 程 序 、输入 的 初 始 数 据 以 及 算 法 所 执 行 过 程 需 要 的 额 外 空 间 。 时 间 复 杂 度 和 空 间 复 杂 度 相 互 独 立数 据 结 构 的 基 本 概 念数 据 ：需 要 处 理 的 数 据 元 素 的 集 合 ，一 般 来 说 ，这 些 数 据 元 素 ，具有 某 个 共 同 特 征 。 数 据 元 素 是 数 据 的 基 本 单 位 ，即 数 据 集 合 中 个 的 个 体 。有 时 一 个 数 据 元 素 可 有 若 干 数 据 项 组 成 。数 据 项 是 数 据 的 最 小单 位结 构 ：是 集 合

4、中 个 数 据 元 素 之 间 存 在 的 某 种 关 系 （联 系 ）数 据 结 构 ：是 指 相 互 有 关 联 的 数 据 元 素 的 集 合分 类 ：逻 辑 结 构 ： 线 性 结 构 ：线 性 表 、栈 、队 列 ； 非 线 性 结 构 ：树 、图存 储 结 构 ： 顺 序 存 储 ； 链 式 存 储运 算 ： 插 入 ； 删 除 ； 查 找 ； 排 序 逻 辑 结 构 ：反 映 数 据 元 素 之 间 的 逻 辑 关 系 的 数 据 结 构 线 性 结 构 ：有 且 只 有 一 个 根 结 点 ，它 无 前 件每 一 个 节 点 最 多 有 一 个 前 件 ，也 最 多 只 有 一

5、 个 后 件 例 如 ：春 夏 秋 冬 ：春 即 为 根 节 点 ，秋 即 为 夏 的 后件 ，春 为 夏 的 前 件 非 线 性 结 构 ：不 满 足 以 上 两 个 条 件 的 数 据 结 构 存 储 结 构 ：是 数 据 逻 辑 结 构 在 计 算 机 存 储 空 间 中 的 存 放 方 式 顺 序 存 储 结 构 ：主 要 用 于 线 性 的 数 据 结 构 ，它 把 逻 辑 相邻 的 数 据 元 素 存 储 在 物 理 上 相 邻 的 存 储 单 元 里 链 式 存 储 结 构 ：每 一 个 节 点 至 少 包 含 一 个 指 针 域 ，用 指 针的 指 向 来 体 现 数 据 元

6、素 之 间 在 逻 辑 上 的 联 系特 点 ： 一 种 逻 辑 结 构 可 以 有 多 种 存 储 结 构 不 同 的 存 储 结 构 其 数 据 处 理 的 效 率 不 同线 性 表 及 其 顺 序 存 储 结 构线 性 表 ：n（n0） 个 数 据 构 成 的 有限 序 列 ，表 中 除 第 一 个 元 素 外 的每 个 元 素 ，有 且 只 有 一 个 前 件 ，除 最 后 一 个 元 素 外 ，有 且 只 有 一个 后 件 。（线 性 结 构 习 惯 称 为 线 性 表 ）例 如 ，春 夏 秋 冬 ；英 文字 母 表 ；地 理 学 中 的 四 向 ；表 格 线 性 表 的 顺 序 存

7、 储 结 构 ：通 常 ，线 性 表 可 以 用 顺 序 存 储 和 链 式 存储 ，但 一 般 使 用 顺 序 存 储 结 构 。线 性 表 的 顺 序 存 储 又 叫 顺 序 表 。特 点 ：线 性 表 中 所 有 元 素 所 占 的 存 储 空 间 是 连 续 的线 性 表 中 数 据 元 素 所 在 的 存 储 空 间 中 是 按 逻 辑 顺 序 依次 存 放 的可 以 随 机 访 问 数 据 元 素做 插 入 、删 除 时 需 移 动 大 量 的 元 素 ，因 此 线 性 表 不 便 于插 入 和 删 除 元 素栈 和 队 列栈 ：是 限 定 在 一 端 进 行 插 入 和 删 除

8、的 线 性 表特 点 ： 栈 是只 能 在 栈 顶 进行 插 入 和 删 除栈 的 修 改 原 则 是 “先 进 后 出 ”或 “后 进 先 出 ”栈 底 指 针 不 变 ，栈 中 元 素 随 栈 顶 指 针 的 变 化 而 动 态 变 化（1）栈 底 指 针 bottom （2）栈 顶 指 针 top （3）入栈 （4）栈 满 （5）出 栈栈 具 有 记 忆 功 能栈 支 持 子 程 序 的 调 用队 列 ：是 指 允 许 在 一 端 进 行 插 入 ，而 在 另 一 端 进 行 删 除 的 线 性 表 。原 则 是 ：先 进 先 出 （或 后 进 后 出 ） 队 头 指 针 front 队

9、 尾 指 针 rear 入 队 出 队特 点 ：队 列 只 允 许 在 队 尾 进 行 插 入 ，而 在 对 头 进 行 删 除队 列 的 修 改 原 则 是 “先 进 先 出 ”或 “后 进 后 出 ”队 列 中 的 元 素 随 队 头 指 针 和 队 尾 指 针 的 变 化 而 动 态 变 化循 环 队 列 ：将 队 列 存 储 空 间 的 最 后 一 个 位 置 绕 到 第 一 个 位 置 ，形成逻 辑 上 的 环 状 空 间 。 Rear front，则 s=rear-front Rear=front，则 s=容 量 +rear-front Rear front，则 s=1 或 0（s

10、=1 是 队 列 中 元 素 已 满 元 素个 数 等 于 容 量 ，s=0 时 ，元 素 全 部 出 队 ）线 性 链 表线 性 表 可 以 采 用 顺 序 存 储 和 链 式 存 储顺 序 表 ：线 性 表 的 顺 序 存 储线 性 链 表 ：线 性 表 的 链 式 存 储 结 构特 点 ：各 数 据 结 点 的 存 储 空 间 可 以 不 连 续各 数 据 元 素 的 存 储 顺 序 与 逻 辑 顺 序 可 以 不 一 致线 性 表 的 链 式 存 储 空 间 所 占 存 储 空 间 大 于 顺 序 存 储 结 构（由 于 每 个 结 点 之 间 都 有 一 个 指 针 域 ）查 找 结

11、 点 时 链 式 存 储 要 比 顺 序 存 储 慢 （因 为 查 找 的 时 候 ，还 需 要 看 指 针 的 指 向 ，而 顺 序 存 储 结 构 一 目 了 然 ）链 式 存 储 插 入 删 除 元 素 比 顺 序 存 储 要 灵 活 （在 线 性 链 表 中进 行 插 入 和 删 除 ，不 需 要 移 动 链 表 中 的 元 素 ）线 性 表 ：线 性 表 顺 序 存 储 结 构线 性 表 链 式 存 储 结 构双 向 链 表循 环 链 表查 找 技 术顺 序 查 找 ：从 第 一 个 元 素 开 始 ，逐 个 将 线 性 表 中 的 元 素 与 被 查 找 元素 进 行 比 较 ，如

12、 果 相 等 则 查 找 成 功 。对 于 长 度 为 n 的 线 性 表 ，平 均要 进 行 n/2 次 比 较 ，在 最 坏 情 况 下 要 进 行 n 次 查 找 顺 序 查 找 适 用 于 无 序 表 和 线 性 链 表 （不 管 是 有 序 还 是 无 序 ）二 分 查 找 ：适 用 于 顺 序 存 储 的 有 序 表 ，对 长 度 为 n 的 线 性 表 ，在 最坏 的 情 况 下 进 行 log2n 次 比 较排 序 技 术排 序 平 均 时 间 最 坏 情 况冒 泡 排 序 n(n-1)/2 n(n-1)/2交 换 类快 速 排 序 n(n-1)/2 n(n-1)/2插 入 排

13、 序 n(n-1)/2 n(n-1)/2插 入 类 希 尔 排 序 nlog2n n1.5选 择 排 序 n(n-1)/2 n(n-1)/2选 择 类堆 排 序 nlog2n nlog2n快 速 排 序 ：基 本 思 想 ：在 要 排 序 的 序 列 找 一 个 数 作 为 基 准 数 （通 常 为 第 一 个 ）通 过 交 换 将 这 个 序 列 中 所 有 比 基 准 数 大 的 数 放 在 右边 ，比 基 准 数 小 的 放 在 左 边以 基 准 数 作 为 分 割 线 分 为 两 个 子 表 ，对 两 个 子 表 重复 上 述 步 骤第 二 章 程 序 设 计 基 础程 序 设 计 风

14、 格程 序 设 计 的 风 格 主 要 强 调 ：“清 晰 第 一 ，效 率 第 二 ” 应 当 注 重 和 考 虑 下 述 一 些 因 素 ：源 程 序 文 档 化数 据 说 明语 句 的 结 构输 入 和 输 出结 构 化 程 序 设 计结 构 化 程 序 设 计 方 法 的 主 要 原 则 可 以 概 括 为 ：自 顶 向 下 ：程 序 设 计 时 ，应 先 考 虑 总 体 ，后 考 虑 细 节 ；先 考 虑全 局 目 标 ，后 考 虑 局 部 目 标 。不 要 一 开 始 就 追 求 众 多 的 细 节 ，先 从 最 上 层 总 目 标 开 始 设 计 ，逐 步 使 问 题 具 体 化

15、 。（即 总 体 细 节 ；全 局 局 部 ）逐 步 求 精 ：对 于 复 杂 的 问 题 ，应 设 计 一 些 子 目 标 作 过 渡 ，逐步 细 化模 块 化 ：一 个 复 杂 问 题 ，肯 定 是 由 若 干 个 稍 简 单 的 问 题 构 成 。模 块 化 是 把 程 序 要 解 决 的 总 目 标 分 解 成 分 目 标 ，再 进 一 步 分 解 为具 体 的 小 目 标 ，把 每 个 小 目 标 称 为 一 个 模 块限 制 使 用 goto 语 句基 本 结 构 ：顺 序 结 构 ：一 种 简 单 的 程 序 设 计 ，即 按 照 程 序 语 句的 自 然 顺 序 ，一 条 语

16、句 一 条 语 句 地 执 行 程 序 ，它 是最 基 本 、最 常 用 的 结 构选 择 结 构 ：又 称 分 支 结 构 ，包 括 简 单 选 择 和 多 分 支 选择 结 构 ，可 根 据 条 件 ，判 断 应 该 选 择 哪 一 条 分 支 来执 行 相 应 的 语 句 序 列重 复 结 构 ：又 称 为 循 环 结 构 ，可 根 据 是 否 需 要 重 复 执行 某 一 相 同 或 类 似 的 程 序 段面 向 对 象 的 程 序 设 计 （如 JAVA）面 向 对 象 的 方 法 的 本 质 就 是 主 张 从 客 观 世 界 固 有 的 事 物 出 发 来 构造 系 统 ，提 倡 人 们 在 现 实 生 活 中 常 用 的 思 维 来 认 识 、理 解