《全国计算机二级之公共基础》由会员分享,可在线阅读,更多相关《全国计算机二级之公共基础(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)面 向 对 象 的 方 法 的 本 质 就 是 主 张 从 客 观 世 界 固 有 的 事 物 出 发 来 构造 系 统 ,提 倡 人 们 在 现 实 生 活 中 常 用 的 思 维 来 认 识 、理 解