本试卷共包括4门专业课程试题，每位考生任意选择其中2门进行答题，每门课程75分，总分150分

青 岛 大 学 2013 年 硕 士 研 究 生 入 学 考 试 试 题 科 目 代 码 : 911 科 目 名 称 : 计 算 机 专 业 综 合 ( 共 13 页 ) 请 考 生 写 明 题 号, 将 答 案 全 部 答 在 答 题 纸 上, 答 在 试 卷 上 无 效 须 知 : 本 试 卷 共 包 括 4 门 专 业 课 程 试 题, 每 位 考 生 任 意 选 择 其 中 2 门 进 行 解 答, 每 门 课 程 75 分, 总 分 150 分 考 试 时 间 为 180 分 钟, 考 试 形 式 为 闭 卷 笔 答 请 考 生 在 以 下 4 门 课 程 中 选 择 2 门 课 程 1 数 据 结 构 ( ) 2 计 算 机 操 作 系 统 ( ) 3 计 算 机 组 成 原 理 ( ) 4 计 算 机 网 络 原 理 ( ) 注 意 : 若 多 选, 则 取 前 两 门 课 默 认 为 你 的 选 择 比 如 你 选 择 了 1 3 4, 则 认 为 你 选 择 了 1 3 课 程 作 为 你 的 本 次 选 择 模 块 一 : 数 据 结 构 一 单 项 选 择 题 ( 本 大 题 共 10 小 题, 每 小 题 1 分, 共 10 分 ) 在 每 小 题 列 出 的 四 个 备 选 项 中 只 有 一 个 是 符 合 题 目 要 求 的 错 选 多 选 或 未 选 均 无 分 1. 某 算 法 的 时 间 复 杂 度 是 O(n 2 ), 表 明 该 算 法 ( ) A. 问 题 规 模 是 n 2 B. 问 题 规 模 与 n 2 成 正 比 C. 执 行 时 间 等 于 n 2 D. 执 行 时 间 与 n 2 成 正 比 2. 当 使 用 大 小 为 n 的 一 维 数 组 顺 序 存 储 一 个 栈 时, 假 定 top == n 表 示 栈 空, 则 向 该 栈 压 入 一 个 元 素 时, 首 先 应 执 行 ( ) 语 句 修 改 top 指 针 A.top++ B.top-- C.top=0 D.top=n 3. 对 于 链 式 队 列, 在 执 行 入 队 列 操 作 时 ( ) A. 仅 修 改 头 指 针 B. 仅 修 改 尾 指 针 C. 头 尾 指 针 都 要 修 改 D. 头 尾 指 针 可 能 都 修 改 4. 一 个 二 维 数 组 A[10][20] 按 列 存 放 在 一 个 连 续 的 存 储 空 间 中 A[0][0] 的 存 储 地 址 是 100, 每 个 数 组 元 素 占 1 个 存 储 单 元, 则 A[6][2] 的 地 址 为 ( ) A.126 B.222 C.241 D.242 5. 一 个 深 度 为 k 且 只 有 k 个 结 点 的 二 叉 树 按 照 完 全 二 叉 树 顺 序 存 储 的 方 式 1

存 放 在 一 个 一 维 数 组 A[n] 中, 那 么 n 应 至 少 是 ( ) A.2k B.2k-1 C.2 k - 1 D.2 k 6. 用 邻 接 表 存 储 图 所 用 的 空 间 大 小 ( ) A. 与 图 的 顶 点 数 和 边 数 都 有 关 B. 只 与 图 的 顶 点 数 有 关 C. 只 与 图 的 边 数 有 关 D. 与 边 数 的 平 方 有 关 7.( ) 算 法 可 以 求 出 无 向 图 的 所 有 连 通 分 量 A. 广 度 优 先 遍 历 B. 拓 扑 排 序 C. 求 最 短 路 径 D. 求 关 键 路 径 8. 在 10 阶 B- 树 中, 根 结 点 所 包 含 的 关 键 字 个 数 最 少 为 ( ) A.1 B.5 C.9 D.10 9. 在 下 列 的 排 序 方 法 中, 最 耗 费 内 存 量 的 是 ( ) A. 插 入 排 序 B. 快 速 排 序 C. 选 择 排 序 D. 归 并 排 序 10. 下 述 几 种 排 序 方 法 中, 平 均 查 找 长 度 最 小 的 是 ( ) A. 插 入 排 序 B. 选 择 排 序 C. 快 速 排 序 D. 归 并 排 序 二 简 答 题 ( 本 大 题 共 5 小 题, 每 小 题 5 分, 共 25 分 ) 1. 内 存 中 一 片 连 续 空 间 ( 不 妨 假 设 地 址 从 0 到 m-1) 提 供 给 两 个 栈 S1 与 S2 使 用, 怎 样 分 配 这 部 分 存 储 空 间, 使 得 对 任 一 个 栈 仅 当 这 部 分 空 间 全 满 时 才 发 生 上 溢 2. 试 说 明 一 棵 二 叉 树 无 论 进 行 前 序 中 序 或 后 序 遍 历, 其 叶 子 结 点 的 相 对 次 序 都 不 会 发 生 改 变 3. 有 4 个 顶 点 A B C D 的 无 向 连 通 图 按 广 度 优 先 和 深 度 优 先 搜 索 遍 历 结 果 都 为 A B C D, 画 出 所 有 可 能 的 结 构 图 4. 如 果 有 一 组 关 键 字, 以 不 同 的 次 序 输 入 后 建 立 起 来 的 二 叉 排 序 树 是 否 相 同? 当 中 序 遍 历 这 些 二 叉 排 序 树 时, 其 遍 历 的 结 果 是 否 相 同? 为 什 么? 5. 现 有 一 文 件 含 有 10000 个 记 录, 其 中 只 有 少 量 次 序 不 对, 且 它 们 距 离 正 确 位 置 不 远, 如 果 以 比 较 和 移 动 次 数 作 度 量, 将 其 进 行 排 序 的 最 好 方 法 是 什 么? 三 综 合 应 用 与 算 法 设 计 题 ( 本 大 题 共 5 小 题, 每 小 题 8 分, 共 40 分 ) 2

1. 对 于 图 ds-1 所 示 的 有 向 图, 试 给 出 : 图 ds-1 (1) 邻 接 矩 阵 ; (2) 邻 接 表 ; (3) 强 连 通 分 量 ; (4) 从 顶 点 v1 出 发 的 深 度 优 先 遍 历 序 列 2. 已 知 一 个 长 度 为 12 的 线 性 表 List=(7,2,5,8,12,3,10,4,1,6, 9,11), 试 回 答 下 面 的 问 题 : (1) 将 线 性 表 中 的 元 素 依 次 插 入 到 一 个 空 的 平 衡 二 叉 排 序 树 中, 画 出 所 得 的 平 衡 二 叉 排 序 树 假 设 查 找 每 一 个 元 素 的 概 率 相 同, 查 找 此 平 衡 二 叉 排 序 树 中 任 一 结 点 的 平 均 查 找 长 度 为 多 少? (2) 若 对 线 性 表 中 的 元 素 排 序 之 后, 再 用 折 半 查 找 算 法, 画 出 描 述 折 半 查 找 过 程 的 判 定 树 假 设 查 找 每 个 元 素 的 概 率 相 同, 计 算 查 找 成 功 时 的 平 均 查 找 长 度 3. 某 整 型 数 组 A 的 10 个 元 素 值 依 次 为 :{6 2 9 7 3 8 4 5 0 10}, 用 下 列 各 排 序 方 法, 将 A 中 元 素 由 小 到 大 排 序 (1) 取 第 一 个 元 素 6 作 为 枢 轴 试 写 出 快 速 排 序 第 一 趟 后 A 中 的 结 果 (2) 用 堆 排 序 ( 大 根 堆 ), 试 写 出 将 第 一 个 选 出 的 数 据 放 在 A 的 最 后 位 置 上, 将 A 调 整 成 堆 后 的 A 中 结 果 4. 已 知 元 素 数 据 类 型 为 整 数 的 顺 序 表 SL=(a1,a2,,am,bl,b2,, bn), 试 设 计 算 法 将 SL 中 元 素 的 两 部 分 互 换 为 (bl,b2,,bn,a1,a2,, am) 要 求 : 不 能 使 用 额 外 的 数 组 空 间 (1) 用 文 字 给 出 你 的 算 法 思 想 ; (2) 用 C 语 言 写 出 算 法 的 实 现 3

5. 对 以 二 叉 链 表 存 储 的 非 空 二 叉 树, 从 右 向 左 依 次 释 放 所 有 叶 子 结 点, 释 放 的 同 时, 把 结 点 值 存 放 到 一 个 数 组 中 要 求 : (1) 用 文 字 写 出 实 现 上 述 过 程 的 基 本 思 想 (2) 用 C 语 言 写 出 算 法 的 实 现 模 块 二 : 计 算 机 操 作 系 统 一. 单 项 选 择 题 ( 每 小 题 1 分, 共 10 分 ) 1. 下 列 操 作 系 统 的 功 能 程 序 中, 不 适 合 放 入 内 核 的 是 ( ) A. 代 码 加 载 程 序 和 代 码 卸 出 程 序 B. 进 程 控 制 与 进 程 调 度 原 语 C. 磁 盘 扫 描 与 格 式 化 程 序 D. 处 理 机 闲 逛 程 序 2. 下 列 说 法 正 确 的 是 ( ) A. 在 多 道 程 序 运 行 环 境 中, 如 果 处 理 机 利 用 率 不 高 就 应 当 立 即 创 建 新 进 程, 通 过 增 加 进 程 数 量 来 提 高 处 理 机 利 用 率 B. 为 了 使 高 层 的 某 个 短 小 精 悍 的 程 序 块 运 行 过 程 不 受 干 扰, 可 以 将 其 用 原 语 实 现 C. 在 单 道 批 处 理 系 统 中, 整 个 内 存 只 用 来 存 放 一 个 用 户 程 序, 只 有 多 任 务 操 作 系 统 中 才 划 分 出 一 部 分 空 间 用 来 存 放 管 理 程 序 D. 在 HPF 算 法 中, 系 统 ( 或 管 理 员 ) 给 I/O 类 进 程 较 高 的 优 先 级 能 够 改 善 系 统 性 能 3. 以 下 关 于 线 程 和 进 程 说 法 错 误 的 是 ( ) A. 一 个 进 程 可 以 有 一 个 或 多 个 线 程 B. 线 程 是 进 程 中 可 独 立 调 度 和 执 行 的 基 本 单 位 C. 系 统 级 线 程 的 切 换 和 用 户 级 线 程 的 切 换 都 需 要 内 核 的 支 持 D. 在 支 持 多 线 程 的 系 统 中, 进 程 P 创 建 的 若 干 个 线 程 能 够 共 享 进 程 P 的 代 码 段 4. 以 下 关 于 存 储 管 理 说 法 错 误 的 是 ( ) A. 分 段 系 统 较 之 分 页 系 统 更 易 于 实 现 信 息 共 享 B. 设 有 8 页 的 逻 辑 空 间, 每 页 有 1024 字 节, 它 们 被 映 射 到 32 块 的 物 理 存 储 区 中 那 么, 逻 辑 地 址 的 有 效 位 是 13 位, 物 理 地 址 至 少 是 15 位 C. 在 采 用 一 级 页 表 结 构 且 不 采 用 快 表 的 分 页 管 理 系 统 中, 处 理 机 每 次 4

读 出 / 写 入 一 个 数 据, 需 要 访 问 2 次 内 存 ; 同 样, 在 分 区 存 储 管 理 系 统 中, 也 需 要 访 问 2 次 内 存 D. 分 页 存 储 管 理 系 统 中 用 户 程 序 装 入 之 前 的 逻 辑 地 址 是 一 维 的 ; 分 段 存 储 管 理 系 统 中 用 户 程 序 装 入 之 前 的 逻 辑 地 址 是 二 维 的 5. 有 关 死 锁 的 叙 述 正 确 的 是 ( ) A. 死 锁 的 产 生 与 资 源 分 配 策 略 无 关, 与 进 程 并 发 执 行 的 速 度 有 关 B. 对 资 源 采 用 按 序 分 配 策 略 就 不 会 出 现 循 环 等 待 资 源 的 情 况 了 C. 通 过 破 坏 互 斥 使 用 资 源 的 条 件 就 能 防 止 死 锁 D. 资 源 请 求 分 配 图 中 有 环 路 则 可 断 定 有 死 锁 6. 在 动 态 多 分 区 分 配 方 案 中, 某 一 作 业 完 成 后, 系 统 收 回 其 主 存 空 间 并 与 相 邻 空 闲 区 合 并, 为 此 需 修 改 空 闲 区 表, 造 成 空 闲 区 数 减 1 的 情 况 是 ( ) A. 无 上 邻 空 闲 区 也 无 下 邻 空 闲 区 B. 有 上 邻 空 闲 区 但 无 下 邻 空 闲 区 C. 有 下 邻 空 闲 区 但 无 上 邻 空 闲 区 D. 有 上 邻 空 闲 区 也 有 下 邻 空 闲 区 7. 一 个 分 段 存 储 管 理 系 统 中, 地 址 字 长 度 为 32 位, 其 中 段 号 占 8 位, 则 允 许 的 进 程 的 最 大 长 度 是 ( ) A. 2 32 字 节 B. 2 24 字 节 C. 2 16 字 节 D. 2 8 字 节 8. 系 统 采 用 中 断 和 通 道 技 术, 使 得 ( ) A. CPU 与 外 设 紧 密 结 合 B. CPU 与 外 设 能 并 行 工 作 C. CPU 速 度 提 高 D. 外 设 速 度 提 高 9. 磁 盘 调 度 算 法 中, ( ) 算 法 可 能 会 随 时 改 变 移 动 磁 臂 的 运 动 方 向 A. 先 来 先 服 务 和 电 梯 调 度 B. 单 向 扫 描 和 最 短 寻 道 时 间 优 先 C. 电 梯 调 度 和 单 向 扫 描 D. 最 短 寻 道 时 间 优 先 和 先 来 先 服 务 10. 对 物 理 结 构 为 ( ) 的 文 件 只 能 顺 序 存 取, 不 能 随 机 存 取 A. 连 续 存 储 结 构 B. 隐 式 链 接 存 储 结 构 C. 显 式 链 接 存 储 结 构 D. 索 引 存 储 结 构 二. 简 答 题 ( 每 小 题 5 分, 共 25 分 ) 5

1. 通 用 的 操 作 系 统 应 具 有 哪 几 个 基 本 特 征? 并 请 叙 述 这 几 个 基 本 特 征 的 主 要 表 现 2. 为 了 让 用 户 进 程 互 斥 地 进 入 临 界 区, 把 整 个 临 界 区 实 现 成 不 可 中 断 的 过 程, 即 : 每 当 用 户 程 序 进 入 临 界 区 的 时 候, 屏 蔽 所 有 中 断 ; 当 出 了 临 界 区 的 时 候, 再 开 放 所 有 中 断 你 认 为 这 种 方 法 可 取 吗? 为 什 么? 3. 什 么 是 原 语? 原 语 有 什 么 特 点? 操 作 系 统 中 将 哪 些 程 序 设 置 为 原 语, 请 举 例 说 明 4. 操 作 系 统 通 过 建 立 逻 辑 设 备 与 物 理 设 备 的 映 射 机 制 来 实 现 设 备 独 立 性, 请 问 什 么 是 设 备 独 立 性? 它 带 来 的 好 处 是 什 么? 5. 在 操 作 系 统 管 理 下, 磁 盘 空 间 被 划 分 为 文 件 区 和 交 换 区, 请 问 二 者 的 区 别 是 什 么? 三. 综 合 应 用 题 ( 要 求 写 出 分 析 和 计 算 过 程, 每 小 题 8 分, 共 40 分 ) 1. 设 系 统 中 有 三 种 类 型 的 资 源 (A B C) 和 五 个 进 程 (P1 P2 P3 P4 P5) A 资 源 的 数 量 为 16,B 资 源 的 数 量 为 5,C 资 源 的 数 量 为 20 在 T0 时 刻 系 统 分 配 情 况 如 下 表 所 示, 若 系 统 采 用 银 行 家 算 法, 请 问 : (1) T0 时 刻 系 统 是 否 为 安 全 的? 若 是, 请 给 出 安 全 序 列 (2) 在 T0 时 刻 若 进 程 P2 请 求 资 源 (0,3,4), 是 否 能 实 施 资 源 分 配? 为 什 么? (3) 在 T0 时 刻, 若 进 程 P4 请 求 资 源 (1,0,1), 是 否 能 实 施 资 源 分 配? 为 什 么? 进 程 最 大 资 源 需 求 量 已 分 配 资 源 数 量 A B C A B C P1 5 4 9 2 1 2 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 2. 假 设 系 统 采 用 基 本 分 页 式 存 储 管 理, 地 址 空 间 由 32 位 二 进 制 表 示, 页 面 长 度 为 4KB, 每 个 页 表 项 占 用 4B, 请 计 算 回 答 : 6

(1) 所 允 许 的 进 程 的 最 大 长 度 是 多 少? (2) 需 要 采 用 几 级 页 表 结 构? (3) 相 对 地 址 的 32 位 被 分 成 几 部 分, 各 部 分 分 别 占 用 几 个 二 进 制 位? 3. 已 知 一 个 采 用 固 定 分 配 局 部 置 换 的 请 求 分 页 存 储 管 理 系 统 中, 页 面 尺 寸 为 4KB, 有 一 个 长 度 为 30KB 的 进 程 P 进 入 系 统, 分 配 给 P 的 存 储 块 有 3 块, 进 程 的 所 有 页 面 都 是 在 该 进 程 运 行 中 动 态 装 入 (1) 对 应 于 下 述 页 面 访 问 序 列 : 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 采 用 LRU 置 换 算 法, 请 计 算 缺 页 中 断 率 p (2) 已 知 不 发 生 缺 页 中 断 时 页 面 的 有 效 访 问 时 间 为 200ns, 发 生 缺 页 中 断 时, 缺 页 中 断 处 理 时 间 为 25ms/ 次 利 用 前 面 计 算 的 缺 页 中 断 率 p, 请 计 算 每 个 页 面 的 平 均 有 效 访 问 时 间 T 4. 设 文 件 索 引 节 点 中 有 7 个 地 址 项, 其 中 4 个 地 址 项 为 直 接 地 址 索 引, 2 个 地 址 项 是 一 级 间 接 地 址 索 引,1 个 地 址 项 是 二 级 间 接 地 址 索 引, 每 个 地 址 项 的 大 小 为 4B 若 磁 盘 索 引 块 和 磁 盘 数 据 块 大 小 均 为 256B, 则 可 表 示 的 单 个 文 件 的 最 大 长 度 是 多 少? 5. 两 个 进 程 P1 P2 通 过 互 斥 访 问 消 息 队 列 MessageQueen( 链 队 ) 进 行 通 信 系 统 初 始 时 MessageQueen 为 空, 工 作 过 程 如 下 : P1 每 次 调 用 produce( ) 生 成 一 个 新 的 Mail, 然 后 调 用 allocate( ) 申 请 一 个 空 白 消 息 块 M, 将 Mail 复 制 到 M, 然 后 将 消 息 块 M 发 送 到 MessageQueen 队 中 ; MessageQueen 不 空 时, P2 每 次 从 队 列 中 取 出 一 个 消 息 块 N, 调 用 consume( ) 使 用 完 消 息 块 N, 然 后 调 用 free( ) 将 该 消 息 块 释 放 (1) 请 用 信 号 量 机 制 实 现 这 两 个 进 程 的 同 步 与 互 斥 活 动, 要 求 用 伪 代 码 描 述 (2) 说 明 所 定 义 的 信 号 量 的 用 途 模 块 三 : 计 算 机 组 成 原 理 一 单 项 选 择 题 ( 每 小 题 1 分, 共 10 分 ) 1. 冯. 诺 依 曼 计 算 机 中 指 令 和 数 据 均 以 二 进 制 形 式 存 放 在 存 储 器 中,CPU 区 分 它 们 的 依 据 是 ( ) 7

A. 指 令 操 作 码 的 译 码 结 果 B. 指 令 和 数 据 的 寻 址 方 式 C. 指 令 周 期 的 不 同 阶 段 D. 指 令 和 数 据 所 在 的 存 储 单 元 2. 下 列 选 项 中, 描 述 浮 点 数 操 作 速 度 指 标 的 是 ( ) A.MIPS B.CPI C.IPC D.MFLOPS 3. 在 定 点 二 进 制 运 算 器 中, 减 法 运 算 一 般 通 过 ( ) 来 实 现 A 原 码 运 算 的 二 进 制 减 法 器 B 补 码 运 算 的 二 进 制 减 法 器 C 原 码 运 算 的 十 进 制 加 法 器 D 补 码 运 算 的 二 进 制 加 法 器 4. 长 度 相 同 但 格 式 不 同 的 两 种 浮 点 数, 若 A 型 阶 码 长 尾 数 短,B 型 阶 码 短 尾 数 长, 其 它 规 定 相 同, 则 其 表 示 数 的 范 围 和 精 度 ( ) A. 两 者 范 围 与 精 度 相 同 B. A 型 范 围 大 但 精 度 低 C. B 型 范 围 大 且 精 度 高 D. A 型 范 围 大 且 精 度 高 5. 某 计 算 机 主 存 容 量 为 64KB, 其 中 ROM 区 为 4K, 其 余 为 RAM 区, 按 字 节 编 址 现 要 用 2K 8 位 的 ROM 芯 片 和 4K 4 位 的 RAM 芯 片 来 设 计 该 存 储 器, 则 需 要 上 述 规 格 的 ROM 芯 片 数 和 RAM 芯 片 数 分 别 是 ( ) A.1 15 B. 2 15 C.1 30 D. 2 30 6. 以 下 四 种 类 型 指 令 中, 执 行 时 间 最 长 的 是 ( ) A.RR 型 指 令 B.RS 型 指 令 C.SS 型 指 令 D. 程 序 控 制 指 令 7. 偏 移 寻 址 通 过 将 某 个 寄 存 器 内 容 与 一 个 形 式 地 址 相 加 而 生 成 有 效 地 址 下 列 寻 址 方 式 中, 不 属 于 偏 移 寻 址 方 式 的 是 ( ) A. 间 接 寻 址 B. 基 址 寻 址 C. 相 对 寻 址 D. 变 址 寻 址 8. 假 设 某 系 统 总 线 在 一 个 总 线 周 期 中 并 行 传 输 4 字 节 信 息, 一 个 总 线 周 期 占 用 2 个 时 钟 周 期, 总 线 时 钟 频 率 为 10MHz, 则 总 线 带 宽 是 ( ) A.10MB/s B.20MB/s C.40MB/s D.80MB/s 9. 在 系 统 总 线 的 数 据 线 上, 不 可 能 传 输 的 是 ( ) A. 指 令 B. 操 作 数 C. 握 手 ( 应 答 ) 信 号 D. 中 断 类 型 号 10 相 联 存 储 器 是 指 按 ( ) 进 行 寻 址 的 存 储 器 8

A. 地 址 指 定 方 式 B. 堆 栈 存 取 方 式 C. 内 容 指 定 方 式 D. 地 址 指 定 与 堆 栈 存 取 方 式 结 合 二 简 答 题 ( 共 25 分 ) 1 冯. 诺 依 曼 结 构 计 算 机 包 括 哪 几 个 组 成 部 分? 各 有 什 么 作 用?(5 分 ) 2 现 代 计 算 机 存 储 系 统 包 含 哪 几 个 层 次? 为 什 么 采 用 层 次 结 构?(5 分 ) 3 什 么 是 RISC? 什 么 是 CISC?RISC 主 要 有 哪 些 特 点?(7 分 ) 4 什 么 是 中 断? 中 断 处 理 的 一 般 过 程 如 何?(8 分 ) 三 综 合 应 用 题 ( 共 40 分 ) 1 一 台 处 理 机 具 有 如 下 指 令 格 式 : 6 位 2 位 3 位 3 位 OP X 源 寄 存 器 目 标 寄 存 器 地 址 其 格 式 表 明 有 8 个 通 用 寄 存 器 ( 长 度 16 位 ),X 为 指 定 的 寻 址 模 式, 主 存 最 大 容 量 为 256 K 字 1) 假 设 不 用 通 用 寄 存 器 也 能 直 接 访 问 主 存 的 每 一 个 操 作 数, 并 假 设 操 作 码 域 OP=6 位, 请 问 地 址 码 域 应 该 分 配 多 少 位? 指 令 字 长 度 是 多 少 位? 2) 假 设 X=11 时, 指 定 的 那 个 通 用 寄 存 器 用 作 基 址 寄 存 器, 请 提 出 一 个 硬 件 设 计 规 则, 使 得 被 指 定 的 通 用 寄 存 器 能 访 问 1M 的 主 存 空 间 中 的 每 一 个 单 元 ( 本 题 12 分 ) 2 某 计 算 机 的 CPU 主 频 为 500MHz,CPI 为 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 之 间 没 有 访 存 冲 突 )( 本 题 13 分 ) 9

3 某 计 算 机 的 数 据 通 路 如 图 1 所 示, 其 中 M 主 存, MBR 主 存 数 据 寄 存 器, MAR 主 存 地 址 寄 存 器, R0-R3 通 用 寄 存 器, IR 指 令 寄 存 器, PC 程 序 计 数 器 ( 具 有 自 增 能 力 ), C D-- 暂 存 器, ALU 算 术 逻 辑 单 元 ( 此 处 做 加 法 器 看 待 ), 移 位 器 左 移 右 移 直 通 传 送 所 有 双 向 箭 头 表 示 信 息 可 以 双 向 传 送 请 按 数 据 通 路 图 画 出 ADD(R1),(R2)+ 指 令 的 指 令 周 期 流 程 图 该 指 令 的 含 义 是 两 个 数 进 行 求 和 操 作 其 中 源 操 作 地 址 在 寄 存 器 R1 中, 目 的 操 作 数 寻 址 方 式 为 自 增 型 寄 存 器 间 接 寻 址 ( 先 取 地 址 后 加 1) ( 本 题 15 分 ) 图 1 模 块 四 : 计 算 机 网 络 原 理 一 单 项 选 择 题 ( 每 题 1 分, 共 10 分 ) 1. TCP/IP 参 考 模 型 中 的 网 络 层 提 供 的 是 ( ) A. 无 连 接 可 靠 的 数 据 报 服 务 B. 有 连 接 可 靠 的 虚 电 路 服 务 C. 有 连 接 不 可 靠 的 数 据 报 服 务 D. 无 连 接 不 可 靠 的 数 据 报 服 务 2. 若 某 通 信 链 路 的 数 据 传 输 速 率 是 1200bps, 采 用 4 相 位 调 制, 则 该 链 路 的 波 特 率 是 ( ) A. 4800 波 特 B. 600 波 特 C. 300 波 特 D. 2400 波 特 3. 以 下 选 项 中, 对 正 确 接 收 到 的 数 据 帧 进 行 确 认 的 MAC 协 议 是 ( ) A. CSMA B. CDMA C. CSMA/CD D. CSMA/CA 4. 在 子 网 192.168.128.0/30 中, 能 够 收 到 目 的 地 址 为 192.168.128.3 的 IP 10

分 组 的 最 大 主 机 数 是 ( ) A. 0 B. 1 C. 2 D. 4 5. 主 机 A 向 主 机 B 发 送 一 个 (SYN=1, seq=12321) 的 TCP 段, 期 望 与 主 机 B 建 立 TCP 连 接, 若 主 机 B 接 受 该 连 接 请 求, 则 主 机 B 想 主 机 A 发 送 的 正 确 TCP 段 可 能 是 ( ) A. (SYN=0, ACK=0, seq=12321, ack=12321) B. (SYN=1, ACK=1, seq=12321, ack=12321) C. (SYN=1, ACK=1, seq=12322, ack=12322) D. (SYN=0, ACK=0, seq=12322, ack=12322) 6. FTP 客 户 与 服 务 器 之 间 传 递 FTP 命 令 时, 使 用 的 连 接 是 ( ) A. 建 立 在 TCP 上 的 控 制 连 接 B. 建 立 在 TCP 上 的 数 据 连 接 C. 建 立 在 UDP 上 的 控 制 连 接 D. 建 立 在 UDP 上 的 数 据 连 接 7. 在 OSI 参 考 模 型 中, 自 下 而 上 第 一 个 提 供 端 到 端 服 务 的 层 次 是 ( ) A. 数 据 链 路 层 B. 传 输 层 C. 会 话 层 D. 应 用 层 8. 在 无 噪 声 情 况 下, 若 某 个 通 信 链 路 的 带 宽 为 3kHz, 采 用 4 个 相 位, 每 个 相 位 4 种 振 幅 的 QAM 调 制 技 术, 则 该 通 信 链 路 的 最 大 数 据 传 输 速 率 是 ( ) A. 12 kbps B. 48 kbps C. 96 kbps D. 24 kbps 9. 数 据 链 路 层 采 用 后 退 N 帧 (GBN) 协 议, 发 送 方 已 经 发 送 了 编 号 为 0~ 7 的 帧 当 计 时 器 超 时 时, 若 发 送 方 只 收 到 0 2 3 号 帧 的 确 认 帧, 则 发 送 方 需 要 重 发 的 帧 数 是 ( ) A. 5 B. 4 C. 3 D. 2 10. 以 太 网 交 换 机 进 行 转 发 决 策 时 使 用 的 PDU 地 址 是 ( ) A. 目 的 物 理 地 址 B. 目 的 IP 地 址 C. 源 物 理 地 址 D. 源 IP 地 址 二 简 答 题 ( 每 题 5 分, 共 25 分 ) 1. 网 络 协 议 的 三 个 要 素 是 什 么? 各 有 什 么 含 义? 2. 面 向 连 接 服 务 与 无 连 接 报 务 各 自 的 特 点 是 什 么? 3. 比 较 半 双 工 通 信 全 双 工 通 信 的 主 要 区 别 4. 试 简 单 说 明 下 列 协 议 的 作 用 :IP ARP RARP 和 ICMP 11

5. 要 发 送 的 数 据 为 1101011011 采 用 CRC 的 生 成 多 项 式 是 P(x)=x 4 +x+1 (1) 试 求 应 添 加 在 数 据 后 面 的 余 数 (2) 数 据 在 传 输 过 程 中 最 后 一 个 1 变 成 了 0, 试 分 析 接 收 端 能 否 发 现? (3) 若 数 据 1101011011 在 传 输 过 程 中 最 后 两 个 1 都 变 成 了 0, 试 分 析 接 收 端 能 否 发 现? 三 综 合 应 用 ( 共 40 分 ) 1. (14 分 ) 某 单 位 分 配 到 一 个 C 类 IP 地 址, 其 net-id 为 202.250.17.0 该 单 位 的 主 机 分 布 在 6 个 不 同 的 地 点, 地 点 A 有 12 台 主 机, 地 点 B 有 20 台 主 机, 地 点 C 有 8 台 主 机, 地 点 D E F 各 有 10 台 主 机 (1) 试 写 出 子 网 掩 码, 将 6 个 地 点 划 分 为 6 个 子 网 (2) 分 别 写 出 六 个 子 网 的 网 络 号, 并 写 出 各 个 子 网 中 可 分 配 的 主 机 IP 地 址 范 围 2. (13 分 ) 现 有 五 个 站 分 别 连 接 在 三 个 局 域 网 上, 并 且 用 两 个 透 明 网 桥 连 接 起 来, 如 下 图 所 示 每 一 个 网 桥 的 两 个 端 口 号 都 标 明 在 图 上 B 1 B 2 1 2 1 2 H 1 H 2 H 3 H 4 H 5 M A C 1 M A C 2 M A C 3 M A C 4 M A C 5 在 一 开 始, 两 个 网 桥 中 的 转 发 表 都 是 空 的 以 后 有 以 下 各 站 向 其 他 的 站 发 送 了 数 据 帧, 发 送 顺 序 依 次 是 H1 发 送 给 H5,H3 发 送 给 H2,H4 发 送 给 H3,H2 发 送 给 H1 请 将 下 表 画 在 答 题 纸 上, 然 后 试 填 入 空 白 内 容 ( 处 理 方 式 可 填 写 的 内 容 有 : 登 记 并 转 发, 登 记 并 丢 弃, 转 发 不 登 记, 丢 弃 不 登 记, 接 收 不 到 此 帧 ) 12

发 送 的 帧 网 桥 1 的 转 发 表 网 桥 2 的 转 发 表 站 地 址 端 口 站 地 址 端 口 网 桥 1 的 处 理 方 式 网 桥 2 的 处 理 方 式 H1 H5 H3 H2 H4 H3 H2 H1 3. (13 分 ) 假 定 网 络 中 的 路 由 器 B 的 路 由 表 有 如 下 的 项 目 目 的 网 络 距 离 下 一 跳 路 由 器 N1 7 A N2 2 C N5 0 直 接 交 付 N6 8 F N7 9 F N8 4 E N9 4 F N12 10 E 现 在 B 收 到 从 C 发 来 的 路 由 信 息 : 目 的 网 络 距 离 N2 4 N3 8 N6 4 N8 3 N9 5 试 求 出 路 由 器 B 更 新 后 的 路 由 表 13