《数据结构练习题》答案.pdf

第 一 章 概 论 自 测 题 答 案 姓 名 班 级 题 号 一 二 三 四 五 六 总 分 题 分 33 15 9 8 20 15 100得 分 一、填 空 题（每 空 1分，共 3 3分）1.一 个 计 算 机 系 统 包 括 硬 件 系 统 和 软 件 系 统 两 大 部 分。2.一 台 计 算 机 中 全 部 程 序 的 集 合，称 为 这 台 计 算 机 的 软 件 资 源/（系 统）。3.计 算 机 软 件 可 以 分 为 系 统 软 件 和 应 用 软 件 两 大 类。科 学 计 算 程 序 包 属 于 应 用 软 件，诊 断 程 序 属 于 系 统 软 件（工 具）。4.一 种 用 助 忆 符 号 来 表 示 机 器 指 令 的 操 作 符 和 操 作 数 的 语 言 是 汇 编 语 言。5.数 据 结 构 是 一 门 研 究 非 数 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的 操 作 对 象 以 及 它 们 之 间 的 关 系 和 运 算 等 的 学 科。6.数 据 结 构 被 形 式 地 定 义 为（D,R）,其 中 D 是 数 据 元 素 的 有 限 集 合,R 是 D 上 的 关 系 有 限 集 合。7.数 据 结 构 包 括 数 据 的 逻 辑 结 构、数 据 的 存 储 结 构 和 数 据 的 运 算 这 三 个 方 面 的 内 容。8.数 据 结 构 按 逻 辑 结 构 可 分 为 两 大 类，它 们 分 别 是 线 性 结 构 和 非 线 性 结 构。9.线 性 结 构 中 元 素 之 间 存 在 一 对 一 关 系,树 形 结 构 中 元 素 之 间 存 在 一 对 多 关 系,图 形 结 构 中 元 素 之 间 存 在 多 对 多 关 系。10.在 线 性 结 构 中，第 一 个 结 点 没 有 前 驱 结 点,其 余 每 个 结 点 有 且 只 有 1个 前 驱 结 点；最 后 一 个 结 点 没 有 后 续 结 点,其 余 每 个 结 点 有 且 只 有 1个 后 续 结 点。11.在 树 形 结 构 中，树 根 结 点 没 有 前 驱 结 点,其 余 每 个 结 点 有 且 只 有 1 个 前 驱 结 点；叶 子 结 点 没 有 后 续 结 点,其 余 每 个 结 点 的 后 续 结 点 数 可 以 任 意 多 个。12.在 图 形 结 构 中，每 个 结 点 的 前 驱 结 点 数 和 后 续 结 点 数 可 以 任 意 多 个。13.数 据 的 存 储 结 构 可 用 四 种 基 本 的 存 储 方 法 表 示，它 们 分 别 是 顺 序、链 式、索 引 和 散 列。14.数 据 的 运 算 最 常 用 的 有 5 种，它 们 分 别 是 插 入、删 除、修 改、查 找、排 序。15.一 个 算 法 的 效 率 可 分 为 时 间 效 率 和 空 间 效 率。16.0 年 省 统 考 任 何 一 个 C 程 序 都 由 一 个 主 函 数 和 若 干 个 被 调 用 的 其 它 函 数 组 成。17.【00年 省 统 考 题】变 量 一 经 说 明，就 确 定 该 变 量 的 取 值 范 围（即 存 储 单 元）及 确 定 变 量 所 允 许 的 运 算二、单 项 选 择 题（每 小 题 1 分，共 1 5分）（B）1.通 常 所 说 的 主 机 是 指：A）CPU B）CPU和 内 存 C）CPU、内 存 与 外 存 D）CPU、内 存 与 硬 盘（C）2.在 计 算 机 内 部，一 切 信 息 的 存 取、处 理 和 传 送 的 形 式 是：A）ACSH码 B）BCD码 C）二 进 制 D）十 六 进 制（D）3.软 件 与 程 序 的 区 别 是：A）程 序 价 格 便 宜、软 件 价 格 昂 贵；B）程 序 是 用 户 自 己 编 写 的，而 软 件 是 由 厂 家 提 供 的；C）程 序 是 用 高 级 语 言 编 写 的，而 软 件 是 由 机 器 语 言 编 写 的；D）软 件 是 程 序 以 及 开 发、使 用 和 维 护 所 需 要 的 所 有 文 档 的 总 称，而 程 序 只 是 软 件 的 一 部 分。（c）4.所 谓 裸 机 是 指：A：单 片 机 B）单 板 机 C）不 装 备 任 何 软 件 的 计 算 机 D）只 装 备 操 作 系 统 的 计 算 机（D）5.应 用 软 件 是 指：A）所 有 能 够 使 用 的 软 件 B）能 被 各 应 用 单 位 共 同 使 用 的 某 种 软 件 C）所 有 微 机 上 都 应 使 用 的 基 本 软 件 D）专 门 为 某 一 应 用 目 的 而 编 制 的 软 件（*A）6.K O O年 省 统 考 a C 语 言 中 的 常 量 可 分 为 整 型 常 量、实 型 常 量、字 符 型 常 量 及（枚 举）四 种。（A）符 号 常 量（B）长 整 型 常 量（C）逻 辑 常 量（D）二 进 制 整 数（*C）7.编 译 程 序 的 功 能 是：A）发 现 源 程 序 中 的 语 法 错 误 C）将 源 程 序 编 译 成 目 标 程 序（A）8.系 统 软 件 中 最 重 要 的 是：A）操 作 系 统 B）语 言 处 理 系 统（C）9.可 移 植 性 最 好 的 计 算 机 语 言 是：A）机 器 语 言 B）汇 编 语 言（B）1 0.非 线 性 结 构 是 数 据 元 素 之 间 存 在 一 种：A）一 对 多 关 系 B）多 对 多 关 系 B）改 正 源 程 序 中 的 语 法 错 误 D）将 某 一 高 级 语 言 程 序 翻 译 成 另 一 种 高 级 语 言 程 序 C）工 具 软 件 D）数 据 库 管 理 系 统 C）高 级 语 言 D）自 然 语 言 C）多 对 一 关 系 D）一 对 一 关 系（C）1 1.数 据 结 构 中，与 所 使 用 的 计 算 机 无 关 的 是 数 据 的 A）存 储 B）物 理 C）逻 辑 _结 构；D）物 理 和 存 储（C）1 2.算 法 分 析 的 目 的 是：A）找 出 数 据 结 构 的 合 理 性 C）分 析 算 法 的 效 率 以 求 改 进（A）1 3.算 法 分 析 的 两 个 主 要 方 面 是:A）空 间 复 杂 性 和 时 间 复 杂 性 C）可 读 性 和 文 档 性 B）研 究 算 法 中 的 输 入 和 输 出 的 关 系 D）分 析 算 法 的 易 懂 性 和 文 档 性 B）正 确 性 和 简 明 性 D）数 据 复 杂 性 和 程 序 复 杂 性（C）1 4.计 算 机 算 法 指 的 是:A)计 算 方 法 B)排 序 方 法 C)解 决 问 题 的 有 限 运 算 序 列 D)调 度 方 法(B)1 5.计 算 机 算 法 必 须 具 备 输 入、输 出 和 等 5 个 特 性。A)可 行 性、可 移 植 性 和 可 扩 充 性 B)可 行 性、确 定 性 和 有 穷 性 C)确 定 性、有 穷 性 和 稳 定 性 D)易 读 性、稳 定 性 和 安 全 性 三、简 答 题(每 小 题 3 分，共 9 分)1.我 们 知 道 计 算 机 只 能 执 行 机 器 指 令，为 什 么 它 能 运 行 用 汇 编 语 言 和 高 级 语 言 编 写 的 程 序?答：靠 汇 编 程 序 将 汇 编 语 言 或 高 级 语 言 翻 译 转 换 为 目 标 程 序(即 机 器 语 言)。2.【严 题 集 1.2】数 据 结 构 和 数 据 类 型 两 个 概 念 之 间 有 区 别 吗？答：简 单 地 说，数 据 结 构 定 义 了 一 组 按 某 些 关 系 结 合 在 一 起 的 数 组 元 素。数 据 类 型 不 仅 定 义 了 一 组 带 结 构 的 数 据 元 素，而 且 还 在 其 上 定 义 了 一 组 操 作。3.简 述 线 性 结 构 与 非 线 性 结 构 的 不 同 点。答：线 性 结 构 反 映 结 点 间 的 逻 辑 关 系 是 一 对 一 的，非 线 性 结 构 反 映 结 点 间 的 逻 辑 关 系 是 多 对 多 的。四、Koo年 统 考 题 X 阅 读 下 列 C 程 序 段，写 出 相 应 的 执 行 结 果(每 小 题 4 分，共 8 分)1.printf(uInput x”)；scanf(%d,&x);if(x20)y=x;else if(x10)y=2*x;if(x0&xl)f=n*fact(n-l);else f=l;return(f);)main()int n;long y;n=5;y=fact(n);printf(u%d,%ldn,n,y);答：运 行 结 果 为：5,120 此 题 为 递 归 运 算五、【严 题 集 1.8】分 析 下 面 各 程 序 段 的 时 间 复 杂 度(每 小 题 5 分，共 2 0 分)1.for(i=0;ivn;i+)for(j=0;jm;j+)Ai 皿=0;答：O(m*n)2.s=0;for i=0;in;i+)for(j=0;jn;j+)s+=Bi|jJ；sum=s;答：O(n2)3.x=0;for(i=l;in;i+)for(j=l;j=n-i;j+)x+;解：因 为 x+共 执 行 了 n-l+n-2+.+1=n(n-l)/2,所 以 执 行 时 间 为 O(Y)1=1 JM+1 1=1 24.i=l;while(i=n)i=i*3;答：O(log3n)六、设 有 数 据 逻 辑 结 构 S=(D,R),试 按 各 小 题 所 给 条 件 画 出 这 些 逻 辑 结 构 的 图 示，并 确 定 相 对 于 关 系 R,哪 些 结 点 是 开 始 结 点，哪 些 结 点 是 终 端 结 点？(每 小 题 5 分，共 15分)1.【严 蔚 敏 习 题 集 P7 1.3】D=dl,d2,d3,d4 R=(dl,d2),(d2,d3),(d3,d4)答：d l-d 2 f d 3 f d 4 dl一 无 直 接 前 驱，是 首 结 点 d4一 无 直 接 后 继 是 尾 结 点 2.D=dl,d2,d9R=(dl,d2),(dl,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)答：此 图 为 树 形 结 构 dl一 无 直 接 前 驱，是 根 结 点 d2,d5,d7,d9一 无 直 接 后 继 是 叶 子 结 点 3.D=dl,d2,-,d9R=(dl,d3),(dl,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)答：此 图 为 图 形 结 构 dl,d2一 无 直 接 前 驱，是 开 始 结 点 d6,d7一 无 直 接 后 继 是 终 端 结 点(3)第 2 章 自 测 卷 答 案 姓 名 班 级 题 号 一 二 三 四 五 六 七 总 分 题 分 13 10 10 10 7 10 40 100得 分 一、填 空(每 空 1分，共 1 3分)1.【严 题 集 2.2】在 顺 序 表 中 插 入 或 删 除 一 个 元 素，需 要 平 均 移 动 表 中 一 半 元 素,具 体 移 动 的 元 素 个 数 与 表 长 和 该 元 素 在 表 中 的 位 置 有 关。2.线 性 表 中 结 点 的 集 合 是 有 限 的,结 点 间 的 关 系 是 一 对 一 的。3.向 一 个 长 度 为 n 的 向 量 的 第 i 个 元 素(1式 in+1)之 前 插 入 一 个 元 素 时，需 向 后 移 动 n-i+1 个 元 素。4.向 一 个 长 度 为 n 的 向 量 中 删 除 第 i 个 元 素(IWiWn)时，需 向 前 移 动 上 个 元 素。5.在 顺 序 表 中 访 问 任 意 一 结 点 的 时 间 复 杂 度 均 为 0(1),因 此，顺 序 表 也 称 为 随 机 存 取 的 数 据 结 构。6.【严 题 集 2.2】顺 序 表 中 逻 辑 上 相 邻 的 元 素 的 物 理 位 置 一 必 定 相 邻。单 链 表 中 逻 辑 上 相 邻 的 元 素 的 物 理 位 置 不 定 相 邻。7.【严 题 集 2.2】在 单 链 表 中，除 了 首 元 结 点 外，任 一 结 点 的 存 储 位 置 由 其 直 接 前 驱 结 点 的 链 域 的 值 指 7 Jo8.在 n 个 结 点 的 单 链 表 中 要 删 除 一 知 结 点*p,需 找 到 它 的 前 驱 结 点 的 地 址,其 时 间 复 杂 度 为 0(n)。二、判 断 正 误(在 正 确 的 说 法 后 面 打 勾，反 之 打 叉)(每 小 题 1 分，共 1 0分)(X)1.链 表 的 每 个 结 点 中 都 恰 好 包 含 一 个 指 针。答：错 误。链 表 中 的 结 点 可 含 多 个 指 针 域，分 别 存 放 多 个 指 针。例 如，双 向 链 表 中 的 结 点 可 以 含 有 两 个 指 针 域，分 别 存 放 指 向 其 直 接 前 趋 和 直 接 后 继 结 点 的 指 针。(X)2.链 表 的 物 理 存 储 结 构 具 有 同 链 表 一 样 的 顺 序。错，链 表 的 存 储 结 构 特 点 是 无 序，而 链 表 的 小 意 图 仃 序。(X)3.链 表 的 删 除 算 法 很 简 单，因 为 当 删 除 链 中 某 个 结 点 后，计 算 机 会 自 动 地 将 后 续 的 各 个 单 元 向 前 移 动。错，链 表 的 结 点 不 会 移 动，只 是 指 针 内 容 改 变。(X)4.线 性 表 的 每 个 结 点 只 能 是 一 个 简 单 类 型，而 链 表 的 每 个 结 点 可 以 是 一 个 复 杂 类 型。错，混 淆 了 逻 辑 结 构 与 物 理 结 构，链 表 也 是 线 性 表！且 即 使 是 顺 序 表，也 能 存 放 记 录 型 数 据。(X)5.顺 序 表 结 构 适 宜 于 进 行 顺 序 存 取，而 链 表 适 宜 于 进 行 随 机 存 取。错，正 好 说 反 了。顺 序 表 才 适 合 随 机 存 取，链 表 恰 恰 适 于“顺 藤 摸 瓜”(X)6.顺 序 存 储 方 式 的 优 点 是 存 储 密 度 大，且 插 入、删 除 运 算 效 率 高。错，前 一 半 正 确，但 后 一 半 说 法 错 误，那 是 链 式 存 储 的 优 点。顺 序 存 储 方 式 插 入、删 除 运 算 效 率 较 低,在 表 长 为 n 的 顺 序 表 中，插 入 和 删 除 一 个 数 据 元 素，平 均 需 移 动 表 长 一 半 个 数 的 数 据 元 素。(X)7.线 性 表 在 物 理 存 储 空 间 中 也 一 定 是 连 续 的。错，线 性 表 有 两 种 存 储 方 式，顺 序 存 储 和 链 式 存 储。后 者 不 要 求 连 续 存 放。(X)8.线 性 表 在 顺 序 存 储 时，逻 辑 上 相 邻 的 元 素 未 必 在 存 储 的 物 理 位 置 次 序 上 相 邻。错 误。线 性 表 有 两 种 存 储 方 式，在 顺 序 存 储 时，逻 辑 L相 邻 的 元 素 在 存 储 的 物 理 位 置 次 序 I:也 相 邻。(X)9.顺 序 存 储 方 式 只 能 用 于 存 储 线 性 结 构。错 误。顺 序 存 储 方 式 不 仅 能 用 于 存 储 线 性 结 构，还 可 以 用 来 存 放 非 线 性 结 构，例 如 完 全 二 叉 树 是 属 于 非 线 性 结 构，但 其 最 佳 存 储 方 式 是 顺 序 存 储 方 式。(后 一 节 介 绍)(X)10.线 性 表 的 逻 辑 顺 序 与 存 储 顺 序 总 是 一 致 的。错，理 由 同 7。链 式 存 储 就 无 需 一 致。三、单 项 选 择 题（每 小 题 1 分，共 1 0分）（C）1.数 据 在 计 算 机 存 储 器 内 表 示 时，物 理 地 址 与 逻 辑 地 址 相 同 并 且 是 连 续 的，称 之 为：（A）存 储 结 构（B）逻 辑 结 构（C）顺 序 存 储 结 构（D）链 式 存 储 结 构（B）2 个 向 量 第 一 个 元 素 的 存 储 地 址 是 100,每 个 元 素 的 长 度 为 2,则 第 5 个 元 素 的 地 址 是（A）110（B）108（C）100（D）120（A）3.在 n 个 结 点 的 顺 序 表 中，算 法 的 时 间 复 杂 度 是 O（1）的 操 作 是：（A）访 问 第 i个 结 点（1 WiWn）和 求 第 i个 结 点 的 直 接 前 驱（2WiWn）（B）在 第 i个 结 点 后 插 入 一 个 新 结 点（iWiWn）（C）删 除 第 i个 结 点（lWi n）（D）将 n 个 结 点 从 小 到 大 排 序（B）4.向 一 个 有 127个 元 素 的 顺 序 表 中 插 入 一 个 新 元 素 并 保 持 原 来 顺 序 不 变，平 均 要 移 动 _ 个 元 素（A）8（B）63.5（C）63（D）7（A）5.链 接 存 储 的 存 储 结 构 所 占 存 储 空 间：（A）分 两 部 分，一 部 分 存 放 结 点 值，另 一 部 分 存 放 表 示 结 点 间 关 系 的 指 针（B）只 有 一 部 分，存 放 结 点 值（C）只 有 一 部 分，存 储 表 示 结 点 间 关 系 的 指 针（D）分 两 部 分，一 部 分 存 放 结 点 值，另 一 部 分 存 放 结 点 所 占 单 元 数（B）6.链 表 是 一 种 采 用 存 储 结 构 存 储 的 线 性 表；（A）顺 序（B）链 式（C）星 式（D）网 状（D）7.线 性 表 若 采 用 链 式 存 储 结 构 时，要 求 内 存 中 可 用 存 储 单 元 的 地 址：（A）必 须 是 连 续 的（B）部 分 地 址 必 须 是 连 续 的（C）一 定 是 不 连 续 的（D）连 续 或 不 连 续 都 可 以（B）8.线 性 表 L 在 _ 情 况 下 适 用 于 使 用 链 式 结 构 实 现。（A）需 经 常 修 改 L 中 的 结 点 值（B）需 不 断 对 L 进 行 删 除 插 入（C）L 中 含 有 大 量 的 结 点（D）L 中 结 点 结 构 复 杂（C）9.单 链 表 的 存 储 密 度（A）大 于 1；（B）等 于 1；（C）小 于 1；（D）不 能 确 定（B）10,设 al、a2、a3为 3 个 结 点，整 数 P。，3,4 代 表 地 址，则 如 下 的 链 式 存 储 结 构 称 为 R）3 4Po-I al I 3 I I a2 I 4|）|A3|0|（A）循 环 链 表（B）单 链 表（C）双 向 循 环 链 表（D）双 向 链 表 四、简 答 题（每 小 题 5 分，共 1 0分）1.【严 题 集 2.3 试 比 较 顺 序 存 储 结 构 和 链 式 存 储 结 构 的 优 缺 点。在 什 么 情 况 下 用 顺 序 表 比 链 表 好？答：顺 序 存 储 时，相 邻 数 据 元 素 的 存 放 地 址 也 相 邻（逻 辑 与 物 理 统 一）；要 求 内 存 中 可 用 存 储 单 元 的 地 址 必 须 是 连 续 的。优 点：存 储 密 度 大（=1?）,存 储 空 间 利 用 率 高。缺 点：插 入 或 删 除 元 素 时 不 方 便。链 式 存 储 时，相 邻 数 据 元 素 可 随 意 存 放，但 所 占 存 储 空 间 分 两 部 分，一 部 分 存 放 结 点 值，另 一 部 分 存 放 表 示 结 点 间 关 系 的 指 针 优 点：插 入 或 删 除 元 素 时 很 方 便，使 用 灵 活。缺 点：存 储 密 度 小（1）,存 储 空 间 利 用 率 低。顺 序 表 适 宜 于 做 查 找 这 样 的 静 态 操 作；链 表 宜 于 做 插 入、删 除 这 样 的 动 态 操 作。若 线 性 表 的 长 度 变 化 不 大，且 其 主 要 操 作 是 查 找，则 采 用 顺 序 表；若 线 性 表 的 长 度 变 化 较 大，且 其 主 要 操 作 是 插 入、删 除 操 作，则 采 用 链 表。2.【严 题 集 2.1】描 述 以 下 三 个 概 念 的 区 别：头 指 针、头 结 点、首 元 结 点（第 一 个 元 素 结 点）。在 单 链 表 中 设 置 头 结 点 的 作 用 是 什 么？答：苴 兀 结 点 是 指 链 表 中 存 储 线 性 表 中 第 一 个 数 据 元 素 乐 的 结 点。为 了 操 作 方 便，通 常 在 链 表 的 首 元 结 点 之 前 附 设 一 个 结 点，称 为 头 结 点,该 结 点 的 数 据 域 中 不 存 储 线 性 表 的 数 据 元 素，其 作 用 是 为 了 对 链 表 进 行 操 作 时，可 以 对 空 表、非 空 表 的 情 况 以 及 对 首 元 结 点 进 行 统 一 处 理。头 指 针 是 指 向 链 表 中 第 一 个 结 点（或 为 头 结 点 或 为 首 元 结 点）的 指 针。若 链 表 中 附 设 头 结 点，则 不 管 线 性 表 是 否 为 空 表，头 指 针 均 不 为 空。否 则 表 示 空 表 的 链 表 的 头 指 针 为 空。这 三 个 概 念 对 单 链 表、双 向 链 表 和 循 环 链 表 均 适 用。是 否 设 置 头 结 点，是 不 同 的 存 储 结 构 表 示 同 一 逻 辑 结 构 的 问 题.头 结 点|head 今|data|link|头 指 针 首 元 结 点 简 而 言 之，头 指 针 是 指 向 链 表 中 第 一 个 结 点（或 为 头 结 点 或 为 首 元 结 点）的 指 针；头 结 点 是 在 链 表 的 首 元 结 点 之 前 附 设 的 一 个 结 点；数 据 域 内 只 放 空 表 标 志 和 表 长 等 信 息（内 放 头 指 针？那 还 得 另 配 一 个 头 指 针！）首 元 素 结 点 是 指 链 表 中 存 储 线 性 表 中 第 一 个 数 据 元 素 ai的 结 点。五、【软 考 题】线 性 表 具 有 两 种 存 储 方 式，即 顺 序 方 式 和 链 接 方 式。现 有 一 个 具 有 五 个 元 素 的 线 性 表 L=23,17,47,05,31,若 它 以 链 接 方 式 存 储 在 下 列 100 119号 地 址 空 间 中，每 个 结 点 由 数 据（占 2 个 字 节）和 指 针（占 2 个 字 节）组 成，如 下 所 示:|05|U 口 7|X|231Vl 31|Y|47|Z|A A100 120其 中 指 针 X,Y,Z 的 值 分 别 为 多 少？该 线 性 表 的 首 结 点 起 始 地 址 为 多 少？末 结 点 的 起 始 地 址 为 多 少？（10分）答：X=116 Y=0 Z=100 首 址=108 末 址=112六、阅 读 分 析 题(10分)【严 题 集 2.10】指 出 以 下 算 法 中 的 错 误 和 低 效(即 费 时)之 处，并 将 它 改 写 为 个 既 正 确 又 高 效 的 算 法。Status DeleteK(SqList&a,int i,int k)本 过 程 从 顺 序 存 储 结 构 的 线 性 表 a 中 删 除 第 i 个 元 素 起 的 k 个 元 素 if(i l I I k a.length)return INFEASIBLE;参 数 不 合 法 elsefor(count=1;count=i+l;j)a.elemj-l=a.elemj;a.length-)return OK;/DeleteK答 注：上 题 涉 及 的 类 型 定 义 如 下:#define LIST INIT SIZE 100#define LISTINCREMENT 10typedef struct Elem Type*elem;Int length;Int listsize;SqList;存 储 空 间 基 址 当 前 长 度 当 前 分 配 的 存 储 容 量，要 求 合/V：1 1(；U%1 7 a.i c I I 片 I I I，K C d.l C l i g U l-l)7)I C L U l 11 1 1 1 I S/A O I O I I S第 二 个 FOR 语 句 中，元 素 前 移 的 次 序 错 误。应 将 for(j=a.length;j=i+l;j-)a.elemj-l=a.elemj;改 为 for(i=i+l;j=a.length;j+)a.elemj-l=a.elemljj;七、编 程 题(每 题 10分，共 4 0分)1.【徐 士 良 题 集，2002年 1月 省 统 考 题】写 出 在 顺 序 存 储 结 构 下 将 线 性 表 逆 转 的 算 法，要 求 使 用 最 少 的 附 加 空 间 解：输 入：长 度 为 n 的 线 性 表 数 组 A(l:n)输 出：逆 转 后 的 长 度 为 n 的 线 性 表 数 组 A(l:n)。C 语 言 描 述 如 下(其 中 E T为 数 据 元 素 的 类 型)：invsl(n,a)int n;ETa;int k;ETt;for(k=l;knext=P-next;(1)P-next=S;3.编 写 程 序，将 若 干 整 数 从 键 盘 输 入，以 单 链 表 形 式 存 储 起 来，然 后 计 算 单 链 表 中 结 点 的 个 数（其 中 指 针 P 指 向 该 链 表 的 第 一 个 结 点）。注：统 计 结 点 个 数 是【省 统 考 样 题】的 要 求，也 是 教 材 P60 4-6计 算 链 表 长 度 的 要 求，编 程 又 简 单，很 容 易 作 为 考 题。解：编 写 C 程 序 如 下（已 上 机 通 过）：全 局 变 量 及 函 数 提 前 说 明：#include#includetypedef struct liuyuint data;struct liuyu*link;test;text*p,*q,*r,*head;int m=sizeof(test);void main()/*第 一 步，从 键 盘 输 入 整 数，不 断 添 加 到 链 表*/inti;head=(test*)malloc(m);/*m=sizeof(test);*Zp=head;i=0;while(i!=-9999)printf(n/ninput an integer stop b y 19999:);scanf(%dn,&i);p-data=i;/*input data is saved*/p-link=(test*)malloc(m);/*m=sizeof(test);*/q=p；p=p-link;q-link=NULL;/*原 先 用 p-link=NULL 似 乎 太 晚！*/p=head;i=l;/*统 计 链 表 结 点 的 个 数 并 打 印 出 来*/while(p-link!=NULL)printf(n%du,p-data);p=p-link;i+；)printf(n node number=%dnH,i-1);/*结 点 的 个 数 不 包 括-9999*/法 二：#include#includetypedef struct liuyu int data;struct liuyu*link;lnode;Inode*p,*q,*r,*head;int m=sizeof(struct liuyu);void main()int i;head=(struct liuyu*)malloc(m);/*m=sizeof(test);*/head-link=NULL;q=head;scanf(n%dM,&i);while(i!=-9999)printf(7ninput an integer stop by-9999:)；p=(lnode*)malloc(sizeof(m);p-data=i;/*input data is saved*/p-link=NULL;q-link=p;q=p；scanf(,%d,&i);/*m=sizeof(test);*/)/*原 先 用 p-link=NULL似 乎 太 晚！刃 p=head;i=0;/*统 计 链 表 结 点 的 个 数 并 打 印 出 来*/while(p!=NULL)printf(”d”,p-data);p=p-link;i+;)printf(Hn node number=%dnH,i-1);/*结 点 的 个 数 不 包 括-9999*/I4.请 编 写 2 6 个 字 母 按 特 定 字 母 值 插 入 或 删 除 的 完 整 程 序，可 自 行 选 用 顺 序 存 储 或 链 表 结 构。答:#include/*全 局 变 量 及 函 数 提 前 说 明：*/#indudetypedef struct liuyuchar data;struct liuyu*link;test;liuyu*p,*q,*r;*head;int L;int m=sizeof(test);/*元 素 的 个 数*/void build();void displayO;/*主 函 数 中 会 被 调 用 的 函 数 应 当 预 先 说 明*/int insert_char(chai;char);/*插 入 一 个 字 母，在 第 字 母 丫 之 前，若 无 字 母 则 加 到 末 尾*/int delet_char(char);/*删 除 元 素 X,注 意 保 存 X 的 前 趋 元 素 指 针！*/*-*/void build()inti;/*字 母 链 表 的 生 成*/head=(test*)nialloc(m);p=head;for(i=l;idata=i+*a-l;/*匕 也 可 用 其 ASCII码 9 7来 表 示*/p-link=(test*)malloc(m);p=p-link;p-data=i+,a,-l;p-link=NULL;)/*m=sizeof(test);*/void displayO/*字 母 链 表 的 输 出 力 p=head;while(p-link!=NULL)printf(M%cH,p-data);p=p.link;printf(M%cnH,p-data);)/*.*/int insert_char(char X,char Y)/*插 入 一 个 字 母 X 在 某 个 字 母 Y 之 前，若 找 不 到 Y 字 母 则 加 到 末 尾*/p=head;r=(test*)malloc(m);r-data=X;if(head-data=Y)head=r;r-link=p;else while(p-data!=Y)&(p-link!=NULL)q=p;p=p-link;if(p-data=Y)q-link=r;r-link=p;elsep-link=r;r-link=NULL;)L+;return(O);)/*.东/int delet_char(char X)/*删 除 元 素 X,注 意 保 存 X 的 前 趋 元 素 指 针！*/p=head;if(head-data=X)head=head-link;free(p);)else while(p-data!=X)&(p-link!=NULL)q=p;p=p-link;if(p-data=X)q-link=p-link;free(p);)else return(-l);)L-；return(O);)/*.东/void main(void)/*字 母 线 性 表 的 生 成 和 输 出*/L=26;build();displayO;printf(Hinsert return value=%dn,insert_char(*L,W,);displayO;printf(ndelete return value=%dn,delet_char(*z*);display();)附：屏 幕 上 显 示 的 执 行 结 果 是：a b c d e f g h i j k l m n o p q r s t u v w x y zinsert return value=0a b c d 9 c f g h i j k l m n o p q r s t u v w x y z Ldelete return value=0a b c d e f g h i j k l m n o p q r s t u v w x y L第 一 次 上 机 安 排 上 机 内 容 要 求 时 间 1 线 性 表 的 插 入 与 删 除 用 链 表 存 储 方 式 制 作 福 利 彩 票(3 6选 7)和 体 育 彩 票(1 0选 7)的 选 号 器。第 4 周 二 晚 6:30-9:50对 内 容 的 两 点 说 明：1.福 利 彩 票(3 6选 7)的 7 个 号 不 能 重 复，而 体 育 彩 票(10选 7)的 7 个 号 可 以 重 复；2.建 议 用 首 尾 相 连 的 链 式 结 构，这 样 可 以 更 逼 真 地 模 拟“摇 奖”过 程；而 每 个 号 的“摇 动”次 数 可 用 随 机 数 来 确 定。3.怎 样 产 生 随 机 数？可 以 利 用 C 语 言 中 的 种 子 函 数 srand()和 伪 随 机 函 数 r a n d()来 实 现。首 先，给 srand(m)提 供 一 个 种 子 m,它 的 取 值 范 围 是 从。65535。然 后，调 用 r a n d(),是 伪 随 机 数，它 会 根 据 提 供 给 srand()的“种 子”值 返 回 一 个 随 机 数(在。32767 之 间)。根 据 需 要 多 次 调 用 rand(),从 而 不 断 地 得 到 新 的 随 机 数。无 论 何 时，你 都 可 以 给 srand()提 供 一 个 新 的“种 子”，从 而 进 一 步“随 机 化”rand()的 输 出 结 果。例 如，取 m=1 7,则 执 行 了 srand(17)之 后，再 执 行 rand()函 数，将 得 到 输 出 值 94；第 二 次 调 用 rand(),会 得 到 26,反 复 调 用 rand()就 能 产 生 一 系 列 的 随 机 数。注 意：若 m 不 变，则 rand()的 输 出 系 列 也 不 变，总 是 94,26,602,等 等。所 以，建 议 摇 号 的“种 子”选 为 当 前 日 期 或 时 间，以 保 证 每 天 的 摇 号 值 都 不 相 同。实 验 安 排 实 验 内 容 要 求 时 间 1线 性 表 的 插 入 与 删 除 用 链 表 存 储 方 式 制 作 福 利 彩 票(36选 7)和 体 育 彩 票(10选 7)的 选 号 器。第 4 周 二 晚 6:30-9:502 二 叉 排 序 树(内 容 二 选 一)对 序 列 12,7,17,11,16,2,13,9,21,4 构 成 一 棵 二 叉 排 序 树，并 输 出 按 递 增 排 序 的 数 据 元 素 序 列。先 建 立 一 个 二 叉 树，再 分 别 按 先 序、中 序、后 序 遍 历 输 出 得 到 的 结 点 序 列。第 9 周 二 晚 6:30-9:503 排 序 和 查 找(内 容 二 选 一)先 从 键 盘 输