资源描述
2020 年 招 收 攻 读 硕 士 学 位 研 究 生 入 学 考 试 试 题 （ B）*招 生 专 业 与 代 码 ： 计 算 机 系 统 结 构 081201、 计 算 机 软 件 与 理 论 081202、 计 算 机 应 用 技 术081203、 电 子 信 息 (专 业 学 位 ) 085400考 试 科 目 名 称 及 代 码 ： 计 算 机 基 础 综 合 848考 生 注 意 ： 所 有 答 案 必 须 写 在 答 题 纸 （ 卷 ） 上 ， 写 在 本 试 题 上 一 律 不 给 分 。第 一 部 分 数 据 结 构 （ 75 分 ）一 、 单 项 选 择 题 (每 题 2 分 ， 共 20 分 )1. 含 有 m 个 结 点 的 二 叉 树 链 式 存 储 结 构 中 空 指 针 的 个 数 为 ( )。A 2m B m-1 C m+1 D m2. 下 列 排 序 算 法 中 元 素 的 移 动 次 数 和 关 键 字 的 初 始 排 列 次 序 无 关 的 是 （ ） 。A. 快 速 排 序 B. 插 入 排 序 C. 选 择 排 序 D. 希 尔 排 序3. 一 个 栈 的 进 栈 序 列 是 a b c d e， 则 栈 的 输 出 序 列 不 可 能 的 是 （ ） 。 A a b c d e B e d c b a C d e c b a D d c e a b4. 需 要 的 辅 助 空 间 最 多 的 排 序 算 法 为 （ ） 。A. 归 并 排 序 B. 快 速 排 序C. 基 数 排 序 D. 堆 排 序5. 哈 希 表 的 平 均 查 找 长 度 说 法 错 误 的 是 ( )。A. 与 处 理 冲 突 方 法 有 关 而 与 表 的 长 度 无 关B. 与 选 用 的 哈 希 函 数 有 关C. 与 哈 希 表 的 饱 和 程 度 有 关D. 与 表 中 填 入 的 记 录 数 有 关6. 有 n 个 顶 点 、 e条 边 且 使 用 了 邻 接 表 存 储 的 有 向 图 进 行 深 度 优 先 遍 历 ， 其 算 法 的 时 间 复 杂 度 是（ ） 。A. O（ n+e） B. O（ n 2） C. O（ n+2e） D. O（ n*e）7. 已 知 一 个 长 度 为 11 的 顺 序 表 ， 其 元 素 按 关 键 字 有 序 排 列 ， 若 采 用 折 半 查 找 查 找 一 个 其 中 不 存存 在 的 元 素 ， 则 关 键 字 的 比 较 次 数 最 多 是 （ ） 。A 3 B 4 C 5 D 68. 一 棵 完 全 二 叉 树 上 有 3001个 结 点 ， 其 中 叶 子 结 点 的 个 数 是 （ ） 。A. 1500 B.1501 C. 1000 D.10019. 若 一 棵 二 叉 树 度 为 2 的 结 点 有 18 个 ， 度 为 1的 结 点 有 10 个 ， 则 度 为 0 的 结 点 个 数 是 （ ） 。A. 46 B. 28 C. 19 D. 1710. m阶 B-树 是 一 棵 （ ） 。A .m叉 排 序 树 B. m-1 叉 平 衡 排 序 树 C. m叉 平 衡 排 序 树 D. m+1 叉 平 衡 排 序 树二 、 填 空 题 (每 空 2 分 ， 共 14 分 ) 1. 已 知 一 棵 二 叉 树 的 中 序 遍 历 序 列 为 GDHBAECIF， 后 序 遍 历 序 列 为 GHDBEIFCA， 那 么 先 序 遍 历 序 序列 为 。2. 若 某 记 录 的 关 键 字 序 列 是 （ 491， 77， 572， 16， 996， 101， 863， 258， 689， 325） ， 以 第 一个 关 键 字 为 枢 轴 ， 写 出 采 用 快 速 排 序 算 法 第 一 趟 排 序 的 结 果 。考 试 科 目 ： 计 算 机 基 础 综 合 共 4 页 ， 第 1 页 3. 将 对 称 矩 阵 A88的 下 三 角 部 分 逐 行 存 储 到 起 始 地 址 为 2000 的 内 存 单 元 中 ， 已 知 每 个 元素 占 4 个 单 元 ， 假 设 第 一 个 元 素 是 A00， 则 A46的 地 址 是 。4. 在 顺 序 表 中 插 入 一 个 元 素 ， 需 要 平 均 移 动 表 中 一 半 元 素 ， 具 体 移 动 元 素 的 个 数 与有 关 。5.在 哈 希 查 找 方 法 中 ， 要 解 决 两 方 面 的 问 题 ， 它 们 是 和 。6. 循 环 队 列 中 ， Q.rear = Q.front表 示 循 环 队 列 空 ， 表 示 循 环 队 列 满 的 条 件 是 。三 、 简 答 题 （ 共 3 小 题 ， 每 题 7 分 ， 共 21 分 ）1. 将 下 面 的 森 林 转 换 为 二 叉 树 （ 3分 ） ， 并 给 出 该 二 叉 树 的 中 序 线 索 链 表 （ 4 分 ） 。 2. 设 Huffman 编 码 的 长 度 不 超 过 4， 若 已 对 两 个 字 符 编 码 为 01和 11， 则 最 多 还 可 以 对 多 少 个字 符 编 码 ， 为 什 么 ？ (7分 ）3. 假 设 图 的 顶 点 是 A、 B、 C、 D、 E， 请 根 据 下 面 的 邻 接 矩 阵 画 出 相 应 的 有 向 图 （ 3 分 ） ， 然 后画 出 图 的 邻 接 表 和 逆 邻 接 表 （ 4 分 ） 。 01010 00001 10001 01000 00110 四 、 编 写 算 法 （ 共 2 小 题 ， 每 题 10 分 ， 共 20 分 ）1. 试 编 写 一 个 算 法 完 成 下 面 的 功 能 ： 对 于 输 入 的 任 意 一 个 非 负 十 进 制 整 数 ， 输 出 与 其 等 值 的八 进 制 数 。 （ 10分 ）2. 试 编 写 一 个 算 法 ， 在 有 向 图 G 中 ， 判 定 从 顶 点 Vi到 顶 点 Vj是 否 有 通 路 。 （ 10分 ）第 二 部 分 操 作 系 统 （ 75 分 ）五 、 判 断 题 (每 小 题 1 分 ， 共 10 分 ， 正 确 的 打 ， 错 误 的 打 )1. 系 统 调 用 中 的 被 调 用 程 序 运 行 在 系 统 态 。2. 银 行 家 算 法 采 用 了 死 锁 预 防 的 方 法 。3. 文 件 系 统 采 用 树 形 目 录 结 构 可 以 节 省 内 存 空 间 。4. 虚 存 管 理 允 许 用 户 程 序 大 于 主 存 容 量 ， 而 且 还 可 以 提 高 系 统 的 吞 吐 量 。5. SPOOLing 系 统 实 现 了 设 备 的 独 立 性 。 AB CD E F GH 考 试 科 目 ： 计 算 机 基 础 综 合 共 4 页 ， 第 2 页 6. 分 时 系 统 的 时 间 片 越 小 ， 用 户 的 满 意 度 就 越 高 。7. 管 程 每 次 只 允 许 一 个 进 程 进 入 。8. 操 作 系 统 既 可 看 作 虚 拟 机 ， 也 可 看 作 资 源 管 理 器 。9. 在 作 业 调 度 时 ， 采 用 最 高 响 应 比 优 先 的 作 业 调 度 算 法 可 以 得 到 最 短 的 作 业 平 均 周 转 时 间 。10. 并 行 程 序 设 计 中 ， 使 用 信 号 量 比 使 用 管 程 更 能 保 证 程 序 的 正 确 性 。六 、 填 空 题 (每 小 题 1 分 ， 共 10 分 )1. 对 于 速 率 为 9.6KB/s 的 数 据 通 信 而 言 ， 如 果 设 置 一 个 具 有 8 位 的 缓 冲 寄 存 器 ， 则 CPU 中 断时 间 和 响 应 时 间 分 别 大 约 为 （ 1） 、 （ 2） 。2. 如 果 计 算 机 连 接 了 三 个 同 类 型 的 激 光 打 印 机 及 五 个 同 类 型 的 喷 墨 打 印 机 ， 需 要 安 装 的 驱 动程 序 数 目 是 （ 3） 。3. 在 具 有 n 个 进 程 的 系 统 中 ， 允 许 m个 进 程 (n m 1)同 时 进 入 它 们 的 临 界 区 ， 其 信 号 量 S的值 的 变 化 范 围 是 （ 4） ， 处 于 等 待 状 态 的 进 程 数 最 多 有 （ 5） 个 。 4. 动 态 分 区 的 （ 6） 算 法 可 以 使 内 存 中 的 空 闲 分 区 分 布 得 更 均 匀 。5. UNIX的 目 录 项 由 文 件 名 和 （ 7） 构 成 。6. 若 干 事 件 在 同 一 时 间 间 隔 内 发 生 称 为 （ 8） 。7. 虚 拟 存 储 器 具 有 （ 9） 、 （ 10） 和 虚 拟 性 三 大 特 征 。七 、 单 选 题 (每 小 题 1 分 ， 共 10 分 )1. 请 求 调 页 系 统 中 ， 如 下 算 法 中 ， ( ) 淘 汰 自 上 次 访 问 以 来 经 历 时 间 最 长 的 页 面 。A. FIFO B. OPT C. NRU D. LRU2. 下 列 进 程 调 度 算 法 中 ， ( ) 可 能 会 出 现 进 程 长 期 得 不 到 调 度 的 情 况 。A. 静 态 优 先 权 法 B. 抢 占 式 调 度 中 采 用 动 态 优 先 权 法C. 分 时 处 理 中 的 时 间 片 轮 转 调 度 算 法 D. 非 抢 占 式 调 度 中 采 用 FIFO 算 法3. 分 时 系 统 中 ， CPU进 程 切 换 需 要 3ms， 为 使 得 100 个 用 户 均 能 在 1 秒 内 得 到 响 应 ， 可 以 选 择 的 时 间 片 是 （ ） 。A. 2ms B. 50 ms C. 10ms D. 7 ms4. 磁 盘 的 I/O 控 制 主 要 采 取 ( ) 方 式 。A. 程 序 I/O B. 中 断 C. DMA D. SPOOLing5. 系 统 产 生 死 锁 是 指 ( ) 。A. 系 统 发 生 重 大 故 障B. 若 干 进 程 同 时 处 于 阻 塞 状 态C. 请 求 的 资 源 数 大 于 系 统 提 供 的 资 源 数D. 若 干 进 程 等 待 被 其 他 进 程 所 占 用 而 又 不 可 能 被 释 放 的 资 源6. 通 道 又 称 I/O处 理 机 ， 它 用 于 实 现 ( ) 之 间 的 信 息 传 输 。A. CPU与 外 存 B. CPU与 外 设 C. 内 存 与 外 存 D. 内 存 与 外 设7. 下 面 叙 述 正 确 的 是 ( ) 。 A. 程 序 段 是 进 程 存 在 的 唯 一 标 志B. 系 统 通 过 PCB来 控 制 和 管 理 进 程 ， 用 户 可 以 从 PCB中 读 出 与 本 身 运 行 状 态 相 关 的 信 息C. 当 进 程 有 执 行 状 态 变 为 就 绪 状 态 时 ， CPU现 场 信 息 必 须 被 保 存 在 PCB中D. 当 进 程 申 请 CPU 得 不 到 满 足 时 ， 它 将 处 于 阻 塞 状 态8. 在 没 有 快 表 的 情 况 下 ， 分 页 系 统 要 访 问 ( )次 内 存 。A. 1 B. 2 C .3 D. 49. 计 算 机 操 作 系 统 中 ， 若 WAIT、 SIGNAL 操 作 的 信 号 量 S 初 值 为 3， 当 前 值 为 -4， 则 表 示 当 前考 试 科 目 ： 计 算 机 基 础 综 合 共 4 页 ， 第 3 页 有 ( ) 个 等 待 信 号 量 S的 进 程 。A. 1 B. 2 C. 3 D. 410. 有 10 个 进 程 共 享 5 个 打 印 机 ， 若 信 号 量 S 的 当 前 值 是 -2， 则 当 前 有 ( )个 进 程 提 出 了 打印 请 求 ？A. 10 B. 7 C. 5 D. 2八 、 简 答 题 (每 小 题 5 分 ， 共 25 分 )1. 什 么 是 文 件 目 录 、 目 录 文 件 ， 各 起 什 么 作 用 ？2. 多 级 树 形 目 录 的 文 件 系 统 ， 怎 样 才 能 提 高 查 找 文 件 的 速 度 ?3. 多 线 程 系 统 与 传 统 多 进 程 系 统 相 比 有 哪 些 优 点 ？4. 分 页 存 储 管 理 和 分 段 存 储 管 理 的 主 要 区 别 有 哪 些 ？5. 用 伪 代 码 或 文 字 描 述 fork()系 统 调 用 是 如 何 创 建 进 程 的 。 九 、 应 用 题 (每 小 题 10 分 ， 共 20 分 )1. 某 类 Unix系 统 采 用 成 组 链 接 法 来 管 理 磁 盘 的 空 闲 空 间 ， 目 前 磁 盘 的 状 态 图 如 下 （ 10 分 ） ： （ 1） 该 磁 盘 中 目 前 还 有 多 少 个 空 闲 盘 块 ？ (4 分 )（ 2） 给 出 该 系 统 的 磁 盘 块 分 配 及 回 收 算 法 （ 流 程 图 或 描 述 ） 。 （ 6 分 ）2. 分 析 下 面 给 出 的 表 达 式 的 并 行 性 ， 并 用 信 号 量 机 制 实 现 该 表 达 式 的 并 行 计 算 。 （ 10分 ）（ 3 * a * b + 4） / ( c + d )( e f ) 考 试 科 目 ： 计 算 机 基 础 综 合 共 4 页 ， 第 4 页
展开阅读全文