10. 若 数 据 元 素 序 列 11,12,13,7,8,9,23,4,5 是 采 用 下 列 排 序 方 法 之 一 得 到 的 第 二 趟 排 序 后 的 结 果, 则 该 排 序 算 法 只 能 是 A. 起 泡 排 序 B. 插 入 排 序 C. 选 择 排 序 D. 二 路 归 并 排

Transcription

1 2009 年 全 国 硕 士 研 究 生 入 学 统 一 考 试 计 算 机 科 学 与 技 术 学 科 联 考 计 算 机 学 科 专 业 基 础 综 合 试 题 一 单 项 选 择 题 : 第 1~40 小 题, 每 小 题 2 分, 共 80 分 下 列 每 题 给 出 的 四 个 选 项 中, 只 有 一 个 选 项 最 符 合 试 题 要 求 1. 为 解 决 计 算 机 主 机 与 打 印 机 之 间 速 度 不 匹 配 问 题, 通 常 设 置 一 个 打 印 数 据 缓 冲 区, 主 机 将 要 输 出 的 数 据 依 次 写 入 该 缓 冲 区, 而 打 印 机 则 依 次 从 该 缓 冲 区 中 取 出 数 据 该 缓 冲 区 的 逻 辑 结 构 应 该 是 A. 栈 B. 队 列 C. 树 D. 图 2. 设 栈 S 和 队 列 Q 的 初 始 状 态 均 为 空, 元 素 a,b,c,d,e,f,g 依 次 进 入 栈 S 若 每 个 元 素 出 栈 后 立 即 进 入 队 列 Q, 且 7 个 元 素 出 队 的 顺 序 是 b,d,c,f,e,a,g, 则 栈 S 的 容 量 至 少 是 A.1 B.2 C.3 D.4 3. 给 定 二 叉 树 如 右 图 所 示 设 N 代 表 二 叉 树 的 根,L 代 表 根 结 点 的 左 子 树,R 代 表 根 结 点 的 右 子 树 若 遍 历 后 的 结 点 序 列 是 3,1,7,5,6,2,4, 则 其 遍 历 方 式 是 A.LRN B.NRL C.RLN D.RNL 4. 下 列 二 叉 排 序 树 中, 满 足 平 衡 二 叉 树 定 义 的 是 5. 已 知 一 棵 完 全 二 叉 树 的 第 6 层 ( 设 根 为 第 1 层 ) 有 8 个 叶 结 点, 则 该 完 全 二 叉 树 的 结 点 个 数 最 多 是 A. 39 B.52 C.111 D 将 森 林 转 换 为 对 应 的 二 叉 树, 若 在 二 叉 树 中, 结 点 u 是 结 点 v 的 父 结 点 的 父 结 点, 则 在 原 来 的 森 林 中,u 和 v 可 能 具 有 的 关 系 是 Ⅰ. 父 子 关 系 Ⅱ. 兄 弟 关 系 Ⅲ.u 的 父 结 点 与 v 的 父 结 点 是 兄 弟 关 系 A. 只 有 Ⅱ B.Ⅰ 和 Ⅱ C.Ⅰ 和 Ⅲ D.Ⅰ Ⅱ 和 Ⅲ 7. 下 列 关 于 无 向 连 通 图 特 性 的 叙 述 中, 正 确 的 是 I. 所 有 顶 点 的 度 之 和 为 偶 数 II. 边 数 大 于 顶 点 个 数 减 1 III. 至 少 有 一 个 顶 点 的 度 为 1 A. 只 有 Ⅰ B. 只 有 Ⅱ C.Ⅰ 和 Ⅱ D.Ⅰ 和 Ⅲ 8. 下 列 叙 述 中, 不. 符 合 m 阶 B 树 定 义 要 求 的 是 A. 根 节 点 最 多 有 m 棵 子 树 B. 所 有 叶 结 点 都 在 同 一 层 上 C. 各 结 点 内 关 键 字 均 升 序 或 降 序 排 列 D. 叶 结 点 之 间 通 过 指 针 链 接 9. 已 知 关 键 字 序 列 5,8,12,19,28,20,15,22 是 小 根 堆 ( 最 小 堆 ), 插 入 关 键 字 3, 调 整 后 得 到 的 小 根 堆 是 A.3,5,12,8,28,20,15,22,19 B.3,5,12,19,20,15,22,8,28 C.3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19

2 10. 若 数 据 元 素 序 列 11,12,13,7,8,9,23,4,5 是 采 用 下 列 排 序 方 法 之 一 得 到 的 第 二 趟 排 序 后 的 结 果, 则 该 排 序 算 法 只 能 是 A. 起 泡 排 序 B. 插 入 排 序 C. 选 择 排 序 D. 二 路 归 并 排 序 11. 冯 诺 依 曼 计 算 机 中 指 令 和 数 据 均 以 二 进 制 形 式 存 放 在 存 储 器 中,CPU 区 分 它 们 的 依 据 是 A. 指 令 操 作 码 的 译 码 结 果 B. 指 令 和 数 据 的 寻 址 方 式 C. 指 令 周 期 的 不 同 阶 段 D. 指 令 和 数 据 所 在 的 存 储 单 元 12. 一 个 C 语 言 程 序 在 一 台 32 位 机 器 上 运 行 程 序 中 定 义 了 三 个 变 量 x y 和 z, 其 中 x 和 z 为 int 型,y 为 short 型 当 x=127,y=-9 时, 执 行 赋 值 语 句 z=x+y 后,x y 和 z 的 值 分 别 是 A. x= fh,y=fff9h,z= h B. x= fh,y=fff9h,z=ffff0076h C. x= fh,y=fff7h,z=ffff0076h D. x= fh,y=fff7h,z= h 13. 浮 点 数 加 减 运 算 过 程 一 般 包 括 对 阶 尾 数 运 算 规 格 化 舍 入 和 判 溢 出 等 步 骤 设 浮 点 数 的 阶 码 和 尾 数 均 采 用 补 码 表 示, 且 位 数 分 别 为 5 位 和 7 位 ( 均 含 2 位 符 号 位 ) 若 有 两 个 数 X=2 7 29/32,Y=2 5 5/8, 则 用 浮 点 加 法 计 算 X+Y 的 最 终 结 果 是 A B C D. 发 生 溢 出 14. 某 计 算 机 的 Cache 共 有 16 块, 采 用 2 路 组 相 联 映 射 方 式 ( 即 每 组 2 块 ) 每 个 主 存 块 大 小 为 32 字 节, 按 字 节 编 址 主 存 129 号 单 元 所 在 主 存 块 应 装 入 到 的 Cache 组 号 是 A.0 B.1 C.4 D 某 计 算 机 主 存 容 量 为 64KB, 其 中 ROM 区 为 4KB, 其 余 为 RAM 区, 按 字 节 编 址 现 要 用 2K 8 位 的 ROM 芯 片 和 4K 4 位 的 RAM 芯 片 来 设 计 该 存 储 器, 则 需 要 上 述 规 格 的 ROM 芯 片 数 和 RAM 芯 片 数 分 别 是 A.1 15 B.2 15 C.1 30 D 某 机 器 字 长 16 位, 主 存 按 字 节 编 址, 转 移 指 令 采 用 相 对 寻 址, 由 两 个 字 节 组 成, 第 一 字 节 为 操 作 码 字 段, 第 二 字 节 为 相 对 位 移 量 字 段 假 定 取 指 令 时, 每 取 一 个 字 节 PC 自 动 加 1 若 某 转 移 指 令 所 在 主 存 地 址 为 2000H, 相 对 位 移 量 字 段 的 内 容 为 06H, 则 该 转 移 指 令 成 功 转 移 后 的 目 标 地 址 是 A.2006H B.2007H C.2008H D.2009H 17. 下 列 关 于 RISC 的 叙 述 中, 错 误.. 的 是 A.RISC 普 遍 采 用 微 程 序 控 制 器 B.RISC 大 多 数 指 令 在 一 个 时 钟 周 期 内 完 成 C.RISC 的 内 部 通 用 寄 存 器 数 量 相 对 CISC 多 D.RISC 的 指 令 数 寻 址 方 式 和 指 令 格 式 种 类 相 对 CISC 少 18. 某 计 算 机 的 指 令 流 水 线 由 四 个 功 能 段 组 成, 指 令 流 经 各 功 能 段 的 时 间 ( 忽 略 各 功 能 段 之 间 的 缓 存 时 间 ) 分 别 为 90 ns 80 ns 70 ns 和 60 ns, 则 该 计 算 机 的 CPU 时 钟 周 期 至 少 是 A.90 ns B.80 ns C.70 ns D.60 ns 19. 相 对 于 微 程 序 控 制 器, 硬 布 线 控 制 器 的 特 点 是 A. 指 令 执 行 速 度 慢, 指 令 功 能 的 修 改 和 扩 展 容 易 B. 指 令 执 行 速 度 慢, 指 令 功 能 的 修 改 和 扩 展 难 C. 指 令 执 行 速 度 快, 指 令 功 能 的 修 改 和 扩 展 容 易 D. 指 令 执 行 速 度 快, 指 令 功 能 的 修 改 和 扩 展 难

3 20. 假 设 某 系 统 总 线 在 一 个 总 线 周 期 中 并 行 传 输 4 字 节 信 息, 一 个 总 线 周 期 占 用 2 个 时 钟 周 期, 总 线 时 钟 频 率 为 10MHz, 则 总 线 带 宽 是 A.10MB/S B.20MB/S C.40MB/S D.80MB/S 21. 假 设 某 计 算 机 的 存 储 系 统 由 Cache 和 主 存 组 成, 某 程 序 执 行 过 程 中 访 存 次, 其 中 访 问 Cache 缺 失 ( 未 命 中 )50 次, 则 Cache 的 命 中 率 是 A.5% B.9.5% C.50% D.95% 22. 下 列 选 项 中, 能 引 起 外 部 中 断 的 事 件 是 A. 键 盘 输 入 B. 除 数 为 0 C. 浮 点 运 算 下 溢 D. 访 存 缺 页 23. 单 处 理 机 系 统 中, 可 并 行 的 是 Ⅰ 进 程 与 进 程 Ⅱ 处 理 机 与 设 备 Ⅲ 处 理 机 与 通 道 Ⅳ 设 备 与 设 备 A.Ⅰ Ⅱ 和 Ⅲ C.Ⅰ Ⅲ 和 Ⅳ B.Ⅰ Ⅱ 和 Ⅳ D.Ⅱ Ⅲ 和 Ⅳ 24. 下 列 进 程 调 度 算 法 中, 综 合 考 虑 进 程 等 待 时 间 和 执 行 时 间 的 是 A. 时 间 片 轮 转 调 度 算 法 B. 短 进 程 优 先 调 度 算 法 C. 先 来 先 服 务 调 度 算 法 D. 高 响 应 比 优 先 调 度 算 法 25. 某 计 算 机 系 统 中 有 8 台 打 印 机, 由 K 个 进 程 竞 争 使 用, 每 个 进 程 最 多 需 要 3 台 打 印 机 该 系 统 可 能 会 发 生 死 锁 的 K 的 最 小 值 是 A.2 B.3 C.4 D 分 区 分 配 内 存 管 理 方 式 的 主 要 保 护 措 施 是 A. 界 地 址 保 护 B. 程 序 代 码 保 护 C. 数 据 保 护 D. 栈 保 护 27. 一 个 分 段 存 储 管 理 系 统 中, 地 址 长 度 为 32 位, 其 中 段 号 占 8 位, 则 最 大 段 长 是 A.2 8 字 节 B.2 16 字 节 C.2 24 字 节 D.2 32 字 节 28. 下 列 文 件 物 理 结 构 中, 适 合 随 机 访 问 且 易 于 文 件 扩 展 的 是 A. 连 续 结 构 B. 索 引 结 构 C. 链 式 结 构 且 磁 盘 块 定 长 D. 链 式 结 构 且 磁 盘 块 变 长 29. 假 设 磁 头 当 前 位 于 第 105 道, 正 在 向 磁 道 序 号 增 加 的 方 向 移 动 现 有 一 个 磁 道 访 问 请 求 序 列 为 35,45,12, 68,110,180,170,195, 采 用 SCAN 调 度 ( 电 梯 调 度 ) 算 法 得 到 的 磁 道 访 问 序 列 是 A.110,170,180,195,68,45,35,12 C.110,170,180,195,12,35,45,68 B.110,68,45,35,12,170,180,195 D.12,35,45,68,110,170,180, 文 件 系 统 中, 文 件 访 问 控 制 信 息 存 储 的 合 理 位 置 是 A. 文 件 控 制 块 B. 文 件 分 配 表 C. 用 户 口 令 表 D. 系 统 注 册 表 31. 设 文 件 F1 的 当 前 引 用 计 数 值 为 1, 先 建 立 F1 的 符 号 链 接 ( 软 链 接 ) 文 件 F2, 再 建 立 F1 的 硬 链 接 文 件 F3, 然 后 删 除 F1 此 时,F2 和 F3 的 引 用 计 数 值 分 别 是 A. 0 1 B.1 1 C.1 2 D 程 序 员 利 用 系 统 调 用 打 开 I/O 设 备 时, 通 常 使 用 的 设 备 标 识 是 A. 逻 辑 设 备 名 B. 物 理 设 备 名 C. 主 设 备 号 D. 从 设 备 号 33. 在 OSI 参 考 模 型 中, 自 下 而 上 第 一 个 提 供 端 到 端 服 务 的 层 次 是 A. 数 据 链 路 层 B. 传 输 层 C. 会 话 层 D. 应 用 层 34. 在 无 噪 声 情 况 下, 若 某 通 信 链 路 的 带 宽 为 3kHz, 采 用 4 个 相 位, 每 个 相 位 具 有 4 种 振 幅 的 QAM 调 制 技 术,

4 则 该 通 信 链 路 的 最 大 数 据 传 输 速 率 是 A.12kbps B.24 kbps C.48 kbps D.96 kbps 35. 数 据 链 路 层 采 用 后 退 N 帧 (GBN) 协 议, 发 送 方 已 经 发 送 了 编 号 为 0~7 的 帧 当 计 时 器 超 时 时, 若 发 送 方 只 收 到 号 帧 的 确 认, 则 发 送 方 需 要 重 发 的 帧 数 是 A.2 B.3 C.4 D 以 太 网 交 换 机 进 行 转 发 决 策 时 使 用 的 PDU 地 址 是 A. 目 的 物 理 地 址 B. 目 的 IP 地 址 C. 源 物 理 地 址 D. 源 IP 地 址 37. 在 一 个 采 用 CSMA/CD 协 议 的 网 络 中, 传 输 介 质 是 一 根 完 整 的 电 缆, 传 输 速 率 为 1Gbps, 电 缆 中 的 信 号 传 播 速 度 是 km/s 若 最 小 数 据 帧 长 度 减 少 800 比 特, 则 最 远 的 两 个 站 点 之 间 的 距 离 至 少 需 要 A. 增 加 160m B. 增 加 80m C. 减 少 160m D. 减 少 80m 38. 主 机 甲 与 主 机 乙 之 间 已 建 立 一 个 TCP 连 接, 主 机 甲 向 主 机 乙 发 送 了 两 个 连 续 的 TCP 段, 分 别 包 含 300 字 节 和 500 字 节 的 有 效 载 荷, 第 一 个 段 的 序 列 号 为 200, 主 机 乙 正 确 接 收 到 两 个 段 后, 发 送 给 主 机 甲 的 确 认 序 列 号 是 A.500 B.700 C.800 D 一 个 TCP 连 接 总 是 以 1KB 的 最 大 段 长 发 送 TCP 段, 发 送 方 有 足 够 多 的 数 据 要 发 送 当 拥 塞 窗 口 为 16KB 时 发 生 了 超 时, 如 果 接 下 来 的 4 个 RTT( 往 返 时 间 ) 时 间 内 的 TCP 段 的 传 输 都 是 成 功 的, 那 么 当 第 4 个 RTT 时 间 内 发 送 的 所 有 TCP 段 都 得 到 肯 定 应 答 时, 拥 塞 窗 口 大 小 是 A.7 KB B.8 KB C.9 KB D.16 KB 40. FTP 客 户 和 服 务 器 间 传 递 FTP 命 令 时, 使 用 的 连 接 是 A. 建 立 在 TCP 之 上 的 控 制 连 接 B. 建 立 在 TCP 之 上 的 数 据 连 接 C. 建 立 在 UDP 之 上 的 控 制 连 接 D. 建 立 在 UDP 之 上 的 数 据 连 接 二 综 合 应 用 题 : 第 41~47 题, 共 70 分 41. (10 分 ) 带 权 图 ( 权 值 非 负, 表 示 边 连 接 的 两 顶 点 间 的 距 离 ) 的 最 短 路 径 问 题 是 找 出 从 初 始 顶 点 到 目 标 顶 点 之 间 的 一 条 最 短 路 径 假 设 从 初 始 顶 点 到 目 标 顶 点 之 间 存 在 路 径, 现 有 一 种 解 决 该 问 题 的 方 法 : 1 设 最 短 路 径 初 始 时 仅 包 含 初 始 顶 点, 令 当 前 顶 点 u 为 初 始 顶 点 ; 2 选 择 离 u 最 近 且 尚 未 在 最 短 路 径 中 的 一 个 顶 点 v, 加 入 到 最 短 路 径 中, 修 改 当 前 顶 点 u=v; 3 重 复 步 骤 2, 直 到 u 是 目 标 顶 点 时 为 止 请 问 上 述 方 法 能 否 求 得 最 短 路 径? 若 该 方 法 可 行, 请 证 明 之 ; 否 则, 请 举 例 说 明 42. (15 分 ) 已 知 一 个 带 有 表 头 结 点 的 单 链 表, 结 点 结 构 为 : data link 假 设 该 链 表 只 给 出 了 头 指 针 list 在 不 改 变 链 表 的 前 提 下, 请 设 计 一 个 尽 可 能 高 效 的 算 法, 查 找 链 表 中 倒 数 第 k 个 位 置 上 的 结 点 ( k 为 正 整 数 ) 若 查 找 成 功, 算 法 输 出 该 结 点 的 data 域 的 值, 并 返 回 1; 否 则, 只 返 回 0 要 求 : ⑴ 描 述 算 法 的 基 本 设 计 思 想 ; ⑵ 描 述 算 法 的 详 细 实 现 步 骤 ; ⑶ 根 据 设 计 思 想 和 实 现 步 骤, 采 用 程 序 设 计 语 言 描 述 算 法 ( 使 用 C C++ 或 Java 语 言 实 现 ), 关 键 之 处 请 给 出 简 要 注 释 43. (8 分 ) 某 计 算 机 的 CPU 主 频 为 500MHz,CPI 为 5( 即 执 行 每 条 指 令 平 均 需 5 个 时 钟 周 期 ) 假 定 某 外 设

5 的 数 据 传 输 率 为 0.5MB/s, 采 用 中 断 方 式 与 主 机 进 行 数 据 传 送, 以 32 位 为 传 输 单 位, 对 应 的 中 断 服 务 程 序 包 含 18 条 指 令, 中 断 服 务 的 其 他 开 销 相 当 于 2 条 指 令 的 执 行 时 间 请 回 答 下 列 问 题, 要 求 给 出 计 算 过 程 1) 在 中 断 方 式 下,CPU 用 于 该 外 设 I/O 的 时 间 占 整 个 CPU 时 间 的 百 分 比 是 多 少? 2) 当 该 外 设 的 数 据 传 输 率 达 到 5MB/s 时, 改 用 DMA 方 式 传 送 数 据 假 定 每 次 DMA 传 送 块 大 小 为 5000B, 且 DMA 预 处 理 和 后 处 理 的 总 开 销 为 500 个 时 钟 周 期, 则 CPU 用 于 该 外 设 I/O 的 时 间 占 整 个 CPU 时 间 的 百 分 比 是 多 少?( 假 设 DMA 与 CPU 之 间 没 有 访 存 冲 突 ) 44. (13 分 ) 某 计 算 机 字 长 16 位, 采 用 16 位 定 长 指 令 字 结 构, 部 分 数 据 通 路 结 构 如 下 图 所 示, 图 中 所 有 控 制 信 号 为 1 时 表 示 有 效 为 0 时 表 示 无 效 例 如 控 制 信 号 MDRinE 为 1 表 示 允 许 数 据 从 DB 打 入 MDR,MDRin 为 1 表 示 允 许 数 据 从 内 总 线 打 入 MDR 假 设 MAR 的 输 出 一 直 处 于 使 能 状 态 加 法 指 令 ADD (R1),R0 的 功 能 为 (R0)+((R1)) (R1), 即 将 R0 中 的 数 据 与 R1 的 内 容 所 指 主 存 单 元 的 数 据 相 加, 并 将 结 果 送 入 R1 的 内 容 所 指 主 存 单 元 中 保 存 下 表 给 出 了 上 述 指 令 取 指 和 译 码 阶 段 每 个 节 拍 ( 时 钟 周 期 ) 的 功 能 和 有 效 控 制 信 号, 请 按 表 中 描 述 方 式 用 表 格.. 列 出 指 令 执 行 阶 段... 每 个 节 拍 的 功 能 和 有 效 控 制 信 号 时 钟 功 能 有 效 控 制 信 号 C1 MAR (PC) PCout, MARin C2 MDR M(MDR) PC (PC)+1 MemR, MDRinE, PC+1 C3 IR (MDR) MDRout, IRin C4 指 令 译 码 无 45. (7 分 ) 三 个 进 程 P1 P2 P3 互 斥 使 用 一 个 包 含 N(N>0) 个 单 元 的 缓 冲 区 P1 每 次 用 produce() 生 成 一 个 正 整 数 并 用 put() 送 入 缓 冲 区 某 一 空 单 元 中 ;P2 每 次 用 getodd() 从 该 缓 冲 区 中 取 出 一 个 奇 数 并 用 countodd() 统 计 奇 数 个 数 ;P3 每 次 用 geteven() 从 该 缓 冲 区 中 取 出 一 个 偶 数 并 用 counteven() 统 计 偶 数 个 数 请 用 信 号 量 机 制 实 现 这 三 个 进 程 的 同 步 与 互 斥 活 动, 并 说 明 所 定 义 信 号 量 的 含 义 要 求 用 伪 代 码 描 述 46. (8 分 ) 请 求 分 页 管 理 系 统 中, 假 设 某 进 程 的 页 表 内 容 如 下 表 所 示 : 页 号 页 框 (Page Frame) 号 有 效 位 ( 存 在 位 )

6 0 101H H 1 页 面 大 小 为 4KB, 一 次 内 存 的 访 问 时 间 是 100ns, 一 次 快 表 (TLB) 的 访 问 时 间 是 10ns, 处 理 一 次 缺 页 的 平 均 时 间 10 8 ns( 已 含 更 新 TLB 和 页 表 的 时 间 ), 进 程 的 驻 留 集 大 小 固 定 为 2, 采 用 最 近 最 少 使 用 置 换 算 法 (LRU) 和 局 部 淘 汰 策 略 假 设 1TLB 初 始 为 空 ;2 地 址 转 换 时 先 访 问 TLB, 若 TLB 未 命 中, 再 访 问 页 表 ( 忽 略 访 问 页 表 之 后 的 TLB 更 新 时 间 );3 有 效 位 为 0 表 示 页 面 不 在 内 存, 产 生 缺 页 中 断, 缺 页 中 断 处 理 后, 返 回 到 产 生 缺 页 中 断 的 指 令 处 重 新 执 行 设 有 虚 地 址 访 问 序 列 2362H 1565H 25A5H, 请 问 : (1) 依 次 访 问 上 述 三 个 虚 地 址, 各 需 多 少 时 间? 给 出 计 算 过 程 (2) 基 于 上 述 访 问 序 列, 虚 地 址 1565H 的 物 理 地 址 是 多 少? 请 说 明 理 由 47. (9 分 ) 某 网 络 拓 扑 如 下 图 所 示, 路 由 器 R1 通 过 接 口 E1 E2 分 别 连 接 局 域 网 1 局 域 网 2, 通 过 接 口 L0 连 接 路 由 器 R2, 并 通 过 路 由 器 R2 连 接 域 名 服 务 器 与 互 联 网 R1 的 L0 接 口 的 IP 地 址 是 ;R2 的 L0 接 口 的 IP 地 址 是 ,L1 接 口 的 IP 地 址 是 ,E0 接 口 的 IP 地 址 是 ; 域 名 服 务 器 的 IP 地 址 是 R1 和 R2 的 路 由 表 结 构 为 : 目 的 网 络 IP 地 址 子 网 掩 码 下 一 跳 IP 地 址 接 口 ⑴ 将 IP 地 址 空 间 /24 划 分 为 2 个 子 网, 分 别 分 配 给 局 域 网 1 局 域 网 2, 每 个 局 域 网 需 分 配 的 IP 地 址 数 不 少 于 120 个 请 给 出 子 网 划 分 结 果, 说 明 理 由 或 给 出 必 要 的 计 算 过 程 ⑵ 请 给 出 R1 的 路 由 表, 使 其 明 确 包 括 到 局 域 网 1 的 路 由 局 域 网 2 的 路 由 域 名 服 务 器 的 主 机 路 由 和 互 联 网 的 路 由 ⑶ 请 采 用 路 由 聚 合 技 术, 给 出 R2 到 局 域 网 1 和 局 域 网 2 的 路 由

7 参 考 答 案 一 单 项 选 择 题 1. B 2. C 3. D 4. B 5. C 6. B 7. A 8. D 9. A 10. B 11. C 12. D 13. D 14. C 15. D 16. C 17. A 18. A 19. D 20. B 21. D 22. A 23. D 24. D 25. C 26. A 27. C 28. B 29. A 30. A 31. B 32. A 33. B 34. B 35. C 36. A 37. D 38. D 39. C 40. A 二 综 合 应 用 题 41. 解 答 : 该 方 法 不 一 定 能 ( 或 不 能 ) 求 得 最 短 路 径 例 如, 对 于 下 图 所 示 的 带 权 图, 如 果 按 照 题 中 的 原 则, 从 A 到 C 的 最 短 路 径 是 A->B->C, 事 实 上 其 最 短 路 径 是 A->D->C 1 A B 2 10 D C 解 答 : (1) 算 法 的 基 本 设 计 思 想 (5 分 ): 问 题 的 关 键 是 设 计 一 个 尽 可 能 高 效 的 算 法, 通 过 链 表 的 一 趟 遍 历, 找 到 倒 数 第 k 个 结 点 的 位 置 算 法 的 基 本 设 计 思 想 是 : 定 义 两 个 指 针 变 量 p 和 q, 初 始 时 均 指 向 头 结 点 的 下 一 个 结 点 ( 链 表 的 第 一 个 结 点 ) p 指 针 沿 链 表 移 动 ; 当 p 指 针 移 动 到 第 k 个 结 点 时,q 指 针 开 始 与 p 指 针 同 步 移 动 ; 当 p 指 针 移 动 到 最 后 一 个 结 点 时,q 指 针 所 指 示 结 点 为 倒 数 第 k 个 结 点 以 上 过 程 对 链 表 仅 进 行 一 遍 扫 描 (2) 算 法 的 详 细 实 现 步 骤 (5 分 ): 1 count=0,p 和 q 指 向 链 表 表 头 结 点 的 下 一 个 结 点 ; 2 若 p 为 空, 转 5; 3 若 count 等 于 k, 则 q 指 向 下 一 个 结 点 ; 否 则,count=count+1; 4 p 指 向 下 一 个 结 点, 转 2; 5 若 count 等 于 k, 则 查 找 成 功, 输 出 该 结 点 的 data 域 的 值, 返 回 1; 否 则, 说 明 k 值 超 过 了 线 性 表 的 长 度, 查 找 失 败, 返 回 0; 6 算 法 结 束 (3) 算 法 实 现 (5 分 ): typedef int ElemType; 链 表 数 据 的 类 型 定 义 typedef struct LNode{ 链 表 结 点 的 结 构 定 义 ElemType data; 结 点 数 据 struct Lnode *link; 结 点 链 接 指 针 } *LinkList; int Search_k(LinkList list, int k){ 查 找 链 表 list 倒 数 第 k 个 结 点, 并 输 出 该 结 点 data 域 的 值 LinkList p = list->link, q = list->link; 指 针 p q 指 示 第 一 个 结 点

8 int count = 0; while(p!= NULL){ 遍 历 链 表 直 到 最 后 一 个 结 点 if(count < k) count++; 计 数, 若 count < k 只 移 动 p else q = q->link; p = p->link; 之 后 让 p q 同 步 移 动 } while if(count < k) return 0; 查 找 失 败 返 回 0 else { 否 则 打 印 并 返 回 1 printf( %d,q->data); return 1; } } Search_k 提 示 : 算 法 程 序 题, 如 果 能 够 写 出 数 据 结 构 类 型 定 义 正 确 的 算 法 思 想 都 会 至 少 给 一 半 以 上 分 数, 如 果 能 用 伪 代 码 写 出 自 然 更 好, 比 较 复 杂 的 地 方 可 以 直 接 用 文 字 表 达 若 所 给 出 的 算 法 采 用 一 遍 扫 描 方 式 就 能 得 到 正 确 结 果, 可 给 满 分 15 分 ; 若 采 用 两 遍 或 多 遍 扫 描 才 能 得 到 正 确 结 果 的, 最 高 分 10 分 若 采 用 递 归 算 法 得 到 正 确 结 果 的, 最 高 给 10 分 ; 若 实 现 算 法 的 空 间 复 杂 度 过 高 ( 使 用 了 大 小 与 k 有 关 的 辅 助 数 组 ), 但 结 果 正 确, 最 高 给 10 分 43. 解 答 : (1) 按 题 意, 外 设 每 秒 传 送 0.5MB, 中 断 时 每 次 传 送 4B 中 断 方 式 下,CPU 每 次 用 于 数 据 传 送 的 时 钟 周 期 为 : =100. 为 达 到 外 设 0.5MB/s 的 数 据 传 输 率, 外 设 每 秒 申 请 的 中 断 次 数 为 :0.5MB/4B= 秒 钟 内 用 于 中 断 的 开 销 : = =12.5M 个 时 钟 周 期 CPU 用 于 外 设 I/O 的 时 间 占 整 个 CPU 时 间 的 百 分 比 :12.5M/500M=2.5% (2) 当 外 设 数 据 传 输 率 提 高 到 5MB/s 时 改 用 DMA 方 式 传 送, 每 次 DMA 传 送 5 000B,1 秒 钟 内 需 产 生 的 DMA 次 数 :5 MB/5 000 B= CPU 用 于 DMA 处 理 的 总 开 销 : = =0.5M 个 时 钟 周 期 CPU 用 于 外 设 I/O 的 时 间 占 整 个 CPU 时 间 的 百 分 比 :0.5M/500M=0.1% 44. 解 答 : 一 条 指 令 的 执 行 过 程 通 常 由 取 指 译 码 和 执 行 3 个 步 骤 完 成, 本 题 中 取 指 用 3 个 节 拍 译 码 用 1 个 节 拍, 执 行 加 法 运 算 并 把 结 果 写 入 主 存 如 何 完 成 呢? 包 括 划 分 执 行 步 骤 确 定 完 成 的 功 能 要 提 供 的 控 制 信 号, 这 是 本 题 要 测 试 的 内 容 为 回 答 这 个 问 题, 首 先 要 看 清 图 中 给 出 的 部 件 组 成 情 况 和 信 息 传 送 的 路 径 要 完 成 的 功 能 时 (R0)+(( R1)) (R1), 从 图 中 看 到 : (1) R0 R1 都 有 送 自 己 内 容 到 内 总 线 的 路 径, 控 制 信 号 分 别 是 R0out 和 R1out; (2) ALU 加 运 算,2 个 数 据 由 工 作 寄 存 器 A 和 内 总 线 提 供, 控 制 信 号 是 Add;A 只 接 收 内 总 线 的 内 容, 控 制 信 号 是 Ain; 结 果 需 存 AC, 控 制 信 号 是 ACin;AC 的 内 容 可 送 内 总 线, 控 制 信 号 是 ACout; (3) PC 可 接 收 内 总 线 的 内 容, 还 可 增 1, 控 制 信 号 是 PCin 和 PC+1,PC 的 内 容 可 送 内 总 线, 控 制 信 号 是 PCout; (4) 指 令 寄 存 器 IR 可 接 收 内 总 线 的 内 容, 控 制 信 号 是 IRin; (5) 读 写 存 储 器 时, 地 址 由 MAR 经 AB 提 供,MAR 只 接 收 总 线 上 的 信 息, 控 制 信 号 是 MARin; (6) 读 存 储 器, 提 供 读 命 令 MemR, 并 通 过 DB 送 入 MDR, 控 制 信 号 是 MDRinE;MDR 的 内 容 可 送 入 总 线, 控 制 信 号 是 MDRout; (7) 写 存 储 器, 提 供 写 命 令 MemW, 数 据 由 MDR 通 过 DB 送 到 存 储 器 的 数 据 引 脚, 控 制 信 号 是 MDRoutE;

9 然 后 是 划 分 执 行 步 骤 确 定 每 一 步 完 成 的 功 能 需 要 提 供 的 控 制 信 号 这 是 由 指 令 应 完 成 的 功 能 和 计 算 机 硬 件 的 实 际 组 成 情 况 和 信 息 传 送 的 可 用 路 径 共 同 决 定 的, 基 本 原 则 是 步 骤 越 少 越 好 硬 件 电 路 要 能 支 持, 可 以 有 多 种 方 案, 解 题 时 应 参 照 以 给 出 的 答 题 格 式, 即 取 指 和 译 码 阶 段 的 那 张 表 的 内 容, 但 不 必 把 表 已 有 的 内 容 再 抄 一 遍 划 分 指 令 执 行 步 骤, 确 定 每 一 步 完 成 的 功 能 给 出 需 要 提 供 的 控 制 信 号 : 请 注 意,(R0)+(( R1)) 表 示 :R0 寄 存 器 的 内 容 与 R1 作 地 址 从 主 存 中 读 出 来 的 数 据 完 成 加 法 运 算 ; 而 (R1) 表 示 把 R1 的 内 容 作 为 主 存 储 器 的 地 址 完 成 写 主 存 操 作 为 防 止 出 现 误 解, 题 中 还 特 地 对 此 作 了 文 字 说 明 这 条 指 令 的 功 能 是 先 到 主 存 储 器 取 一 个 数, 之 后 运 算, 再 将 结 果 写 回 主 存 储 器 (1) 执 行 相 加 运 算, 需 把 存 储 器 中 的 数 据 读 出, 为 此 首 先 送 地 址, 将 R1 的 内 容 送 MAR, 控 制 信 号 是 R1out MARin (2) 启 动 读 主 存 操 作, 读 出 的 内 容 送 入 MDR, 控 制 信 号 是 MemR MDRinE 还 可 同 时 把 R0 的 内 容 经 内 总 线 送 入 A, 用 到 的 控 制 信 号 是 R0out Ain (3) 执 行 加 法 运 算, 即 A 的 内 容 与 MDR 的 内 容 相 加, 结 果 保 存 到 AC, 控 制 信 号 是 MDRout Add Acin (4) 要 把 AC 的 内 容 写 入 主 存, 由 于 R1 的 内 容 已 经 在 MAR 中, 地 址 已 经 有 了, 但 需 要 把 写 入 的 数 据 ( 已 经 在 AC 中 ) 经 内 总 线 送 入 MDR, 控 制 信 号 是 ACout MDRin (5) 给 出 写 主 存 的 命 令, 把 MDR 的 内 容 经 DB 送 存 储 器 的 数 据 线 引 脚, 执 行 写 操 作, 控 制 信 号 是 MDRoutE MemW 这 几 个 步 骤 是 有 先 后 次 序 的, 前 面 的 完 成 了, 下 一 步 才 可 以 执 行, 也 保 证 了 不 会 产 生 硬 件 线 路 的 冲 突 请 注 意, 使 用 最 为 频 繁 的 是 内 总 线, 它 在 任 何 时 刻 只 能 接 收 一 个 输 入 数 据, 并 且 向 内 总 线 发 送 信 息 的 电 路 只 能 以 三 态 门 器 件 连 接 到 内 总 线,5 个 向 内 总 裁 发 送 信 息 的 控 制 信 号 (ACout,PCout,R0out,R1out,MDRout) 最 多 只 能 有 一 个 为 1, 其 他 4 个 必 须 全 为 0, 或 者 5 个 全 为 0. 仔 细 看 一 下, 发 现 可 以 把 第 2 个 步 骤 的 操 作 划 分 到 两 个 步 骤 中 完 成, 一 个 步 骤 中 安 排 MDR 接 收 从 存 储 器 中 读 出 的 内 容, 到 另 外 一 个 步 骤 实 现 R0 的 内 容 送 入 A, 这 多 用 了 一 个 操 作 步 骤, 指 令 的 执 行 速 度 会 变 慢 有 些 解 题 者 在 写 存 储 器 之 前, 还 会 再 执 行 一 次 把 R1 的 内 容 送 MAR, 尽 管 无 此 必 要, 但 不 属 于 原 理 上 的 错 误 当 然 还 可 以 有 其 他 的 设 计 结 果 解 题 时 这 些 叙 述 内 容 不 必 写 出 来 ( 这 里 写 出 这 些 内 容 是 希 望 帮 助 大 家 领 会 本 题 要 测 试 的 知 识 点 和 指 令 的 执 行 过 程 ), 直 接 按 照 已 经 给 出 的 表 格 的 形 式 按 照 提 供 的 填 写 办 法 把 设 计 的 表 格 及 其 内 容 填 好 就 可 以 了 请 注 意, 题 目 表 格 内 容 ( 告 诉 你 答 题 的 格 式 和 答 题 内 容 的 表 达 方 式 ) 与 你 答 题 的 表 格 内 容 合 在 一 起 才 是 这 条 指 令 的 完 整 的 执 行 过 程, 千 万 不 要 产 生 任 何 错 觉 参 考 答 案 一 : 时 钟 功 能 有 效 控 制 信 号 C5 MAR (R1) R1out,MARin C6 MDR M(MAR) A (R0) MemR,MDRinE, R0out,Ain C7 AC (MDR)+(A) MDRout,Add,ACin C8 MDR (AC) ACout,MDRin C9 M(MAR) (MDR) MDRoutE,MemW A (R0) 也 可 在 C7: AC (MDR)+(A) 之 前 单 列 的 一 个 时 钟 周 期 内 执 行 参 考 答 案 二 : 时 钟 功 能 有 效 控 制 信 号 C5 MAR (R1) R1out,MARin

10 C6 MDR M(MAR) MemR,MDRinE C7 A (MDR) MDRout,Ain C8 AC (A)+(R0) R0out,Add,ACin C9 MDR (AC) ACout,MDRin C10 M(MAR) (MDR) MDRoutE,MemW 45. 解 答 : 定 义 信 号 量 odd 控 制 P1 与 P2 之 间 的 同 步 ;even 控 制 P1 与 P3 之 间 的 同 步 ;empty 控 制 生 产 者 与 消 费 者 之 间 的 同 步 ;mutex 控 制 进 程 间 互 斥 使 用 缓 冲 区 程 序 如 下 : semaphore odd = 0, even = 0, empty = N, mutex = 1; P1( ) { x = produce(); 生 成 一 个 数 P(empty); 判 断 缓 冲 区 是 否 有 空 单 元 P(mutex); 缓 冲 区 是 否 被 占 用 Put(); V(mutex); 释 放 缓 冲 区 if(x%2 == 0) V(even); 如 果 是 偶 数, 向 P3 发 出 信 号 else V(odd); 如 果 是 奇 数, 向 P2 发 出 信 号 } P2( ) { P(odd); 收 到 P1 发 来 的 信 号, 已 产 生 一 个 奇 数 P(mutex); 缓 冲 区 是 否 被 占 用 getodd(); V(mutex); 释 放 缓 冲 区 V(empty); 向 P1 发 信 号, 多 出 一 个 空 单 元 countodd(); } P3( ) { P(even); 收 到 P1 发 来 的 信 号, 已 产 生 一 个 偶 数 P(mutext); 缓 冲 区 是 否 被 占 用 geteven(); V(mutex); 释 放 缓 冲 区 V(empty); 向 P1 发 信 号, 多 出 一 个 空 单 元 counteven(); } 46. 解 答 : (1) 根 据 页 式 管 理 的 工 作 原 理, 应 先 考 虑 页 面 大 小, 以 便 将 页 号 和 页 内 位 移 分 解 出 来 页 面 大 小 为 4KB,

11 即 2 12, 则 得 到 页 内 位 移 占 虚 地 址 的 低 12 位, 页 号 占 剩 余 高 位 可 得 三 个 虚 地 址 的 页 号 P 如 下 ( 十 六 进 制 的 一 位 数 字 转 换 成 4 位 二 进 制, 因 此, 十 六 进 制 的 低 三 位 正 好 为 页 内 位 移, 最 高 位 为 页 号 ): 2362H:P=2, 访 问 快 表 10ns, 因 初 始 为 空, 访 问 页 表 100ns 得 到 页 框 号, 合 成 物 理 地 址 后 访 问 主 存 100ns, 共 计 10ns+100ns+100ns=210ns 1565H:P=1, 访 问 快 表 10ns, 落 空, 访 问 页 表 100ns 落 空, 进 行 缺 页 中 断 处 理 10 8 ns, 访 问 快 表 10ns, 合 成 物 理 地 址 后 访 问 主 存 100ns, 共 计 10ns+100ns+10 8 ns+10ns+100ns= ns 25A5H:P=2, 访 问 快 表, 因 第 一 次 访 问 已 将 该 页 号 放 入 快 表, 因 此 花 费 10ns 便 可 合 成 物 理 地 址, 访 问 主 存 100ns, 共 计 10ns+100ns=110ns (2) 当 访 问 虚 地 址 1565H 时, 产 生 缺 页 中 断, 合 法 驻 留 集 为 2, 必 须 从 页 表 中 淘 汰 一 个 页 面, 根 据 题 目 的 置 换 算 法, 应 淘 汰 0 号 页 面, 因 此 1565H 的 对 应 页 框 号 为 101H 由 此 可 得 1565H 的 物 理 地 址 为 H 47. 解 答 : ⑴ CIDR 中 的 子 网 号 可 以 全 0 或 全 1, 但 主 机 号 不 能 全 0 或 全 1 因 此 若 将 IP 地 址 空 间 /24 划 分 为 2 个 子 网, 且 每 个 局 域 网 需 分 配 的 IP 地 址 个 数 不 少 于 120 个, 子 网 号 至 少 要 占 用 一 位 由 2 6-2<120<2 7-2 可 知, 主 机 号 至 少 要 占 用 7 位 由 于 源 IP 地 址 空 间 的 网 络 前 缀 为 24 位, 因 此 主 机 号 位 数 + 子 网 号 位 数 =8 综 上 可 得 主 机 号 位 数 为 7, 子 网 号 位 数 为 1 因 此 子 网 的 划 分 结 果 为 : 子 网 1: /25, 子 网 2: /25 地 址 分 配 方 案 : 子 网 1 分 配 给 局 域 网 1, 子 网 2 分 配 给 局 域 网 2, 或 子 网 1 分 配 给 局 域 网 2, 子 网 2 分 配 给 局 域 网 1 ⑵ 由 于 局 域 网 1 和 局 域 网 2 分 别 与 路 由 器 R1 的 E1 E2 接 口 直 接 相 连, 因 此 在 R1 的 路 由 表 中, 目 的 网 络 为 局 域 网 1 的 转 发 路 径 是 直 接 通 过 接 口 E1 转 发, 目 的 网 络 为 局 域 网 2 的 转 发 路 径 是 直 接 通 过 接 口 E1 转 发 由 于 局 域 网 1 2 的 网 络 前 缀 均 为 25 位, 因 此 它 们 的 子 网 掩 码 均 为 根 据 题 意, R1 专 门 为 域 名 服 务 器 设 定 了 一 个 特 定 的 路 由 表 项, 因 此 该 路 由 表 项 中 的 子 网 掩 码 应 为 对 应 的 下 一 跳 转 发 地 址 是 , 转 发 接 口 是 L0 根 据 题 意, 到 互 联 网 的 路 由 实 质 上 相 当 于 一 个 默 认 路 由, 默 认 路 由 一 般 写 作 0/0, 即 目 的 地 址 为 , 子 网 掩 码 为 对 应 的 下 一 跳 转 发 地 址 是 , 转 发 接 口 是 L0 综 上 可 得 到 路 由 器 R1 的 路 由 表 为 : ( 若 子 网 1 分 配 给 局 域 网 1, 子 网 2 分 配 给 局 域 网 2) 目 的 网 络 IP 地 址 子 网 掩 码 下 一 跳 IP 地 址 接 口 E E L L0 ( 若 子 网 1 分 配 给 局 域 网 2, 子 网 2 分 配 给 局 域 网 1) 目 的 网 络 IP 地 址 子 网 掩 码 下 一 跳 IP 地 址 接 口 E E L L0 ⑶ 局 域 网 1 和 局 域 网 2 的 地 址 可 以 聚 合 为 /24, 而 对 于 路 由 器 R2 来 说, 通 往 局 域 网 1 和 2 的

12 转 发 路 径 都 是 从 L0 接 口 转 发, 因 此 采 用 路 由 聚 合 技 术 后, 路 由 器 R2 到 局 域 网 1 和 局 域 网 2 的 路 由 为 : 目 的 网 络 IP 地 址 子 网 掩 码 下 一 跳 IP 地 址 接 口 L0

13 2010 年 全 国 硕 士 研 究 生 入 学 统 一 考 试 计 算 机 科 学 与 技 术 学 科 联 考 计 算 机 学 科 专 业 基 础 综 合 试 题 一 单 项 选 择 题 : 第 1~40 小 题, 每 小 题 2 分, 共 80 分 下 列 每 题 给 出 的 四 个 选 项 中, 只 有 一 个 选 项 最 符 合 试 题 要 求 1. 若 元 素 a b c d e f 依 次 进 栈, 允 许 进 栈 退 栈 操 作 交 替 进 行, 但 不 允 许 连 续 三 次 进 行 退 栈 操 作, 则 不. 可 能 得 到 的 出 栈 序 列 是 A.d c e b f a B.c b d a e f C.b c a e f d D.a f e d c b 2. 某 队 列 允 许 在 其 两 端 进 行 入 队 操 作, 但 仅 允 许 在 一 端 进 行 出 队 操 作 若 元 素 a b c d e 依 次 入 此 队 列 后 再 进 行 出 队 操 作, 则 不. 可 能 得 到 的 出 队 序 列 是 A.b a c d e B.d b a c e C.d b c a e D.e c b a d 3. 下 列 线 索 二 叉 树 中 ( 用 虚 线 表 示 线 索 ), 符 合 后 序 线 索 树 定 义 的 是 a a a a b c Null b c Null b c Null b c Null d d d Null d A. B. C. D. 4. 在 右 图 所 示 的 平 衡 二 叉 树 中, 插 入 关 键 字 48 后 得 到 一 棵 新 平 衡 二 叉 树 在 新 平 衡 二 叉 树 中, 关 键 字 37 所 在 结 点 的 左 右 子 结 点 中 保 存 的 关 键 字 分 别 是 24 A.13,48 C.24,53 B.24,48 D 24, 在 一 棵 度 为 4 的 树 T 中, 若 有 20 个 度 为 4 的 结 点,10 个 度 为 3 的 结 点,1 个 度 为 2 的 结 点,10 个 度 为 1 的 结 点, 则 树 T 的 叶 结 点 个 数 是 A.41 B.82 C.113 D 对 n(n 2) 个 权 值 均 不 相 同 的 字 符 构 造 成 哈 夫 曼 树 下 列 关 于 该 哈 夫 曼 树 的 叙 述 中, 错 误.. 的 是 A. 该 树 一 定 是 一 棵 完 全 二 叉 树 B. 树 中 一 定 没 有 度 为 1 的 结 点 C. 树 中 两 个 权 值 最 小 的 结 点 一 定 是 兄 弟 结 点 D. 树 中 任 一 非 叶 结 点 的 权 值 一 定 不 小 于 下 一 层 任 一 结 点 的 权 值 7. 若 无 向 图 G=(V, E) 中 含 有 7 个 顶 点, 要 保 证 图 G 在 任 何 情 况 下 都 是 连 通 的, 则 需 要 的 边 数 最 少 是 A.6 B.15 C.16 D 对 右 图 进 行 拓 扑 排 序, 可 以 得 到 不 同 的 拓 扑 序 列 的 个 数 是 e A.4 B. 3 C.2 D.1 9. 已 知 一 个 长 度 为 16 的 顺 序 表 L, 其 元 素 按 关 键 字 有 序 排 列 若 采 用 折 半 查 a d 找 法 查 找 一 个 L 中 不 存 在 的 元 素, 则 关 键 字 的 比 较 次 数 最 多 的 是 A.4 B.5 C.6 D.7 b c 10. 采 用 递 归 方 式 对 顺 序 表 进 行 快 速 排 序 下 列 关 于 递 归 次 数 的 叙 述 中, 正 确 的 是 A. 递 归 次 数 与 初 始 数 据 的 排 列 次 序 无 关

14 B. 每 次 划 分 后, 先 处 理 较 长 的 分 区 可 以 减 少 递 归 次 数 C. 每 次 划 分 后, 先 处 理 较 短 的 分 区 可 以 减 少 递 归 次 数 D. 递 归 次 数 与 每 次 划 分 后 得 到 的 分 区 的 处 理 顺 序 无 关 11. 对 一 组 数 据 (2,12,16,88,5,10) 进 行 排 序, 若 前 三 趟 排 序 结 果 如 下 : 第 一 趟 排 序 结 果 :2,12,16,5,10,88 第 二 趟 排 序 结 果 :2,12,5,10,16,88 第 三 趟 排 序 结 果 :2,5,10,12,16,88 则 采 用 的 排 序 方 法 可 能 是 A. 起 泡 排 序 B. 希 尔 排 序 C. 归 并 排 序 D. 基 数 排 序 12. 下 列 选 项 中, 能 缩 短 程 序 执 行 时 间 的 措 施 是 Ⅰ. 提 高 CPU 时 钟 频 率 Ⅲ. 对 程 序 进 行 编 译 优 化 Ⅱ. 优 化 数 据 通 路 结 构 A. 仅 Ⅰ 和 Ⅱ B. 仅 Ⅰ 和 Ⅲ C. 仅 Ⅱ 和 Ⅲ D.Ⅰ Ⅱ 和 Ⅲ 13. 假 定 有 4 个 整 数 用 8 位 补 码 分 别 表 示 r1=feh,r2=f2h,r3=90h,r4=f8h, 若 将 运 算 结 果 存 放 在 一 个 8 位 寄 存 器 中, 则 下 列 运 算 中 会 发 生 溢 出 的 是 A.r1 x r2 C.r1 x r4 B.r2 x r3 D.r2 x r4 14. 假 定 变 量 i f 和 d 的 数 据 类 型 分 别 为 int,float 和 double(int 用 补 码 表 示,float 和 double 分 别 用 IEEE754 单 精 度 和 双 精 度 浮 点 数 格 式 表 示 ), 已 知 i=785,f=1.5678e3,d=1.5e100 若 在 32 位 机 器 中 执 行 下 列 关 系 表 达 式, 则 结 果 为 真 的 是 (I)i == (int)(float)i (III)f == (float)(double)f (II)f == (float)(int)f (IV)(d+f)-d == f A. 仅 I 和 II B. 仅 I 和 III C. 仅 II 和 III D. 仅 III 和 IV 假 定 用 若 干 个 2kx4 位 的 芯 片 组 成 一 个 8kx8 位 的 存 储 器, 则 地 址 0B1FH 所 在 芯 片 的 最 小 地 址 是 A.0000H B.0600H C.0700H D.0800H 16. 下 列 有 关 RAM 和 ROM 的 叙 述 中, 正 确 的 是 I RAM 是 易 失 性 存 储 器,ROM 是 非 易 失 性 存 储 器 II RAM 和 ROM 都 采 用 随 机 存 取 方 式 进 行 信 息 访 问 III RAM 和 ROM 都 可 用 作 Cache IV RAM 和 ROM 都 需 要 进 行 刷 新 A. 仅 I 和 II B. 仅 II 和 III C. 仅 I,II 和 IV D. 仅 II,III 和 IV 17. 下 列 命 中 组 合 情 况 中, 一 次 访 存 过 程 中 不. 可 能 发 生 的 是 A.TLB 未 命 中,Cache 未 命 中,Page 未 命 中 B.TLB 未 命 中,Cache 命 中,Page 命 中 C.TLB 命 中,Cache 未 命 中,Page 命 中 D.TLB 命 中,Cache 命 中,Page 未 命 中 18. 下 列 寄 存 器 中, 汇 编 语 言 程 序 员 可 见 的 是 A. 存 储 器 地 址 寄 存 器 (MAR) B. 程 序 计 数 器 (PC) C. 存 储 器 数 据 寄 存 器 (MDR) D. 指 令 寄 存 器 (IR) 19. 下 列 选 项 中, 不. 会 引 起 指 令 流 水 线 阻 塞 的 是 A. 数 据 旁 路 ( 转 发 ) B. 数 据 相 关 C. 条 件 转 移 D. 资 源 冲 突

15 20. 下 列 选 项 中 的 英 文 缩 写 均 为 总 线 标 准 的 是 A.PCI CRT USB EISA B.ISA CPI VESA EISA C.ISA SCSI RAM MIPS D.ISA EISA PCI PCI-Express 21. 单 级 中 断 系 统 中, 中 断 服 务 程 序 内 的 执 行 顺 序 是 I 保 护 现 场 II 开 中 断 III 关 中 断 IV 保 存 断 点 V 中 断 事 件 处 理 VI 恢 复 现 场 VII 中 断 返 回 A.I->V->VI->II->VII C.III->IV->V->VI->VII B.III->I->V->VII D.IV->I->V->VI->VII 22. 假 定 一 台 计 算 机 的 显 示 存 储 器 用 DRAM 芯 片 实 现, 若 要 求 显 示 分 辨 率 为 1600*1200, 颜 色 深 度 为 24 位, 帧 频 为 85HZ, 显 存 总 带 宽 的 50% 用 来 刷 新 屏 幕, 则 需 要 的 显 存 总 带 宽 至 少 约 为 A.245Mbps B.979Mbps C.1 958Mbps D.7 834Mbps 23. 下 列 选 项 中, 操 作 系 统 提 供 给 应 用 程 序 的 接 口 是 A. 系 统 调 用 B. 中 断 C. 库 函 数 D. 原 语 24. 下 列 选 项 中, 导 致 创 建 新 进 程 的 操 作 是 Ⅰ 用 户 登 录 成 功 Ⅱ 设 备 分 配 Ⅲ 启 动 程 序 执 行 A. 仅 Ⅰ 和 Ⅱ B. 仅 Ⅱ 和 Ⅲ C. 仅 Ⅰ 和 Ⅲ D.Ⅰ Ⅱ 和 Ⅲ 25. 设 与 某 资 源 关 联 的 信 号 量 初 值 为 3, 当 前 值 为 1 若 M 表 示 该 资 源 的 可 用 个 数,N 表 示 等 待 该 资 源 的 进 程 数, 则 M N 分 别 是 A.0 1 B.1 0 C.1 2 D 下 列 选 项 中, 降 低 进 程 优 先 级 的 合 理 时 机 是 A. 进 程 的 时 间 片 用 完 B. 进 程 刚 完 成 I/O, 进 入 就 绪 列 队 C. 进 程 长 期 处 于 就 绪 列 队 中 D. 进 程 从 就 绪 态 转 为 运 行 态 27. 进 程 P0 和 P1 的 共 享 变 量 定 义 及 其 初 值 为 boolean flag[2]; int turn = 0; flag[0] = FALSE; flag[1] = FALSE; 若 进 程 P0 和 P1 访 问 临 界 资 源 的 类 C 伪 代 码 实 现 如 下 : void P0() { } // 进 程 P0 while(true) { flag[0]=true; turn=1; while(flag[1]&&(turn==1)) ; } 临 界 区 ; flag[0]=false; void P1() { } // 进 程 P1 while(true) { flag[1]=true; turn=0; while(flag[0]&&(turn==0)) ; } 临 界 区 ; flag[1]=false;

16 则 并 发 执 行 进 程 P0 和 P1 时 产 生 的 情 形 是 A. 不 能 保 证 进 程 互 斥 进 入 临 界 区, 会 出 现 饥 饿 现 象 B. 不 能 保 证 进 程 互 斥 进 入 临 界 区, 不 会 出 现 饥 饿 现 象 C. 能 保 证 进 程 互 斥 进 入 临 界 区, 会 出 现 饥 饿 现 象 D. 能 保 证 进 程 互 斥 进 入 临 界 区, 不 会 出 现 饥 饿 现 象 28. 某 基 于 动 态 分 区 存 储 管 理 的 计 算 机, 其 主 存 容 量 为 55MB( 初 始 为 空 闲 ), 采 用 最 佳 适 配 (Best Fit) 算 法, 分 配 和 释 放 的 顺 序 为 : 分 配 15M B, 分 配 30MB, 释 放 15M B, 分 配 8M B, 分 配 6M B, 此 时 主 存 中 最 大 空 闲 分 区 的 大 小 是 A.7MB B.9MB C.10MB D.15MB 29. 某 计 算 机 采 用 二 级 页 表 的 分 页 存 储 管 理 方 式, 按 字 节 编 址, 页 大 小 为 2 10 字 节, 页 表 项 大 小 为 2 字 节, 逻 辑 地 址 结 构 为 : 页 目 录 号 页 号 页 内 偏 移 量 逻 辑 地 址 空 间 大 小 为 2 16 页, 则 表 示 整 个 逻 辑 地 址 空 间 的 页 目 录 表 中 包 含 表 项 的 个 数 至 少.. 是 A. 64 B. 128 C. 256 D 设 文 件 索 引 节 点 中 有 7 个 地 址 项, 其 中 4 个 地 址 项 是 直 接 地 址 索 引,2 个 地 址 项 是 一 级 间 接 地 址 索 引,1 个 地 址 项 是 二 级 间 接 地 址 索 引, 每 个 地 址 项 大 小 为 4 字 节 若 磁 盘 索 引 块 和 磁 盘 数 据 块 大 小 均 为 256 字 节, 则 可 表 示 的 单 个 文 件 最 大 长 度 是 A.33 KB B.519 KB C KB D KB 31. 设 置 当 前 工 作 目 录 的 主 要 目 的 是 A. 节 省 外 存 空 间 B. 节 省 内 存 空 间 C. 加 快 文 件 的 检 索 速 度 D. 加 快 文 件 的 读 / 写 速 度 32. 本 地 用 户 通 过 键 盘 登 陆 系 统 时, 首 先 获 得 键 盘 输 入 信 息 的 程 序 是 A. 命 令 解 释 程 序 B. 中 断 处 理 程 序 C. 系 统 调 用 服 务 程 序 D. 用 户 登 录 程 序 33. 下 列 选 项 中, 不. 属 于 网 络 体 系 结 构 所 描 述 的 内 容 是 A. 网 络 的 层 次 B. 每 一 层 使 用 的 协 议 C. 协 议 的 内 部 实 现 细 节 D. 每 一 层 必 须 完 成 的 功 能 34. 在 下 图 所 示 的 采 用 存 储 - 转 发 方 式 的 分 组 交 换 网 络 中, 所 有 链 路 的 数 据 传 输 速 率 为 100Mbps, 分 组 大 小 为 1000B, 其 中 分 组 头 大 小 为 20B 若 主 机 H1 向 主 机 H2 发 送 一 个 大 小 为 B 的 文 件, 则 在 不 考 虑 分 组 拆 装 时 间 和 传 播 延 迟 的 情 况 下, 从 H1 发 送 开 始 到 H2 接 收 完 为 止, 需 要 的 时 间 至 少.. 是 A.80 ms B ms C ms D ms 35. 某 自 治 系 统 内 采 用 RIP 协 议, 若 该 自 治 系 统 内 的 路 由 器 R1 收 到 其 邻 居 路 由 器 R2 的 距 离 矢 量, 距 离 矢 量 中 包 含 信 息 <net1, 16>, 则 能 得 出 的 结 论 是 A.R2 可 以 经 过 R1 到 达 net1, 跳 数 为 17 B.R2 可 以 到 达 net1, 跳 数 为 16 C.R1 可 以 经 过 R2 到 达 net1, 跳 数 为 17 D.R1 不 能 经 过 R2 到 达 net1

17 36. 若 路 由 器 R 因 为 拥 塞 丢 弃 IP 分 组, 则 此 时 R 可 向 发 出 该 IP 分 组 的 源 主 机 发 送 的 ICMP 报 文 类 型 是 A. 路 由 重 定 向 B. 目 的 不 可 达 C. 源 点 抑 制 D. 超 时 37. 某 网 络 的 IP 地 址 空 间 为 /24, 采 用 定 长 子 网 划 分, 子 网 掩 码 为 , 则 该 网 络 中 的 最 大 子 网 个 数 每 个 子 网 内 的 最 大 可 分 配 地 址 个 数 分 别 是 A.32,8 C.8,32 D.8,30 B.32,6 38. 下 列 网 络 设 备 中, 能 够 抑 制 广 播 风 暴 的 是 Ⅰ 中 继 器 Ⅱ 集 线 器 Ⅲ 网 桥 Ⅳ 路 由 器 A. 仅 Ⅰ 和 Ⅱ B. 仅 Ⅲ C. 仅 Ⅲ 和 Ⅳ D. 仅 Ⅳ 39. 主 机 甲 和 主 机 乙 之 间 已 建 立 了 一 个 TCP 连 接,TCP 最 大 段 长 度 为 字 节 若 主 机 甲 的 当 前 拥 塞 窗 口 为 字 节, 在 主 机 甲 向 主 机 乙 连 续 发 送 两 个 最 大 段 后, 成 功 收 到 主 机 乙 发 送 的 第 一 个 段 的 确 认 段, 确 认 段 中 通 告 的 接 收 窗 口 大 小 为 字 节, 则 此 时 主 机 甲 还 可 以 向 主 机 乙 发 送 的 最 大 字 节 数 是 A B C D 如 果 本 地 域 名 服 务 器 无 缓 存, 当 采 用 递 归 方 法 解 析 另 一 网 络 某 主 机 域 名 时, 用 户 主 机 本 地 域 名 服 务 器 发 送 的 域 名 请 求 消 息 数 分 别 为 A. 一 条 一 条 B. 一 条 多 条 C. 多 条 一 条 D. 多 条 多 条 二 综 合 应 用 题 : 第 41~47 题, 共 70 分 41. (10 分 ) 将 关 键 字 序 列 ( ) 散 列 存 储 到 散 列 表 中 散 列 表 的 存 储 空 间 是 一 个 下 标 从 0 开 始 的 一 维 数 组, 散 列 函 数 为 :H(key) = (keyx3) MOD 7, 处 理 冲 突 采 用 线 性 探 测 再 散 列 法, 要 求 装 填 ( 载 ) 因 子 为 0.7 (1) 请 画 出 所 构 造 的 散 列 表 (2) 分 别 计 算 等 概 率 情 况 下 查 找 成 功 和 查 找 不 成 功 的 平 均 查 找 长 度 42. (13 分 ) 设 将 n(n>1) 个 整 数 存 放 到 一 维 数 组 R 中 试 设 计 一 个 在 时 间 和 空 间 两 方 面 都 尽 可 能 高 效 的 算 法 将 R 中 保 存 的 序 列 循 环 左 移 p(0<p<n) 个 位 置, 即 将 R 中 的 数 据 由 (X0, X1 Xn-1) 变 换 为 (Xp, Xp+1 Xn-1, X0, X1 Xp-1) 要 求 : ⑴ 给 出 算 法 的 基 本 设 计 思 想 ⑵ 根 据 设 计 思 想, 采 用 C 或 C++ 或 JAVA 语 言 描 述 算 法, 关 键 之 处 给 出 注 释 ⑶ 说 明 你 所 设 计 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 43. (11 分 ) 某 计 算 机 字 长 为 16 位, 主 存 地 址 空 间 大 小 为 128KB, 按 字 编 址 采 用 单 字 长 指 令 格 式, 指 令 各 字 段 定 义 如 下 : OP Ms Rs Md Rd 源 操 作 数 目 的 操 作 数 转 移 指 令 采 用 相 对 寻 址 方 式, 相 对 偏 移 量 用 补 码 表 示, 寻 址 方 式 定 义 如 下 : Ms/Md 寻 址 方 式 助 记 符 含 义 000B 寄 存 器 直 接 Rn 操 作 数 =(Rn)

18 001B 寄 存 器 间 接 (Rn) 操 作 数 =((Rn)) 010B 寄 存 器 间 接 自 增 (Rn)+ 操 作 数 =((Rn)),(Rn)+1 Rn 011B 相 对 D(Rn) 转 移 目 标 地 址 =(PC)+(Rn) 注 :(X) 表 示 存 储 器 地 址 X 或 寄 存 器 X 的 内 容 请 回 答 下 列 问 题 : ⑴ 该 指 令 系 统 最 多 可 有 多 少 条 指 令? 该 计 算 机 最 多 有 多 少 个 通 用 寄 存 器? 存 储 器 地 址 寄 存 器 (MAR) 和 存 储 器 数 据 寄 存 器 (MDR) 至 少 各 需 要 多 少 位? ⑵ 转 移 指 令 的 目 标 地 址 范 围 是 多 少? ⑶ 若 操 作 码 0010B 表 示 加 法 操 作 ( 助 记 符 为 add), 寄 存 器 R4 和 R5 的 编 号 分 别 为 100B 和 101B,R4 的 内 容 为 1234H,R5 的 内 容 为 5678H, 地 址 1234H 中 的 内 容 为 5678H, 地 址 5678H 中 的 内 容 为 1234H, 则 汇 编 语 言 为 add (R4),( R5)+ ( 逗 号 前 为 源 操 作 数, 逗 号 后 为 目 的 操 作 数 ) 对 应 的 机 器 码 是 什 么 ( 用 十 六 进 制 表 示 )? 该 指 令 执 行 后, 哪 些 寄 存 器 和 存 储 单 元 中 的 内 容 会 改 变? 改 变 后 的 内 容 是 什 么? 44. (12 分 ) 某 计 算 机 的 主 存 地 址 空 间 大 小 为 256MB, 按 字 节 编 址 指 令 Cache 和 数 据 Cache 分 离, 均 有 8 个 Cache 行, 每 个 Cache 行 大 小 为 64B, 数 据 Cache 采 用 直 接 映 射 方 式 现 有 两 个 功 能 相 同 的 程 序 A 和 B, 其 伪 代 码 如 下 所 示 : 程 序 A: int a[256][256] int sum_array1() { int i, j, sum=0; for(i=0; i<256; i++) for(j=0; j<256; j++) sum += a[i][j]; return sum; } 假 定 int 类 型 数 据 用 32 位 补 码 表 示, 程 序 编 译 时 i,j,sum 均 分 配 在 寄 存 器 中, 数 组 a 按 行 优 先 方 式 存 放, 其 首 地 址 为 320( 十 进 制 数 ) 请 回 答 下 列 问 题, 要 求 说 明 理 由 或 给 出 计 算 过 程 (1) 若 不 考 虑 用 于 cache 一 致 性 维 护 和 替 换 算 法 的 控 制 位, 则 数 据 Cache 的 总 容 量 为 多 少? (2) 数 组 元 素 a[0][31] 和 a[1][1] 各 自 所 在 的 主 存 块 对 应 的 Cache 行 号 分 别 是 多 少 (Cache 行 号 从 0 开 始 )? (3) 程 序 A 和 B 的 数 据 访 问 命 中 率 各 是 多 少? 哪 个 程 序 的 执 行 时 间 更 短? 45. (7 分 ) 假 设 计 算 机 系 统 采 用 CSCAN( 循 环 扫 描 ) 磁 盘 调 度 策 略, 使 用 2KB 的 内 存 空 间 记 录 个 磁 盘 块 的 空 闲 状 态 (1) 请 说 明 在 上 述 条 件 下 如 何 进 行 磁 盘 块 空 闲 状 态 的 管 理 (2) 设 某 单 面 磁 盘 旋 转 速 度 为 每 分 钟 6000 转, 每 个 磁 道 有 100 个 扇 区, 相 邻 磁 道 间 的 平 均 移 动 时 间 为 1ms 若 在 某 时 刻, 磁 头 位 于 100 号 磁 道 处, 并 沿 着 磁 道 号 增 大 的 方 向 移 动 ( 如 下 图 所 示 ), 磁 道 号 请 求 队 列 为 50, 90,30,120, 对 请 求 队 列 中 的 每 个 磁 道 需 读 取 1 个 随 机 分 布 的 扇 区, 则 读 完 这 4 个 扇 区 点 共 需 要 多 少 时 间? 要 求 给 出 计 算 过 程 程 序 B: int a[256][256] int sum_array2() { int i, j, sum=0; for(j=0; j<256; j++) for(i=0; i<256; i++) sum += a[i][j]; return sum; } (3) 如 果 将 磁 盘 替 换 为 随 机 访 问 的 Flash 半 导 体 存 储 器 ( 如 U 盘 SSD 等 ), 是 否 有 比 CSCAN 更 高 效 的 磁 盘 调 度 策 略? 若 有, 给 出 磁 盘 调 度 策 略 的 名 称 并 说 明 理 由 ; 若 无, 说 明 理 由

19 0 号 磁 道 随 机 分 布 的 某 扇 区 磁 头 移 动 方 向 100 号 磁 道 46. (8 分 ) 设 某 计 算 机 的 逻 辑 地 址 空 间 和 物 理 地 址 空 间 均 为 64KB, 按 字 节 编 址 若 某 进 程 最 多 需 要 6 页 (Page) 数 据 存 储 空 间, 页 的 大 小 为 1KB, 操 作 系 统 采 用 固 定 分 配 局 部 置 换 策 略 为 此 进 程 分 配 4 个 页 框 (Page Frame) 在 时 刻 260 前 的 该 进 程 访 问 情 况 如 下 表 所 示 ( 访 问 位 即 使 用 位 ) 页 号 页 框 号 装 入 时 刻 访 问 位 当 该 进 程 执 行 到 时 刻 260 时, 要 访 问 逻 辑 地 址 为 17CAH 的 数 据 请 回 答 下 列 问 题 : (1) 该 逻 辑 地 址 对 应 的 页 号 是 多 少? (2) 若 采 用 先 进 先 出 (FIFO) 置 换 算 法, 该 逻 辑 地 址 对 应 的 物 理 地 址 是 多 少? 要 求 给 出 计 算 过 程 (3) 若 采 用 时 钟 (CLOCK) 置 换 算 法, 该 逻 辑 地 址 对 应 的 物 理 地 址 是 多 少? 要 求 给 出 计 算 过 程 ( 设 搜 索 下 一 页 的 指 针 沿 顺 时 针 方 向 移 动, 且 当 前 指 向 2 号 页 框, 示 意 图 如 下 ) 9 号 页 框 2 号 页 框 3 号 页 2 号 页 0 号 页 7 号 页 框 1 号 页 4 号 页 框 图 3.15 页 框 示 意 图 47. (9 分 ) 某 局 域 网 采 用 CSMA/CD 协 议 实 现 介 质 访 问 控 制, 数 据 传 输 速 率 为 10Mbps, 主 机 甲 和 主 机 乙 之 间 的 距 离 为 2 km, 信 号 传 播 速 度 是 km/s 请 回 答 下 列 问 题, 要 求 说 明 理 由 或 写 出 计 算 过 程 ⑴ 若 主 机 甲 和 主 机 乙 发 送 数 据 时 发 生 冲 突, 则 从 开 始 发 送 数 据 时 刻 起, 到 两 台 主 机 均 检 测 到 冲 突 时 刻 止, 最 短 需 经 过 多 长 时 间? 最 长 需 经 过 多 长 时 间 ( 假 设 主 机 甲 和 主 机 乙 发 送 数 据 过 程 中, 其 他 主 机 不 发 送 数 据 )? ⑵ 若 网 络 不 存 在 任 何 冲 突 与 差 错, 主 机 甲 总 是 以 标 准 的 最 长 以 太 网 数 据 帧 (1 518 字 节 ) 向 主 机 乙 发 送 数 据, 主 机 乙 每 成 功 收 到 一 个 数 据 帧 后 立 即 向 主 机 甲 发 送 一 个 64 字 节 的 确 认 帧, 主 机 甲 收 到 确 认 帧 后 方 可 发 送 下 一 个 数 据 帧 此 时 主 机 甲 的 有 效 数 据 传 输 速 率 是 多 少 ( 不 考 虑 以 太 网 的 前 导 码 )?

20 参 考 答 案 一 单 项 选 择 题 1. D 2. C 3. D 4. C 5. B 6. A 7. C 8. B 9. B 10. D 11. A 12. D 13. B 14. B 15. D 16. A 17. D 18. B 19. A 20. D 21. A 22. D 23. A 24. C 25. B 26. A 27. D 28. B 29. B 30. C 31. C 32. B 33. C 34. C 35. D 36. C 37. B 38. D 39. A 40. A 二 综 合 应 用 题 41. 解 答 : (1) 由 装 载 因 子 0.7, 数 据 总 数 为 7, 得 一 维 数 组 大 小 为 7/0.7=10, 数 组 下 标 为 0~9 所 构 造 的 散 列 函 数 值 如 下 所 示 : key H(key) 采 用 线 性 探 测 再 散 列 法 处 理 冲 突, 所 构 造 的 散 列 表 为 : 地 址 关 键 字 (2) 查 找 成 功 时, 是 根 据 每 个 元 素 查 找 次 数 来 计 算 平 均 长 度, 在 等 概 率 的 情 况 下, 各 关 键 字 的 查 找 次 数 为 : key 次 数 故,ASL 成 功 = 查 找 次 数 / 元 素 个 数 = ( ) / 7 = 12/7 这 里 要 特 别 防 止 惯 性 思 维 查 找 失 败 时, 是 根 据 查 找 失 败 位 置 计 算 平 均 次 数, 根 据 散 列 函 数 MOD 7, 初 始 只 可 能 在 0~6 的 位 置 等 概 率 情 况 下, 查 找 0~6 位 置 查 找 失 败 的 查 找 次 数 为 : H(key) 次 数 故,ASL 不 成 功 = 查 找 次 数 / 散 列 后 的 地 址 个 数 = ( ) / 7 = 18 / 解 答 : (1) 算 法 的 基 本 设 计 思 想 : 可 以 将 这 个 问 题 看 做 是 把 数 组 ab 转 换 成 数 组 ba(a 代 表 数 组 的 前 p 个 元 素,b 代 表 数 组 中 余 下 的 n-p 个 元 素 ), 先 将 a 逆 置 得 到 a -1 b, 再 将 b 逆 置 得 到 a -1 b -1, 最 后 将 整 个 a -1 b -1 逆 置 得 到 (a -1 b -1 ) -1 =ba 设 Reverse 函 数 执 行 将 数 组 元 素 逆 置 的 操 作, 对 abcdefgh 向 左 循 环 移 动 3(p=3) 个 位 置 的 过 程 如 下 : Reverse(0,p-1) 得 到 cbadefgh; Reverse(p,n-1) 得 到 cbahgfed; Reverse(0,n-1) 得 到 defghabc; 注 :Reverse 中, 两 个 参 数 分 别 表 示 数 组 中 待 转 换 元 素 的 始 末 位 置 (2) 使 用 c 语 言 描 述 算 法 如 下 : void Reverse(int R[],int from,int to) { int i,temp; for(i = 0; i < (to-from+1)/2; i++)

21 { temp = R[from+i]; R[from+i] = R[to-i]; R[to-i] = temp; } } Reverse void Converse(int R[],int n,int p){ } Reverse(R,0,p-1); Reverse(R,p,n-1); Reverse(R,0,n-1); (3) 上 述 算 法 中 三 个 Reverse 函 数 的 时 间 复 杂 度 分 别 为 ( p/ 2) (( n p)/ 2) 和 ( n/ 2) 的 算 法 的 时 间 复 杂 度 为 (n), 空 间 复 杂 度 为 (1) 另 解, 借 助 辅 助 数 组 来 实 现 :, 故 所 设 计 算 法 思 想 : 创 建 大 小 为 p 的 辅 助 数 组 S, 将 R 中 前 p 个 整 数 依 次 暂 存 在 S 中, 同 时 将 R 中 后 n-p 个 整 数 左 移, 然 后 将 S 中 暂 存 的 p 个 数 依 次 放 回 到 R 中 的 后 续 单 元 时 间 复 杂 度 为 (n), 空 间 复 杂 度 为 ( p) 43. 解 答 : (1) 操 作 码 占 4 位, 则 该 指 令 系 统 最 多 可 有 2 4 =16 条 指 令 ; 操 作 数 占 6 位, 寻 址 方 式 占 3 位, 于 是 寄 存 器 编 号 占 3 位, 则 该 机 最 多 有 2 3 =8 个 通 用 寄 存 器 ; 主 存 容 量 128KB, 按 字 编 址, 计 算 机 字 长 为 16 位, 划 分 为 128KB/2B=2 16 个 存 储 单 元, 故 MDR 和 MAR 至 少 各 需 16 位 (2) PC 和 Rn 可 表 示 的 地 址 范 围 均 为 0~2 16-1, 而 主 存 地 址 空 间 为 2 16, 故 转 移 指 令 的 目 标 地 址 范 围 是 0000H~ FFFFH(0~2 16-1) (3) 汇 编 语 句 add (R4), (R5) +, 对 应 的 机 器 码 为 B=2315H 该 指 令 执 行 后, 寄 存 器 R5 和 存 储 单 元 5678H 的 内 容 会 改 变 执 行 后,R5 的 内 容 从 5678H 变 成 5679H 存 储 单 元 5678H 中 的 内 容 变 成 该 加 法 指 令 计 算 的 结 果 5678H+1234H=68ACH 44. 解 答 : (1) 数 据 Cache 有 8 个 Cache 行, 每 个 Cache 行 大 小 为 64B,Cache 中 每 个 字 块 的 Tag 字 段 的 位 数 是 28-9 =19 位, 此 外 还 需 使 用 一 个 有 效 位, 合 计 20 位 因 此, 数 据 Cache 的 总 容 量 应 为 :8 (64+20/8)B=532B (2) 数 组 a 在 主 存 的 存 放 位 置 及 其 与 Cache 之 间 的 映 射 关 系 如 下 图 所 示 : 数 组 按 行 优 先 方 式 存 放, 首 地 址 为 320, 数 组 元 素 占 四 个 字 节 a[0][31] 所 在 的 主 存 块 对 应 的 Cache 行 号 为 : ( ) DIV 64 = 6 ; a[1][1] 所 在 的 主 存 块 对 应 的 Cache 行 号 为 : ( ) DIV 64 MOD 8 = 5 (3) 编 译 时 i j sum 均 分 配 在 寄 存 器 中, 故 数 据 访 问 命 中 率 仅 考 虑 数 组 a 的 情 况 1 该 程 序 的 特 点 是 数 组 中 的 每 一 个 元 素 仅 被 使 用 一 次 数 组 a 按 行 优 先 存 放, 数 据 Cache 正 好 放 下 数 组 半 行 中 的 全 部 元 素, 即 元 素 的 存 储 顺 序 与 使 用 次 序 高 度 的 吻 合, 每 个 字 块 的 16 个 int 型 元 素 中, 除 访 问 的 第 一 个 不 会 命 中, 接 下 来 的 15 个 都 会 命 中 访 问 全 部 字 块 都 符 合 这 一 规 律, 故 命 中 率 为 15/16, 即 程 序 A 的 数 据 访 问 命 中 率 是 93.75% 2 程 序 B 按 照 数 组 的 列 执 行 外 层 循 环, 在 执 行 内 层 循 环 的 过 程 中, 将 连 续 访 问 不 同 行 的 同 一 列 的 数 据, 不 同 行 的 同 一 列 数 组 使 用 的 是 同 一 个 Cache 单 元, 每 次 都 不 会 命 中, 故 命 中 率 是 0 由 于 从 Cache 读 数 据 比 从 主 存 读 数 据 快 很 多, 所 以 程 序 A 的 执 行 比 程 序 B 快 得 多 注 意 : 本 题 考 查 Cache 容 量 计 算, 直 接 映 射 方 式 的 地 址 计 算, 以 及 命 中 率 计 算 ( 注 意 : 行 优 先 遍 历 与 列 优 先 遍 历 命 中 率 差 别 很 大 )

22 45. 解 答 : (1) 用 位 图 表 示 磁 盘 的 空 闲 状 态 每 一 位 表 示 一 个 磁 盘 块 的 空 闲 状 态, 共 需 要 /32=512 个 字 =512 4 个 字 节 =2KB, 正 好 可 放 在 系 统 提 供 的 内 存 中 (2) 采 用 CSCAN 调 度 算 法, 访 问 磁 道 的 顺 序 和 移 动 的 磁 道 数 如 下 表 所 示 : 被 访 问 的 下 一 个 磁 道 号 移 动 距 离 ( 磁 道 数 ) 移 动 的 磁 道 数 为 =170, 故 总 的 移 动 磁 道 时 间 为 170ms 由 于 转 速 为 6000r/m, 则 平 均 旋 转 延 迟 为 5ms, 总 的 旋 转 延 迟 时 间 =20ms 由 于 转 速 为 6000r/m, 则 读 取 一 个 磁 道 上 一 个 扇 区 的 平 均 读 取 时 间 为 0.1ms, 总 的 读 取 扇 区 的 时 间 平 均 读 取 时 间 为 0.1ms, 总 的 读 取 扇 区 的 时 间 为 0.4ms 综 上, 读 取 上 述 磁 道 上 所 有 扇 区 所 花 的 总 时 间 为 190.4ms (3) 采 用 FCFS( 先 来 先 服 务 ) 调 度 策 略 更 高 效 因 为 Flash 半 导 体 存 储 器 的 物 理 结 构 不 需 要 考 虑 寻 道 时 间 和 旋 转 延 迟, 可 直 接 按 I/O 请 求 的 先 后 顺 序 服 务 46. 解 答 : (1) 由 于 该 计 算 机 的 逻 辑 地 址 空 间 和 物 理 地 址 空 间 均 为 64KB = 2 16 B, 按 字 节 编 址, 且 页 的 大 小 为 1K = 2 10, 故 逻 辑 地 址 和 物 理 地 址 的 地 址 格 式 均 为 : 页 号 / 页 框 号 (6 位 ) 页 内 偏 移 量 (10 位 ) 17CAH = B, 可 知 该 逻 辑 地 址 的 页 号 为 B = 5 (2) 根 据 FIFO 算 法, 需 要 替 换 装 入 时 间 最 早 的 页, 故 需 要 置 换 装 入 时 间 最 早 的 0 号 页, 即 将 5 号 页 装 入 7 号 页 框 中, 所 以 物 理 地 址 为 B = 1FCAH (3) 根 据 CLOCK 算 法, 如 果 当 前 指 针 所 指 页 框 的 使 用 位 为 0, 则 替 换 该 页 ; 否 则 将 使 用 位 清 零, 并 将 指 针 指 向 下 一 个 页 框, 继 续 查 找 根 据 题 设 和 示 意 图, 将 从 2 号 页 框 开 始, 前 4 次 查 找 页 框 号 的 顺 序 为

23 , 并 将 对 应 页 框 的 使 用 位 清 零 在 第 5 次 查 找 中, 指 针 指 向 2 号 页 框, 因 2 号 页 框 的 使 用 位 为 0, 故 淘 汰 2 号 页 框 对 应 的 2 号 页, 把 5 号 页 装 入 2 号 页 框 中, 并 将 对 应 使 用 位 设 置 为 1, 所 以 对 应 的 物 理 地 址 为 B = 0BCAH 47. 解 答 : ⑴ 当 主 机 甲 和 主 机 乙 同 时 向 对 方 发 送 数 据 时, 信 号 在 信 道 中 发 生 冲 突 后, 冲 突 信 号 继 续 向 两 个 方 向 传 播 这 种 情 况 下 两 台 主 机 均 检 测 到 冲 突 需 要 经 过 的 时 间 最 短, 等 于 单 程 的 传 播 时 延 t0= 2km/ km/s = 0.01ms 主 机 甲 ( 或 主 机 乙 ) 先 发 送 一 个 数 据 帧, 当 该 数 据 帧 即 将 到 达 主 机 乙 ( 或 主 机 乙 ) 时, 主 机 乙 ( 或 主 机 甲 ) 也 开 始 发 送 一 个 数 据 帧, 这 时, 主 机 乙 ( 或 主 机 甲 ) 将 立 刻 检 测 到 冲 突, 而 主 机 甲 ( 或 主 机 乙 ) 要 检 测 到 冲 突, 冲 突 信 号 还 需 要 从 主 机 乙 ( 或 主 机 甲 ) 传 播 到 主 机 甲 ( 或 主 机 乙 ), 因 此 甲 乙 两 台 主 机 均 检 测 到 冲 突 所 需 的 最 长 时 间 等 于 双 程 的 传 播 时 延 2*t0 = 0.02ms ⑵ 主 机 甲 发 送 一 个 数 据 帧 的 时 间, 即 发 送 时 延 t1 = b/10Mbps = ms ; 主 机 乙 每 成 功 收 到 一 个 数 据 帧 后, 向 主 机 甲 发 送 确 认 帧, 确 认 帧 的 发 送 时 延 t2 = 64 8b/10Mbps = ms ; 主 机 甲 收 到 确 认 帧 后, 即 发 送 下 一 数 据 帧, 故 主 机 甲 的 发 送 周 期 T = 数 据 帧 发 送 时 延 t1 + 确 认 帧 发 送 时 延 t2 + 双 程 传 播 时 延 = t1 + t2 + 2*t0 = ms ; 于 是 主 机 甲 的 有 效 数 据 传 输 率 为 /T = 12000b/ ms 9.33 Mbps ( 以 太 网 有 效 数 据 1500 字 节, 即 以 太 网 帧 的 数 据 部 分 )