数据结构 陈明 习题答案

《数据结构 陈明 习题答案》由会员分享，可在线阅读，更多相关《数据结构 陈明 习题答案（40页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构 _陈 明 _习 题 答 案第 1 页 共 40 页习 题 一 答 案1 填 空 题（1） 数 据 元 素 的 有 限 集 合 ，k上 关 系 的 有 限 集 合（2） 顺 序 存 储 （ 连 续 ） ， 链 式 存 储 （ 不 连 续 ）（3） 有 穷 性 ， 确 定 性 ， 可 行 性 ， 输 入 ， 输 出（4） 时 间 复 杂 度 ， 空 间 复 杂 度3 简 述 下 列 术 语（1） 数 据是 信 息 的 载 体 ， 它 是 描 述 客 观 事 物 的 数 、 字 符 以 及 所 有 能 输 入 到 计 算 机 中 被 计 算 机 程 序 识别 、 加 工 处 理 的

2、信 息 的 集 合 。（2） 数 据 元 素是 数 据 的 基 本 单 位 ， 是 对 一 个 客 观 实 体 的 数 据 描 述 。 一 个 数 据 元 素 可 以 由 一 个 或 若干 个 数 据 项 组 成 。 数 据 元 素 也 被 称 为 结 点 或 记 录 。（3） 数 据 对 象具 有 相 同 性 质 的 数 据 元 素 的 集 合 就 是 一 个 数 据 对 象 ， 它 是 数 据 的 一 个 子 集 。（4） 数 据 结 构数 据 结 构 就 是 数 据 之 间 的 相 互 关 系 （ 即 数 据 的 组 织 形 式 ） 及 在 这 些 数 据 上 定 义 的 数 据运 算

3、方 法 的 集 合 。（5） 存 储 结 构数 据 的 存 储 结 构 是 数 据 的 逻 辑 结 构 在 计 算 机 内 部 的 表 示 或 实 现 ， 又 称 为 数 据 的 物 理 结构 ， 它 包 括 数 据 元 素 的 表 示 和 关 系 的 表 示 。（6） 数 据 类 型是 具 有 相 同 性 质 的 计 算 机 数 据 的 集 合 及 定 义 在 这 个 数 据 集 合 上 的 一 组 操 作 的 总 称 。5 常 用 的 存 储 表 示 方 法 有 哪 几 种 ？（1） 顺 序 存 储 方 法该 方 法 是 将 逻 辑 上 相 邻 的 结 点 存 储 在 物 理 位 置 上

4、也 相 邻 的 存 储 单 元 里 ， 结 点 之 间的 逻 辑 关 系 由 存 储 单 元 的 邻 接 关 系 来 表 示 （ 也 就 是 说 ， 只 存 储 结 点 的 值 ， 不 存 储 结 点 之 间 的 关 系 ） ，这 种 存 储 表 示 称 为 顺 序 存 储 结 构 。（2） 链 式 存 储 方 法链 式 存 储 方 法 不 要 求 逻 辑 上 相 邻 的 结 点 在 物 理 位 置 上 亦 相 邻 ， 结 点 间 的 关 系 由 附加 的 指 针 来 表 示 ， 指 针 指 向 结 点 的 邻 接 结 点 ， 这 样 将 所 有 结 点 串 联 在 一 起 ， 称 为 链 式

5、 存 储 结 构 。（3） 索 引 存 储 方 法索 引 存 储 是 在 存 储 结 点 信 息 的 同 时 ， 再 建 立 一 个 附 加 的 索 引 表 ， 然 后 利 用 索 引 表中 索 引 项 的 值 来 确 定 结 点 的 实 际 存 储 单 元 地 址 。（4） 散 列 存 储 方 法散 列 存 储 的 基 本 思 想 是 根 据 结 点 的 关 键 字 直 接 计 算 出 结 点 的 存 储 地 址 。7 举 例 说 明 一 下 数 据 结 构 和 算 法 的 关 系 。通 过 公 式 ： 程 序=数 据 结 构+算 法 我 们 可 以 比 较 直 观 地 看 出 二 者 的

6、关 系 ， 即 数 据 结 构 （ 包 个 完 整 的 程序 括 逻 辑 结 构 和 存 储 结 构 ） 的 设 计 和 算 法 的 编 写 是 程 序 设 计 的 两 个 关 键 步 骤 ， 一 就 是 由 一 套 合 理 的 数 据 结构 和 建 立 在 该 结 构 上 的 算 法 构 成 的 。 具 体 的 说 ： 在 进 行 程 序 设 计 之 前 我 们 首 先 要 为 待 处 理 的 数 据 设 计 一 个合 理 的 逻 辑 结 构 ， 进 而 为 之 设 计 一 种 适 合 的 存 储 结 构 ， 因 为 光 有 逻 辑 结 构 是 不 够 的 ， 只 有 存 储 结 构 才 是

7、 与计 算 机 语 言 直 接 相 关 的 ！ 有 了 这 一 套 前 期 准 备 ， 我 们 才 能 在 这 个 基 础 上 设 计 算 法 ， 用 一 种 计 算 机 语 言 去 处理 这 些 数 据 ， 最 终 达 到 程 序 设 计 的 目 的 。 当 然 ， 随 着 逻 辑 结 构 和 存 储 结 构 的 不 同 ， 我 们 设 计 的 算 法 也 会 有所 差 别 ， 这 在 以 后 的 学 习 中 会 体 会 到 。 下 面 通 过 一 个 简 单 的 例 子 说 明 这 种 关 系 。假 设 我 们 要 设 计 一 个 两 个n阶 方 阵 相 乘 的 程 序 ： 已 知 两 个

8、n阶 方 阵A和B， 我 们 要 计 算 它 们 的 乘 积 ，得 到 一 个 新 的n阶 方 阵C。 那 么 在 设 计 这 个 程 序 之 前 首 先 想 到 得 就 是 设 计 一 种 逻 辑 结 构 表 示 方 阵 ， 这 里 我们 用 二 维 数 组 表 示 它 们 ， 因 为 二 维 数 组 最 能 直 观 地 表 示 这 种 结 构 ； 有 了 逻 辑 结 构 了 自 然 还 要 为 之 设 计 一 种存 储 结 构 ， 这 里 我 们 选 择 顺 序 存 储 方 法 ， 因 为C语 言 对 这 种 存 储 结 构 给 予 了 很 好 的 支 持 ， 例 如 定 义 一 个n阶

9、实 型 的 二 维 数 组A只 要 用floatAnn;这 条 语 句 就 可 以 了 ，C语 言 在 内 存 种 为 之 分 配 了 一 个n*n长 度 的 顺 序 存 储 空 间 （ 注 意 ：C语 言 默 认 二 维 数 组 是 按 行 优 先 存 储 的 ） ， 是 不 是 很 方 便 ？ 有 了 这 些 准 备 ， 我们 就 可 以 设 计 算 法 进 行 计 算 了 ， 其 算 法 如 下 ：voidmatrixmult(floatAnn,floatBnn,floatCnn)inti,j,k;floatx;for(i=0;i,画 出 这 个 逻 辑 结 构 的 图 示 ， 并 确

10、定 相 对 于r哪 些 结 点 是 开 始 结 点 ， 哪 些 结 点 是 终 端结 点 ？通 过 以 后 的 学 习 我 们 会 知 道 这 是 一 个 有 向 图 ， 图 中 共 有9个 结 点 ， 其 中 开 始 结 点 有2个 ， 分 别 为K1和K2； 终 端 结 点 有2个 ， 分 别 为K6和K7。逻 辑 结 构 图 表 示 如 下 ： k4k2k1k6k5 k7k3k8 k911 何 谓 算 法 ？ 试 详 述 算 法 设 计 的 目 的 和 算 法 必 须 满 足 的 条 件 。算 法 是 对 特 定 问 题 求 解 步 骤 的 一 种 描 述 ， 实 际 上 是 指 令 的

11、 有 限 序 列 ， 其 中 每 一 条 指 令 表 示 一 个 或 多 个操 作 。 我 们 知 道 ， 程 序 设 计 的 第 一 步 是 为 待 处 理 的 数 据 设 计 一 种 合 理 的 数 据 结 构 （ 包 括 逻 辑 结 构 和 物 理 结构 ） ， 这 一 步 固 然 重 要 ， 但 这 不 是 我 们 的 目 的 ， 设 计 数 据 结 构 的 最 终 目 的 是 为 了 在 这 个 基 础 上 编 写 算 法 进 而对 其 进 行 相 关 的 操 作 （ 例 如 ： 遍 历 ， 查 找 ， 排 序 ， 插 入 ， 删 除 等 ） ， 如 果 不 去 编 写 相 应 的

12、算 法 那 么 设 计 数 据结 构 也 就 失 去 了 它 的 意 义 ， 你 所 输 入 到 计 算 机 的 数 据 永 远 都 是“死 数 据”， 程 序 设 计 也 就 成 了 空 谈 ！ 一 句 话 ：设 计 数 据 结 构 的 目 的 是 为 了 对 它 们 进 行 处 理 ， 而 数 据 处 理 正 是 通 过 相 应 的 算 法 实 现 的 ！总 的 来 说 ， 一 个 算 法 应 具 有 以 下5个 重 要 特 性 ： 第 一 ， 有 穷 性 ： 一 个 算 法 必 须 总 是 （ 对 任 何 合 法 的 输入 值 ） 在 执 行 有 穷 步 之 后 结 束 ， 且 每 一

13、步 都 可 在 有 穷 时 间 内 完 成 ； 第 二 ， 确 定 性 ： 算 法 中 每 条 指 令 必 须 有确 切 的 含 义 ， 读 者 理 解 时 不 会 产 生 二 意 性 。 并 且 ， 在 任 何 条 件 下 ， 算 法 只 有 唯 一 的 一 条 执 行 路 径 ， 即 对 相同 的 输 入 只 能 得 到 相 同 的 输 出 ； 第 三 ， 可 行 性 ： 一 个 算 法 是 能 行 的 ， 即 算 法 中 描 述 的 操 作 都 是 通 过 已 经 实现 的 基 本 运 算 执 行 有 限 次 来 实 现 的 ； 第 四 ， 输 入 ： 一 个 算 法 有 零 个 或 多

14、 个 的 输 入 ， 这 些 输 入 取 自 于 某 个 特定 的 对 象 的 集 合 ； 第 五 ， 输 出 ： 一 个 算 法 有 一 个 或 多 个 的 输 出 。 这 些 输 出 是 同 输 入 有 着 某 些 特 定 关 系 的 量 。13 编 写 一 个 算 法 ， 对 三 个 两 位 数 按 由 大 到 小 的 顺 序 进 行 排 序 ， 描 述 构 造 该 算 法 的 思 维 程 。算 法 如 下 ：voidorder(shorta,shortb,shortc)shortt;if(a 10,000） ,哪 个 程 序 对 运 行 时 间 有 保 证 ？Ab. N值 较 小 （

15、N N 时 ， 算 法 终 止 ， 运 行 时 间 为 O（ NloglogN） ， 写 出 一 个 程 序 来 执 行Eratosthenes过 滤 法 ， 并 证 实 所 声 明 的 运 行 时 间 ， 区 别 O（ N） 和 O（ NlogN） 的 运 行 时 间 有 多 困 难 ？程 序 略15.等 式 A5 + B5 + C5 + D5 + E5 = F5， 有 一 个 满 足 0 next=p-next-next;（3）Head-next=Head（Head为 链 表 的 头 结 点 ） ，Head=NULL（Head为 链 表 的 第 一 个 结 点 ）（4）Head-next=

16、Head-next-next（Head为 链 表 的 头 结 点 ） ；Head=Head-next（Head为 链 表的 第 一 个 结 点 ） ， 以 上 均 假 设 链 表 存 在 至 少 两 个 结 点 。（5）D（ 因 为 顺 序 表 具 有 随 即 存 取 的 优 点 ）3 动 态 与 静 态 数 据 结 构 在 计 算 机 内 存 中 的 存 储 方 式 有 何 不 同 ？ 各 有 何 优 缺 点 ？参 考 答 案 ： 静 态 存 储 方 式 （ 顺 序 存 储 ）逻 辑 相 邻 ， 物 理 相 邻 。 优 点 ： 便 于 数 据 的 随 即 存 取 ， 结 点 存 储 利用 率 高 （ 不 需 要 存 储 指 针 ） ； 缺 点 ： 存 取 数 据 时 要 移 动 大 量 的 元 素 ， 由 于 事 先 不 知 道 存 储 结 点 的 最 大 个 数 ，所 以 应 该 分 配 尽 可 能 大 的 存 储 空 间 ， 从 而 可 能 会 造