新编计算机科学概论刘艺、蔡敏习题与答案.docx

1、第 0章 习 题 （ 1） 复 习 题 1、 简 述 计 算 机 科 学 的 研 究 领 域 。 数 值 和 符 号 计 算 、 算 法 和 数 据 结 构 、 体 系 结 构 、 操 作 系 统 、 程 序 设 计 语 言 、 软 件 方 法 学 和 工程 、 数 据 库 和 信 息 检 索 、 计 算 理 论 、 人 工 智 能 和 机 器 人 学 等 。 （ P2） 2、 简 述 现 代 计 算 机 的 发 展 简 史 。 计 算 机 发 展 经 历 了 算 盘 时 代 、 机 械 时 代 和 机 电 时 代 这 些 原 始 阶 段 。 自 从 电 子 计 算 机 问 世 以 来 ，计

2、算 机 经 历 了 电 子 管 时 代 、 晶 体 管 时 代 、 集 成 电 路 时 代 和 大 规 模 、 超 大 规 模 集 成 电 路 时 代 等 ，发 展 速 度 越 来 越 快 。 （ P8-16） 3、 试 分 析 计 算 机 对 社 会 的 影 响 。 计 算 机 的 产 生 与 发 展 使 得 社 会 对 计 算 机 产 生 了 依 赖 ， 也 改 变 了 我 们 人 类 的 生 活 方 式 ， 并 带 来了 许 多 有 关 于 伦 理 和 犯 罪 的 问 题 。 （ P16-P17） 4、 试 列 出 与 计 算 机 科 学 相 关 的 学 科 及 技 术 。 计 算 机

3、科 学 是 一 门 实 用 性 很 强 、 发 展 极 其 迅 速 的 面 向 广 大 社 会 的 学 科 ， 它 建 立 在 数 学 、 电 子学 (特 别 是 微 电 子 学 )、 磁 学 、 光 学 、 精 密 机 械 等 多 门 学 科 的 基 础 之 上 , 与 数 学 、 计 算 机 程 序设 计 、 软 件 工 程 和 计 算 机 工 程 等 学 科 之 间 存 在 不 同 程 度 的 交 叉 和 覆 盖 。 （ P2） 5、 尝 试 到 网 络 上 搜 索 关 于 计 算 机 学 科 中 几 个 典 型 问 题 的 资 料 。 提 示 本 书 P4-7页 列 出 了 一 些 经

4、 典 问 题 ， 大 家 可 以 查 找 相 关 的 情 况 6、 简 述 电 子 数 字 计 算 机 的 发 展 趋 势 。 . 计 算 机 将 向 更 高 性 能 、 更 加 易 用 、 联 网 更 广 泛 和 更 专 业 的 应 用 发 展 。 随 着 硬 件 技 术 和 算法 设 计 的 进 步 ， 计 算 机 的 处 理 能 力 将 进 一 步 提 高 ， 计 算 机 有 能 力 处 理 更 加 复 杂 和 规 模 更 大 的问 题 。 随 着 计 算 机 向 智 能 化 方 向 发 展 ， 计 算 机 具 有 人 的 某 些 智 能 ， 如 学 习 和 推 理 的 能 力 。（ P

5、14-P15） 7、 谈 谈 你 对 电 子 计 算 机 的 印 象 。 提 示 ： 可 从 计 算 机 的 应 用 、 能 力 、 社 会 影 响 等 方 面 考 虑 8、 试 述 计 算 机 模 型 与 计 算 机 的 联 系 和 区 别 。 图 灵 设 想 所 有 的 计 算 都 可 能 在 一 种 特 殊 的 机 器 上 执 行 ， 通 用 图 灵 机 是 对 现 代 计 算 机 的 首次 描 述 ， 该 机 器 只 要 提 供 了 合 适 的 程 序 就 能 做 任 何 运 算 。 而 计 算 机 只 是 一 种 计 算 的 工 具 。（ P4） 9、 列 举 出 你 所 知 道 的

6、 操 作 系 统 。 提 示 ： 可 从 互 联 网 上 了 解 ， 或 向 周 围 的 人 们 打 听 （ 2） 练 习 题 (1)填 空 题 1、 ACM是 _组 织 的 简 称 。 国 际 计 算 机 组 织 第 一 章 习 题 （ 1） 复 习 题 1、 试 述 数 制 的 概 念 。 位 置 化 数 字 系 统 中 ， 在 数 字 中 符 号 所 占 据 的 位 置 决 定 了 其 表 示 的 值 。 大 多 数 人 使 用 的 数 字 系统 是 以 10为 底 的 ， 也 就 是 十 进 制 。 二 进 制 数 字 系 统 是 最 简 单 的 数 字 系 统 。 （ P21-3）

7、2、 列 举 出 你 所 知 道 的 数 字 系 统 。 提 示 ： 根 据 本 章 内 容 和 自 己 接 触 过 的 情 况 ， 也 可 以 上 网 搜 索 有 关 资 料 。 3、 谈 谈 二 进 制 、 八 进 制 和 十 六 进 制 等 数 字 表 示 方 法 各 有 什 么 有 点 和 缺 点 。 八 进 制 就 是 逢 8进 位 ， 十 六 进 制 就 是 逢 16进 位 ， 2、 8、 16， 分 别 是 2的 1次 方 ， 3次 方 ， 4次 方 。 这 三 种 进 制 之 间 可 以 非 常 直 接 地 互 相 转 换 。 八 进 制 数 或 十 六 进 制 数 实 际 上

8、 是 缩 短 了 的二 进 制 数 ， 但 保 持 了 二 进 制 数 的 表 达 特 点 。 （ P23-P25） 4、 为 什 么 使 用 二 进 制 计 算 的 时 候 会 出 现 溢 出 ？ 因 为 存 储 空 间 大 小 （ 即 存 储 单 元 的 位 的 数 量 ） 的 限 制 ， 可 以 表 达 的 整 数 范 围 是 有 限 的 。 二 进制 补 码 中 两 个 整 数 相 加 的 法 则 是 ， 2个 位 相 加 ， 将 进 位 加 到 下 一 列 。 如 果 最 左 边 的 列 相 加 后还 有 进 位 ， 则 舍 弃 它 。 如 果 在 最 高 位 有 进 位 ， 那 就

9、 会 产 生 溢 出 。 （ P29-32） 5、 反 码 和 补 码 相 对 于 原 码 有 什 么 优 点 ？ 计 算 机 中 的 数 是 用 原 码 表 示 的 还 是 用 反 码 、 补 码 表示 的 ？ 数 值 的 反 码 表 示 法 是 用 最 高 位 存 放 符 号 ， 并 将 原 码 的 其 余 各 位 逐 位 取 反 。 反 码 的 取 值 空间 和 原 码 相 同 且 一 一 对 应 。 在 补 码 表 示 法 中 ， 正 数 的 补 码 表 示 与 原 码 相 同 ， 即 最 高 符 号 位 用0表 示 正 ， 其 余 位 为 数 值 位 。 而 负 数 的 补 码 则

10、为 它 的 反 码 、 并 在 最 低 有 效 位 （ 即 D0位 ） 加1所 形 成 。 处 理 器 内 部 默 认 采 用 补 码 表 示 有 符 号 数 。 （ P29） 6、 汉 字 编 码 有 哪 几 种 ？ 各 自 的 特 点 是 什 么 ？ 汉 字 的 编 码 有 国 际 码 、 机 内 码 等 。 在 国 标 码 的 字 符 集 中 共 收 录 了 673个 常 用 汉 字 和 682个非 汉 字 字 符 ， 汉 字 机 内 码 是 与 ASCI对 应 的 ， 用 二 进 制 对 汉 字 进 行 的 编 码 。 由 于 汉 字 数 量多 ， 一 般 用 2个 字 节 来 存 放

11、 汉 字 的 内 码 ， 即 双 字 节 字 符 集 （ double-byte charcter set， 简 称DBCS） 。 （ P36-7） 7、 图 像 是 如 何 压 缩 存 储 的 ？ 哪 一 种 图 像 占 用 空 间 最 小 ， 为 什 么 ？ 图 形 压 缩 编 码 的 考 虑 主 要由 于 位 图 文 件 体 积 太 大 ， 人 们 研 究 通 过 编 码 的 形 式 ， 在 保 证 图 像 具 备 一 定 质 量 的 前 提 下 ， 缩小 图 像 文 件 的 大 小 。 压 缩 编 码 按 其 对 图 像 质 量 的 影 响 可 分 为 无 损 压 缩 和 有 损 压

12、缩 两 类 。 当 前最 主 流 的 图 像 压 缩 方 式 是 JPEG ， JPEG压 缩 技 术 十 分 先 进 ， 即 能 支 持 无 损 压 缩 ， 也 支 持 大压 缩 比 的 有 损 压 缩 。 （ P40-41） 8、 ASCI码 是 什 么 编 码 ？ 为 什 么 国 际 上 推 行 Unicode码 ？ I编 码 是 由 美 国 国 家 标 准 学 会 制 定 的 标 准 单 字 节 字 符 编 码 方 案 ， 用 于 基 于 文 本 的 数 据 。ASCI码 是 计 算 机 世 界 里 最 重 要 的 标 准 ， 但 它 存 在 严 重 的 国 际 化 问 题 Unico

13、de扩 展 自 ASCI第 二 章 习 题 （ 1） 复 习 题 简 述 冯 诺 依 曼 原 理 ， 冯 诺 依 曼 结 构 计 算 机 包 含 哪 几 部 分 部 件 ， 其 结 构 以 何 部 件 为 中 心 ？ 答 ： 冯 诺 依 曼 理 论 的 要 点 包 括 ： 指 令 像 数 据 那 样 存 放 在 存 储 器 中 ， 并 可 以 像 数 据 那 样 进 行处 理 ； 指 令 格 式 使 用 二 进 制 机 器 码 表 示 ； 用 程 序 存 储 控 制 方 式 工 作 。 这 3条 合 称 冯 诺 依 曼原 理 冯 诺 依 曼 计 算 机 由 五 大 部 分 组 成 ： 运 算

14、器 、 控 制 器 、 存 储 器 、 输 入 设 备 、 输 出 设 备 ，整 个 结 构 一 般 以 运 算 器 为 中 心 ， 也 可 以 以 控 制 器 为 中 心 。 (P52-P5) 2 简 述 计 算 机 体 系 结 构 与 组 成 、 实 现 之 间 的 关 系 。 答 ： 计 算 机 体 系 结 构 通 常 是 指 程 序 设 计 人 员 所 见 到 的 计 算 机 系 统 的 属 性 ， 是 硬 件 子 系 统 的 结构 概 念 及 其 功 能 特 性 。 计 算 机 组 成 （ computer organization） 是 依 据 计 算 机 体 系 结 构 确 定

15、并 且分 配 了 硬 件 系 统 的 概 念 结 构 和 功 能 特 性 的 基 础 上 ， 设 计 计 算 机 各 部 件 的 具 体 组 成 ， 它 们 之 间的 连 接 关 系 ， 实 现 机 器 指 令 级 的 各 种 功 能 和 特 性 。 同 时 ， 为 实 现 指 令 的 控 制 功 能 ， 还 需 要 设计 相 应 的 软 件 系 统 来 构 成 一 个 完 整 的 运 算 系 统 。 计 算 机 实 现 ， 是 计 算 机 组 成 的 物 理 实 现 , 就是 把 完 成 逻 辑 设 计 的 计 算 机 组 成 方 案 转 换 为 真 实 的 计 算 机 。 计 算 机 体

16、系 结 构 、 计 算 机 组 成 和计 算 机 实 现 是 三 个 不 同 的 概 念 ， 各 自 有 不 同 的 含 义 ， 但 是 又 有 着 密 切 的 联 系 ， 而 且 随 着 时 间和 技 术 的 进 步 ， 这 些 含 意 也 会 有 所 改 变 。 在 某 些 情 况 下 ， 有 时 也 无 须 特 意 地 去 区 分 计 算 机 体系 结 构 和 计 算 机 组 成 的 不 同 含 义 。 (P48-P52) 3 根 据 指 令 系 统 结 构 划 分 ， 现 代 计 算 机 包 含 哪 两 种 主 要 的 体 系 结 构 ？ 答 ： 根 据 指 令 系 统 结 构 划 分

17、 ， 现 代 计 算 机 主 要 包 含 ： CIS和 RISC两 种 结 构 。 (P57) 4 简 述 RISC技 术 的 特 点 ？ 答 ： 从 指 令 系 统 结 构 上 看 ， RISC 体 系 结 构 一 般 具 有 如 下 特 点 ： (1) 精 简 指 令 系 统 。 可 以 通 过 对 过 去 大 量 的 机 器 语 言 程 序 进 行 指 令 使 用 频 度 的 统 计 ， 来选 取 其 中 常 用 的 基 本 指 令 ， 并 根 据 对 操 作 系 统 、 高 级 语 言 和 应 用 环 境 等 的 支 持 增 设 一 些 最常 用 的 指 令 ; (2) 减 少 指 令

18、 系 统 可 采 用 的 寻 址 方 式 种 类 ， 一 般 限 制 在 2或 3种 ; (3) 在 指 令 的 功 能 、 格 式 和 编 码 设 计 上 尽 可 能 地 简 化 和 规 整 ， 让 所 有 指 令 尽 可 能 等 长 ; (4) 单 机 器 周 期 指 令 ， 即 大 多 数 的 指 令 都 可 以 在 一 个 机 器 周 期 内 完 成 ， 并 且 允 许 处 理 器在 同 一 时 间 内 执 行 一 系 列 的 指 令 。 (P59-60) 5 有 人 认 为 ， RISC技 术 将 全 面 替 代 CIS， 这 种 观 点 是 否 正 确 ， 说 明 理 由 ？ 答

19、： 不 正 确 。 与 I 架 构 相 比 较 ， RI计 算 机 具 备 结 构 简 单 、 易 于 设 计 和 程 序 执 行 效 率高 的 特 点 ， 但 并 不 能 认 为 RISC 架 构 就 可 以 取 代 CIS 架 构 。 事 实 上 ， RISC 和 CIS 各 有优 势 ， CIS计 算 机 功 能 丰 富 ， 指 令 执 行 更 加 灵 活 ， 这 些 时 RISC计 算 机 无 法 比 拟 的 ， 当 今时 代 ， 两 者 正 在 逐 步 融 合 ， 成 为 CPU设 计 的 新 趋 势 。 (P60-2) 6 什 么 是 流 水 线 技 术 ？ 答 ： 流 水 线 技

20、 术 ， 指 的 是 允 许 一 个 机 器 周 期 内 的 计 算 机 各 处 理 步 骤 重 叠 进 行 。 特 别 是 ， 当 执行 一 条 指 令 时 ， 可 以 读 取 下 一 条 指 令 ， 也 就 意 味 着 ， 在 任 何 一 个 时 刻 可 以 有 不 止 一 条 指 令 在“流 水 线 ”上 ， 每 条 指 令 处 在 不 同 的 执 行 阶 段 。 这 样 ， 即 便 读 取 和 执 行 每 条 指 令 的 时 间 保 持不 变 ， 而 计 算 机 的 总 的 吞 吐 量 提 高 了 。 (P60-1) 7 并 行 处 理 结 构 包 含 哪 几 种 主 要 的 体 系

21、结 构 ， 分 别 有 什 么 特 点 ？ 第 三 章 习 题 （ 1） 复 习 题 计 算 机 由 哪 几 部 分 组 成 ， 其 中 哪 些 部 分 组 成 了 中 央 处 理 器 ？ 答 ： 计 算 机 硬 件 系 统 主 要 由 运 算 器 、 控 制 器 、 存 储 器 、 输 入 设 备 、 输 出 设 备 等 五 部 分 组 成 其 中 ， 运 算 器 和 控 制 器 组 成 中 央 处 理 器 （ CPU） 。 （ P69） 2 试 简 述 计 算 机 多 级 存 储 系 统 的 组 成 及 其 优 点 ？ 答 ： 多 级 存 储 系 统 主 要 包 括 ： 高 速 缓 存 、

22、 主 存 储 器 和 辅 助 存 储 器 。 把 存 储 器 分 为 几 个 层 次 主 要 基 于 下 述 原 因 ： （ 1） 合 理 解 决 速 度 与 成 本 的 矛 盾 ， 以 得 到 较 高 的 性 能 价 格 比 。 （ 2） 使 用 磁 盘 、 磁 带 等 作 为 外 存 ， 不 仅 价 格 便 宜 ， 可 以 把 存 储 容 量 做 得 很 大 ， 而 且 在断 电 时 它 所 存 放 的 信 息 也 不 丢 失 ， 可 以 长 久 保 存 ， 且 复 制 、 携 带 都 很 方 便 。 (P74-P75) 3 简 述 Cache的 工 作 原 理 ， 说 明 其 作 用 。

23、 答 ： Cache的 工 作 原 理 是 基 于 程 序 访 问 的 局 部 性 的 。 即 主 存 中 存 储 的 程 序 和 数 据 并 不 是 CPU每 时 每 刻 都 在 访 问 的 ， 在 一 段 时 间 内 ， CPU只 访 问 其 一 个 局 部 。 这 样 只 要 CPU当 前 访 问 部分 的 速 度 能 够 与 CPU匹 配 即 可 ， 并 不 需 要 整 个 主 存 的 速 度 都 很 高 。 Cache与 虚 拟 存 储 器 的 基 本 原 理 相 同 ， 都 是 把 信 息 分 成 基 本 的 块 并 通 过 一 定 的 替 换 策略 ， 以 块 为 单 位 ， 由

24、 低 一 级 存 储 器 调 入 高 一 级 存 储 器 ， 供 CPU使 用 。 但 是 ， 虚 拟 存 储 器 的替 换 策 略 主 要 由 软 件 实 现 ， 而 Cache的 控 制 与 管 理 全 部 由 硬 件 实 现 。 因 此 Cache效 率 高 并 且其 存 在 和 操 作 对 程 序 员 和 系 统 程 序 员 透 明 ， 而 虚 拟 存 储 器 中 ， 页 面 管 理 虽 然 对 用 户 透 明 ， 但对 程 序 员 不 透 明 ； 段 管 理 对 用 户 可 透 明 也 可 不 透 明 。 Cache的 主 要 作 用 是 解 决 了 存 储 器 速 度 与 CPU速

25、 度 不 匹 配 的 问 题 ， 提 高 了 整 个 计 算 机系 统 的 性 能 。 (P7) 4 描 述 摩 尔 定 律 的 内 容 ， 并 说 明 其 对 于 计 算 机 的 发 展 具 有 怎 样 的 指 导 意 义 ？ 答 ： 摩 尔 定 律 （ More law） 源 于 1965年 戈 登 摩 尔 （ GordnMore， 时 任 英 特 尔 (Intel)公司 名 誉 董 事 长 ） 的 一 份 关 于 计 算 机 存 储 器 发 展 趋 势 的 报 告 。 根 据 他 对 当 时 掌 握 的 数 据 资 料 的整 理 和 分 析 研 究 ， 发 现 了 一 个 重 要 的 趋

26、 势 ： 每 一 代 新 芯 片 大 体 上 包 含 其 前 一 代 产 品 两 倍 的 容量 ， 新 一 代 芯 片 的 产 生 是 在 前 一 代 产 生 后 的 18-24个 月 内 。 随 着 计 算 机 技 术 的 发 展 ， 摩 尔 定 律 得 到 业 界 人 士 的 公 认 ， 并 产 生 巨 大 的 反 响 ， 逐 渐 成 为硬 件 领 域 最 重 要 的 规 律 。 许 多 基 于 未 来 预 期 的 研 究 和 预 测 都 是 以 它 为 理 论 基 础 。 这 里 需 要 特别 指 出 ， 摩 尔 定 律 并 非 数 学 、 物 理 定 律 ， 而 是 对 发 展 趋 势

27、 的 一 种 分 析 预 测 ， 因 此 ， 无 论 是 它的 文 字 表 述 还 是 定 量 计 算 ， 都 应 当 容 许 一 定 的 宽 裕 度 。 从 某 种 意 义 上 说 ， 摩 尔 定 律 是 关 于 人 类 创 造 力 的 定 律 ， 而 不 是 物 理 学 定 律 。 摩 尔 定 律 实 际 上是 关 于 人 类 信 念 的 定 律 ， 当 人 们 相 信 某 件 事 情 一 定 能 做 到 时 ， 就 会 努 力 去 实 现 它 。 摩 尔 当 初提 出 他 的 观 察 报 告 时 ， 在 某 种 程 度 上 是 给 了 人 们 一 种 信 念 ， 使 大 家 相 信 他

28、预 言 的 发 展 趋 势 一定 会 持 续 。 而 所 以 摩 尔 定 律 在 长 达 40多 年 的 时 间 里 不 断 被 证 实 ， 正 是 由 于 人 们 这 些 年 来 的不 懈 努 力 。 摩 尔 提 出 的 周 期 可 以 认 为 是 英 特 尔 公 司 芯 片 研 发 的 基 本 计 划 周 期 。 (P72-P73) 5 与 主 存 相 比 Cache具 有 哪 些 特 点 ？ 答 ： 主 存 相 比 ace具 有 以 下 特 点 ： （ 1） Cache一 般 用 存 取 速 度 高 的 SRAM元 件 组 成 ， 其 速 度 已 经 与 CPU相 当 。 （ 2） ac

29、e与 虚 拟 存 储 器 的 基 本 原 理 相 同 ， 都 是 把 信 息 分 成 基 本 的 块 并 通 过 一 定 的 替换 策 略 ， 以 块 为 单 位 ， 由 低 一 级 存 储 器 调 入 高 一 级 存 储 器 ， 供 CPU使 用 。 但 是 ， 虚 拟 存 储器 的 替 换 策 略 主 要 由 软 件 实 现 ， 而 Cache的 控 制 与 管 理 全 部 由 硬 件 实 现 。 因 此 Cache效 率 高并 且 其 存 在 和 操 作 对 程 序 员 和 系 统 程 序 员 透 明 ， 而 虚 拟 存 储 器 中 ， 页 面 管 理 虽 然 对 用 户 透 明 ，但

30、对 程 序 员 不 透 明 ； 段 管 理 对 用 户 可 透 明 也 可 不 透 明 。 （ 3） Cache的 价 格 较 贵 ， 为 了 保 持 最 佳 的 性 能 价 格 比 ， Cache的 容 量 应 尽 量 小 ， 但 太 小 会 影响 命 中 率 ， 所 以 Cache的 容 量 是 性 能 价 格 比 和 命 中 率 的 折 衷 。 （ P7） 第 五 章 习 题 （ 1） 复 习 题 1、 试 述 数 据 和 数 据 结 构 的 概 念 及 其 区 别 。 数 据 是 对 客 观 事 物 的 符 号 表 示 ， 是 信 息 的 载 体 ； 数 据 结 构 则 是 指 互 相

31、 之 间 存 在 着 一 种 或 多 种关 系 的 数 据 元 素 的 集 合 。 （ P13） 2、 列 出 算 法 的 五 个 重 要 特 征 并 对 其 进 行 说 明 。 算 法 具 有 以 下 五 个 重 要 的 特 征 ： 有 穷 性 ： 一 个 算 法 必 须 保 证 执 行 有 限 步 之 后 结 束 。 确 切 性 ：算 法 的 每 一 步 骤 必 须 有 确 切 的 定 义 。 输 入 ： 一 个 算 法 有 0个 或 多 个 输 入 ， 以 刻 画 运 算 对 象 的初 始 情 况 ， 所 谓 0个 输 入 是 指 算 法 本 身 定 除 了 初 始 条 件 。 输 出

32、： 一 个 算 法 有 一 个 或 多 个 输 出 ，以 反 映 对 输 入 数 据 加 工 后 的 结 果 。 没 有 输 出 的 算 法 没 有 实 际 意 义 。 可 行 性 ： 算 法 原 则 上 能 够精 确 地 运 行 ， 而 且 人 们 用 笔 和 纸 做 有 限 次 运 算 后 即 可 完 成 。 （ P15） 3、 算 法 的 优 劣 用 什 么 来 衡 量 ？ 试 述 如 何 设 计 出 优 秀 的 算 法 。 时 间 复 杂 度 空 间 复 杂 度 （ P17） 4、 线 性 和 非 线 性 结 构 各 包 含 哪 些 种 类 的 数 据 结 构 ？ 线 性 结 构 和

33、非 线 性 结 构 各 有 什 么 特 点 ？ 线 性 结 构 用 于 描 述 一 对 一 的 相 互 关 系 ， 即 结 构 中 元 素 之 间 只 有 最 基 本 的 联 系 ， 线 性 结 构 的 特点 是 逻 辑 结 构 简 单 。 所 谓 非 线 性 结 构 是 指 ， 在 该 结 构 中 至 少 存 在 一 个 数 据 元 素 ， 有 两 个 或 两个 以 上 的 直 接 前 驱 （ 或 直 接 后 继 ） 元 素 。 树 型 和 图 型 结 构 就 是 其 中 十 分 重 要 的 非 线 性 结 构 ，可 以 用 来 描 述 客 观 世 界 中 广 泛 存 在 的 层 次 结 构

34、 和 网 状 结 构 的 关 系 。 （ P18 P12） 5、 简 述 树 与 二 叉 树 的 区 别 ； 简 述 树 与 图 的 区 别 。 树 用 来 描 述 层 次 结 构 ， 是 一 对 多 或 多 对 一 的 关 系 ； 二 叉 树 （ Binary Tre） 是 个 有 限 元 素 的 集合 ， 该 集 合 或 者 为 空 、 或 者 由 一 个 称 为 根 (rot)的 元 素 及 两 个 不 相 交 的 、 被 分 别 称 为 左 子 树和 右 子 树 的 二 叉 树 组 成 。 二 叉 树 是 有 序 的 ， 即 若 将 其 左 、 右 子 树 颠 倒 ， 就 成 为 另

35、一 棵 不 同 的二 叉 树 。 图 也 称 做 网 ， 是 一 种 比 树 形 结 构 更 复 杂 的 非 线 性 结 构 。 在 图 中 ， 任 意 两 个 节 点 之 间都 可 能 相 关 ， 即 节 点 之 间 的 邻 接 关 系 可 以 是 任 意 的 ， 图 表 示 的 多 对 多 的 关 系 。 （ P12-P124） 6、 请 举 出 遍 历 算 法 在 实 际 中 使 用 的 例 子 。 提 示 ： 根 据 实 际 生 活 中 需 要 逐 个 访 问 处 理 的 情 况 举 例 。 7、 编 写 一 个 算 法 ， 统 计 在 一 个 输 入 字 符 串 中 各 个 不 同

36、字 符 出 现 的 频 度 。 用 适 当 的 测 试 数 据来 验 证 这 个 算 法 。 提 示 ： 根 据 查 找 算 法 和 串 中 求 子 串 的 算 法 ， 查 找 输 入 串 中 以 单 个 字 符 形 式 的 子 串 。 8、 若 对 有 n个 元 素 的 有 序 顺 序 表 和 无 序 顺 序 表 进 行 顺 序 搜 索 ， 试 就 下 列 三 种 情 况 分 别 讨 论两 者 在 等 搜 索 概 率 时 的 平 均 搜 索 长 度 是 否 相 同 ? (1) 搜 索 失 败 ； (2) 搜 索 成 功 ， 且 表 中 只 有 一 个 关 键 码 等 于 给 定 值 k的 对

37、 象 ； (3) 搜 索 成 功 ， 且 表 中 有 若 干 个 关 键 码 等 于 给 定 值 k的 对 象 ， 要 求 一 次 搜 索 找 出 所 有 对第 4章 操 作 系 统 习 题 （ 1） 复 习 题 1、 什 么 是 操 作 系 统 ？ 答 ： 操 作 系 统 （ Operating System， 简 称 OS） 是 管 理 计 算 机 系 统 资 源 、 控 制 程 序 执 行 ， 改 善人 机 界 面 ， 提 供 各 种 服 务 ， 合 理 组 织 计 算 机 工 作 流 程 和 为 用 户 使 用 计 算 机 提 供 良 好 运 行 环 境的 一 类 系 统 软 件 。

38、（ ） 2、 操 作 系 统 的 基 本 功 能 是 什 么 ？ 答 ： 操 作 系 统 是 用 户 与 计 算 机 硬 件 之 间 的 接 口 。 使 得 用 户 能 够 方 便 、 可 靠 、 安 全 、 高 效 地 操纵 计 算 机 硬 件 和 运 行 自 己 的 程 序 。 操 作 系 统 合 理 组 织 计 算 机 的 工 作 流 程 ， 协 调 各 个 部 件 有 效工 作 ， 为 用 户 提 供 一 个 良 好 的 运 行 环 境 。 操 作 系 统 是 计 算 机 系 统 的 资 源 管 理 者 ， 负 责 管 理 包括 处 理 器 、 存 储 器 、 I/O设 备 等 硬 件

39、 资 源 和 程 序 和 数 据 等 软 件 资 源 ， 跟 踪 资 源 使 用 情 况 ， 监视 资 源 的 状 态 ， 满 足 用 户 对 资 源 的 需 求 ， 协 调 各 程 序 对 资 源 的 使 用 冲 突 ； 为 用 户 提 供 简 单 、有 效 使 用 资 源 统 一 的 手 段 ， 最 大 限 度 地 实 现 各 类 资 源 的 共 享 ， 提 高 资 源 利 用 率 。 （ ） 3、 操 作 系 统 的 基 本 组 成 有 哪 些 ？ 答 ： 操 作 系 统 构 成 的 基 本 单 位 包 括 内 核 和 进 程 、 线 程 。 内 核 对 硬 件 处 理 器 及 有 关

40、资 源 进 行 管理 ， 给 进 程 的 执 行 提 供 运 行 环 境 。 进 程 是 程 序 动 态 执 行 的 过 程 。 （ ） 4、 操 作 系 统 如 何 分 类 ？ 答 ： 根 据 系 统 运 行 的 方 式 分 类 ， 操 作 系 统 的 基 本 类 型 有 三 种 ： 批 处 理 系 统 、 分 时 系 统 和 实 时系 统 。 具 备 全 部 或 兼 有 两 者 功 能 的 系 统 称 通 用 操 作 系 统 。 根 据 系 统 的 运 行 环 境 分 类 的 操 作 系统 有 ： 微 机 操 作 系 统 、 网 络 操 作 系 统 、 分 布 式 操 作 系 统 和 嵌

41、入 式 操 作 系 统 。 （ 2-94） 5、 什 么 是 进 程 ？ 它 与 程 序 是 什 么 关 系 ？ 答 ： 进 程 是 一 个 可 并 发 执 行 的 具 有 独 立 功 能 的 程 序 关 于 某 个 数 据 集 合 的 一 次 执 行 过 程 ， 也 是操 作 系 统 进 行 资 源 分 配 和 保 护 的 基 本 单 位 。 程 序 是 静 态 的 概 念 ， 它 以 文 件 形 式 存 在 于 辅 助 存储 器 中 ， 进 程 是 动 态 的 概 念 ， 程 序 执 行 时 创 建 进 程 ， 一 个 程 序 多 次 执 行 创 建 多 个 进 程 ， 这 多个 进 程

42、可 同 时 存 在 于 机 器 的 内 存 中 。 进 行 执 行 完 成 后 结 束 ， 进 程 终 止 ， 但 程 序 本 身 仍 然 存 在 ，并 不 因 进 程 的 终 止 而 消 失 。 （ P91， 96-8） 6、 什 么 是 死 锁 ？ 死 锁 产 生 的 原 因 是 什 么 ？ 答 ： 在 系 统 运 行 过 程 中 ， 多 个 进 程 间 相 互 永 久 等 待 对 方 占 用 的 资 源 而 导 致 各 进 程 都 无 法 继 续运 行 的 现 象 称 为 “死 锁 ”。 发 生 死 锁 后 ， 实 际 上 各 进 程 都 占 有 一 定 的 资 源 而 都 不 能 正

43、常 使 用 ，系 统 的 资 源 实 际 上 被 罢 占 并 空 闲 的 ， 是 严 重 的 资 源 的 浪 费 ； 若 无 外 力 作 用 ， 进 程 不 能 自 己 从死 锁 中 解 脱 出 来 。 产 生 死 锁 的 原 因 主 要 是 ： 系 统 资 源 不 足 ， 进 程 会 因 争 夺 有 限 的 资 源 而 陷 入 死 锁 ； 进 程 运 行 推进 的 顺 序 不 合 适 ， 进 程 运 行 推 进 顺 序 与 速 度 不 同 ， 也 可 能 产 生 死 锁 ； 资 源 分 配 不 当 等 。 （ P9-10） 第 六 章 习 题 （ 1） 复 习 题 1、 简 述 自 然 语

44、言 与 形 式 语 言 的 概 念 以 及 区 别 、 汇 编 语 言 与 机 器 语 言 的 概 念 及 区 别 。 自 然 语 言 是 某 一 社 会 发 展 中 形 成 的 一 种 民 族 语 言 ， 而 形 式 语 言 是 进 行 形 式 化 工 作 的 元 语言 ， 它 是 以 数 学 和 数 理 逻 辑 为 基 础 的 科 学 语 言 。 用 机 器 指 令 形 式 编 写 的 程 序 称 为 机 器 语 言 ， 用 带 符 号 或 助 记 符 的 指 令 和 地 址 代 替 二 进 制 代 码 成 为 语 言 进 化 的 目 标 。 这 些 使 用 助 记 符 语 言的 语 言

45、后 来 就 被 称 之 为 汇 编 语 言 。 （ P135 P136） 2、 什 么 是 高 级 程 序 设 计 语 言 ？ 它 有 什 么 特 点 ？ 高 级 语 言 是 汇 编 语 言 的 一 种 抽 象 。 高 级 语 言 的 设 计 目 标 就 是 使 程 序 员 摆 脱 汇 编 语 言 细 节 的 繁琐 。 高 级 语 言 同 汇 编 语 言 都 有 一 个 共 性 ， 那 就 是 ： 它 们 必 须 被 转 化 为 机 器 语 言 ， 这 个 转 化 的过 程 称 为 解 释 或 编 译 。 （ 1） 高 级 语 言 接 近 算 法 语 言 ， 易 学 、 易 掌 握 ； （ 2

46、） 高 级 语 言 设 计 出 来 的 程 序 可 读 性 好 ， 可 维 护 性 强 ， 可 靠 性 高 ； （ 3） 高 级 语 言 与 具 体 的 计 算 机 硬 件 关 系 不 大 ， 其 程 序 可 移 植 性 好 ， 重 用 率 高 ； （ 4） 高 级 语 言 自 动 化 程 度 高 ， 开 发 周 期 短 ， 利 于 提 高 程 序 的 质 量 。 （ P138） 3、 列 举 程 序 设 计 语 言 的 几 种 范 型 。 程 序 语 言 大 致 分 为 命 令 式 程 序 设 计 语 言 、 面 向 对 象 的 程 序 设 计 语 言 、 函 数 式 程 序 设 计 语 言

47、 和逻 辑 型 程 序 设 计 语 言 等 范 型 。 （ P138-140） 4、 简 述 语 言 虚 拟 机 。 提 示 ： 语 言 虚 拟 机 是 某 种 语 言 的 解 释 器 。 语 言 虚 拟 机 是 建 立 在 硬 件 和 操 作 系 统 之 上 ， 针 对 不同 的 硬 件 和 操 作 系 统 有 不 同 的 虚 拟 机 ， 通 过 语 言 虚 拟 机 屏 蔽 掉 硬 件 的 差 异 。 这 样 使 得 硬 件 系统 能 够 支 持 这 种 语 言 编 写 的 程 序 的 有 效 执 行 。 目 前 最 流 行 的 语 言 虚 拟 机 是 Jav虚 拟 机 。 （ P147）

48、5、 计 算 机 执 行 用 高 级 语 言 编 写 的 程 序 有 哪 些 途 径 ？ 它 们 之 间 的 主 要 区 别 是 什 么 ？ 提 示 ： 主 要 有 编 译 、 解 释 等 方 式 ， 也 有 两 种 方 式 的 混 合 使 用 的 形 式 。 编 译 是 使 用 编 译 器 将 高 级 语 言 编 写 的 源 程 序 转 换 成 计 算 机 可 以 执 行 的 机 器 语 言 可 执 行程 序 ， 也 可 以 理 解 为 用 编 译 器 产 生 可 执 行 程 序 的 动 作 。 编 译 方 式 是 一 次 编 译 ， 然 后 执 行 程 序可 以 反 复 多 次 执 行 。 解 释 是 另 一 种 将 高 级 语 言 转 换 为 可 执 行 程 序 的 方 式 。 与 编 译 不 同 ， 解 释 性 语 言 的 程 序 不需 要 编 译 ， 省 了 道 工 序 ， 解 释 性 语 言 在 运 行 程 序 的 时 候 才 翻 译 ， 每 个 语 句 都 是 执 行 的 时 候 才翻 译 。 这 样 解 释 性 语 言 每 执 行 一 次 就 要 翻 译 一 次 ， 效 率 比 较 低 。 近 来 随 着 网 络 的 发 展 ， 为 了 实 现