2013年全国硕士研究生入学统一考试

2013 年 全 国 硕 士 研 究 生 入 学 统 一 考 试 计 算 机 科 学 与 技 术 学 科 联 考 计 算 机 学 科 专 业 基 础 综 合 试 题 一 单 项 选 择 题 :1~40 小 题, 每 小 题 2 分, 共 80 分 下 列 每 题 给 出 的 四 个 选 项 中, 只 有 一 个 选 项 符 合 试 题 要 求 1. 已 知 两 个 长 度 分 别 为 m 和 n 的 升 序 链 表, 若 将 它 们 合 并 为 一 个 长 度 为 m+n 的 降 序 链 表, 则 最 坏 情 况 下 的 时 间 复 杂 度 是 A. On ( ) B. O( m n) C. O(min( m, n )) D. O(max( m, n )) 2. 一 个 栈 的 入 栈 序 列 为 1,2,3,,n, 其 出 栈 序 列 是 p1, p2, p3,, p n 若 p2 3, 则 p 3 可 能 取 值 的 个 数 是 A. n 3 B. n 2 C. n 1 D. 无 法 确 定 3. 若 将 关 键 字 1,2,3,4,5,6,7 依 次 插 入 到 初 始 为 空 的 平 衡 二 叉 树 T 中, 则 T 中 平 衡 因 子 为 0 的 分 支 结 点 的 个 数 是 A. 0 B. 1 C. 2 D. 3 4. 已 知 三 叉 树 T 中 6 个 叶 结 点 的 权 分 别 是 2,3,4,5,6,7,T 的 带 权 ( 外 部 ) 路 径 长 度 最 小 是 A. 27 B. 46 C. 54 D. 56 5. 若 X 是 后 序 线 索 二 叉 树 中 的 叶 结 点, 且 X 存 在 左 兄 弟 结 点 Y, 则 X 的 右 线 索 指 向 的 是 A. X 的 父 结 点 B. 以 Y 为 根 的 子 树 的 最 左 下 结 点 C. X 的 左 兄 弟 结 点 Y D. 以 Y 为 根 的 子 树 的 最 右 下 结 点 6. 在 任 意 一 棵 非 空 二 叉 排 序 树 T 1 中, 删 除 某 结 点 v 之 后 形 成 二 叉 排 序 树 T 2, 再 将 v 插 入 T 2 形 成 二 叉 排 序 树 T 3 下 列 关 于 T 1 与 T 3 的 叙 述 中, 正 确 的 是 I. 若 v 是 T 1 的 叶 结 点, 则 T 1 与 T 3 不 同 II. 若 v 是 T 1 的 叶 结 点, 则 T 1 与 T 3 相 同 III. 若 v 不 是 T 1 的 叶 结 点, 则 T 1 与 T 3 不 同 IV. 若 v 不 是 T 1 的 叶 结 点, 则 T 1 与 T 3 相 同 A. 仅 I III B. 仅 I IV C. 仅 II III D. 仅 II IV 7. 设 图 的 邻 接 矩 阵 A 如 下 所 示 各 顶 点 的 度 依 次 是 0 1 0 1 0 0 1 1 A 0 1 0 0 1 0 0 0 A. 1,2,1,2 B. 2,2,1,1 C. 3,4,2,3 D. 4,4,2,2 8. 若 对 如 下 无 向 图 进 行 遍 历, 则 下 列 选 项 中, 不. 是 广 度 优 先 遍 历 序 列 的 是 A. h,c,a,b,d,e,g,f B. e,a,f,g,b,h,c,d C. d,b,c,a,h,e,f,g D. a,b,c,d,h,e,f,g

a b e c d f g h 9. 下 列 AOE 网 表 示 一 项 包 含 8 个 活 动 的 工 程 通 过 同 时 加 快 若 干 活 动 的 进 度 可 以 缩 短 整 个 工 程 的 工 期 下 列 选 项 中, 加 快 其 进 度 就 可 以 缩 短 工 程 工 期 的 是 c=9 2 4 a=3 g=6 e=6 2 d=4 4 b=8 h=9 2 4 f=10 A.c 和 e B. d 和 e C. f 和 d D. f 和 h 10. 在 一 株 高 度 为 2 的 5 阶 B 树 中, 所 含 关 键 字 的 个 数 最 少 是 A.5 B. 7 C. 8 D. 14 11. 对 给 定 的 关 键 字 序 列 110,119,007,911,114,120,122 进 行 基 数 排 序, 则 第 2 趟 分 配 收 集 后 得 到 的 关 键 字 序 列 是 A. 007,110,119,114,911,120,122 B. 007,110,119,114,911,122,120 C. 007,110,911,114,119,120,122 D. 110,120,911,122,114,007,119 12. 某 计 算 机 主 频 为 1.2 GHz, 其 指 令 分 为 4 类, 它 们 在 基 准 程 序 中 所 占 比 例 及 CPI 如 下 表 所 示 指 令 类 型 所 占 比 例 CPI A 50% 2 B 20% 3 C 10% 4 D 20% 5 该 机 的 MIPS 数 是 A. 100 B. 200 C. 400 D. 600 13. 某 数 采 用 IEEE 754 单 精 度 浮 点 数 格 式 表 示 为 C640 0000H, 则 该 数 的 值 是

A. -1.5 2 13 B. -1.5 2 12 C. -0.5x 2 13 D. -0.5 2 12 14. 某 字 长 为 8 位 的 计 算 机 中, 已 知 整 型 变 量 x y 的 机 器 数 分 别 为 [x] 补 =1 1110100,[y] 补 =1 0110000 若 整 型 变 量 z=2*x+y/2, 则 z 的 机 器 数 为 A. 1 1000000 B. 0 0100100 C. 1 0101010 D. 溢 出 15. 用 海 明 码 对 长 度 为 8 位 的 数 据 进 行 检 / 纠 错 时, 若 能 纠 正 一 位 错 则 校 验 位 数 至 少 为 A. 2 B. 3 C. 4 D. 5 16. 某 计 算 机 主 存 地 址 空 间 大 小 为 256 MB, 按 字 节 编 址 虚 拟 地 址 空 间 大 小 为 4 GB, 采 用 页 式 存 储 管 理, 页 面 大 小 为 4 KB,TLB( 快 表 ) 采 用 全 相 联 映 射, 有 4 个 页 表 项, 内 容 如 下 表 所 示 有 效 位 标 记 页 框 号 0 FF180H 0002H 1 3FFF1H 0035H 0 02FF3H 0351H 1 03FFFH 0153H 则 对 虚 拟 地 址 03FF F180H 进 行 虚 实 地 址 变 换 的 结 果 是 A. 015 3180H B. 003 5180H C. TLB 缺 失 D. 缺 页 17. 假 设 变 址 寄 存 器 R 的 内 容 为 1000H, 指 令 中 的 形 式 地 址 为 2000 H; 地 址 1000H 中 的 内 容 为 2000H, 地 址 2000H 中 的 内 容 为 3000H, 地 址 3000 H 中 的 内 容 为 4000H, 则 变 址 寻 址 方 式 下 访 问 到 的 操 作 数 是 A. 1000H B. 2000H C. 3000H D. 4000 H 18. 某 CPU 主 频 为 1.03 GHz, 采 用 4 级 指 令 流 水 线, 每 个 流 水 段 的 执 行 需 要 1 个 时 钟 周 期 假 定 CPU 执 行 了 100 条 指 令, 在 其 执 行 过 程 中, 没 有 发 生 任 何 流 水 线 阻 塞, 此 时 流 水 线 的 吞 吐 率 为 A. 0.25 10 9 条 指 令 / 秒 B. 0.97 10 9 条 指 令 / 秒 C. 1.0 10 9 条 指 令 / 秒 D. 1.03 10 9 条 指 令 / 秒 19. 下 列 选 项 中, 用 于 设 备 和 设 备 控 制 器 (I/O 接 口 ) 之 间 互 连 的 接 口 标 准 是 A. PCI B. USB C. AGP D. PCI-Express 20. 下 列 选 项 中, 用 于 提 高 RAID 可 靠 性 的 措 施 有 I. 磁 盘 镜 像 II. 条 带 化 III. 奇 偶 校 验 IV. 增 加 Cache 机 制 A. 仅 I II B. 仅 I III C. 仅 I III 和 IV D. 仅 II III 和 IV 21. 某 磁 盘 的 转 速 为 10 000 转 / 分, 平 均 寻 道 时 间 是 6 ms, 磁 盘 传 输 速 率 是 20 MB/s, 磁 盘 控 制 器 延 迟 为 0.2 ms, 读 取 一 个 4 KB 的 扇 区 所 需 的 平 均 时 间 约 为 A. 9 ms B. 9.4 ms C. 12 ms D. 12.4 ms 22. 下 列 关 于 中 断 I/O 方 式 和 DMA 方 式 比 较 的 叙 述 中, 错 误.. 的 是 A. 中 断 I/O 方 式 请 求 的 是 CPU 处 理 时 间,DMA 方 式 请 求 的 是 总 线 使 用 权 B. 中 断 响 应 发 生 在 一 条 指 令 执 行 结 束 后,DMA 响 应 发 生 在 一 个 总 线 事 务 完 成 后 C. 中 断 I/O 方 式 下 数 据 传 送 通 过 软 件 完 成,DMA 方 式 下 数 据 传 送 由 硬 件 完 成

D. 中 断 I/O 方 式 适 用 于 所 有 外 部 设 备,DMA 方 式 仅 适 用 于 快 速 外 部 设 备 23. 用 户 在 删 除 某 文 件 的 过 程 中, 操 作 系 统 不 可 能 执 行 的 操 作 是 A. 删 除 此 文 件 所 在 的 目 录 B. 删 除 与 此 文 件 关 联 的 目 录 项 C. 删 除 与 此 文 件 对 应 的 文 件 控 制 块 D. 释 放 与 此 文 件 关 联 的 内 存 级 冲 区 24. 为 支 持 CD-ROM 中 视 频 文 件 的 快 速 随 机 播 放, 播 放 性 能 最 好 的 文 件 数 据 块 组 织 方 式 是 A. 连 续 结 构 B. 链 式 结 构 C. 直 接 索 引 结 构 D. 多 级 索 引 结 钩 25. 用 户 程 序 发 出 磁 盘 I/O 请 求 后, 系 统 的 处 理 流 程 是 : 用 户 程 序 系 统 调 用 处 理 程 序 设 备 骆 动 程 序 中 断 处 理 程 序 其 中, 计 算 数 据 所 在 磁 盘 的 柱 面 号 磁 头 号 扇 区 号 的 程 序 是 A. 用 户 程 序 B. 系 统 调 用 处 理 程 序 C. 设 备 驱 动 程 序 D. 中 断 处 理 程 序 26. 若 某 文 件 系 统 索 引 结 点 (inode) 中 有 直 接 地 址 项 和 间 接 地 址 项, 则 下 列 选 项 中, 与 单 个 文 件 长 度 无 关.. 的 因 素 是 A. 索 引 结 点 的 总 数 B. 间 接 地 址 索 引 的 级 数 C. 地 址 项 的 个 数 D. 文 件 块 大 小 27. 设 系 统 缓 冲 区 和 用 户 工 作 区 均 采 用 单 缓 冲, 从 外 设 读 入 1 个 数 据 块 到 系 统 缓 冲 区 的 时 间 为 100, 从 系 统 缓 冲 区 读 入 1 个 数 据 块 到 用 户 工 作 区 的 时 间 为 5, 对 用 户 工 作 区 中 的 1 个 数 据 块 进 行 分 析 的 时 间 为 90( 如 下 图 所 示 ) 进 程 从 外 设 读 入 并 分 析 2 个 数 据 块 的 最 短 时 间 是 90 用 户 工 作 区 5 系 统 缓 冲 区 100 外 设 A. 200 B. 295 C. 300 D.390 28. 下 列 选 项 中, 会 导 致 用 户 进 程 从 用 户 态 切 换 到 内 核 态 的 操 作 是 I. 整 数 除 以 零 II. sin( ) 函 数 调 用 III. read 系 统 调 用 A. 仅 I II B. 仅 I III C. 仅 II III D. I II 和 III 29. 计 算 机 开 机 后, 操 作 系 统 最 终 被 加 载 到 A. BIOS B. ROM C. EPROM D. RAM 30. 若 用 户 进 程 访 问 内 存 时 产 生 缺 页, 则 下 列 选 项 中, 操 作 系 统 可 能 执 行 的 操 作 是 I. 处 理 越 界 错 II. 置 换 页 III. 分 配 内 存 A. 仅 I II B. 仅 II III C. 仅 I III D. I II 和 III 31. 某 系 统 正 在 执 行 三 个 进 程 P1 P2 和 P3, 各 进 程 的 计 算 (CPU) 时 间 和 I/O 时 间 比 例 如 下 表 所 示

进 程 计 算 时 间 I/O 时 间 P1 90% 10% P2 50% 50% P3 15% 85% 为 提 高 系 统 资 源 利 用 率, 合 理 的 进 程 优 先 级 设 置 应 为 A. P1>P2>P3 B. P3>P2>P1 C. P2>P1=P3 D. P1>P2=P3 32. 下 列 关 于 银 行 家 算 法 的 叙 述 中, 正 确 的 是 A. 银 行 家 算 法 可 以 预 防 死 锁 B. 当 系 统 处 于 安 全 状 态 时, 系 统 中 一 定 无 死 锁 进 程 C. 当 系 统 处 于 不 安 全 状 态 时, 系 统 中 一 定 会 出 现 死 锁 进 程 D. 银 行 家 算 法 破 坏 了 死 锁 必 要 条 件 中 的 请 求 和 保 持 条 件 33. 在 OSI 参 考 摸 型 中, 下 列 功 能 需 由 应 用 层 的 相 邻 层 实 现 的 是 A. 对 话 管 理 B. 数 据 格 式 转 换 C. 路 由 选 择 D. 可 靠 数 据 传 输 34. 若 下 图 为 10 BaseT 网 卡 接 收 到 的 信 号 波 形, 则 该 网 卡 收 到 的 比 特 串 是 A. 0011 0110 B. 1010 1101 C. 0101 0010 D. 1100 0101 35. 主 机 甲 通 过 1 个 路 由 器 ( 存 储 转 发 方 式 ) 与 主 机 乙 互 联, 两 段 链 路 的 数 据 传 输 速 率 均 为 10 Mbps, 主 机 甲 分 别 采 用 报 文 交 换 和 分 组 大 小 为 10 kb 的 分 组 交 换 向 主 机 乙 发 送 1 个 大 小 为 8 Mb(1M=10 6 ) 的 报 文. 若 忽 略 链 路 传 播 延 迟 分 组 头 开 销 和 分 组 拆 装 时 间, 则 两 种 交 换 方 式 完 成 该 报 文 传 输 所 需 的 总 时 间 分 别 为 A. 800 ms 1 600 ms B. 801 ms 1 600 ms C. 1 600 ms 800 ms D. 1 600 ms 801 ms 36. 下 列 介 质 访 问 控 制 方 法 中, 可 能 发 生 冲 突 的 是 A. CDMA B. CSMA C. TDMA D. FDMA 37. HDLC 协 议 对 01111100 01111110 组 帧 后 对 应 的 比 特 串 为 A. 01111100 00111110 10 B. 01111100 01111101 01111110 C. 01111100 01111101 0 D. 01111100 01111110 01111101 38. 对 于 100Mbps 的 以 太 网 交 换 机, 当 输 出 端 口 无 排 队, 以 直 通 交 换 (cut-through switching) 方 式 转 发 一 个 以 太 网 帧 ( 不 包 括 前 导 码 ) 时, 引 入 的 转 发 延 迟 至 少 是 A. 0 μs B. 0.48 μs C. 5.12 μs D. 121.44 μs 39. 主 机 甲 与 主 机 乙 之 间 已 建 立 一 个 TCP 连 接, 双 方 持 续 有 数 据 传 输, 且 数 据 无 差 错 与 丢 失 若 甲 收 到 1 个 来 自 乙 的 TCP 段, 该 段 的 序 号 为 1913 确 认 序 号 为 2046 有 效 载 荷 为 100 字 节, 则 甲 立 即 发 送 给 乙 的 TCP 段 的 序 号 和 确 认 序 号 分 别 是 A. 2046 2012 B. 2046 2013 C. 2047 2012 D. 2047 2013

40. 下 列 关 于 SMTP 协 议 的 叙 述 中, 正 确 的 是 I. 只 支 持 传 输 7 比 特 ASC II 码 内 容 II. 支 持 在 邮 件 服 务 器 之 间 发 送 邮 件 III. 支 持 从 用 户 代 理 向 邮 件 服 务 器 发 送 邮 件 IV. 支 持 从 邮 件 服 务 器 向 用 户 代 理 发 送 邮 件 A. 仅 I II 和 III B. 仅 I II 和 IV C. 仅 I III 和 IV D. 仅 II III 和 IV 二 综 合 应 用 题 :41~47 小 题, 共 70 分 41. ( 13 分 ) 已 知 一 个 整 数 序 列 A ( a0, a1,, an 1), 其 中 0 ai n(0 i n) 若 存 在 a a a x 且 m n / 2(0 p n,1 k m), 则 称 x 为 A 的 主 元 素 例 如 A= p1 p2 pm k ( 0, 5,5,3,5,7,5,5 ), 侧 5 为 主 元 素 ; 又 如 A= ( 0,5,5,3,5,1,5,7 ), 则 A 中 没 有 主 元 素 假 设 A 中 的 n 个 元 素 保 存 在 一 个 一 维 数 组 中, 请 设 计 一 个 尽 可 能 高 效 的 算 法, 找 出 A 的 主 元 素 若 存 在 主 元 素, 则 输 出 该 元 素 ; 否 则 输 出 -1 要 求 : (1) 给 出 算 法 的 基 本 设 计 思 想 (2) 根 据 设 计 思 想, 采 用 C 或 C++ 或 Java 语 言 描 述 算 法, 关 键 之 处 给 出 注 释 (3) 说 明 你 所 设 计 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 42. (10 分 ) 设 包 含 4 个 数 据 元 素 的 集 合 S={ "do","for"," repeat"," while"}, 各 元 素 的 查 找 概 率 依 次 为 :p1=0.35,p2 = 0.15,p3=0. 15,p4=0.35 将 S 保 存 在 一 个 长 度 为 4 的 顺 序 表 中, 采 用 折 半 查 找 法, 查 找 成 功 时 的 平 均 查 找 长 度 为 2.2 请 回 答 : (1) 若 采 用 顺 序 存 储 结 构 保 存 S, 且 要 求 平 均 查 找 长 度 更 短, 则 元 素 应 如 何 排 列? 应 使 用 何 种 查 找 方 法? 查 找 成 功 时 的 平 均 查 找 长 度 是 多 少? (2) 若 采 用 链 式 存 储 结 构 保 存 S, 且 要 求 平 均 查 找 长 度 更 短, 则 元 素 应 如 何 排 列? 应 使 用 何 种 查 找 方 法? 查 找 成 功 时 的 平 均 查 找 长 度 是 多 少? 43.(9 分 ) 某 32 位 计 算 机,CPU 主 频 为 800MHz,Cache 命 中 时 的 CPI 为 4,Cache 块 大 小 为 32 字 节 ; 主 存 采 用 8 体 交 叉 存 储 方 式, 每 个 体 的 存 储 字 长 为 32 位 存 储 周 期 为 40 ns; 存 储 器 总 线 宽 度 为 32 位, 总 线 时 钟 频 率 为 200 MHz, 支 持 突 发 传 送 总 线 事 务 每 次 读 突 发 传 送 总 线 事 务 的 过 程 包 括 : 送 首 地 址 和 命 令 存 储 器 准 备 数 据 传 送 数 据 每 次 突 发 传 送 32 字 节, 传 送 地 址 或 32 位 数 据 均 需 要 一 个 总 线 时 钟 周 期 请 回 答 下 列 问 题, 要 求 给 出 理 由 或 计 算 过 程 (1)CPU 和 总 线 的 时 钟 周 期 各 为 多 少? 总 线 的 带 宽 ( 即 最 大 数 据 传 输 率 ) 为 多 少? (2)Cache 缺 失 时, 需 要 用 几 个 读 突 发 传 送 总 线 事 务 来 完 成 一 个 主 存 块 的 读 取? (3) 存 储 器 总 线 完 成 一 次 读 突 发 传 送 总 线 事 务 所 需 的 时 间 是 多 少? (4) 若 程 序 BP 执 行 过 程 中, 共 执 行 了 100 条 指 令, 平 均 每 条 指 令 需 进 行 1.2 次 访 存, Cache 缺 失 率 为 5%, 不 考 虑 替 换 等 开 销, 则 BP 的 CPU 执 行 时 间 是 多 少? 44.(14 分 ) 某 计 算 机 采 用 16 位 定 长 指 令 字 格 式, 其 CPU 中 有 一 个 标 志 寄 存 器, 其 中 包 含 进 位 / 借 位 标 志 CF 零 标 志 ZF 和 符 号 标 志 NF 假 定 为 该 机 设 计 了 条 件 转 移 指 令, 其 格 式 如

下 : 15 11 10 9 8 7 0 0 0 0 0 0 C Z N OFFSET 其 中,00000 为 操 作 码 OP;C Z 和 N 分 别 为 CF ZF 和 NF 的 对 应 检 测 位, 某 检 测 位 为 1 时 表 示 需 检 测 对 应 标 志, 需 检 测 的 标 志 位 中 只 要 有 一 个 为 1 就 转 移, 否 则 不 转 移, 例 如, 若 C=1,Z=0,N=1, 则 需 检 测 CF 和 NF 的 值, 当 CF=1 或 NF=1 时 发 生 转 移 ; OFFSET 是 相 对 偏 移 量, 用 补 码 表 示 转 移 执 行 时, 转 移 目 标 地 址 为 (PC)+2+2 OFFSET; 顺 序 执 行 时, 下 条 指 令 地 址 为 (PC)+2 请 回 答 下 列 问 题 (1) 该 计 算 机 存 储 器 按 字 节 编 址 还 是 按 字 编 址? 该 条 件 转 移 指 令 向 后 ( 反 向 ) 最 多 可 跳 转 多 少 条 指 令? (2) 某 条 件 转 移 指 令 的 地 址 为 200CH, 指 令 内 容 如 下 图 所 示, 若 该 指 令 执 行 时 CF=0, ZF=0,NF=1, 则 该 指 令 执 行 后 PC 的 值 是 多 少? 若 该 指 令 执 行 时 CF=1,ZF=0,NF=0, 则 该 指 令 执 行 后 PC 的 值 又 是 多 少? 请 给 出 计 算 过 程 15 11 10 9 8 7 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 (3) 实 现 无 符 号 数 比 较 小 于 等 于 时 转 移 功 能 的 指 令 中,C Z 和 N 应 各 是 什 么? (4) 以 下 是 该 指 令 对 应 的 数 据 通 路 示 意 图, 要 求 给 出 图 中 部 件 1~3 的 名 称 或 功 能 说 明 标 志 寄 存 器 1 OP C Z N OFFSET 2 PC 符 号 扩 展 器 加 法 器 2 3 多 路 选 择 器 45.(7 分 ) 某 博 物 馆 最 多 可 容 纳 500 人 同 时 参 观, 有 一 个 出 入 口, 该 出 入 口 一 次 仅 允 许 一 个 人 通 过 参 观 者 的 活 动 描 述 如 下 : cobegin 参 观 者 进 程 i:

{ 进 门 ; 参 观 ; 出 门 ; } coend 请 添 加 必 要 的 信 号 量 和 P V( 或 wait() signal( )) 操 作, 以 实 现 上 述 过 程 中 的 互 斥 与 同 步 要 求 写 出 完 整 的 过 程, 说 明 信 号 量 的 含 义 并 赋 初 值 46.(8 分 ) 某 计 算 机 主 存 按 字 节 编 址, 逻 辑 地 址 和 物 理 地 址 都 是 32 位, 页 表 项 大 小 为 4 字 节 请 回 答 下 列 问 题 (1) 若 使 用 一 级 页 表 的 分 页 存 储 管 理 方 式, 逻 辑 地 址 结 构 为 : 页 号 (20 位 ) 页 内 偏 移 量 (12 位 ) 则 页 的 大 小 是 多 少 字 节? 页 表 最 大 占 用 多 少 字 节? (2) 若 使 用 二 级 页 表 的 分 页 存 储 管 理 方 式, 逻 辑 地 址 结 构 为 : 页 目 录 号 (10 位 ) 页 表 索 引 (10 位 ) 页 内 偏 移 量 (12 位 ) 设 逻 辑 地 址 为 LA, 请 分 别 给 出 其 对 应 的 页 目 录 号 和 页 表 索 引 的 表 达 式 (3) 采 用 (1) 中 的 分 页 存 储 管 理 方 式, 一 个 代 码 段 起 始 逻 辑 地 址 为 0000 8000H, 其 长 度 为 8 KB, 被 装 载 到 从 物 理 地 址 0090 0000H 开 始 的 连 续 主 存 空 间 中 页 表 从 主 存 0020 0000H 开 始 的 物 理 地 址 处 连 续 存 放, 如 下 图 所 示 ( 地 址 大 小 自 下 向 上 递 增 ) 请 计 算 出 该 代 码 段 对 应 的 两 个 页 表 项 的 物 理 地 址 这 两 个 页 表 项 中 的 页 框 号 以 及 代 码 页 面 2 的 起 始 物 理 地 址 页 表 物 理 地 址 3 代 码 页 面 2 物 理 地 址 2 物 理 地 址 1 页 框 号 2 页 框 号 1 0090 0000H 代 码 页 面 1 0020 0000H 47.(9 分 ) 假 设 Internet 的 两 个 自 治 系 统 构 成 的 网 络 如 题 47 图 所 示, 自 治 系 统 ASI 由 路 由 器 R1 连 接 两 个 子 网 构 成 ; 自 治 系 统 AS2 由 路 由 器 R2 R3 互 联 并 连 接 3 个 子 网 构 成 各 子

网 地 址 R2 的 接 口 名 R1 与 R3 的 部 分 接 口 IP 地 址 如 题 47 图 所 示 AS1 R1 153.14.5.0/25 153.14.5.128/25 153.14.3.2 R2 SO EO 194.17.20.128/25 S1 153.14.3.2 AS2 R3 194.17.24.2 194.17.20.0/25 194.17.21.0/24 题 47 图 网 络 拓 扑 结 构 请 回 答 下 列 问 题 (1) 假 设 路 由 表 结 构 如 下 表 所 示 请 利 用 路 由 聚 合 技 术, 给 出 R2 的 路 由 表, 要 求 包 括 到 达 题 47 图 中 所 有 子 网 的 路 由, 且 路 由 表 中 的 路 由 项 尽 可 能 少 目 的 网 络 下 一 跳 接 口 (2) 若 R2 收 到 一 个 目 的 IP 地 址 为 194.17.20.200 的 IP 分 组,R2 会 通 过 哪 个 接 口 转 发 该 IP 分 组? (3)R1 与 R2 之 间 利 用 哪 个 路 由 协 议 交 换 路 由 信 息? 该 路 由 协 议 的 报 文 被 封 装 到 哪 个 协 议 的 分 组 中 进 行 传 输?

计 算 机 学 科 专 业 基 础 综 合 试 题 参 考 答 案 及 解 析 (2013 年 ) 一 单 项 选 择 题 1. D 2. C 3. D 解 析 :m n 是 两 个 升 序 链 表, 长 度 分 别 为 m 和 n 在 合 并 过 程 中, 最 坏 的 情 况 是 两 个 链 表 中 的 元 素 依 次 进 行 比 较, 比 较 的 次 数 最 少 是 m 和 n 中 的 最 小 值 解 析 : 除 了 3 本 身 以 外, 其 他 的 值 均 可 以 取 到, 因 此 可 能 取 值 的 个 数 为 n 1 解 析 : 利 用 7 个 关 键 字 构 建 平 衡 二 叉 树 T, 平 衡 因 子 为 0 的 分 支 结 点 个 数 为 3, 构 建 的 平 衡 二 叉 树 如 下 图 所 示 5 2 6 1 4 7 3 4. B 5. A 6. C 7. C 解 析 : 利 用 三 叉 树 的 6 个 叶 子 结 点 的 权 构 建 最 小 带 权 生 成 树, 最 小 的 带 权 路 径 长 度 为 (2 3) 3 (4 5) 2 (6 7) 1 46 8. D 9. C 解 析 : 根 据 后 续 线 索 二 叉 树 的 定 义,X 结 点 为 叶 子 结 点 且 有 左 兄 弟, 那 么 这 个 结 点 为 右 孩 子 结 点, 利 用 后 续 遍 历 的 方 式 可 知 X 结 点 的 后 继 是 其 父 结 点, 即 其 右 线 索 指 向 的 是 父 结 点 解 析 : 在 一 棵 二 叉 排 序 树 中 删 除 一 个 结 点 后 再 将 此 结 点 插 入 到 二 叉 排 序 树 中, 如 果 删 除 的 结 点 是 叶 子 结 点, 那 么 在 插 入 结 点 后, 后 来 的 二 叉 排 序 树 与 删 除 结 点 之 前 相 同 如 果 删 除 的 结 点 不 是 叶 子 结 点, 那 么 再 插 入 这 个 结 点 后, 后 来 的 二 叉 树 可 能 发 生 变 化, 不 完 全 相 同 解 析 : 各 顶 点 的 度 是 矩 阵 中 此 结 点 对 应 的 横 行 和 纵 列 非 零 元 素 之 和 解 析 :D 选 项 是 深 度 优 先 遍 历 不 是 广 度 优 先 遍 历 的 顺 序

解 析 : 根 据 AOE 网 的 定 义 可 知, 关 键 路 径 上 的 活 动 时 间 同 时 减 少, 可 以 缩 短 工 期 10. A 11. C 12. C 13. A 解 析 : 一 棵 高 度 为 2 的 5 阶 B 树, 根 结 点 只 有 到 达 5 个 关 键 字 的 时 候 才 能 产 生 分 裂, 成 为 高 度 为 2 的 B 树 解 析 : 基 数 排 序 的 第 1 趟 排 序 是 按 照 个 位 数 字 来 排 序 的, 第 2 趟 排 序 是 按 然 十 位 数 字 的 大 小 进 行 排 序 的, 答 案 是 C 选 项 解 析 : 基 准 程 序 的 CPI 2 0.5 3 0.2 4 0.1 5 0.2 3, 计 算 机 的 主 频 为 1.2GHa, 为 1 200MHz, 该 机 器 的 是 MIPS 为 1 200/3=400 解 析 :IEEE 754 单 精 度 浮 点 数 格 式 为 C640 0000H, 二 进 制 格 式 为 1100 0110 0100 0000 0000 0000 0000 0000, 转 换 为 标 准 的 格 式 为 : S 阶 码 尾 数 1 1000 1100 100 0000 0000 0000 0000 0000 14. A 15. C 16. A 17. D 13 因 此, 浮 点 数 的 值 为 1.5 2 解 析 : 将 x 左 移 一 位,y 右 移 一 位, 两 个 数 的 补 码 相 加 的 机 器 数 为 1 1000000, 答 案 选 择 A k 解 析 : 设 校 验 位 的 位 数 为 k, 数 据 位 的 位 数 为 n, 应 满 足 下 述 关 系 : 2 n k 1 n 8, 当 k 4 时, 2 4 ( 16) 8 4 1( 13) 符 合 要 求, 校 验 位 至 少 是 4 位 解 析 : 虚 拟 地 址 为 03FF F180H, 其 中 页 号 为 03FFFH, 页 内 地 址 为 180H, 根 据 题 目 中 给 出 的 页 表 项 可 知 页 标 记 为 03FFFH 所 对 应 的 页 框 号 为 0153H, 页 框 号 与 页 内 地 址 之 和 即 为 物 理 地 址 015 3180 H 解 析 : 根 据 变 址 寻 址 的 主 要 方 法, 变 址 寄 存 器 的 内 容 与 形 式 地 址 的 内 容 相 加 之 后, 得 到 操 作 数 的 实 际 地 址, 根 据 实 际 地 址 访 问 内 存, 获 取 操 作 数 4000H 变 址 寄 存 器 1000 H 形 式 地 址 2000 H 地 址 内 容 1000 H 2000 H + 2000 H 3000 H 3000 H 4000 H 18. C

19. B 20. B 21. B 22. D 23. A 24. A 25. C 26. A 27. C 28. B 29. D 解 析 : 采 用 4 级 流 水 执 行 100 条 指 令, 在 执 行 过 程 中 共 用 4 (100 1) 103 个 时 钟 周 期 CPU 的 主 频 是 1.03 GHz, 也 就 是 说 每 秒 钟 有 1.03 G 个 时 钟 周 期 流 水 线 的 吞 吐 率 为 9 1.03G 100/103 1.0 10条 指 令 / 秒 解 析 : 设 备 和 设 备 控 制 器 之 间 的 接 口 是 USB 接 口, 其 余 选 项 不 符 合, 答 案 为 B 解 析 : 能 够 提 高 RAID 可 靠 性 的 措 施 主 要 是 对 磁 盘 进 行 镜 像 处 理 和 进 行 奇 偶 校 验 其 余 选 项 不 符 合 条 件 解 析 : 磁 盘 转 速 是 10 000 转 / 分 钟, 平 均 转 一 转 的 时 间 是 6 ms, 因 此 平 均 查 询 扇 区 的 时 间 是 3 ms, 平 均 寻 道 时 间 是 6 ms, 读 取 4 KB 扇 区 信 息 的 时 间 为 0.2 ms, 信 息 延 迟 的 时 间 为 0.2 ms, 总 时 间 为 3+6+0.2+0.2=9.4 ms 解 析 : 中 断 处 理 方 式 : 在 I/O 设 备 输 入 每 个 数 据 的 过 程 中, 由 于 无 需 CPU 干 预, 因 而 可 使 CPU 与 I/O 设 备 并 行 工 作 仅 当 输 完 一 个 数 据 时, 才 需 CPU 花 费 极 短 的 时 间 去 做 些 中 断 处 理 因 此 中 断 申 请 使 用 的 是 CPU 处 理 时 间, 发 生 的 时 间 是 在 一 条 指 令 执 行 结 束 之 后, 数 据 是 在 软 件 的 控 制 下 完 成 传 送 而 DMA 方 式 与 之 不 同 DMA 方 式 : 数 据 传 输 的 基 本 单 位 是 数 据 块, 即 在 CPU 与 I/O 设 备 之 间, 每 次 传 送 至 少 一 个 数 据 块 ;DMA 方 式 每 次 申 请 的 是 总 线 的 使 用 权, 所 传 送 的 数 据 是 从 设 备 直 接 送 入 内 存 的, 或 者 相 反 ; 仅 在 传 送 一 个 或 多 个 数 据 块 的 开 始 和 结 束 时, 才 需 CPU 干 预, 整 块 数 据 的 传 送 是 在 控 制 器 的 控 制 下 完 成 的 答 案 D 的 说 法 不 正 确 解 析 : 删 除 文 件 不 需 要 删 除 文 件 所 在 的 目 录, 而 文 件 的 关 联 目 录 项 和 文 件 控 制 块 需 要 随 着 文 件 一 同 删 除, 同 时 释 放 文 件 的 关 联 缓 冲 区 解 析 : 为 了 实 现 快 速 随 机 播 放, 要 保 证 最 短 的 查 询 时 间, 即 不 能 选 取 链 表 和 索 引 结 构, 因 此 连 续 结 构 最 优 解 析 : 计 算 磁 盘 号 磁 头 号 和 扇 区 号 的 工 作 是 由 设 备 驱 动 程 序 完 成 的, 答 案 选 C 解 析 : 四 个 选 项 中, 只 有 A 选 项 是 与 单 个 文 件 长 度 无 关 的 解 析 : 数 据 块 1 从 外 设 到 用 户 工 作 区 的 总 时 间 为 105, 在 这 段 时 间 中, 数 据 块 2 没 有 进 行 操 作 在 数 据 块 1 进 行 分 析 处 理 时, 数 据 块 2 从 外 设 到 用 户 工 作 区 的 总 时 间 为 105, 这 段 时 间 是 并 行 的 再 加 上 数 据 块 2 进 行 处 理 的 时 间 90, 总 共 是 300, 答 案 为 C 解 析 : 需 要 在 系 统 内 核 态 执 行 的 操 作 是 整 数 除 零 操 作 和 read 系 统 调 用 函 数, 答 案 选 B

解 析 : 系 统 开 机 后, 操 作 系 统 的 程 序 会 被 自 动 加 载 到 内 存 中 的 系 统 区, 这 段 区 城 是 RAM, 答 案 选 D 30. B 解 析 : 用 户 进 程 访 问 内 存 时 缺 页 会 发 生 缺 页 中 断 发 生 缺 页 中 断, 系 统 地 执 行 的 操 作 可 能 是 置 换 页 面 或 分 配 内 存 系 统 内 没 有 越 界 的 错 误, 不 会 进 行 越 界 出 错 处 理 31. B 解 析 : 为 了 合 理 地 设 置 进 程 优 先 级, 应 该 将 进 程 的 CPU 利 用 时 间 和 I/O 时 间 做 综 合 考 虑, 答 案 选 B 32. B 解 析 : 银 行 家 算 法 是 避 免 死 锁 的 方 法 利 用 银 行 家 算 法, 系 统 处 于 安 全 状 态 时 没 有 死 锁 进 程, 答 案 选 B 33. B 解 析 :OSI 参 考 模 型 中, 应 用 层 的 相 邻 层 是 表 示 层 表 示 层 是 OSI 七 层 协 议 的 第 六 层 表 示 层 的 目 的 是 表 示 出 用 户 看 得 懂 的 数 据 格 式, 实 现 与 数 据 表 示 有 关 的 功 能 主 要 完 成 数 据 字 符 集 的 转 换 数 据 格 式 化 和 文 本 压 缩 数 据 加 密 解 密 等 工 作 因 此 答 案 选 B 34. A 解 析 : 根 据 信 号 编 码 的 基 本 规 则 可 知, 网 卡 收 到 的 比 特 串 为 0011 0110, 答 案 选 A 35. D 解 析 : 不 进 行 分 组 时, 发 送 一 个 报 文 的 时 延 是 8 Mb/10 Mb/s=800 ms, 在 接 收 端 接 收 此 报 文 件 的 时 延 也 是 800 ms, 共 计 1 600 ms 进 行 分 组 后, 发 送 一 个 报 文 的 时 延 是 10 kb/10mb/s=1 ms, 接 收 一 个 报 文 的 时 延 也 是 1 ms, 但 是 在 发 送 第 二 个 报 文 时, 第 一 个 报 文 已 经 开 始 接 收 共 计 有 800 个 分 组, 总 时 间 为 801 ms 36. B 解 析 : 介 质 访 向 控 制 协 议 中 能 够 发 生 冲 突 的 是 CSMA 协 议, 答 案 为 B 37. A 解 析 :HDLC 协 议 对 比 特 串 进 行 组 帧 时,HDLC 数 据 帧 以 位 模 式 0111 1110 标 识 每 一 个 帧 的 开 始 和 结 束, 因 此 在 帧 数 据 中 凡 是 出 现 了 5 个 连 续 的 位 1 的 时 候, 就 会 在 输 出 的 位 流 中 填 充 一 个 0 所 以 答 案 为 A 38. B 解 析 : 直 通 交 换 方 式 是 指 以 太 网 交 换 机 可 以 在 各 端 口 间 交 换 数 据 它 在 输 入 端 口 检 测 到 一 个 数 据 包 时, 检 查 该 包 的 包 头, 获 取 包 的 目 的 地 址, 启 动 内 部 的 动 态 查 找 表 转 换 成 相 应 的 输 出 端 口, 在 输 入 与 输 出 交 叉 处 接 通, 把 数 据 包 直 通 到 相 应 的 端 口, 实 现 交 换 功 能 通 常 情 况 下, 直 通 交 换 方 式 只 检 查 数 据 包 的 包 头 即 前 14 个 字 节, 由 于 不 需 要 考 虑 前 导 码, 只 需 要 检 测 目 的 地 址 的 6 B, 所 以 最 短 的 传 输 延 迟 是 0.48μs 39. B 解 析 : 若 甲 收 到 1 个 来 自 乙 的 TCP 段, 该 段 的 序 号 seq=1913 确 认 序 号 ack = 2046 有 效 载 荷 为 100 字 节, 则 甲 立 即 发 送 给 乙 的 TCP 段 的 序 号 seq1=ack=2046 和 确 认 序 号 ack1=seq+100=2013, 答 案 为 B

40. A 解 析 : 根 据 下 图 可 知,SMTP 协 议 支 持 在 邮 件 服 务 器 之 间 发 送 邮 件, 也 支 持 从 用 户 代 理 向 邮 件 服 务 器 发 送 信 息 SMTP 协 议 只 支 持 传 输 7 比 特 的 ASC II 码 内 容 发 件 人 用 户 代 理 SMTP 发 送 邮 件 SMTP 发 送 方 邮 件 服 务 器 SMTP 接 收 方 邮 件 服 务 器 POP3 读 取 邮 件 POP3 收 件 人 用 户 代 理 POP3 客 户 TCP 连 接 服 务 器 服 务 器 TCP 连 接 客 户 SMTP 客 户 发 送 邮 件 SMTP TCP 连 接 SMTP 服 务 器 二 综 合 应 用 题 41. 答 案 要 点 (1) 给 出 算 法 的 基 本 设 计 思 想 :( 4 分 ) 算 法 的 策 略 是 从 前 向 后 扫 描 数 组 元 素, 标 记 出 一 个 可 能 成 为 主 元 素 的 元 素 Num 然 后 重 新 计 数, 确 认 Num 是 否 是 主 元 素 算 法 可 分 为 以 下 两 步 : 1 选 取 候 选 的 主 元 素 : 依 次 扫 描 所 给 数 组 中 的 每 个 整 数, 将 第 一 个 遇 到 的 整 数 Num 保 存 到 c 中, 记 录 Num 的 出 现 次 数 为 1; 若 遇 到 的 下 一 个 整 数 仍 等 于 Num, 则 计 数 加 1, 否 则 计 数 减 1; 当 计 数 减 到 0 时, 将 遇 到 的 下 一 个 整 数 保 存 到 c 中, 计 数 重 新 记 为 1, 开 始 新 一 轮 计 数, 即 从 当 前 位 置 开 始 重 复 上 述 过 程, 直 到 扫 描 完 全 部 数 组 元 素 2 判 断 c 中 元 素 是 否 是 真 正 的 主 元 素 : 再 次 扫 描 该 数 组, 统 计 c 中 元 素 出 现 的 次 数, 若 大 于 n/2, 则 为 主 元 素 ; 否 则, 序 列 中 不 存 在 主 元 素 (2) 算 法 实 现 :( 7 分 ) int Majority ( int A[ ], int n ) { int i, c, count=1; / / c 用 来 保 存 候 选 主 元 素,count 用 来 计 数 c = A[0]; / / 设 置 A[0] 为 候 选 主 元 素 for ( i=1; i<n; i++ ) / / 查 找 候 选 主 元 素 if ( A[i] = = c ) count++; / / 对 A 中 的 候 选 主 元 素 计 数 else if ( count > 0) / / 处 理 不 是 候 选 主 元 素 的 情 况 count--; else / / 更 换 候 选 主 元 素, 重 新 计 数 { c = A[i];

count = 1; } if ( count>0 ) for ( i=count=0; i<n; i++ ) / / 统 计 候 选 主 元 素 的 实 际 出 现 次 数 if ( A[i] = = c ) count++; if ( count> n/2 ) return c; / / 确 认 候 选 主 元 素 else return -1; / / 不 存 在 主 元 素 } ( 1) ( 2) 的 评 分 说 明 1 若 考 生 设 计 的 算 法 满 足 题 目 的 功 能 要 求 且 正 确, 则 (1) (2) 根 据 所 实 现 算 法 的 效 率 给 分, 细 则 见 下 表 : 时 间 空 间 (1) (2) 复 杂 度 复 杂 度 得 分 得 分 说 明 O ( n ) O ( 1 ) 4 7 O ( n ) O ( n ) 4 6 如 采 用 计 数 排 序 思 想, 见 表 后 Majority1 程 序 O ( nlog 2 n ) 其 他 3 6 如 采 用 其 他 排 序 的 思 想 O ( n 2 ) 其 他 3 5 其 他 方 法 int Majority1 ( int A[ ], int n) / / 采 用 计 数 排 序 思 想, 时 间 :O ( n ), 空 间 :O ( n ) { int k, * p, max; p = ( int * ) malloc ( sizeof ( int ) * n ); / / 申 请 辅 助 计 数 数 组 for ( k=0; k < n ; k++ ) p [k] =0; / / 计 数 数 组 清 0 max = 0 ; for ( k=0; k<n; k++ ) { p[ A[k] ] ++; / / 计 数 器 +1 if (p[a[k] ] >p [ max ] ) max = A[k]; / / 记 录 出 现 次 数 最 多 的 元 素 } if ( p[ max ] > n/2 ) return max; else return -1; } 2 若 在 算 法 的 基 本 设 计 思 想 描 述 中 因 文 字 表 达 没 有 非 常 清 晰 反 映 出 算 法 思 路, 但 在 算 法 实 现 中 能 够 清 晰 看 出 算 法 思 想 且 正 确 的, 可 参 照 1 的 标 准 给 分 3 若 算 法 的 基 本 设 计 思 想 描 述 或 算 法 实 现 中 部 分 正 确, 可 参 照 1 中 各 种 情 况 的 相 应 给 分 标 准 酌 情 给 分 4 参 考 答 案 中 只 给 出 了 使 用 C 语 言 的 版 本, 使 用 C++ 或 Java 语 言 的 答 案 视 同 使 用 C 语 言

(3) 说 明 算 法 复 杂 性 :( 2 分 ) 参 考 答 案 中 实 现 的 程 序 的 时 间 复 杂 度 为 O(n), 空 间 复 杂 度 为 O(1) 评 分 说 明 若 考 生 所 估 计 的 时 间 复 杂 度 与 空 间 复 杂 度 与 考 生 所 实 现 的 算 法 一 致, 可 各 给 1 分 42. 答 案 要 点 (1) 采 用 顺 序 存 储 结 构, 数 据 元 素 按 其 查 找 概 率 降 序 排 列 (2 分 ) 采 用 顺 序 查 找 方 法 (1 分 ) 查 找 成 功 时 的 平 均 查 找 长 度 = 0.35 1+0.35 2+0.15 3+0.15 4=2.1 ( 2 分 ) (2) 答 案 一 采 用 链 式 存 储 结 构, 数 据 元 素 按 其 查 找 概 率 降 序 排 列, 构 成 单 链 表 (2 分 ) 采 用 顺 序 查 找 方 法 (1 分 ) 查 找 成 功 时 的 平 均 查 找 长 度 =0.35 1+0.35 2+0.15 3+0.15 4=2.1 (2 分 ) 答 案 二 采 用 二 叉 链 表 存 储 结 构, 构 造 二 叉 排 序 树, 元 素 存 储 方 式 见 下 图 (2 分 ) for repeat do while 或 do while repeat for 二 叉 排 序 树 1 二 叉 排 序 树 2 采 用 二 叉 排 序 树 的 查 找 方 法 (1 分 ) 查 找 成 功 时 的 平 均 查 找 长 度 =0.15 1+0.35 2+0.35 2+0.15 3=2.0 (2 分 ) ( 1) ( 2) 的 评 分 说 明 1 若 考 生 以 实 际 元 素 表 示 降 序 排 列, 同 样 给 分 2 若 考 生 正 确 求 出 与 其 查 找 方 法 对 应 的 查 找 成 功 时 的 平 均 查 找 长 度, 给 2 分 ; 若 计 算 过 程 正 确, 但 结 果 错 误, 给 1 分 3 若 考 生 给 出 其 他 更 高 效 的 查 找 方 法 且 正 确, 可 参 照 评 分 标 准 给 分 43. 答 案 要 点 (1)CPU 的 时 钟 周 期 为 :1/800 MHz = 1.25 ns ( 1 分 ) 总 线 的 时 钟 周 期 为 :1/200 MHz = 5 ns ( 1 分 ) 总 线 带 宽 为 :4 B 200 MHz = 800 MB/s 或 4 B/5 ns = 800 MB/s ( 1 分 ) (2)Cache 块 大 小 是 32 B, 因 此 Cache 缺 失 时 需 要 一 个 读 突 发 传 送 总 线 事 务 读 取 一 个 主 存 块 (1 分 ) (3) 一 次 读 突 发 传 送 总 线 事 务 包 括 一 次 地 址 传 送 和 32 B 数 据 传 送 : 用 1 个 总 线 时 钟 周 期

传 输 地 址 ; 每 隔 40 ns/8 = 5 ns 启 动 一 个 体 工 作 ( 各 进 行 1 次 存 取 ), 第 一 个 体 读 数 据 花 费 40 ns, 之 后 数 据 存 取 与 数 据 传 输 重 叠 ; 用 8 个 总 线 时 钟 周 期 传 输 数 据 读 突 发 传 送 总 线 事 务 时 间 :5 ns + 40 ns + 8 5 ns = 85 ns ( 2 分 ) (4)BP 的 CPU 执 行 时 间 包 括 Cache 命 中 时 的 指 令 执 行 时 间 和 Cache 缺 失 时 带 来 的 额 外 开 销 命 中 时 的 指 令 执 行 时 间 :100 4 1.25 ns = 500 ns ( 1 分 ) 指 令 执 行 过 程 中 Cache 缺 失 时 的 额 外 开 销 :1.2 100 5% 85 ns = 510 ns BP 的 CPU 执 行 时 间 : 500 ns+510 ns=1 010 ns ( 2 分 ) 评 分 说 明 1 执 行 时 间 采 用 如 下 公 式 计 算 时, 可 酌 情 给 分 执 行 时 间 = 指 令 条 数 CPI 时 钟 周 期 命 中 率 + 访 存 次 数 缺 失 率 缺 失 损 失 2 计 算 公 式 正 确 但 运 算 结 果 不 正 确 时, 可 酌 情 给 分 44. 答 案 要 点 (1) 因 为 指 令 长 度 为 16 位, 且 下 条 指 令 地 址 为 (PC)+2, 故 编 址 单 位 是 字 节 (1 分 ) 偏 移 OFFSET 为 8 位 补 码, 范 围 为 -128~127, 故 相 对 于 当 前 条 件 转 移 指 令, 向 后 最 多 可 跳 转 127 条 指 令 (2 分 ) 评 分 说 明 若 正 确 给 出 OFFSET 的 取 值 范 围, 则 酌 情 给 分 (2) 指 令 中 C = 0,Z = 1,N = 1, 故 应 根 据 ZF 和 NF 的 值 来 判 断 是 否 转 移 当 CF=0, ZF=0,NF=1 时, 需 转 移 (1 分 ) 已 知 指 令 中 偏 移 量 为 1110 0011B=E3H, 符 号 扩 展 后 为 FFE3 H, 左 移 一 位 ( 乘 2) 后 为 FFC6 H, 故 PC 的 值 ( 即 转 移 目 标 地 址 ) 为 200CH+2+FFC6H=1FD4H (2 分 ) 当 CF = 1,ZF = 0,NF = 0 时 不 转 移 (1 分 )PC 的 值 为 :200CH+2=200EH (1 分 ) (3) 指 令 中 的 C Z 和 N 应 分 别 设 置 为 C=Z=1,N=0 (3 分 ) (4) 部 件 1: 指 令 寄 存 器 ( 用 于 存 放 当 前 指 令 ); 部 件 2: 移 位 寄 存 器 ( 用 于 左 移 一 位 ); 部 件 3: 加 法 器 ( 地 址 相 加 ) (3 分 ) 评 分 说 明 合 理 给 出 部 件 名 称 或 功 能 说 明 均 给 分 45. 答 案 要 点 定 义 两 个 信 号 量 Semaphore empty = 500; / / 博 物 馆 可 以 容 纳 的 最 多 人 数 (2 分 ) Semaphore mutex = 1; / / 用 于 出 入 口 资 源 的 控 制 (2 分 ) 参 观 者 进 程 i; { P ( empty ); P ( mutex ); 进 门 ; V( mutex ); 参 观 ; P ( mutex );

出 门 ; V( mutex ); V( empty ); } coend(3 分 ) 评 分 说 明 1 信 号 量 初 值 给 1 分, 说 明 含 义 给 1 分, 两 个 信 号 量 的 初 值 和 含 义 共 4 分 2 对 mutex 的 P V 操 作 正 确 给 2 分 3 对 empty 的 P V 操 作 正 确 给 1 分 4 其 他 答 案, 参 照 1~3 的 标 准 给 分 46. 答 案 要 点 (1) 因 为 页 内 偏 移 量 是 12 位, 所 以 页 大 小 为 4 KB,( 1 分 ) 页 表 项 数 为 2 32 /4K=2 20, 该 一 级 页 表 最 大 为 2 20 4 B=4 MB (2 分 ) (2) 页 目 录 号 可 表 示 为 :( ( ( unsigned int ) ( LA ) ) >> 22 ) & 0x3FF (1 分 ) 页 表 索 引 可 表 示 为 :( ( ( unsigned int ) ( LA ) ) >> 12 ) & 0x3FF (1 分 ) 评 分 说 明 1 页 目 录 号 也 可 以 写 成 ( ( unsigned int ) ( LA ) ) >> 22; 如 果 两 个 表 达 式 没 有 对 LA 进 行 类 型 转 换, 同 样 给 分 2 如 果 用 除 法 和 其 他 开 销 很 大 的 运 算 方 法, 但 对 基 本 原 理 是 理 解 的, 同 样 给 分 3 参 考 答 案 给 出 的 是 C 语 言 的 描 述, 用 其 他 语 言 ( 包 括 自 然 语 言 ) 正 确 地 表 述 了, 同 样 给 分 (3) 代 码 页 面 1 的 逻 辑 地 址 为 0000 8000H, 表 明 其 位 于 第 8 个 页 处, 对 应 页 表 中 的 第 8 个 页 表 项, 所 以 第 8 个 页 表 项 的 物 理 地 址 = 页 表 起 始 地 址 +8 页 表 项 的 字 节 数 = 0020 0000H+8 4 = 0020 0020H 由 此 可 得 如 下 图 所 示 的 答 案 (3 分 ) 页 表 0020 0024H 00901H 0090 1000H 代 码 页 面 2 0020 0020H 00900H 0090 0000H 代 码 页 面 1 评 分 说 明 共 5 个 答 数 物 理 地 址 1 和 物 理 地 址 2 共 1 分 ; 页 框 号 1 和 页 框 号 2 共 1 分 ; 物 理 地 址 3 给 1 分 47. 答 案 要 点

(1)( 6 分 ) 在 AS1 中, 子 网 153.14.5.0/25 和 子 网 153.14.5.128/25 可 以 聚 合 为 子 网 153.14.5.0/24; 在 AS2 中, 子 网 194.17.20.0/25 和 子 网 194.17.21.0/24 可 以 聚 合 为 子 网 194.17.20.0/23, 但 缺 少 194.17.20.128/25; 子 网 194.17.20.128/25 单 独 连 接 到 R2 的 接 口 E0 于 是 可 以 得 到 R2 的 路 由 表 如 下 : 目 的 网 络 下 一 跳 接 口 153.14.5.0/24 153.14.3.2 S0 194.17.20.0/23 194.17.24.2 S1 194.17.20.128/25 E0 评 分 说 明 1 每 正 确 解 答 1 个 路 由 项, 给 2 分, 共 6 分, 每 条 路 由 项 正 确 解 答 目 的 网 络 IP 地 址 但 无 前 缀 长 度, 给 0.5 分, 正 确 解 答 前 缀 长 度 给 0.5 分, 正 确 解 答 下 一 跳 IP 地 址 给 0.5 分, 正 确 解 答 接 口 给 0.5 分 2 路 由 项 解 答 部 分 正 确 或 路 由 项 多 于 3 条, 可 酌 情 给 分 (2) 该 IP 分 组 的 目 的 IP 地 址 194.17.20.200 与 路 由 表 中 194.17.20.0/23 和 194.17.20.128/25 两 个 路 由 表 项 均 匹 配, 根 据 最 长 匹 配 原 则,R2 将 通 过 E0 接 口 转 发 该 1P 分 组 (1 分 ) (3)R1 与 R2 之 间 利 用 BGP4( 或 BGP) 交 换 路 由 信 息 ;( 1 分 )BGP4 的 报 文 被 封 装 到 TCP 协 议 段 中 进 行 传 输 (1 分 ) 评 分 说 明 若 考 生 解 答 为 EGP 协 议, 且 正 确 解 答 EGP 采 用 IP 协 议 进 行 通 信, 亦 给 分