北京工业大学软件工程模拟试卷一.pdf
第 一 部 分 : 数 据 结 构一 、 单 项 选 择 题 ( 共 2 0 分 , 每 题 2 分 ) 在 每 小 题 列 出 的 四 个 选 项 中 只 有 一 个 选 项 是 符 合 题目 要 求 的 , 请 将 正 确 选 项 前 的 字 母 写 在 答 题 纸 上 。1、 在 双 向 循 环 链 表 中 , 在p指 针 所 指 的 结 点 后 插 入 一 个 指 针q所 指 向 的 新 结 点 , 修 改 指 针 的操 作 是 ( ) 。A.p-next=q;q-prior=p;p-next-prior=q;q-next=q;B.p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C.q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;D.q-next=p-next;q-prior=p;p-next=q;p-next=q;2、 五 节 车 厢 以 编 号1,2,3,4,5顺 序 进 入 铁 路 调 度 站 ( 栈 ) , 可 以 得 到 ( ) 的 编 组 。A.3,4,5,1,2B.2,4,1,3,5C.3,5,4,2,1D.1,3,5,2,43、 设SUBSTR(S,i,k)是 求S中 从 第i个 字 符 开 始 的 连 续k个 字 符 组 成 的 子 串 的 操 作 , 则 对 于S=Beijing&Nanjing,SUBSTR(S,4,5)=(B) 。A.ijingB.jing&C.ingNaD.ing&N4、 某 二 叉 树 的 中 序 序 列 为ABCDEFG, 后 序 序 列 为BDCAFGE, 则 其 左 子 树 中 结 点 数 目 为(C) 。A.3B.2C.4D.55、 若 以4,5,6,7,8作 为 权 值 构 造 哈 夫 曼 树 , 则 该 树 的 带 权 路 径 长 度 为 (C) 。A.67B.68C.69D.706、 带 权 有 向 图G用 邻 接 矩 阵A存 储 , 则 顶 点i的 入 度 等 于A中 ( ) 。A.第i行 非 无 穷 的 元 素 之 和B.第i列 非 无 穷 的 元 素 个 数 之 和C.第i行 非 无 穷 且 非0的 元 素 个 数D.第i行 与 第i列 非 无 穷 且 非0的 元 素 之 和7、 下 列 关 于 图 遍 历 的 说 法 不 正 确 的 是 ( ) 。A.连 通 图 的 深 度 优 先 搜 索 是 一 个 递 归 过 程B.图 的 广 度 优 先 搜 索 中 邻 接 点 的 寻 找 具 有 “ 先 进 先 出 ” 的 特 征 C.非 连 通 图 不 能 用 深 度 优 先 搜 索 法D.图 的 遍 历 要 求 每 一 顶 点 仅 被 访 问 一 次8、 在 各 种 查 找 方 法 中 , 平 均 查 找 长 度 与 结 点 个 数n无 关 的 查 找 方 法 是 (C) 。A.顺 序 查 找B.折 半 查 找C.哈 希 查 找D.分 块 查找9、 一 组 待 排 序 序 列 为 (46,79,56,38,40,84) , 则 利 用 堆 排 序 的 方 法 建 立 的 初 始 堆 为 ( ) 。A.79,46,56,38,40,80B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,381 0 、 用 某 种 排 序 方 法 对 线 性 表 ( 2 5 , 8 4 , 2 1 , 4 7 , 1 5 , 2 7 , 6 8 , 3 5 , 2 0 ) 进 行 排 序 时 , 元素 序 列 的 变 化 情 况 如 下 : 2 5 , 8 4 , 2 1 , 4 7 , 1 5 , 2 7 , 6 8 , 3 5 , 2 0 2 0 , 1 5 , 2 1 , 2 5 , 4 7 , 2 7 , 6 8 , 3 5 , 8 4 1 5 , 2 0 , 2 1 , 2 5 , 3 5 , 2 7 , 4 7 , 6 8 , 8 4 1 5 , 2 0 , 2 1 , 2 5 , 2 7 , 3 5 , 4 7 , 6 8 , 8 4则 所 采 用 的 排 序 方 法 是 ( ) 。A.选 择 排 序B.希 尔 排 序C.归 并 排 序D.快 速 排 序 二 、 判 断 题 ( 本 大 题 共 5 小 题 , 每 小 题 2 分 , 共 1 0 分 )( )1、 折 半 查 找 只 适 用 于 有 序 表 , 包 括 有 序 的 顺 序 表 和 链 表 。( )2、 直 接 选 择 排 序 是 一 种 稳 定 的 排 序 方 法 。( )3、 快 速 排 序 在 所 有 排 序 方 法 中 最 快 , 而 且 所 需 附 加 空 间 也 最 少 。( )4、 链 表 的 物 理 存 储 结 构 具 有 同 链 表 一 样 的 顺 序 。( )5、 具 有12个 结 点 的 完 全 二 叉 树 有5个 度 为2的 结 点 。( )6、 在 执 行 某 个 排 序 算 法 过 程 中 , 出 现 了 排 序 码 朝 着 最 终 排 序 序 列 位 置 相 反 方 向 移 动 ,则 该 算 法 是 不 稳 定 的 。( )7、 在 用 堆 排 序 算 法 排 序 时 , 如 果 要 进 行 增 序 排 序 , 则 需 要 采 用 “ 大 根 堆 ” 。( )8、 邻 接 矩 阵 适 用 于 有 向 图 和 无 向 图 的 存 储 , 但 不 能 存 储 带 权 的 有 向 图 和 无 向 图 , 而只 能 使 用 邻 接 表 存 储 形 式 来 存 储 它 。( )9、 哈 希 表 的 结 点 中 只 包 含 数 据 元 素 自 身 的 信 息 , 不 包 含 任 何 指 针 。( )10、 折 半 查 找 法 的 查 找 速 度 一 定 比 顺 序 查 找 法 快 。 三 、 (10分 ) 已 知 图G的 邻 接 矩 阵 如 下 所 示 :(1) 求 从 顶 点1出 发 的 广 度 优 先 搜 索 序 列 ;(2) 根 据prim算 法 , 求 图G从 顶 点1出 发 的 最 小 生 成 树 , 要 求 表 示 出 其 每 一 步 生 成 过 程 。( 用 图 或 者 表 的 方 式 均 可 ) 。 624 663 255 46551 356 516四 、 ( 10 分 ) 试 推 导 出 当 总 盘 数 为 n 的 Hanoi 塔 的 移 动 次 数 。五 、 (10分 ) 设 哈 希 表HT表 长m为13, 哈 希 函 数 为H(k)=kMODm, 给 定 的 关 键 值 序 列 为19,14,23,10,68,20,84,27,55,11。 试 求 出 用 线 性 探 测 法 解 决 冲 突 时 所 构 造 的哈 希 表 , 并 求 出 在 等 概 率 的 情 况 下 查 找 成 功 的 平 均 查 找 长 度ASL。六 、 ( 20分 ) 奇 偶 交 换 排 序 如 下 所 述 : 对 于 初 始 序 列 A1, A2, ,An,第 一 趟 对 所 有 奇数 i( 1=iAi+1, 则 将 两 者 交 换 ; 第 二 趟 对 所有 偶 数 i( 2=iAi+1, 则 将 两 者 交 换 ; 第 三 趟对 所 有 奇 数 i( 1=in) ; 第 四 趟 对 所 有 偶 数 i( 2=in) , , 依 次 类 推 直 至 到 整 个 序 列 有序 为 止 。(1) 分 析 这 种 排 序 方 法 的 结 束 条 件 。(2) 写 出 用 这 种 排 序 方 法 对 35, 70, 33, 65, 24, 21, 33 进 行 排 序 时 , 每 一 趟 的 结 果 。七 、 ( 20分 ) 设 一 棵 二 叉 树 中 各 结 点 的 值 互 不 相 同 , 其 前 序 序 列 和 中 序 序 列 分 别 存 于 两 个 一维 数 组 pre1.n 和 mid1.n 中 , 试 遍 写 算 法 建 立 该 二 叉 树 的 二 叉 链 表 。第 二 部 分 : 操 作 系 统 一 、 单 项 选 择 题 ( 在 每 小 题 的 四 个 备 选 答 案 中 , 只 有 一 个 是 正 确 的 , 将 其 号 码 写 在 题 干 的 括号 中 。 每 小 题 2 分 , 共 2 0 分 )1 、 文 件 系 统 的 主 要 组 成 部 分 是 ( )A、 文 件 控 制 块 及 文 件 B、 I/O 文 件 及 块 设 备 文 件C、 系 统 文 件 及 用 户 文 件 D、 文 件 及 管 理 文 件 的 软 件2 、 实 现 进 程 互 斥 可 采 用 的 方 法 ( ) A、 中 断 B、 查 询 C、 开 锁 和 关 锁 D、 按 键 处 理3 、 某 页 式 管 理 系 统 中 , 地 址 寄 存 器 的 低 9 位 表 示 页 内 地 址 , 则 页 面 大 小 为 ( )A、 1 0 2 4 字 节 B、 5 1 2 字 节 C、 1 0 2 4 K D、 5 1 2 K4 、 串 联 文 件 适 合 于 ( ) 存 取A、 直 接 B、 顺 序 C、 索 引 D、 随 机5 、 进 程 的 同 步 与 互 斥 是 由 于 程 序 的 ( ) 引 起 的A、 顺 序 执 行 B、 长 短 不 同 C、 信 号 量 D、 并 发 执 行6 、 信 号 量 的 值 ( )A、 总 是 为 正 B、 总 是 为 负 C、 总 是 为 0 D、 可 以 为 负 整 数7 、 多 道 程 序 的 实 质 是 ( )A、 程 序 的 顺 序 执 行 B、 程 序 的 并 发 执 行C、 多 个 处 理 机 同 时 执 行 D、 用 户 程 序 和 系 统 程 序 交 叉 执 行8 、 虚 拟 存 储 器 最 基 本 的 特 征 是 ( )A、 从 逻 辑 上 扩 充 内 存 容 量 B、 提 高 内 存 利 用 率 C、 驻 留 性 D、 固 定 性 9 、 飞 机 定 票 系 统 是 一 个 ( )A、 实 时 系 统 B、 批 处 理 系 统 C、 通 用 系 统 D、 分 时 系 统1 0 、 操 作 系 统 中 , 被 调 度 和 分 派 资 源 的 基 本 单 位 , 并 可 独 立 执 行 的 实 体 是 ( )A、 线 程 B、 程 序 C、 进 程 D、 指 令二 、 名 词 解 释 ( 每 小 题 3 分 , 共 1 5 分 )1 .死 锁 :2 .原 子 操 作 :3 .临 界 区 :4 .虚 拟 存 储 器 :5 .文 件 系 统 : 三 、 判 断 改 错 题 ( 判 断 正 误 , 并 改 正 错 误 , 每 小 题 2 分 , 共 2 0 分 )1 、 通 道 是 通 过 通 道 程 序 来 对 I/O设 备 进 行 控 制 的 。 ( )2 、 请 求 页 式 管 理 系 统 中 , 既 可 以 减 少 外 零 头 , 又 可 以 减 少 内 零 头 。 ( )3 、 操 作 系 统 中 系 统 调 用 越 多 , 系 统 功 能 就 越 强 , 用 户 使 用 越 复 杂 。 ( )4 、 一 个 进 程 可 以 挂 起 自 已 , 也 可 以 激 活 自 已 。 ( )5 、 虚 拟 存 储 器 的 最 大 容 量 是 由 磁 盘 空 间 决 定 的 。 ( )6 、 单 级 文 件 目 录 可 以 解 决 文 件 的 重 名 问 题 。 ( )7 、 进 程 调 度 只 有 一 种 方 式 : 剥 夺 方 式 。 ( )8 、 程 序 的 顺 度 执 行 具 有 顺 序 性 , 封 闭 性 和 不 可 再 现 性 。 ( )9 、 并 行 是 指 两 个 或 多 个 事 件 在 同 一 时 间 间 隔 内 发 生 , 而 并 发 性 是 指 两 个 或 多 个 事 件 在同 一 时 刻 发 生 。 ( )1 0 、 进 程 控 制 一 般 都 由 操 作 系 统 内 核 来 实 现 。 ( )四 、 简 答 题 ( 每 小 题 5 分 , 共 25 分 ) 1、 简 述 死 锁 产 生 的 原 因 及 必 要 条 件 。3 、 什 么 是 多 道 程 序 技 术 , 它 带 来 了 什 么 好 处 ?4、 有 结 构 文 件 可 分 为 哪 几 类 , 其 特 点 是 什 么 ? 5 、 分 时 系 统 的 基 本 特 征 是 什 么 ?6 、 分 页 系 统 与 分 段 系 统 的 区 别 主 要 在 于 哪 些 方 面 ?五 、 综 合 应 用 题 ( 每 小 题 1 0 分 , 共 2 0 分 )1 . 有 一 组 作 业 , 其 提 交 时 间 及 运 行 时 间 如 下 表 所 示 , 在 单 道 程 序 管 理 系 统 中 , 采 用 响应 比 高 者 优 先 高 度 算 法 , 给 出 调 度 顺 序 , 各 作 业 的 周 转 时 间 , 并 算 出 平 均 周 转 时 间 和 平均 带 权 周 转 时 间 。 ( 按 十 进 制 计 算 )作 业 号 提 交 时 间 运 行 时 间1 1 0 0 0 0 3 02 1 0 2 0 0 5 03 1 0 4 0 0 1 04 1 0 5 0 0 4 0 2 . 某 移 动 磁 盘 的 柱 面 由 外 向 里 从 0 开 始 顺 序 编 号 , 假 定 当 前 磁 头 停 在 1 0 0 号 柱 面 , 而且 移 动 方 向 是 向 外 的 , 现 有 一 个 请 求 队 列 在 等 待 访 问 磁 盘 , 访 问 的 柱 面 号 分 别 为 1 9 0 、 1 0 、1 6 0 、 8 0 、 9 0 、 1 2 5 、 3 0 、 2 0 、 1 4 0 、 2 5 。 请 写 出 分 别 采 用 最 短 寻 找 时 间 优 先 和 电 梯 调 度 算 法处 理 上 述 请 求 的 次 序 。