10 在 内 部 排 序 过 程 中, 对 尚 未 确 定 最 终 位 置 的 所 有 元 素 进 行 一 遍 处 理 称 为 一 趟 排 序 下 列 排 序 方 法 中, 每 一 趟 排 序 结 束 都 至 少 能 够 确 定 一 个 元 素 最 终 位 置 的 方 法 是 ( ) Ⅰ. 简 单

2012 年 计 算 专 业 综 合 考 研 真 题 一 选 择 题 1 求 整 数 n(n 0) 阶 乘 的 算 法 如 下, 其 时 间 复 杂 度 是 ( ) int fact(int n) { if (n<=1) return 1; return n*fact(n-1); } A. O(log 2 n) B. O(n) C. (nlog 2 n) D. O(n 2 ) 2 已 知 操 作 符 包 括 + - * / ( 和 ) 将 中 缀 表 达 式 a+b-a*((c+d)/e-f)+g 转 换 为 等 价 的 后 缀 表 达 式 ab+acd+e/f-**-g+ 时, 用 栈 来 存 放 暂 时 还 不 能 确 定 运 算 次 序 的 操 作 符, 若 栈 初 始 时 为 空, 则 转 换 过 程 中 同 时 保 存 栈 中 的 操 作 符 的 最 大 个 数 是 ( ) A. 5 B. 7 C. 8 D. 11 3 若 一 颗 二 叉 树 的 前 序 遍 历 序 列 为 a, e, b, d, c, 后 续 遍 历 序 列 为 b, c, d, e, a, 则 根 节 点 的 孩 子 节 点 ( ) A. 只 有 e B. 有 e b C. 有 e c D. 无 法 确 定 4 若 平 衡 二 叉 树 的 高 度 为 6, 且 所 有 非 叶 节 点 的 平 衡 因 子 均 为 1, 则 该 平 衡 二 叉 树 的 节 点 总 数 为 ( ) A. 10 B. 20 C. 32 D. 33 5 对 有 n 个 节 点 e 条 边 且 使 用 邻 接 表 存 储 的 有 向 图 进 行 广 度 优 先 遍 历, 其 算 法 时 间 复 杂 度 ( ) A. O(n) B. O(e) C. O(n+e) D. O(n*e) 6 若 用 邻 接 矩 阵 存 储 有 向 图, 矩 阵 中 主 对 角 线 以 下 的 元 素 均 为 零, 则 关 于 该 图 拓 扑 序 列 的 结 构 是 ( ) A. 存 在, 且 唯 一 B. 存 在, 且 不 唯 一 C. 存 在, 可 能 不 唯 一 D. 无 法 确 定 是 否 存 在 7 如 下 有 向 带 权 图, 若 采 用 迪 杰 斯 特 拉 (Dijkstra) 算 法 求 源 点 a 到 其 他 各 顶 点 的 最 短 路 径, 得 到 的 第 一 条 最 短 路 径 的 目 标 顶 点 是 b, 第 二 条 最 短 路 径 的 目 标 顶 点 是 c, 后 续 得 到 的 其 余 各 最 短 路 径 的 目 标 顶 点 依 次 是 ( ) 3 1 5 A. d, e, f B. e, d,f C. f,d,e D. f,e,d 8 下 列 关 于 最 小 生 成 树 的 说 法 中, 正 确 的 是 ( ) Ⅰ 最 小 生 成 树 的 代 价 唯 一 Ⅱ 所 有 权 值 最 小 的 边 一 定 会 出 现 在 所 有 的 最 小 生 成 树 中 Ⅲ 使 用 普 里 姆 (Prim) 算 法 从 不 同 顶 点 开 始 得 到 的 最 小 生 成 树 一 定 相 同 Ⅳ 使 用 普 里 姆 算 法 和 克 鲁 斯 卡 尔 (Kruskal) 算 法 得 到 的 最 小 生 成 树 总 不 相 同 A. 仅 Ⅰ B. 仅 Ⅱ C. 仅 Ⅰ Ⅲ D. 仅 Ⅱ Ⅳ 9 已 知 一 棵 3 阶 B- 树, 如 下 图 所 示 删 除 关 键 字 78 得 到 一 棵 新 B- 树, 其 最 右 叶 结 点 中 的 关 键 字 是 ( ) A. 60 B. 60, 62 C. 62, 65 D. 65 1

10 在 内 部 排 序 过 程 中, 对 尚 未 确 定 最 终 位 置 的 所 有 元 素 进 行 一 遍 处 理 称 为 一 趟 排 序 下 列 排 序 方 法 中, 每 一 趟 排 序 结 束 都 至 少 能 够 确 定 一 个 元 素 最 终 位 置 的 方 法 是 ( ) Ⅰ. 简 单 选 择 排 序 Ⅱ. 希 尔 排 序 Ⅲ. 快 速 排 序 Ⅳ. 堆 排 序 Ⅴ. 二 路 归 并 排 序 A. 仅 Ⅰ Ⅲ Ⅳ B. 仅 Ⅰ Ⅲ Ⅴ C. 仅 Ⅱ Ⅲ Ⅳ D. 仅 Ⅲ Ⅳ Ⅴ 11. 对 一 待 排 序 序 列 分 别 进 行 折 半 插 入 排 序 和 直 接 插 入 排 序, 两 者 之 间 可 能 的 不 同 之 处 是 ( ) A. 排 序 的 总 趟 数 B. 元 素 的 移 动 次 数 C. 使 用 辅 助 空 间 的 数 量 D. 元 素 之 间 的 比 较 次 数 12 假 定 基 准 程 序 A 在 某 计 算 机 上 的 运 行 时 间 为 100 秒, 其 中 90 秒 为 CPU 时 间, 其 余 为 I/O 时 间 若 CPU 速 度 提 高 50%,I/O 速 度 不 变, 则 运 行 基 准 程 序 A 所 耗 费 的 时 间 是 ( ) A. 55 B. 60 C. 65 D. 70 13 假 定 编 译 器 规 定 int 和 short 型 长 度 分 别 为 32 位 和 16 位, 执 行 下 列 C 语 言 语 句 : unsighned short x = 65530; unsigned int y = x; 得 到 y 的 机 器 数 为 ( ) A. 0000 7FFAH B. 0000 FFFAH C. FFFF 7FFAH D. FFFF FFFAH 14 float 类 型 ( 即 IEEE754 单 精 度 浮 点 数 格 式 ) 能 表 示 的 最 大 正 整 数 是 ( ) A. 2 126-2 103 B. 2 127-2 104 C. 2 127-2 103 D. 2 128-2 104 15 某 计 算 机 存 储 器 按 字 节 编 址, 采 用 小 端 方 式 存 放 数 据 假 定 编 译 器 规 定 int 型 和 short 型 长 度 分 别 为 32 位 和 16 位, 并 且 数 据 按 边 界 对 齐 存 储 某 C 语 言 程 序 段 如 下 : struct{ int a; char b; short c; }record; record.a = 273; 若 record 变 量 的 首 地 址 为 0xC008, 则 地 址 0xC008 中 内 容 及 record.c 的 地 址 分 别 是 ( ) A. 0x00 0xC00D B. 0x00 0xC00E C. 0x11 0xC00D D. 0x11 0xC00E 16 下 列 关 于 闪 存 (Flash Memory) 的 叙 述 中, 错 误 的 是 ( ) A. 信 息 可 读 可 写, 并 且 读 写 速 度 一 样 快 B. 存 储 元 由 MOS 管 组 成, 是 一 种 半 导 体 存 储 器 C. 掉 电 后 信 息 不 丢 失, 是 一 种 非 易 失 性 存 储 器 D. 采 用 随 机 访 问 方 式, 可 替 代 计 算 机 外 部 存 储 器 17 假 设 某 计 算 机 按 字 编 址,Cache 有 4 个 行,Cache 和 主 存 之 间 交 换 的 块 大 小 为 1 个 字 若 Cache 的 内 容 初 始 为 空, 采 用 2 路 组 相 联 映 射 方 式 和 LRU 替 换 策 略 访 问 的 主 存 地 址 依 次 为 0,4,8,2,0,6,8,6,4,8 时, 命 中 Cache 的 次 数 是 ( ) A. 1 B. 2 C. 3 D. 4 2

18 某 计 算 机 的 控 制 器 采 用 微 程 序 控 制 方 式, 微 指 令 中 的 操 作 控 制 字 段 采 用 字 段 直 接 编 码 法, 共 有 33 个 微 命 令, 构 成 5 个 互 斥 类, 分 别 包 含 7 3 12 5 和 6 个 微 命 令, 则 操 作 控 制 字 段 至 少 有 ( ) A. 5 位 B. 6 位 C. 15 位 D. 33 位 19 设 总 线 频 率 为 100MHz, 宽 度 为 32 位, 地 址 / 数 据 线 复 用, 每 传 输 一 个 地 址 或 数 据 占 用 一 个 时 钟 周 期 若 该 总 线 支 持 突 发 ( 猝 发 ) 传 输 方 式, 则 一 次 主 存 写 总 线 事 务 传 输 128 位 数 据 所 需 要 的 时 间 至 少 是 ( ) A. 20ns B. 40ns C. 50ns D. 80ns 20 下 列 关 于 USB 总 线 特 性 的 描 述 中, 错 误 的 是 ( ) A. 可 实 现 外 设 的 即 插 即 用 和 热 拔 插 B. 可 通 过 级 联 方 式 连 接 多 台 设 备 C. 是 一 种 通 信 总 线, 连 接 不 同 外 设 D. 同 时 可 传 输 2 位 数 据, 数 据 传 输 率 高 21 下 列 选 项 中, 在 I/O 总 线 的 数 据 线 上 传 输 的 信 息 包 括 ( ) Ⅰ. I/O 接 口 中 的 命 令 字 Ⅱ. I/O 接 口 中 的 状 态 字 Ⅲ. 中 断 类 型 号 A. 仅 Ⅰ Ⅱ B. 仅 Ⅰ Ⅲ C. 仅 Ⅱ Ⅲ D.Ⅰ Ⅱ Ⅲ 22 响 应 外 部 中 断 的 过 程, 中 断 隐 指 令 完 成 的 操 作, 除 保 护 断 点 外, 还 包 括 ( ) Ⅰ. 关 中 断 Ⅱ. 保 存 通 用 寄 存 器 的 内 容 Ⅲ. 形 成 中 断 服 务 程 序 入 口 地 址 并 送 PC A. 仅 Ⅰ Ⅱ B. 仅 Ⅰ Ⅲ C. 仅 Ⅱ Ⅲ D.Ⅰ Ⅱ Ⅲ 23 下 列 选 项 中, 不 可 能 在 用 户 态 发 生 的 事 件 是 ( ) A. 系 统 调 用 B. 外 部 中 断 C. 进 程 切 换 D. 缺 页 24 中 断 处 理 和 子 程 序 调 用 都 需 要 压 栈 以 保 护 现 场, 中 断 处 理 一 定 会 保 存 而 子 程 序 调 用 不 需 要 保 存 其 内 容 的 是 ( ) A. 程 序 计 数 器 B. 程 序 状 态 字 寄 存 器 C. 通 用 数 据 寄 存 器 D. 通 用 地 址 寄 存 器 25 下 列 关 于 虚 拟 存 储 器 的 叙 述 中, 正 确 的 是 ( ) A. 虚 拟 存 储 只 能 基 于 连 续 分 配 技 术 B. 虚 拟 存 储 只 能 基 于 非 连 续 分 配 技 术 C. 虚 拟 存 储 容 量 只 受 外 存 容 量 的 限 制 D. 虚 拟 存 储 容 量 只 受 内 存 容 量 的 限 制 26 操 作 系 统 的 I/O 子 系 统 通 常 由 四 个 层 次 组 成, 每 一 层 明 确 定 义 了 与 邻 近 层 次 的 接 口 其 合 理 的 层 次 组 织 排 列 顺 序 是 ( ) A. 用 户 级 I/O 软 件 设 备 无 关 软 件 设 备 驱 动 程 序 中 断 处 理 程 序 B. 用 户 级 I/O 软 件 设 备 无 关 软 件 中 断 处 理 程 序 设 备 驱 动 程 序 C. 用 户 级 I/O 软 件 设 备 驱 动 程 序 设 备 无 关 软 件 中 断 处 理 程 序 D. 用 户 级 I/O 软 件 中 断 处 理 程 序 设 备 无 关 软 件 设 备 驱 动 程 序 27 假 设 5 个 进 程 P0 P1 P2 P3 P4 共 享 三 类 资 源 R1 R2 R3, 这 些 资 源 总 数 分 别 为 18 6 22 T0 时 刻 的 资 源 分 配 情 况 如 下 表 所 示, 此 时 存 在 的 一 个 安 全 序 列 是 ( ) 进 程 已 分 配 资 源 资 源 最 大 需 求 R1 R2 R3 R1 R2 R3 P0 3 2 3 5 5 10 P1 4 0 3 5 3 6 P2 4 0 5 4 0 11 P3 2 0 4 4 2 5 P4 3 1 4 4 2 4 A P0,P2,P4,P1,P3 B P1,P0,P3,P4,P2 C P2,P1,P0,P3,P4 D P3,P4,P2,P1,P0 3

28 若 一 个 用 户 进 程 通 过 read 系 统 调 用 读 取 一 个 磁 盘 文 件 中 的 数 据, 则 下 列 关 于 此 过 程 的 叙 述 中, 正 确 的 是 ( ) Ⅰ. 若 该 文 件 的 数 据 不 在 内 存, 则 该 进 程 进 入 睡 眠 等 待 状 态 Ⅱ. 请 求 read 系 统 调 用 会 导 致 CPU 从 用 户 态 切 换 到 核 心 态 Ⅲ.read 系 统 调 用 的 参 数 应 包 含 文 件 的 名 称 A. 仅 Ⅰ Ⅱ B. 仅 Ⅰ Ⅲ C. 仅 Ⅱ Ⅲ D.Ⅰ Ⅱ 和 Ⅲ 29 一 个 多 道 批 处 理 系 统 中 仅 有 P1 和 P2 两 个 作 业,P2 比 P1 晚 5ms 到 达, 它 们 的 计 算 和 I/O 操 作 顺 序 如 下 : P1: 计 算 60ms,I/O80ms, 计 算 20ms P2: 计 算 120ms,I/O40ms, 计 算 40ms 若 不 考 虑 调 度 和 切 换 时 间, 则 完 成 两 个 作 业 需 要 的 时 间 最 少 是 ( ) A. 240ms B. 260ms C. 340ms D. 360ms 30 若 某 单 处 理 器 多 进 程 系 统 中 有 多 个 就 绪 态 进 程, 则 下 列 关 于 处 理 机 调 度 的 叙 述 中 错 误 的 是 ( ) A. 在 进 程 结 束 时 能 进 行 处 理 机 调 度 B. 创 建 新 进 程 后 能 进 行 处 理 机 调 度 C. 在 进 程 处 于 临 界 区 时 不 能 进 行 处 理 机 调 度 D. 在 系 统 调 用 完 成 并 返 回 用 户 态 时 能 进 行 处 理 机 调 度 31 下 列 关 于 进 程 和 线 程 的 叙 述 中, 正 确 的 是 ( ) A. 不 管 系 统 是 否 支 持 线 程, 进 程 都 是 资 源 分 配 的 基 本 单 位 B. 线 程 是 资 源 分 配 的 基 本 单 位, 进 程 是 调 度 的 基 本 单 位 C. 系 统 级 线 程 和 用 户 级 线 程 的 切 换 都 需 要 内 核 的 支 持 D. 同 一 进 程 中 的 各 个 线 程 拥 有 各 自 不 一 的 地 址 空 间 32 下 列 选 项 中, 不 能 改 善 磁 盘 设 备 I/O 性 能 的 是 ( ) A. 重 排 I/O 请 求 次 序 B. 在 一 个 磁 盘 上 设 置 多 个 分 区 C. 预 读 和 滞 后 写 D. 优 化 文 件 物 理 块 的 分 布 33 在 TCP/IP 体 系 结 构 中, 直 接 为 ICMP 提 供 服 务 的 协 议 是 ( ) A. PPP B. IP C. UDP D. TCP 34 在 物 理 层 接 口 特 性 中, 用 于 描 述 完 成 每 种 功 能 的 事 件 发 生 顺 序 的 是 ( ) A. 机 械 特 性 B. 功 能 特 性 C. 过 程 特 性 D. 电 气 特 性 35 以 太 网 的 MAC 协 议 提 供 的 是 ( ) A. 无 连 接 的 不 可 靠 的 服 务 B. 无 连 接 的 可 靠 的 服 务 C. 有 连 接 的 不 可 靠 的 服 务 D. 有 连 接 的 可 靠 的 服 务 36 两 台 主 机 之 间 的 数 据 层 采 用 后 退 N 帧 协 议 (GBN) 传 输 数 据, 数 据 传 输 速 率 为 16kbps, 单 向 传 播 时 延 为 270ms, 数 据 帧 长 度 范 围 是 128~512 字 节, 接 收 方 总 是 以 与 数 据 帧 等 长 的 帧 进 行 确 认 为 使 信 道 利 用 率 达 到 最 高, 帧 序 号 的 比 特 数 至 少 为 ( ) A. 5 B. 4 C. 3 D. 2 37 下 列 关 于 IP 路 由 器 功 能 的 描 述 中, 正 确 的 是 ( ) Ⅰ. 运 行 路 由 协 议, 设 备 路 由 表 Ⅱ. 检 测 到 拥 塞 时, 合 理 丢 弃 IP 分 组 Ⅲ. 对 收 到 的 IP 分 组 头 进 行 差 错 校 验, 确 保 传 输 的 IP 分 组 不 丢 失 Ⅳ. 根 据 收 到 的 IP 分 组 的 目 的 IP 地 址, 将 其 转 发 到 合 适 的 输 出 线 路 上 A. 仅 Ⅲ Ⅳ B. 仅 Ⅰ Ⅱ Ⅲ C. 仅 Ⅰ Ⅱ Ⅳ D. Ⅰ Ⅱ Ⅲ Ⅳ 4

38 ARP 协 议 的 功 能 是 ( ) A. 根 据 IP 地 址 查 询 MAC 地 址 B. 根 据 MAC 地 址 查 询 IP 地 址 C. 根 据 域 名 查 询 IP 地 址 D. 根 据 IP 地 址 查 询 域 名 39 某 主 机 的 IP 地 址 为 180.80.77.55, 子 网 掩 码 为 255.255.252.0 若 该 主 机 向 其 所 在 子 网 发 送 广 播 分 组, 则 目 的 地 址 可 以 是 ( ) A. 180.80.76.0 B. 180.80.76.255 C. 180.80.77.255 D. 180.80.79.255 40 若 用 户 1 与 用 户 2 之 间 发 送 和 接 收 电 子 邮 件 的 过 程 如 下 图 所 示, 则 图 中 1 2 3 阶 段 分 别 使 用 的 应 用 层 协 议 可 以 是 ( ) A. SMTP SMTP SMTP B. POP3 SMTP POP3 C. POP3 SMTP SMTP D. SMTP SMTP POP3 二 问 答 题 41 (10 分 ) 设 有 6 个 有 序 表 A B C D E F, 分 别 含 有 10 35 40 50 60 和 200 个 数 据 元 素, 各 表 中 元 素 按 升 序 排 列 要 求 通 过 5 次 两 两 合 并, 将 6 个 表 最 终 合 并 成 1 个 升 序 表, 并 在 最 坏 情 况 下 比 较 的 总 次 数 达 到 最 小 请 回 答 下 列 问 题 (1) 给 出 完 整 的 合 并 过 程, 并 求 出 最 坏 情 况 下 比 较 的 总 次 数 (2) 根 据 你 的 合 并 过 程, 描 述 N(N 2) 个 不 等 长 升 序 表 的 合 并 策 略, 并 说 明 理 由 42 (13 分 ) 假 定 采 用 带 头 结 点 的 单 链 表 保 存 单 词, 当 两 个 单 词 有 相 同 的 后 时 缀, 则 可 共 享 相 同 的 后 缀 存 储 空 间, 例 如, loaging 和 being, 如 下 图 所 示 设 str1 和 str2 分 别 指 向 两 个 单 词 所 在 单 链 表 的 头 结 点, 链 表 结 点 结 构 为, 请 设 计 一 个 时 间 上 尽 可 能 高 效 的 算 法, 找 出 由 str1 和 str2 所 指 向 两 个 链 表 共 同 后 缀 的 起 始 位 置 ( 如 图 中 字 符 i 所 在 结 点 的 位 置 p) 要 求 : (1) 给 出 算 法 的 基 本 设 计 思 想 (2) 根 据 设 计 思 想, 采 用 C 或 C++ 或 java 语 言 描 述 算 法, 关 键 之 处 给 出 注 释 (3) 说 明 你 所 设 计 算 法 的 时 复 杂 度 43 (11 分 ) 假 设 某 计 算 机 的 CPU 主 频 为 80MHz,CPI 为 4, 平 均 每 条 指 令 访 存 1.5 次, 主 存 与 Cache 之 间 交 换 的 块 大 小 为 16B,Cache 的 命 中 率 为 99%, 存 储 器 总 线 宽 带 为 32 位 请 回 答 下 列 问 题 (1) 该 计 算 机 的 MIPS 数 是 多 少? 平 均 每 秒 Cache 缺 失 的 次 数 是 多 少? 在 不 考 虑 DMA 传 送 的 情 况 下, 主 存 带 宽 至 少 达 到 多 少 才 能 满 足 CPU 的 访 存 要 求? (2) 假 定 在 Cache 缺 失 的 情 况 下 访 问 主 存 时, 存 在 0.0005% 的 缺 页 率, 则 CPU 平 均 每 秒 产 生 多 少 次 缺 页 异 常? 若 页 面 大 小 为 4KB, 每 次 缺 页 都 需 要 访 问 磁 盘, 访 问 磁 5

盘 时 DMA 传 送 采 用 周 期 挪 用 方 式, 磁 盘 I/O 接 口 的 数 据 缓 冲 寄 存 器 为 32 位, 则 磁 盘 I/O 接 口 平 均 每 秒 发 出 的 DMA 请 求 次 数 至 少 是 多 少? (3)CPU 和 DMA 控 制 器 同 时 要 求 使 用 存 储 器 总 线 时, 哪 个 优 先 级 更 高? 为 什 么? (4) 为 了 提 高 性 能, 主 存 采 用 4 体 低 位 交 叉 存 储 模 式, 工 作 时 每 1/4 个 存 储 周 期 启 动 一 个 体, 若 每 个 体 的 存 储 周 期 为 50ns, 则 该 主 存 能 提 供 的 最 大 带 宽 是 多 少? 44 (12 分 ) 某 16 位 计 算 机 中, 带 符 号 整 数 用 补 码 表 示, 数 据 Cache 和 指 令 Cache 分 离 题 44 表 给 出 了 指 令 系 统 中 部 分 指 令 格 式, 其 中 Rs 和 Rd 表 示 寄 存 器,mem 表 示 存 储 单 元 地 址,(x) 表 示 寄 存 器 x 或 存 储 单 元 x 的 内 容 题 44 表 指 令 系 统 中 部 分 指 令 格 式 名 称 指 令 的 汇 编 格 式 指 令 功 能 加 法 指 令 ADD Rs, Rd (Rs)+(Rd)->Rd 算 术 / 逻 辑 左 移 SHL Rd 2*(Rd)->Rd 算 术 右 移 SHR Rd (Rd)/2->Rd 取 数 指 令 LOAD Rd, mem (mem)->rd 存 数 指 令 STORE Rs, mem (Rs)->mem 该 计 算 机 采 用 5 段 流 水 式 执 行 指 令, 各 流 水 段 分 别 是 取 指 (IF), 译 码 / 读 寄 存 器 (ID) 执 行 / 计 算 有 效 地 址 (EX) 访 问 存 储 器 (M) 和 结 果 写 回 寄 存 器 (WB), 流 水 线 采 用 按 序 发 射, 按 序 完 成 方 式, 没 有 采 用 转 发 技 术 处 理 数 据 相 关, 并 且 同 一 个 寄 存 器 的 读 和 写 操 作 不 能 在 同 一 个 时 钟 周 期 内 进 行 请 回 答 下 列 问 题 : (1) 若 int 型 变 量 x 的 值 为 -513, 存 放 在 寄 存 器 R1 中, 则 执 行 SHL R1 后,R1 中 的 内 容 是 多 少?( 用 十 六 进 制 表 示 ) (2) 若 某 个 时 间 段 中, 有 连 续 的 4 条 指 令 进 入 流 水 线, 在 其 执 行 过 程 中 没 有 发 生 任 何 阻 塞, 则 执 行 这 4 条 指 令 所 需 的 时 钟 周 期 数 为 多 少? (3) 若 高 级 语 言 程 序 中 某 赋 值 语 句 为 x = a+b, x a 和 b 均 为 int 型 变 量, 它 们 的 存 储 单 元 地 址 分 别 表 示 为 [x] [a] 和 [b] 该 语 句 对 应 的 指 令 序 列 及 其 在 指 令 流 水 线 中 的 执 行 过 程 如 题 44 图 所 示 I1 LOAD R1, [a] I2 LOAD R2, [b] I3 ADD R1, R2 I4 STORE R2, [x] 时 间 单 元 1 2 3 4 5 6 7 8 9 10 11 12 13 14 I1 IF ID EX M WB I2 IF ID EX M WB I3 IF ID EX M WB I4 IF ID EX M WB 题 44 图 指 令 序 列 及 其 执 行 过 程 示 意 图 则 这 4 条 指 令 执 行 过 程 中,I 3 的 ID 段 和 I 4 的 IF 段 被 阻 塞 的 原 因 各 是 什 么? (4) 若 高 级 语 言 程 序 中 某 赋 值 语 句 为 x=x*2+a,x 和 a 均 为 unsigned int 类 型 变 量, 它 们 的 存 储 单 元 地 址 分 别 表 示 为 [x] [a], 则 执 行 这 条 语 句 至 少 需 要 多 少 个 时 钟 周 期? 要 求 模 仿 题 44 图 画 出 这 条 语 句 对 应 的 指 令 序 列 及 其 在 流 水 线 中 的 执 行 过 程 示 意 图 6

45 (7 分 ) 某 请 求 分 页 系 统 的 局 部 页 面 置 换 策 略 如 下 : 从 0 时 刻 开 始 扫 描, 每 隔 5 个 时 间 单 位 扫 描 一 轮 驻 留 集 ( 扫 描 时 间 忽 略 不 计 ), 本 轮 没 有 被 访 问 过 的 页 框 将 被 系 统 回 收, 并 放 入 到 空 闲 页 框 链 尾, 其 中 内 容 在 下 一 次 分 配 之 前 不 被 清 空 当 发 生 缺 页 时, 如 果 该 页 曾 被 使 用 过 且 还 在 空 闲 页 链 表 中, 则 重 新 放 回 进 程 的 驻 留 集 中 ; 否 则, 从 空 闲 页 框 链 表 头 部 取 出 一 个 页 框 假 设 不 考 虑 其 它 进 程 的 影 响 和 系 统 开 销 初 始 时 进 程 驻 留 集 为 空 目 前 系 统 空 闲 页 框 链 表 中 页 框 号 依 次 为 32 15 21 41 进 程 P 依 次 访 问 的 < 虚 拟 页 号, 访 问 时 刻 > 为 <1,1> <3,2> <0,4> <0,6> <1,11> <0,13> <2,14> 请 回 答 下 列 问 题 (1) 访 问 <0,4> 时, 对 应 的 页 框 号 是 什 么? (2) 访 问 <1,11> 时, 对 应 的 页 框 号 是 什 么? 说 明 理 由 (3) 访 问 <2,14> 时, 对 应 的 页 框 号 是 什 么? 说 明 理 由 (4) 该 策 略 是 否 适 合 于 时 间 局 部 性 好 的 程 序? 说 明 理 由 46 (8 分 ) 某 文 件 系 统 空 间 的 最 大 容 量 为 4TB(1TB =2 40 ), 以 磁 盘 块 为 基 本 分 配 单 元 磁 盘 块 大 小 为 1KB 文 件 控 制 块 (FCB) 包 含 一 个 512B 的 索 引 表 区 请 回 答 下 列 问 题 1) 假 设 索 引 表 区 仅 采 用 直 接 索 引 结 构, 索 引 表 区 存 放 文 件 占 用 的 磁 盘 块 号, 索 引 表 项 中 块 号 最 少 占 多 少 字 节? 可 支 持 的 单 个 文 件 最 大 长 度 是 多 少 字 节? 2) 假 设 索 引 表 区 采 用 如 下 结 构 : 第 0~7 字 节 采 用 < 起 始 块 号, 块 数 > 格 式 表 示 文 件 创 建 时 预 分 配 的 连 续 存 储 空 间 其 中 起 始 块 号 占 6B, 块 数 占 2B; 剩 余 504 字 节 采 用 直 接 索 引 结 构, 一 个 索 引 项 占 6B, 则 可 支 持 的 单 个 文 件 最 大 长 度 是 多 少 字 节? 为 了 使 单 个 文 件 的 长 度 达 到 最 大, 请 指 出 起 始 块 号 和 块 数 分 别 所 占 字 节 数 的 合 理 值 并 说 明 理 由 47 (9 分 ) 主 机 H 通 过 快 速 以 太 网 连 接 Internet,IP 地 址 为 192.168.0.8, 服 务 器 S 的 IP 地 址 为 211.68.71.80 H 与 S 使 用 TCP 通 信 时, 在 H 在 捕 获 的 其 中 5 个 IP 数 据 报 如 下 表 所 示 题 47-a 表 IP 分 组 的 前 40 字 节 内 容 ( 十 六 进 制 ) 45 00 00 30 01 9b 40 00 80 06 1d c8 c0 a8 00 08 d3 44 47 50 1 0b d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 80 5d b0 00 00 45 00 00 30 00 00 40 00 31 06 6e 83 d3 44 47 50 c0 a8 00 08 2 13 88 0b d9 e0 59 9f ef 84 6b 41 c6 70 12 16 d0 37 e1 00 00 45 00 00 28 01 9c 40 00 80 06 1d ef c0 a8 00 08 d3 44 47 50 3 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 f0 43 80 2b 32 00 00 45 00 00 38 01 9d 40 00 80 06 1d de c0 a8 00 08 d3 44 47 50 4 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 18 43 80 e6 55 00 00 45 00 00 28 68 11 40 00 31 06 06 7a d3 44 47 50 c0 a8 00 08 5 13 88 0b d9 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 57 d2 00 00 回 答 下 列 问 题 (1) 题 47-a 表 中 的 IP 分 组 中, 哪 几 个 是 由 H 发 送 的? 哪 几 个 完 成 了 TCP 连 接 建 立 过 程? 哪 几 个 在 通 过 快 速 以 太 网 传 输 时 进 行 了 填 充? (2) 根 据 题 47-a 表 中 的 IP 分 组, 分 析 S 已 经 收 到 的 应 用 层 数 据 字 节 数 是 多 少? (3) 若 题 47-a 表 中 的 某 个 IP 分 组 在 S 发 出 时 的 前 40 字 节 如 题 47-b 表 所 示, 则 该 IP 分 组 到 达 H 时 经 过 了 多 少 个 路 由 器? 7

题 47-b 表 来 自 S 的 45 00 00 28 68 11 40 00 40 06 ec ad d3 44 47 50 ca 76 01 06 分 组 13 88 a1 08 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 b7 d6 00 00 注 :IP 分 组 头 和 TCP 段 头 结 构 分 别 如 题 47-a 图, 题 47-b 图 所 示 bit 0 8 16 24 32 版 本 头 部 长 度 服 务 类 型 总 长 度 标 识 标 志 片 偏 移 生 存 时 间 (TTL) 协 议 头 部 校 验 和 源 IP 地 址 目 的 IP 地 址 题 47-a 图 IP 分 组 头 结 构 源 端 口 目 的 端 口 序 号 确 认 号 数 据 偏 移 保 留 U R G A C K P S H R S T S Y N F I N 窗 口 校 验 和 紧 急 指 针 选 项 ( 长 度 可 变 ) 题 47-b 图 TCP 段 头 结 构 填 充 8