2013考研计算机学科专业基础综合真题及答案.pdf

《2013考研计算机学科专业基础综合真题及答案.pdf》由会员分享，可在线阅读，更多相关《2013考研计算机学科专业基础综合真题及答案.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 1 页 共 16 页2 0 1 3 考 研 计 算 机 学 科 专 业 基 础 综 合 真 题 及 答 案一、单 项 选 择 题：第 1 4 0 小 题，每 小 题 2 分，共 8 0 分。下 列 每 题 给 出 的 四 个 选 项中，只 有 一 个 选 项 最 符 合 试 题 要 求。1.已 知 两 个 长 度 分 别 为 m 和 n 的 升 序 链 表，若 将 它 们 合 并 为 一 个 长 度 为 m+n 的 降 序 链表，则 最 坏 情 况 下 的 时 间 复 杂 度 是（）。A O(n)B O(m n)C O(m i n(m,n)D O(m a x(m,n)2.一 个 栈 的 入

2、 栈 序 列 为1,2,3,n，其 出 栈 序 列 是p1,p2,p3,pn。若p23，则p3可 能 取 值 的 个 数 是（）。A n 3B n 2C n 1D 无 法 确 定3.若 将 关 键 字 1，2，3，4，5，6，7 依 次 插 入 到 初 始 为 空 的 平 衡 二 叉 树 T 中，则 T 中平 衡 因 子 为 0 的分 支 结 点 的 个 数 是（）。A 0 B 1 C 2 D 34.已 知 三 叉 树 T 中 6 个 叶 结 点 的 权 分 别 是 2，3，4，5，6，7，T 的 带 权（外 部）路 径长 度 最 小 是（）。A 2 7 B 4 6 C 5 4 D 5 65.

3、若 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 的 叙 述 中，正 确 的 是（）。第 2 页 共 16 页 ab

4、ec d f ghI.若v是 T 1 的 叶 结 点，则 T 1 与 T 3 不 同I I.若v是 T 1 的 叶 结 点，则 T 1 与 T 3相 同 I I I 若v不 是 T1的 叶 结 点，则 T1与 T 3 不 同 I V 若v不 是 T 1 的 叶 结 点，则 T1与 T3相 同A 仅 I、I I I B 仅 I、I V C 仅 I I、I I I D 仅 I I、I V 7 设 图 的 邻 接 矩 阵 A 如 下 所 示。各 顶 点 的 度 依 次 是（）。0 1 0 10 0 1 1A0 1 0 01 0 0 0A 1，2，1，2 B 2，2，1，1 C 3，4，2，3 D 4

5、，4，2，2 8 若 对 如 下 无 向 图 进 行 遍 历，则 下 列 选 项 中，不 是 广 度 优 先 遍 历 序 列 的 是（）。A h，c，a，b，d，e，g，f B e，a，f，g，b，h，c，dC d，b，c，a，h，e，f，g D a，b，c，d，h，e，f，g9 下 列 A O E 网 表 示 一 项 包 含 8 个 活 动 的 工 程。通 过 同 时 加 快 若 干 活 动 的 进 度 可 以 缩短 整 个 工 程 的 工期。下 列 选 项 中，加 快 其 进 度 就 可 以 缩 短 工 程 工 期 的 是（）。第 3 页 共 16 页A c 和 e B d 和 e C f

6、 和 d D f和 h 1 0 在 一 棵 高 度 为 2 的 5 阶 B 树 中，所 含 关 键 字 的 个 数 最 少 是（）。A 5 B 7 C 8 D 1 41 1 对 给 定 的 关 键 字 序 列 1 1 0，1 1 9，0 0 7，9 1 1，1 1 4，1 2 0，1 2 2 进 行 基 数 排 序，则 第 2趟 分 配 收 集 后 得到 的 关 键 字 序 列 是（）。A 0 0 7，1 1 0，1 1 9，1 1 4，9 1 1，1 2 0，1 2 2 B 0 0 7，1 1 0，1 1 9，1 1 4，9 1 1，1 2 2，1 2 0 C 0 0 7，1 1 0，9 1

7、 1，1 1 4，1 1 9，1 2 0，1 2 2 D 1 1 0，1 2 0，9 1 1，1 2 2，1 1 4，0 0 7，1 1 91 2.某 计 算 机 主 频 为 1.2 G H z，其 指 令 分 为 4 类，它 们 在 基 准 程 序 中 所 占 比 例 及 C P I 如下 表 所 示。指 令 类 型 所 占 比 例 C P IA 5 0%2B 2 0%3C 1 0%4D 2 0%5该 机 的 M I P S 数 是（）。A 1 0 0 B 2 0 0 C 4 0 0 D 6 0 01 3.某 数 采 用 I E E E 7 5 4 单 精 度 浮 点 数 格 式 表 示 为

8、 C 6 4 0 0 0 0 0 H，则 该 数 的 值 是（）。A-1.5 21 3B-1.5 21 2C-0.5 x 21 3D-0.5 21 21 4.某 字 长 为 8 位 的 计 算 机 中，已 知 整 型 变 量 x、y 的 机 器 数 分 别 为 x 补=1 1 1 1 0 1 0 0，y 补=10 1 1 0 0 0 0。若 整 型 变 量 z=2*x+y/2，则 z 的 机 器 数 为（）。A 1 1 0 0 0 0 0 0 B 0 0 1 0 0 1 0 0 C 1 0 1 0 1 0 1 0 D 溢 出1 5.用 海 明 码 对 长 度 为 8 位 的 数 据 进 行 检

9、/纠 错 时，若 能 纠 正 一 位 错。则 校 验 位 数 至 少 为第 4 页 共 16 页（）。A 2 B 3 C 4 D 51 6.某 计 算 机 主 存 地 址 空 间 大 小 为 2 5 6 M B，按 字 节 编 址。虚 拟 地 址 空 间 大 小 为 4 G B，采用 页 式 存 储 管理，页 面 大 小 为 4 K B，T L B（快 表）采 用 全 相 联 映 射，有 4 个 页 表 项，内 容 如 下 表 所 示。有 效 位 标 记 页 框 号 0 F F 1 8 0 H 0 0 0 2 H 1 3 F F F 1 H 0 0 3 5 H 0 0 2 F F 3 H 0

10、3 5 1 H 1 0 3 F F F H 0 1 5 3 H 则 对 虚 拟 地 址 0 3 F F F 1 8 0 H 进 行 虚 实 地 址 变 换 的 结 果 是（）。A 0 1 5 3 1 8 0 H B 0 0 3 5 1 8 0 H C T L B 缺 失 D 缺 页1 7.假 设 变 址 寄 存 器 R 的 内 容 为 1 0 0 0 H，指 令 中 的 形 式 地 址 为 2 0 0 0 H；地 址 1 0 0 0 H 中 的内 容 为2 0 0 0 H，地 址 2 0 0 0 H 中 的 内 容 为 3 0 0 0 H，地 址 3 0 0 0 H 中 的 内 容 为 4 0

11、 0 0 H，则 变 址 寻 址 方式 下 访 问 到 的 操 作 数 是（）。A 1 0 0 0 H B 2 0 0 0 H C 3 0 0 0 H D 4 0 0 0 H1 8.某 C P U 主 频 为 1.0 3 G H z，采 用 4 级 指 令 流 水 线，每 个 流 水 段 的 执 行 需 要 1 个 时 钟 周期。假 定 C P U执 行 了 1 0 0 条 指 令，在 其 执 行 过 程 中，没 有 发 生 任 何 流 水 线 阻 塞，此 时 流 水 线 的 吞 吐 率 为（）。A 0.2 5 1 09条 指 令/秒 B 0.9 7 1 09条 指 令/秒C 1.0 1 09

12、条 指 令/秒 D 1.0 3 1 09条 指 令/秒1 9.下 列 选 项 中，用 于 设 备 和 设 备 控 制 器（I/O 接 口）之 间 互 连 的 接 口 标 准 是（）。A P C I B U S B C A G P D P C I-E x p r e s s 2 0 下 列 选 项 中，用 于 提 高 R A I D 可 靠 性 的 措 施 有（）。I 磁 盘 镜 像 I I 条 带 化 I I I 奇 偶 校 验 I V 增 加 C a c h e 机 制A 仅 I、I I B 仅 I、I I IC 仅 I、I I I 和 I V D 仅 I I、I I I和 I V2 1 某

13、 磁 盘 的 转 速 为 1 0 0 0 0 转/分，平 均 寻 道 时 间 是 6 m s，磁 盘 传 输 速 率 是 2 0 M B/s，磁 盘 控 制 器 延 迟为 0.2 m s，读 取 一 个 4 K B 的 扇 区 所 需 的 平 均 时 间 约 为（）。A 9 m s B 9.4 m s C 1 2 m s D 1 2.4第 5 页 共 16 页9 0用 户 工 作 区5系 统 缓 冲 区1 0 0外 设m s 2 2 下 列 关 于 中 断 I/O 方 式 和 D M A 方 式 比 较 的 叙 述 中，错 误 的 是（）。A.中 断 I/O 方 式 请 求 的 是 C P U

14、 处 理 时 间，D M A 方 式 请 求 的 是 总 线 使 用 权B.中 断 响 应 发 生 在 一 条 指 令 执 行 结 束 后，D M A 响 应 发 生 在 一 个 总 线 事 务 完 成 后C.中 断 I/O 方 式 下 数 据 传 送 通 过 软 件 完 成，D M A 方 式 下 数 据 传 送 由 硬 件 完 成D.中 断 I/O 方 式 适 用 于 所 有 外 部 设 备，D M A 方 式 仅 适 用 于 快 速 外 部 设 备2 3.用 户 在 删 除 某 文 件 的 过 程 中，操 作 系 统 不 可 能 执 行 的 操 作 是（）。A 删 除 此 文 件 所 在

15、 的 目 录 B 删 除 与 此 文 件 关 联 的 目 录 项C 删 除 与 此 文 件 对 应 的 文 件 控 制 块 D 释 放 与 此 文 件 关 联 的 内 存 级 冲区2 4.为 支 持 C D-R O M 中 视 频 文 件 的 快 速 随 机 播 放，播 放 性 能 最 好 的 文 件 数 据 块 组 织 方 式 是（）。A 连 续 结 构 B 链 式 结 构 C 直 接 索 引 结 构 D 多级 索 引 结 钩2 5.用 户 程 序 发 出 磁 盘 I/O 请 求 后，系 统 的 处 理 流 程 是：用 户 程 序 系 统 调 用 处 理 程 序 设 备 骆 动 程 序 中

16、断 处 理 程 序。其 中，计 算 数 据 所 在 磁 盘 的 柱 面 号、磁 头 号、扇 区 号 的 程序 是（）。A 用 户 程 序 B 系 统 调 用 处 理 程 序C 设 备 驱 动 程 序 D 中 断 处 理 程 序2 6.若 某 文 件 系 统 索 引 结 点（i n o d e）中 有 直 接 地 址 项 和 间 接 地 址 项，则 下 列 选 项 中，与 单个 文 件 长 度无 关 的 因 素 是（）。A 索 引 结 点 的 总 数 B 间 接 地 址 索 引 的 级 数C 地 址 项 的 个 数 D 文 件 块 大 小2 7.设 系 统 缓 冲 区 和 用 户 工 作 区 均

17、 采 用 单 缓 冲，从 外 设 读 入 1 个 数 据 块 到 系 统 缓 冲 区 的时 间 为 1 0 0，从系 统 缓 冲 区 读 入 1 个 数 据 块 到 用 户 工 作 区 的 时 间 为 5，对 用 户 工 作 区 中 的 1 个 数 据 块 进 行 分析 的 时 间 为 9 0（如 下 图 所 示）。进 程 从 外 设 读 入 并 分 析 2 个 数 据 块 的 最 短 时 间 是（）。第 6 页 共 16 页A.2 0 0 B.2 9 5 C.3 0 0 D.3 9 02 8.下 列 选 项 中，会 导 致 用 户 进 程 从 用 户 态 切 换 到 内 核 态 的 操 作

18、是（）。I 整 数 除 以 零 I I s i n（）函 数 调 用 I I I r e a d 系 统 调 用A 仅 I、I I B 仅 I、I I I C 仅 I I、I I I D I、I I 和 I I I2 9.计 算 机 开 机 后，操 作 系 统 最 终 被 加 载 到（）。A.B I O S B R O M C E P R O M D R A M3 0.若 用 户 进 程 访 问 内 存 时 产 生 缺 页，则 下 列 选 项 中，操 作 系 统 可 能 执 行 的 操 作 是（）。I 处 理 越 界 错 I I 置 换 页 I I I 分 配 内 存A 仅 I、I I B 仅

19、 I I、I I I C 仅 I、I I I D I、I I和 I I I 3 1 某 系 统 正 在 执 行 三 个 进 程 P 1、P 2 和 P 3，各 进 程 的 计 算（C P U）时 间 和 I/O时 间 比 例 如 下 表 所 示。进 程 计 算 时 间 I/O 时 间P 1 9 0%1 0%P 2 5 0%5 0%P 3 1 5%8 5%为 提 高 系 统 资 源 利 用 率，合 理 的 进 程 优 先 级 设 置 应 为（）。A P 1 P 2 P 3 B P 3 P 2 P 1 C P 2 P 1=P 3 D P 1 P 2=P 33 2.下 列 关 于 银 行 家 算 法

20、 的 叙 述 中，正 确 的 是（）。A.银 行 家 算 法 可 以 预 防 死 锁B.当 系 统 处 于 安 全 状 态 时，系 统 中 一 定 无 死 锁 进 程C.当 系 统 处 于 不 安 全 状 态 时，系 统 中 一 定 会 出 现 死 锁 进 程D 银 行 家 算 法 破 坏 了 死 锁 必 要 条 件 中 的“请 求 和 保 持”条件3 3.在 O S I 参 考 摸 型 中，下 列 功 能 需 由 应 用 层 的 相 邻 层 实 现 的 是（）。A 对 话 管 理 B 数 据 格 式 转 换 C 路 由 选 择 D 可 靠 数 据 传输 3 4 若 下 图 为 1 0 B a

21、 s e T 网 卡 接 收 到 的 信 号 波 形，则 该 网 卡 收 到 的 比 特 串 是（）。A 0 0 1 1 0 1 1 0 B 1 0 1 0 1 1 0 1 C 0 1 0 1 0 0 1 0 D 1 1 0 0 0 1 0 13 5 主 机 甲 通 过 1 个 路 由 器（存 储 转 发 方 式）与 主 机 乙 互 联，两 段 链 路 的 数 据 传 输 速 率 均 为1 0第 7 页 共 16 页M b p s，主 机 甲 分 别 采 用 报 文 交 换 和 分 组 大 小 为 1 0 k b 的 分 组 交 换 向 主 机 乙 发 送 1 个 大 小为 8 M b（1 M

22、=1 06）的 报 文。.若 忽 略 链 路 传 播 延 迟、分 组 头 开 销 和 分 组 拆 装 时 间，则 两 种交 换 方 式 完 成 该 报 文 传 输 所 需 的 总 时 间 分 别 为（）。A 8 0 0 m s、1 6 0 0 m s B 8 0 1 m s、1 6 0 0 m sC 1 6 0 0 m s、8 0 0 m s D 1 6 0 0 m s、8 0 1m s 3 6 下 列 介 质 访 问 控 制 方 法 中，可 能 发 生 冲 突 的 是（）。A.C D M A B C S M A C T D M A D F D M A3 7.H D L C 协 议 对 0 1

23、 1 1 1 1 0 0 0 1 1 1 1 1 1 0 组 帧 后 对 应 的 比 特 串 为（）。A 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 B 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0C 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 D 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 13 8.对 于 1 0 0 M b p s 的 以 太 网 交 换 机，当 输 出 端 口 无 排 队，以 直 通 交 换（c u t-t h r o u

24、 g hs w i t c h i n g）方 式 转 发一 个 以 太 网 帧（不 包 括 前 导 码）时，引 入 的 转 发 延 迟 至 少 是（）。A 0 s B 0.4 8 s C 5.1 2 s D 1 2 1.4 4 s3 9 主 机 甲 与 主 机 乙 之 间 已 建 立 一 个 T C P 连 接，双 方 持 续 有 数 据 传 输，且 数 据 无 差 错 与丢 失。若 甲 收到 1 个 来 自 乙 的 T C P 段，该 段 的 序 号 为 1 9 1 3、确 认 序 号 为 2 0 4 6、有 效 载 荷 为 1 0 0 字 节，则 甲 立 即 发 送 给 乙 的 T C

25、P 段 的 序 号 和 确 认 序 号 分 别 是（）。A 2 0 4 6、2 0 1 2 B 2 0 4 6、2 0 1 3 C 2 0 4 7、2 0 1 2 D 2 0 4 7、2 0 1 34 0.下 列 关 于 S M T P 协 议 的 叙 述 中，正 确 的 是（）。I.只 支 持 传 输 7 比 特 A S C I I 码 内容 I I 支 持 在 邮 件 服 务 器 之 间 发 送 邮 件I I I 支 持 从 用 户 代 理 向 邮 件 服 务 器 发 送邮 件 I V 支 持 从 邮 件 服 务 器 向 用 户 代 理 发送 邮 件A 仅 I、I I 和 I I I B

26、仅 I、I I 和 I VC 仅 I、I I I 和 I V D 仅 I I、I I I 和 I V二、综 合 应 用 题：4 1 4 7 小 题，共 7 0 分。请 将 答 案 写 在 答 题 纸 指 定 位 置 上。4 1（1 3 分）已 知 一 个 整 数 序 列A(a0,a1,an 1)，其 中0 ain(0 in)。若 存 在ap 1ap 2ap mx且m n/2(0 pkn,1 k m)，则 称 x 为 A的 主 元 素。例 如A=(0，5，5，3，5，7，5，5)，侧 5 为 主 元 素；又 如 A=(0，5，5，3，5，1，5，7)，则 A 中 没 有 主 元 素。假 设 A

27、中 的 n 个 元 素 保 存 在 一 个 一 维 数 组 中，请 设 计 一 个 尽 可第 8 页 共 16 页能 高 效 的 算 法，找 出 A 的 主 元 素。若 存 在 主 元 素，则 输 出 该 元 素；否 则 输 出-1。要 求：（1）给 出 算 法 的 基 本 设 计 思 想。（2）根 据 设 计 思 想，采 用 C 或 C+或 J a v a 语 言 描 述 算 法，关 键 之 处 给 出 注 释。（3）说 明 你 所 设 计 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度。4 2（1 0 分）设 包 含 4 个 数 据 元 素 的 集 合 S=d o，f o r，r

28、e p e a t，w h i l e，各元 素 的 查 找 概 率 依次 为：p 1=0.3 5，p 2=0.1 5，p 3=0.1 5，p 4=0.3 5。将 S 保 存 在 一 个 长 度 为 4 的 顺 序 表中，采 用 折 半 查 找 法，查 找 成 功 时 的 平 均 查 找 长 度 为 2.2。请 回 答：（1）若 采 用 顺 序 存 储 结 构 保 存 S，且 要 求 平 均 查 找 长 度 更 短，则 元 素 应 如 何 排 列？应使 用 何 种 查 找 方 法？查 找 成 功 时 的 平 均 查 找 长 度 是 多 少？（2）若 采 用 链 式 存 储 结 构 保 存 S，

29、且 要 求 平 均 查 找 长 度 更 短，则 元 素 应 如 何 排 列？应使 用 何 种 查 找 方 法？查 找 成 功 时 的 平 均 查 找 长 度 是 多 少？4 3（9 分）某 3 2 位 计 算 机，C P U 主 频 为 8 0 0 M H z，C a c h e 命 中 时 的 C P I 为 4，C a c h e 块大 小 为 3 2 字节；主 存 采 用 8 体 交 叉 存 储 方 式，每 个 体 的 存 储 字 长 为 3 2 位、存 储 周 期 为 4 0 n s；存 储 器 总线 宽 度 为 3 2 位，总 线 时 钟 频 率 为 2 0 0 M H z，支 持

30、突 发 传 送 总 线 事 务。每 次 读 突 发 传 送 总 线事 务 的 过 程 包 括：送 首 地 址 和 命 令、存 储 器 准 备 数 据、传 送 数 据。每 次 突 发 传 送 3 2 字 节，传 送 地 址 或 3 2 位 数 据 均 需 要 一 个 总 线 时 钟 周 期。请 回 答 下 列 问 题，要 求 给 出 理 由 或 计算 过 程。（1）C P U 和 总 线 的 时 钟 周 期 各 为 多 少？总 线 的 带 宽（即 最 大 数 据 传 输 率）为 多 少？（2）C a c h e 缺 失 时，需 要 用 几 个 读 突 发 传 送 总 线 事 务 来 完 成 一

31、个 主 存 块 的 读 取？（3）存 储 器 总 线 完 成 一 次 读 突 发 传 送 总 线 事 务 所 需 的 时 间 是 多 少？（4）若 程 序 B P 执 行 过 程 中，共 执 行 了 1 0 0 条 指 令，平 均 每 条 指 令 需 进 行 1.2 次 访 存，C a c h e缺 失 率 为 5%，不 考 虑 替 换 等 开 销，则 B P 的 C P U 执 行 时 间 是 多 少？4 4（1 4 分）某 计 算 机 采 用 1 6 位 定 长 指 令 字 格 式，其 C P U 中 有 一 个 标 志 寄 存 器，其 中包 含 进 位/借 位标 志 C F、零 标 志

32、Z F 和 符 号 标 志 N F。假 定 为 该 机 设 计 了 条 件 转 移 指 令，其 格 式 如 下：1 5 1 1 1 0 9 8 7 00 0 0 0 0 C Z N O F F S E T其 中，0 0 0 0 0 为 操 作 码 O P；C、Z 和 N 分 别 为 C F、Z F 和 N F 的 对 应 检 测 位，某 检 测 位 为1 时 表 示 需 检 测 对 应 标 志，需 检 测 的 标 志 位 中 只 要 有 一 个 为 1 就 转 移，否 则 不 转 移，例 如，若 C=1，Z=0，N=1，则 需 检 测 C F 和 N F 的 值，当 C F=1 或 N F=1

33、 时 发 生 转 移；O F F S E T 是 相对 偏 移 量，用 补 码 表 示。转 移 执 行 时，转 移 目 标 地 址 为（P C）+2+2 O F F S E T；顺 序 执 行 时，下 条 指 令 地 址 为（P C）+2。请 回 答 下 列 问 题。（1）该 计 算 机 存 储 器 按 字 节 编 址 还 是 按 字 编 址？该 条 件 转 移 指 令 向 后（反 向）最 多 可 跳 转第 9 页 共 16 页标 志 寄 存 器O P C Z N符 号 扩 展 器多 路 选 择多 少 条 指 令？（2）某 条 件 转 移 指 令 的 地 址 为 2 0 0 C H，指 令 内

34、 容 如 下 图 所 示，若 该 指 令 执 行 时 C F=0，Z F=0，N F=1，则 该 指 令 执 行 后 P C 的 值 是 多 少？若 该 指 令 执 行 时 C F=1，Z F=0，N F=0，则 该 指 令 执行 后 P C 的 值 又 是 多 少？请 给 出 计 算 过 程。1 5 1 1 1 0 9 8 7 00 0 0 0 0 0 1 1 1 1 1 0 0 0 11（3）实 现“无 符 号 数 比 较 小 于 等 于 时 转 移”功 能 的 指 令 中，C、Z 和 N 应 各 是 什 么？（4）以 下 是 该 指 令 对 应 的 数 据 通 路 示 意 图，要 求 给

35、 出 图 中 部 件 的 名 称 或 功 能 说 明。2P C加 法 器器4 5（7 分）某 博 物 馆 最 多 可 容 纳 5 0 0 人 同 时 参 观，有 一 个 出 入 口，该 出 入 口 一 次 仅 允许 一 个 人 通 过。参 观 者 的 活 动 描 述 如 下：c o b e g i n参 观 者 进 程 i：进 门；参 观；出 门；第 1 0 页 共 16 页物 理 地 址 3物 理 地 址 2物 理 地 址 10 0 9 0 0 0 0 0 H0 0 2 0 0 0 0 0 H页 框 号 2页 框 号 1代 码 页 面 2代 码 页 面 1c o e n d请 添 加 必 要

36、 的 信 号 量 和 P、V（或 w a i t（）、s i g n a l（）操 作，以 实 现 上 述 过 程 中 的 互斥 与 同 步。要 求 写 出 完 整 的 过 程，说 明 信 号 量 的 含 义 并 赋 初 值。4 6（8 分）某 计 算 机 主 存 按 字 节 编 址，逻 辑 地 址 和 物 理 地 址 都 是 3 2 位，页 表 项 大 小 为4 字 节。请 回 答 下 列 问 题。（1）若 使 用 一 级 页 表 的 分 页 存 储 管 理 方 式，逻 辑 地 址 结 构 为：页 号（2 0 位）页 内 偏 移 量（1 2 位）则 页 的 大 小 是 多 少 字 节？页 表

37、 最 大 占 用 多 少 字 节？（2）若 使 用 二 级 页 表 的 分 页 存 储 管 理 方 式，逻 辑 地 址 结 构 为：页 目 录 号（1 0 位）页 表 索 引（1 0 位）页 内 偏 移 量（1 2 位）设 逻 辑 地 址 为 L A，请 分 别 给 出 其 对 应 的 页 目 录 号 和 页 表 索 引 的 表 达 式。（3）采 用（1）中 的 分 页 存 储 管 理 方 式，一 个 代 码 段 起 始 逻 辑 地 址 为 0 0 0 0 8 0 0 0 H，其 长 度 为8 K B，被 装 载 到 从 物 理 地 址 0 0 9 0 0 0 0 0 H 开 始 的 连 续

38、主 存 空 间 中。页 表 从 主 存 0 0 2 0 0 0 0 0 H开 始 的 物 理 地 址 处 连 续 存 放，如 下 图 所 示（地 址 大 小 自 下 向 上 递 增）。请 计 算 出 该 代 码 段对 应 的 两 个 页 表 项 的 物 理 地 址、这 两 个 页 表 项 中 的 页 框 号 以 及 代 码 页 面 2 的 起 始 物 理 地址。页 表AS 1R1 1 5 3.1 4.5.0/2 51 5 3.1 4.5.12 8/2 51 5 3.1 4.3.2R2SOEO1 9 4.1 7.2 0.1 2 8/2S11 5 3.1 4.3.2AS 2R31 9 4.1 7.

39、2 4.21 9 4.1 7.2 0.0/2 51 9 4.1 7.2 1.0/2 4第 1 1 页 共 16 页4 7（9 分）假 设 I n t e r n e t 的 两 个 自 治 系 统 构 成 的 网 络 如 题 4 7 图 所 示，自 治 系 统 A S I 由 路 由 器R 1 连 接 两 个 子 网 构 成；自 治 系 统 A S 2 由 路 由 器 R 2、R 3 互 联 并 连 接 3 个 子 网 构 成。各 子 网 地 址、R 2 的 接 口 名、R 1 与 R 3 的 部 分 接 口 I P 地 址 如 题 4 7 图 所 示。题 4 7 图 网 络 拓 扑结 构 请

40、 回 答 下 列 问 题。（1）假 设 路 由 表 结 构 如 下 表 所 示。请 利 用 路 由 聚 合 技 术，给 出 R 2 的 路 由 表，要 求 包 括 到达 题 4 7 图 中 所 有 子 网 的 路 由，且 路 由 表 中 的 路 由 项 尽 可 能 少。（2）若 R 2 收 到 一 个 目 的 I P 地 址 为 1 9 4.1 7.2 0.2 0 0 的 I P 分 组，R 2 会 通 过 哪 个 接 口 转 发 该 I P分 组？（3）R 1 与 R 2 之 间 利 用 哪 个 路 由 协 议 交 换 路 由 信 息？该 路 由 协 议 的 报 文 被 封 装 到 哪 个协

41、 议 的 分 组 中 进 行 传 输参 考 答 案一、单 项 选 择 题：每 小 题 2 分，共 8 0 分。1 D 2 C 3 D 4 B 5 A6 C 7 C 8 D 9 C 1 0 A1 1 C 1 2 C 1 3 A 1 4 A 1 5 C1 6 A 1 7 D 1 8 C 1 9 B 2 0 B2 1 B 2 2 D 2 3 A 2 4 A 2 5 C2 6 A 2 7 C 2 8 B 2 9 D 3 0 B3 1 B 3 2 B 3 3 B 3 4 A 3 5 D3 6 B 3 7 A 3 8 B 3 9 B 4 0 A二、综 合 应 用 题：4 1 4 7 小 题，共 7 0 分

42、。4 1.【答 案 要 点】（1）给 出 算 法 的 基 本 设 计 思 想：（4 分）算 法 的 策 略 是 从 前 向 后 扫 描 数 组 元 素，标 记 出 一 个 可 能 成 为 主 元 素 的 元 素 N u m。然 后 重新 计 数，确 认 N u m 是 否 是 主 元 素。算 法 可 分 为 以 下 两 步：选 取 候 选 的 主 元 素：依 次 扫 描 所 给 数 组 中 的 每 个 整 数，将 第 一 个 遇 到 的 整 数 N u m 保 存 到目 的 网 络 下 一 跳 接 口第 1 2 页 共 16 页c 中，记 录 N u m 的 出 现 次 数 为 1；若 遇 到

43、 的 下 一 个 整 数 仍 等 于 N u m，则 计 数 加 1，否 则 计 数 减1；当 计 数 减 到 0 时，将 遇 到 的 下 一 个 整 数 保 存 到 c 中，计 数 重 新 记 为 1，开 始 新 一 轮 计 数，即 从 当 前 位 置 开 始 重 复 上 述 过 程，直 到 扫 描 完 全 部 数 组 元 素。判 断 c 中 元 素 是 否 是 真 正 的 主 元 素：再 次 扫 描 该 数 组，统 计 c 中 元 素 出 现 的 次 数，若 大 于 n/2，则 为 主 元 素；否 则，序 列 中 不 存 在 主 元 素。（2）算 法 实 现：（7 分）i n t M a

44、j o r i t y(i n t A,i n t n)i n t i,c,c o u n t=1;/c 用 来 保 存 候 选 主 元 素，c o u n t 用 来 计 数c=A 0;/设 置 A 0 为 候 选 主 元 素f o r(i=1;i 0)/处 理 不 是 候 选 主 元 素 的 情 况e l s e/更 换 候 选 主 元 素，重 新 计 数 c=A i;c o u n t=1;i f(c o u n t 0)f o r(i=c o u n t=0;i n/2)r e t u r n c;/确 认 候 选 主 元 素e l s e r e t u r n-1;/不 存 在 主

45、 元 素【（1）、（2）的 评 分 说 明】若 考 生 设 计 的 算 法 满 足 题 目 的 功 能 要 求 且 正 确，则（1）、（2）根 据 所 实 现 算 法 的 效 率 给分，细 则 见 下 表：时 间复 杂 度空 间复 杂 度（1）得 分（2）得 分说 明O(n)O(1)4 7O(n)O(n)4 6如 采 用 计 数 排 序 思 想，见 表 后 M a j o r i t y 1程序O(n l o g 2 n)其 他 3 6 如 采 用 其 他 排 序 的 思 想第 1 3 页 共 16 页 O(n2)其 他 3 5 其 他 方 法i n t M a j o r i t y 1(i

46、 n t A,i n t n)/采 用 计 数 排 序 思 想，时 间：O(n),空 间：O(n)i n t k,*p,m a x;p=(i n t*)m a l l o c(s i z e o f(i n t)*n);/申请 辅 助 计 数 数 组 f o r(k=0;k n;k+)p k=0;/计数 数 组 初 始 化 为 0 m a x=0;f o r(k=0;k p m a x)m a x=A k;/记 录 出 现 次 数 最 多 的 元 素i f(p m a x n/2)r e t u r n m a x;e l s e r e t u r n-1;若 在 算 法 的 基 本 设 计

47、 思 想 描 述 中 因 文 字 表 达 没 有 非 常 清 晰 反 映 出 算 法 思 路，但 在 算 法 实现 中 能 够 清 晰 看 出 算 法 思 想 且 正 确 的，可 参 照 的 标 准 给 分。若 算 法 的 基 本 设 计 思 想 描 述 或 算 法 实 现 中 部 分 正 确，可 参 照 中 各 种 情 况 的 相 应 给 分 标准 酌 情 给 分。参 考 答 案 中 只 给 出 了 使 用 C 语 言 的 版 本，使 用 C+或 J a v a 语 言 的 答 案 视 同 使 用 C 语 言。（3）说 明 算 法 复 杂 性：（2 分）参 考 答 案 中 实 现 的 程 序

48、 的 时 间 复 杂 度 为 O（n），空 间 复 杂 度 为 O（1）。【评 分 说 明】若 考 生 所 估 计 的 时 间 复 杂 度 与 空 间 复 杂 度 与 考 生 所 实 现 的 算 法 一 致，可 各给 1 分。4 2.【答 案 要 点】（1）采 用 顺 序 存 储 结 构，数 据 元 素 按 其 查 找 概 率 降 序 排 列。（2 分）采 用 顺 序 查 找 方 法。（1 分）查 找 成 功 时 的 平 均 查 找 长 度=0.3 5 1+0.3 5 2+0.1 5 3+0.1 5 4=2.1。（2 分）（2）【答 案 一】采 用 链 式 存 储 结 构，数 据 元 素 按

49、其 查 找 概 率 降 序 排 列，构 成 单 链 表。（2 分）采 用 顺 序 查 找 方 法。（1 分）查 找 成 功 时 的 平 均 查 找 长 度=0.3 5 1+0.3 5 2+0.1 5 3+0.1 5 4=2.1。（2 分）【答 案 二】采 用 二 叉 链 表 存 储 结 构，构 造 二 叉 排 序 树，元 素 存 储 方 式 见 下 图。（2 分）r e p e a或d ow h i lf o r第 1 4 页 共 16 页f o rd ow h i lr e p e a二 叉 排 序 树 1二 叉 排 序 树 2采 用 二 叉 排 序 树 的 查 找 方 法。（1 分）查 找

50、 成 功 时 的 平 均 查 找 长 度=0.1 5 1+0.3 5 2+0.3 5 2+0.1 5 3=2.0。（2 分）【（1）、（2）的 评 分 说 明】若 考 生 以 实 际 元 素 表 示“降 序 排 列”，同 样 给 分。若 考 生 正 确 求 出 与 其 查 找 方 法 对 应 的 查 找 成 功 时 的 平 均 查 找 长 度，给 2 分；若 计 算 过程 正 确，但 结 果 错 误，给 1 分。若 考 生 给 出 其 他 更 高 效 的 查 找 方 法 且 正 确，可 参 照 评 分 标 准 给 分。4 3.【答 案 要 点】（1）C P U 的 时 钟 周 期 为：1/8