2010 年 全 国 研 究 生 考 试 计 算 机 统 考 试 题 及 答 案 一 单 选 题 1 若 元 素 a,b,c,d,e,f 依 次 进 栈, 允 许 进 栈 退 栈 操 作 交 替 进 行 但 不 允 许 连 续 三 次 进 行 退 栈 工 作, 则 不 可 能 得 到 的 出 栈 序 列 是 ( D ) A:dcebfa B:cbdaef C:dbcaef D:afedcb 2 某 队 列 允 许 在 其 两 端 进 行 入 队 操 作, 但 仅 允 许 在 一 端 进 行 出 队 操 作, 则 不 可 能 得 到 的 顺 序 是 ( C ) A:bacde B:dbace C:dbcae D:ecbad 3 下 列 线 索 二 叉 树 中 ( 用 虚 线 表 示 线 索 ), 符 合 后 序 线 索 树 定 义 的 是 ( B ) 4 在 下 列 所 示 的 平 衡 二 叉 树 中 插 入 关 键 字 48 后 得 到 一 棵 新 平 衡 二 叉 树, 在 新 平 衡 二 叉 树 中, 关 键 字 37 所 在 结 点 的 左 右 子 结 点 中 保 存 的 关 键 字 分 别 是 ( C ) A:13,48 B:24,48 C:24,53 D:24,90
5 在 一 棵 度 为 4 的 树 T 中, 若 有 20 个 度 为 4 的 结 点,10 个 度 为 3 的 结 点,1 个 度 为 2 的 结 点,10 个 度 为 1 的 结 点, 则 树 T 的 叶 节 点 个 数 是 (B) A:41 B:82 C:113 D:122 的 是 (B) 6 对 n(n 大 于 等 于 2) 个 权 值 均 不 相 同 的 字 符 构 成 哈 夫 曼 树, 关 于 该 树 的 叙 述 中, 错 误 A: 该 树 一 定 是 一 棵 完 全 二 叉 树 B: 树 中 一 定 没 有 度 为 1 的 结 点 C: 树 中 两 个 权 值 最 小 的 结 点 一 定 是 兄 弟 结 点 D: 树 中 任 一 非 叶 结 点 的 权 值 一 定 不 小 于 下 一 任 一 结 点 的 权 值 7 若 无 向 图 G-(V.E) 中 含 7 个 顶 点, 则 保 证 图 G 在 任 何 情 况 下 都 是 连 通 的, 则 需 要 的 边 数 最 少 是 (A) A :6 B:15 C:16 D:21 8 对 下 图 进 行 拓 补 排 序, 可 以 得 到 不 同 的 拓 补 序 列 的 个 数 是 (B ) A:4 B:3 C:2 D:1 9 已 知 一 个 长 度 为 16 的 顺 序 表 L, 其 元 素 按 关 键 字 有 序 排 列, 若 采 用 折 半 查 找 法 查 找 一 个 不 存 在 的 元 素, 则 比 较 次 数 最 多 是 (A) A:4 B:5 C:6 D:7 10 采 用 递 归 方 式 对 顺 序 表 进 行 快 速 排 序, 下 列 关 于 递 归 次 数 的 叙 述 中, 正 确 的 是 (D) A: 递 归 次 数 与 初 始 数 据 的 排 列 次 序 无 关 B: 每 次 划 分 后, 先 处 理 较 长 的 分 区 可 以 减 少 递 归 次 数 C: 每 次 划 分 后, 先 处 理 较 短 的 分 区 可 以 减 少 递 归 次 数 D: 递 归 次 数 与 每 次 划 分 后 得 到 的 分 区 处 理 顺 序 无 关 11 对 一 组 数 据 (2,12,16,88,5,10) 进 行 排 序, 若 前 三 趟 排 序 结 果 如 下 (A) 第 一 趟 :2,12,16,5,10,88 第 二 趟 :2,12,5,10,16,88
第 三 趟 :2,5,10,12,16,88 则 采 用 的 排 序 方 法 可 能 是 : A: 起 泡 排 序 B: 希 尔 排 序 C: 归 并 排 序 D: 基 数 排 序 12 下 列 选 项 中, 能 缩 短 程 序 执 行 时 间 的 措 施 是 (D) I 提 高 CPU 时 钟 频 率,II 优 化 数 据 通 过 结 构,III 对 程 序 进 行 编 译 优 化 A: 仅 I 和 II B: 仅 I 和 III C: 仅 II 和 III D:I,II,III 13 假 定 有 4 个 整 数 用 8 位 补 码 分 别 表 示 r1=feh,r2=f2h,r3=90h,r4=f8h, 若 将 运 算 结 果 存 放 在 一 个 8 位 的 寄 存 器 中, 则 下 列 运 算 会 发 生 溢 出 的 是 (C) A: r1*r2 B :r2*r3 C:r1*r4 D:r2*r4 14 假 定 变 量 I,f,d 数 据 类 型 分 别 为 int,float 和 double(int 用 补 码 表 示,float 和 double 分 别 用 IEEE754 单 精 度 和 双 精 度 浮 点 数 据 格 式 表 示 ), 已 知 i=785,f=1.5678,d=1.5 若 在 32 位 机 器 中 执 行 下 列 关 系 表 达 式, 则 结 果 为 真 是 (C) (I) f=(int)(float)i (II)f=(float)(int)f (III)f=(float)(double) (IV)=(d +f)-d=f A: 仅 I 和 II B: 仅 I 和 III C: 仅 II 和 III D: 仅 III 和 IV 15 假 定 用 若 干 个 2k*4 位 芯 片 组 成 一 个 8*8 位 存 储 器, 则 地 址 0B1FH 所 在 芯 片 的 最 小 地 址 是 (D) A:0000H B:0600H C: 0700H D:0800H 16 下 列 有 关 RAM 和 ROM 的 叙 述 中, 正 确 的 是 (A) I RAM 是 易 失 性 存 储 器,ROM 是 非 易 失 性 存 储 器 II RAM 和 ROM 都 是 采 用 随 机 存 取 的 方 式 进 行 信 息 访 问 III RAM 和 ROM 都 可 用 作 Cache IV RAM 和 ROM 都 需 要 进 行 刷 新
A: 仅 I 和 II B: 仅 II 和 III C: 仅 I,II,III D: 仅 II,III,IV 17 下 列 命 令 组 合 情 况 中, 一 次 访 存 过 程 中, 不 可 能 发 生 的 是 (D) A:TLB 未 命 中,Cache 未 命 中,Page 未 命 中 B:TLB 未 命 中,Cache 命 中,Page 命 中 C:TLB 命 中,Cache 未 命 中,Page 命 中 D:TLB 命 中,Cache 命 中,Page 未 命 中 18 下 列 存 储 器 中, 汇 编 语 言 程 序 员 可 见 的 是 (B) A: 存 储 器 地 址 寄 存 器 (MAR) B: 程 序 计 数 器 (PC) C: 存 储 器 数 据 寄 存 器 (MDR) D: 指 令 寄 存 器 (IR) 19 下 列 不 会 引 起 指 令 流 水 阻 塞 的 是 (A) A: 数 据 旁 路 B: 数 据 相 关 C: 条 件 转 移 D: 资 源 冲 突 20 下 列 选 项 中 的 英 文 缩 写 均 为 总 线 标 准 的 是 (D) A:PCI CRT USB EISA B:ISA CPI VESA EISA C:ISA SCSI RAM MIPS D:ISA EISA PCI PCI-Express 21 单 级 中 断 系 统 中, 中 断 服 务 程 序 执 行 顺 序 是 (A) I 保 护 现 场 II 开 中 断 III 关 中 断 IV 保 存 断 点 V 中 断 事 件 处 理 VI 恢 复 现 场 VII 中 断 返 回 A:I V VI II VII B:III I V VII C:III IV V VI VII D:IV I V VI VII
22 假 定 一 台 计 算 机 的 显 示 存 储 器 用 DRAM 芯 片 实 现, 若 要 求 显 示 分 辨 率 为 1600*1200, 颜 色 深 度 为 24 位, 帧 频 为 85Hz, 显 示 总 带 宽 的 50% 用 来 刷 新 屏 幕, 则 需 要 的 显 存 总 带 宽 至 少 约 为 (D) A :245 Mbps B:979 Mbps C:1958 Mbps D:7834Mbps 23 下 列 选 项 中, 操 作 S 提 供 的 给 应 用 程 序 的 接 口 是 (A) A: 系 统 调 用 B: 中 断 C: 库 函 数 D: 原 语 24 下 列 选 项 中, 导 致 创 进 新 进 程 的 操 作 是 (C) I 用 户 成 功 登 陆 II 设 备 分 配 III 启 动 程 序 执 行 A: 仅 I 和 II B: 仅 II 和 III C: 仅 I 和 III D:I,II,III 25 设 与 某 资 源 相 关 联 的 信 号 量 初 值 为 3, 当 前 值 为 1, 若 M 表 示 该 资 源 的 可 用 个 数, N 表 示 等 待 资 源 的 进 程 数, 则 M,N 分 别 是 (B ) A:0,1 B:1,0 C:1,2
D:2,0 26 下 列 选 项 中, 降 低 进 程 优 先 权 级 的 合 理 时 机 是 ( A ) A: 进 程 的 时 间 片 用 完 B: 进 程 刚 完 成 Z/O, 进 入 就 绪 队 列 C: 进 程 长 期 处 于 就 绪 队 列 中 D: 就 绪 从 就 绪 状 态 转 为 运 行 态 27 进 行 P0 和 P1 的 共 享 变 量 定 义 及 其 初 值 为 ( A ) boolean flag[2]; int turn=0; flag[0]=faulse;flag[1]=faulse; 若 进 行 P0 和 P1 访 问 临 界 资 源 的 类 C 代 码 实 现 如 下 : Void p0()// 进 程 p0 Void p1()// 进 程 p1 {while(ture)} {while(ture)} Flag[0]=TURE;ture=1 Flag[1]=TURE; ture=1 While (flag[1]&&(turn==1)) While (flag[0]&&(turn==0)) 临 界 区 : Flag[0]=FALSE; Flag[1]=FALSE; } } } } 则 并 发 执 行 进 程 P0 和 P1 时 产 生 的 情 况 是 : A: 不 能 保 证 进 程 互 斥 进 入 临 界 区, 会 出 现 饥 饿 现 象 B: 不 能 保 证 进 程 互 斥 进 入 临 界 区, 不 会 出 现 饥 饿 现 象
C: 能 保 证 进 程 互 斥 进 入 临 界 区, 会 出 现 饥 饿 现 象 D: 能 保 证 进 程 互 斥 进 入 临 界 区, 不 会 出 现 饥 饿 现 象 28 某 基 于 动 态 分 区 存 储 管 理 的 计 算 机, 其 主 存 容 量 为 55mb( 初 试 为 空 间 ), 采 用 最 佳 适 配 (Best fit) 算 法, 分 配 和 释 放 的 顺 序 为 : 分 配 15mb, 分 配 30mb, 释 放 15mb, 分 配 8mb, 此 时 主 存 中 最 大 空 闲 分 区 的 大 小 是 ( B ) A:7mb B:9mb C:10mb D:15mb 29 某 计 算 机 采 用 二 级 页 表 的 分 页 存 储 管 理 方 式, 按 字 节 编 制, 页 大 小 为 216 字 节, 页 表 项 大 小 为 2 字 节, 逻 辑 地 址 结 构 为 页 目 编 号 页 号 页 内 偏 移 量 逻 辑 地 址 空 间 大 小 为 216 页, 则 表 示 整 个 逻 辑 地 址 空 间 的 页 目 录 表 中 包 含 表 项 的 个 数 至 少 是 ( B ) A:64 B:128 C:256 D:512 30 设 文 件 索 引 节 点 中 有 7 个 地 址 项, 其 中 4 个 地 址 项 为 直 接 地 址 索 引,2 个 地 址 项 是 一 级 间 接 地 址 索 引,1 个 地 址 项 是 二 级 间 接 地 址 索 引, 每 个 地 址 项 大 小 为 4 字 节, 若 磁 盘 索 引 块 和 磁 盘 数 据 块 大 小 均 为 256 字 节, 则 可 表 示 的 单 个 文 件 的 最 大 长 度 是 ( C ) A:33kb B:519kb C:1057kb
D:16513kb 31 设 置 当 前 工 作 目 录 的 主 要 目 的 是 ( C ) A: 节 省 外 存 空 间 B: 节 省 内 容 空 间 C: 加 快 文 件 的 检 索 速 度 D: 加 快 文 件 的 读 写 速 度 32 本 地 用 户 通 过 键 盘 登 录 系 统 时, 首 先 获 得 键 盘 输 入 信 息 的 程 序 是 (B ) A: 命 令 解 释 程 序 B: 中 断 处 理 程 序 C: 系 统 调 用 程 序 D: 用 户 登 录 程 序 33 下 列 选 项 中, 不 属 于 网 络 体 系 结 构 中 所 描 述 的 内 容 是 ( C ) A: 网 络 的 层 次 B: 每 一 层 使 用 的 协 议 C: 协 议 的 内 部 实 现 细 节 D: 每 一 层 必 须 完 成 的 功 能 34 在 下 图 所 示 的 采 用 存 储 - 转 发 方 式 分 组 的 交 换 网 络 中, 所 有 链 路 的 数 据 传 输 速 度 为 100mbps, 分 组 大 小 为 1000B, 其 中 分 组 头 大 小 20B, 若 主 机 H1 向 主 机 H2 发 送 一 个 大 小 为 980000B 的 文 件, 则 在 不 考 虑 分 组 拆 装 时 间 和 传 播 延 迟 的 情 况 下, 从 H1 发 送 到 H2 接 收 完 为 止, 需 要 的 时 间 至 少 是 ( A )
A:80ms B:80.08ms C:80.16ms D:80.24ms 35 某 自 治 系 统 采 用 RIP 协 议, 若 该 自 治 系 统 内 的 路 由 器 R1 收 到 其 邻 居 路 由 器 R2 的 距 离 矢 量 中 包 含 信 息 <net1,16>, 则 可 能 得 出 的 结 论 是 ( A ) A:R2 可 以 经 过 R1 到 达 net1, 跳 数 为 17 B:R2 可 以 到 达 net1, 跳 数 为 16 C:R1 可 以 经 过 R2 到 达 net1, 跳 数 为 17 D:R1 不 能 进 过 R2 到 达 net1 36 若 路 由 器 R 因 为 拥 塞 丢 弃 IP 分 组, 则 此 时 R 可 以 向 发 出 该 IP 分 组 的 源 主 机 发 送 的 ICMP 报 文 件 类 型 是 ( C ) A: 路 由 重 定 向 B: 目 的 不 可 达 C: 源 抑 制 D: 超 时 37 某 网 络 的 IP 地 址 为 192.168.5.0/24 采 用 长 子 网 划 分, 子 网 掩 码 为 255.255.255.248, 则 该 网 络 的 最 大 子 网 个 数, 每 个 子 网 内 的 最 大 可 分 配 地 址 个 数 为 ( B ) A:32,8 B:32,6 C:8,32 D:8,30 38 下 列 网 络 设 备 中, 能 够 抑 制 网 络 风 暴 的 是 ( C )
Ⅰ 中 继 器 Ⅱ 集 线 器 Ⅲ 网 桥 Ⅳ 路 由 器 A: 仅 Ⅰ 和 Ⅱ B: 仅 Ⅲ C: 仅 Ⅲ 和 Ⅳ D: 仅 Ⅳ 39 主 机 甲 和 主 机 乙 之 间 已 建 立 一 个 TCP 连 接,TCP 最 大 段 长 度 为 1000 字 节, 若 主 机 甲 的 当 前 拥 塞 窗 口 为 4000 字 节, 在 主 机 甲 向 主 机 乙 连 接 发 送 2 个 最 大 段 后, 成 功 收 到 主 机 乙 发 送 的 第 一 段 的 确 认 段, 确 认 段 中 通 告 的 接 收 窗 口 大 小 为 2000 字 节, 则 此 时 主 机 甲 还 可 以 向 主 机 乙 发 送 的 最 大 字 节 数 是 ( A ) A:1000 B:2000 C:3000 D:4000 40 如 果 本 地 域 名 服 务 无 缓 存, 当 采 用 递 归 方 法 解 析 另 一 网 络 某 主 机 域 名 时, 用 户 主 机 本 地 域 名 服 务 器 发 送 的 域 名 请 求 条 数 分 别 为 ( A ) A:1 条,1 条 B:1 条, 多 条 C: 多 条,1 条 D: 多 条, 多 条 二 综 合 应 用 题 :41-47 小 题, 共 计 70 分 41.(10 分 ) 将 关 键 字 序 列 (7 8 11 18 9 14) 散 列 存 储 到 散 列 列 表 中, 散 列 表 的 存 储 空 间 是 一 个 下 标 从 0 开 始 的 一 个 一 维 数 组 散 列 函 数 维 :H(key)=(key 3)MODT, 处 理 冲 突 采 用 线 性 探 测 再 散 列 法, 要 求 装 填 ( 载 ) 因 子 为 0.7 问 题 :
(1) 请 画 出 所 构 造 的 散 列 表 ; (2) 分 别 计 算 等 概 率 情 况 下, 查 找 成 功 和 查 找 不 成 功 的 平 均 查 找 长 度 解 答 : (1) 由 装 载 因 子 0.7, 数 据 总 数 7 个 存 储 空 间 长 度 为 10 P=10 所 以, 构 造 的 散 列 表 为 : 0 1 2 3 4 5 6 7 8 9 30 7 14 11 8 18. 9.. H(7)=(7 3)MOD10=1 (2) 查 找 成 功 的 ASL=(1+1+1+1+2+1+1)/7=8/7 查 找 不 成 功 的 ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.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) 要 求 : (1) 给 出 算 法 的 基 本 设 计 思 想 (2) 根 据 设 计 思 想, 采 用 C 或 C++ 或 JAVA 语 言 表 述 算 法, 关 键 之 处 给 出 注 释 (3) 说 明 你 所 设 计 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 解 答 : 尾 (1) 前 P 个 数 依 次 进 队,while(1<n-p)A{i}-{i+p}:p 个 数 依 次 出 对, 进 入 数 组 末 (2) 详 细 程 序 略 (3) 时 间 复 杂 度 O(N); 空 间 复 杂 度 o(p) 43.(11 分 ) 某 计 算 机 字 长 为 16q 位, 主 存 地 址 空 间 大 小 为 128KB, 按 字 编 址, 采 用 字 长 指 令 格 式, 指 令 名 字 段 定 义 如 下 :
转 移 指 令 采 用 相 对 寻 址 方 式, 相 对 偏 移 是 用 补 码 表 示, 寻 址 方 式 定 义 如 下 : Ms/Md 寻 址 方 式 助 记 符 含 义 000B 寄 存 器 直 接 Rn 操 作 数 =(Rn) 001B 寄 存 器 间 接 (Rn) 操 作 数 =((Rn)) 010B 寄 存 器 间 接 自 增 (Rn)+ 操 作 数 =((Rn)),(Rn)+1 Rn 011B 相 对 D(Rn) 转 移 目 标 地 址 =(PC)+(Rn) 注 : (X) 表 示 有 储 蓄 地 址 X 或 寄 存 器 X 的 内 容, 请 回 答 下 列 问 题 : (1) 该 指 令 系 统 最 多 可 有 多 少 条 指 令? 该 计 算 机 最 多 有 多 少 个 通 用 寄 存 器? 存 储 器 地 址 寄 存 器 (MDR) 至 少 各 需 多 少 位? (2) 转 移 指 令 的 目 标 地 址 范 围 是 多 少? (3) 若 操 作 码 0010B 表 示 加 法 操 作 ( 助 记 符 为 a d d), 寄 存 器 R4 和 R5 的 编 号 分 别 为 100B 和 101B,R4 的 内 容 为 1 2 3 4 H,R5 的 内 容 为 5 6 7 8 H, 地 址 1 2 3 4 H 中 的 内 容 为 5 6 7 8 H 中 的 内 容 为 1 2 3 4 H, 则 汇 编 语 言 为 a d d(r4).(r5)+( 逗 号 前 原 操 作 数, 都 号 后 为 目 的 操 作 数 ) 对 应 的 机 器 码 是 什 么 ( 用 十 六 进 制 表 示 )? 该 指 令 执 行 后, 哪 些 寄 存 器 和 存 储 单 元 的 内 容 会 改 变? 改 变 后 的 内 容 是 什 么? 解 答 : 该 题 的 考 点 是 指 令 系 统 设 计, 注 意 操 作 位 数 与 指 令 条 数 的 关 系, 地 址 码 与 寄 存 器 数 的 关 系, 指 令 字 长 与 MOR 的 关 系, 存 储 容 量 与 MAR 的 关 系, 注 意 补 码 计 算 的 偏 移 地 址 44.(12 分 ) 某 计 算 机 的 主 存 地 址 空 间 为 256MB, 按 字 节 编 址, 指 令 Cache 分 离 均 有 8 个 Cache 行, 每 个 Cache 行 的 大 小 为 64MB, 数 据 Cache 采 用 直 接 映 射 方 式, 现 有 两 个 功 能 相 同 的 程 序 A 和 B, 其 伪 代 码 如 下 所 示 :
假 定 int 类 型 数 据 用 32 位 补 码 表 示, 程 序 编 译 时 i,j, sum 均 分 配 在 寄 存 器 中, 数 据 a 按 行 优 先 方 式 存 放, 其 地 址 为 320( 十 进 制 数 ), 请 回 答 下 列 问 题, 要 求 说 明 理 由 或 给 出 计 算 过 程 (1) 若 不 考 虑 用 于 cache 一 致 性 维 护 和 替 换 算 法 的 控 制 位, 则 数 据 Cache 的 总 容 量 是 多 少? (2) 要 组 元 素 a[0][31] 和 a[1][1] 各 自 所 在 的 主 存 块 对 应 的 Cache 行 号 分 别 是 多 少 (Cache 行 号 从 0 开 始 )? (3) 程 序 A 和 B 的 数 据 访 问 命 令 中 各 是 多 少? 那 个 程 序 的 执 行 时 间 更 短? 简 答 : 考 点 :Cache 容 量 计 算, 直 接 映 射 方 式 的 地 址 计 算, 以 及 命 中 率 计 算 ( 行 优 先 遍 历 与 列 优 先 遍 历 命 中 率 分 别 很 大 ) 45 (7 分 ) 假 设 计 算 机 系 统 采 用 CSCAN( 循 环 扫 描 ) 磁 盘 调 度 策 略, 使 用 2KB 的 内 存 空 间 记 录 16384 个 磁 盘 块 的 空 间 状 态 (1) 请 说 明 在 上 述 条 件 下 如 何 进 行 磁 盘 块 空 闲 状 态 管 理 (2) 设 某 单 面 磁 盘 旋 转 速 度 为 每 分 钟 6000 转 每 个 磁 道 有 100 个 扇 区, 相 临 磁 道 间 的 平 均 移 动 时 间 为 1ms. 若 在 某 时 刻, 磁 头 位 于 100 号 磁 道 处, 并 沿 着 磁 道 号 大 的 方 向 移 动 ( 如 下 图 所 示 ), 磁 道 号 请 求 队 列 为 50.90.30.120. 对 请 求 队 列 中 的 每 个 磁 道 需 读 取 1 个 随 机 分 布 的 扇 区, 则 读 完 这 个 扇 区 点 共 需 要 多 少 时 间? 要 求 给 出 计 算 过 程
46.(8 分 ) 设 某 计 算 机 的 逻 辑 地 址 空 间 和 物 理 地 址 空 间 均 为 64KB. 按 字 节 编 址 若 某 进 程 最 多 需 要 6 页 (Page) 数 据 存 储 空 间, 页 的 大 小 为 1KB. 操 作 系 统 采 用 固 定 分 配 局 部 置 换 策 略 为 此 进 程 分 配 4 个 页 框 (Page Fame). 页 号 页 根 号 装 入 时 刻 访 问 位 0 7 130 1 1 4 230 1 2 2 200 1 3 9 160 1 当 该 进 程 执 行 到 时 刻 260 时, 要 访 问 逻 辑 地 址 为 17CAH 的 数 据, 请 问 答 下 列 问 题 : (1) 该 逻 辑 地 址 对 应 的 页 号 是 多 少? (2) 若 采 用 先 进 先 出 (FIFO) 置 换 算 法, 该 逻 辑 地 址 对 应 的 物 理 地 址 是 多 少? 要 求 给 出 计 算 过 程 (3) 若 采 用 时 钟 (CLOCK) 置 换 算 法, 该 逻 辑 地 址 对 应 的 物 理 地 址 是 多 少? 要 求 给 出 计 算 过 程 ( 设 搜 索 下 一 页 的 指 针 沿 顺 时 针 方 向 移 动, 且 当 前 指 向 2 号 页 框, 示 意 图 如 下 )
解 答 :17CAH=(0001 0111 1100 1010)2 为 :5 (1) 页 大 小 为 1K, 所 以 页 内 偏 移 地 址 为 10 位, 于 是 前 6 位 是 页 号, 所 以 第 一 间 的 解 (2)FIFO, 则 被 置 换 的 页 面 所 在 页 框 为 7, 所 以 对 应 的 物 理 地 址 为 (0001 1111 1100 1010)2-IFCAH (3)CLOCK, 则 被 置 换 的 页 面 所 在 页 框 为 2, 所 以 对 应 的 物 理 地 址 为 (0000 1011 1100 1010)2-OBCAH 47 (9 分 ) 某 局 域 网 采 用 CSMA/CD 协 议 实 现 介 质 访 问 控 制, 数 据 传 输 速 率 为 10MBPS, 主 机 甲 和 主 机 乙 之 间 的 距 离 为 2KM, 信 号 传 播 速 度 是 200 000KMS. 请 回 答 下 列 问 题, 并 给 出 计 算 过 程 (1) 若 主 机 甲 和 主 机 乙 发 送 数 据 时 发 生 冲 突, 则 从 开 始 发 送 数 据 时 刻 起, 到 两 台 主 机 均 检 测 到 冲 突 时 刻 止, 最 短 需 经 多 长 时 间? 最 长 需 经 过 多 长 时 间?( 假 设 主 机 甲 和 主 机 乙 发 送 数 据 过 程 中, 其 他 主 机 不 发 送 数 据 ) (2) 若 网 络 不 存 在 任 何 冲 突 与 差 错, 主 机 甲 总 是 以 标 准 的 最 长 以 大 网 数 据 锁 (1518 字 节 ) 向 主 机 乙 发 送 数 据, 主 机 乙 每 成 功 收 到 一 个 数 据 锁 后, 立 即 发 送 下 一 个 数 据 锁, 此 时 主 机 甲 的 有 效 数 据 传 输 速 率 是 多 少?( 不 考 虑 以 大 网 锁 的 前 导 码 ) 解 答 : (1) 当 甲 乙 同 时 向 对 方 发 送 数 据 时, 两 台 主 机 均 检 测 到 冲 突 所 需 时 间 最 短 ; 1KM/200000KM/S*2=1*10(-5)S 当 一 方 发 送 的 数 据 马 上 要 到 达 另 一 方 时, 另 一 方 开 始 发 送 数 据, 两 台 主 机 均 检 测 到 冲 突 所 需 时 间 最 长 ;
2KM/2000000KM/S*2=2*10(-5)S (2) 发 送 一 锁 所 需 时 间 ;1518B/10MBPS=1.2144MS 数 据 传 播 时 间 ;2KM/200 000KM/S=1*10(-5)S=0.01MS 有 效 的 数 据 传 输 速 率 =10MBPS*1.2144MS/1.2244MS=9.92MBPS