北京工业大学软件工程模拟试题二答案.pdf
第 一 部 分 : 数 据 结 构一 、1.(rear-front+M)%M2.对 应 位 置 字 符 相 同3.极 小 连 通 子 图4. 邻 接 矩 阵5. 26. 没 有 没 有7. 98. O(n 2) O(n+e)9. 连 续 或 不 连 续 都 可 以10.n(n-1)二 、1-5x x6-10 xxxxx三 、答 : 顺 序 存 储 时 , 相 邻 数 据 元 素 的 存 放 地 址 也 相 邻 ( 逻 辑 与 物 理 统 一 ) ; 要 求 内 存 中 可 用存 储 单 元 的 地 址 必 须 是 连 续 的 。优 点 : 存 储 密 度 大 ( 1? ) , 存 储 空 间 利 用 率 高 。 缺 点 : 插 入 或 删 除 元 素 时 不 方 便 。 链 式 存 储 时 , 相 邻 数 据 元 素 可 随 意 存 放 , 但 所 占 存 储 空 间 分 两 部 分 , 一 部 分 存 放 结 点 值 ,另 一 部 分 存 放 表 示 结 点 间 关 系 的 指 针优 点 : 插 入 或 删 除 元 素 时 很 方 便 , 使 用 灵 活 。 缺 点 : 存 储 密 度 小 ( 1) , 存 储 空 间 利 用 率 低 。 顺 序 表 适 宜 于 做 查 找 这 样 的 静 态 操 作 ; 链 表 宜 于 做 插 入 、 删 除 这 样 的 动 态 操 作 。若 线 性 表 的 长 度 变 化 不 大 , 且 其 主 要 操 作 是 查 找 , 则 采 用 顺 序 表 ;若 线 性 表 的 长 度 变 化 较 大 , 且 其 主 要 操 作 是 插 入 、 删 除 操 作 , 则 采 用 链 表 。四 、答 案 : 1, 5, 2, 3, 6, 4 1, 5, 6, 2, 3, 4 5, 1, 2, 3, 6, 45, 1, 6, 2, 3, 4 5, 6, 1, 2, 3, 4五 、答 案 : kruskal 算 法 的 最 小 生 成 树 六 、答 案 : (1)表 形 态 :(2) 查 找 34 的 比 较 次 数 : 3七 、void BiInsertSort(RecType R, int n)/二 路 插 入 排 序 的 算 法int dn+1; /辅 助 存 储d1=R1;first=1;final=1;for(i=2;i=d1.key) /插 入 后 部 low=1;high=final;while (low=high) /折 半 查 找 插 入 位 置 m=(low+high)/2;if(Ri.key=high+1;j-) dj+1 = dj;/移 动 元 素dhigh+1=Ri; final+; /插 入 有 序 位 置else /插 入 前 部 if(first=1) first=n; dn=Ri;else low=first;high=n;while (low=high) m=(low+high)/2;if(Ri.key dm.key) high=m-1; else low=m+1;/whilefor (j=first;j=high;j+) dj-1 = dj; /移 动 元 素dhigh=Ri; first-;/if/if/forR1 =dfisrt;for(i=first%n+1,j=2;i!=fisrt;i=i%n+1,j+) Rj =di; /将 序 列 复 制 回 去/BiInsertSort 第 二 部 分 : 操 作 系 统一 、 DCABADACDC二 、 1、 抖 动 : 不 适 当 地 提 高 多 道 程 序 度 , 不 仅 不 会 提 高 系 统 吞 吐 量 , 反 而 会 使 之 下 降 , 因为 运 行 进 程 的 大 部 分 时 间 都 用 于 进 行 页 面 的 换 入 /换 出 , 而 几 乎 不 能 完 成 任 何 有 效 的 工 作 。 称 这 时 的 进 程 是 处 于 “抖 动 ”状 态 。2、 内 核 : 将 一 些 与 硬 件 紧 密 相 关 的 模 块 诸 如 中 断 处 理 程 序 , 各 种 常 用 设 备 的 驱 动 程 序 ,以 及 运 行 频 率 较 高 的 模 块 都 安 排 在 紧 靠 硬 件 的 软 件 层 次 中 , 并 使 它 们 常 驻 内 存 , 以 便 提 高OS 的 运 行 效 率 。 并 对 之 加 以 特 殊 的 保 护 。 通 常 将 这 一 部 分 称 为 OS 的 内 核 。3、 临 界 资 源 : 一 段 时 间 只 允 许 一 个 进 程 访 问 的 资 源 。4、 进 程 : 可 并 发 执 行 的 程 序 在 一 个 数 据 集 合 上 的 运 行 过 程 。5、 共 享 设 备 : 一 段 时 间 内 允 许 多 个 进 程 同 时 访 问 的 设 备 。三 、 1、 ( ) 实 时 系 统 也 具 有 一 定 的 交 互 性 。2、 ( )3、 ( ) 固 定 式 分 区 方 式 产 生 “内 零 头 ”, 可 变 式 分 区 分 配 方 式 产 生 “外 零 头 ”4、 ( ) 应 该 为 处 于 就 绪 状 态5、 ( )6、 ( ) 死 锁 定 理 是 利 用 已 知 的 条 件 , 检 测 是 否 死 锁 。 7、 ( ) 静 态 重 定 位 的 地 址 变 换 是 在 装 入 时 一 次 完 成 的 , 以 后 不 再 改 变 , 但 动 态 重 定 位的 地 址 在 运 行 过 程 中 要 变 化 。8、 ( ) 分 页 请 求 系 统 的 置 换 以 页 面 为 单 位 , 而 分 段 请 求 系 统 以 段 为 单 位 。9、 ( ) 访 问 控 制 表 是 以 一 个 文 件 建 立 的 控 制 表 , 而 访 问 权 限 表 是 以 一 个 用 户 建 立 的 控制 表 。10、 ( )四 、 操 作 系 统 的 目 标 是 什 么 ?答 : 操 作 系 统 的 目 标 有 以 下 几 点 :( 1) 方 便 性 ( 2) 有 效 性 ( 3) 可 扩 充 性 ( 4) 开 放 性2 程 序 链 接 的 方 法 有 哪 几 种 , 请 分 别 作 简 要 阐 述 。答 : 链 接 程 序 的 功 能 , 是 将 经 过 编 译 或 汇 编 后 得 到 的 一 组 目 标 模 块 以 及 它 们 所 需 要 的 库函 数 , 装 配 成 一 个 完 整 的 装 入 模 块 , 实 现 的 方 法 有 三 种 :( ! ) 静 态 链 接 , 即 事 先 链 接 , 以 后 不 再 拆 开 的 链 接 方 式 。 ( 2) 装 入 时 动 态 链 接 , 却 用 户 源 程 序 经 编 译 后 所 得 到 的 目 标 模 块 , 是 在 装 入 内 存 时 ,边 装 入 边 链 接 的 。( 3) 运 行 时 动 态 链 接 , 这 种 方 式 可 将 某 些 目 标 模 块 的 链 接 , 推 迟 到 执 行 时 才 进 行 , 即在 执 行 过 程 中 , 若 发 现 一 个 被 调 用 模 块 未 装 入 内 存 时 , 再 由 操 作 系 统 去 找 该 模 块 , 将 它 装 入内 存 , 并 把 它 链 接 到 调 用 者 模 块 上 。3 什 么 叫 虚 拟 存 储 器 ? 实 现 方 式 有 哪 些 ?答 : 所 谓 虚 拟 存 储 器 , 是 指 将 作 业 的 一 部 分 装 入 内 存 便 可 运 行 作 业 的 存 储 器 系 统 。 也 即是 指 具 有 请 示 调 入 功 能 和 置 换 功 能 , 能 从 逻 辑 上 对 内 存 容 量 进 行 扩 充 的 一 种 存 储 器 系 统 。虚 拟 存 储 器 的 实 现 方 式 有 两 种 :( 1) 请 求 分 页 系 统( 2) 请 求 分 段 系 统4 简 述 引 起 进 程 调 度 的 原 因 。答 : 引 起 进 程 调 度 的 事 件 主 要 有 以 下 几 个 :( 1) 在 执 行 进 程 执 行 完 毕 或 因 某 种 事 件 而 不 能 再 执 行 ( 2) 在 进 程 通 信 或 同 步 过 程 中 执 行 某 些 原 语 , 如 P 操 作 , block 原 语( 3) 执 行 中 的 进 程 因 提 出 I/O 操 作 而 暂 停 执 行( 4) 在 可 剥 夺 式 调 度 中 有 一 个 比 当 前 进 程 优 先 级 更 高 的 进 程 进 入 到 就 绪 队 列 。( 5) 在 分 时 系 统 中 时 间 片 用 完5 操 作 系 统 的 基 本 特 征 是 什 么 ?答 : 各 种 操 作 系 统 都 拥 有 共 同 的 特 征 。 分 别 是 :( ! ) 并 发 ( 2) 共 享( 3) 虚 拟( 4) 异 步 性( 分 别 简 要 阐 述 )五 、1、 解 : ( 1) 主 存 容 量 最 大 为 2 的 18 次 方 , 即 256K可 分 为 2 的 7 次 方 块 , 即 128 块每 块 大 小 为 2 的 11 次 块 , 即 2K( 2) 相 对 地 址 为 1500, 没 有 超 出 一 页 的 长 度 , 所 以 指 令 所 在 页 号 为 0 号 , 数 据 存 储 在 2500单 元 , 页 号 为 1 号 。指 令 的 物 理 地 址 为 : 22048+1500=5596数 据 的 物 理 地 址 为 : 22048+2500=65962、页 面 走 向 1 8 1 7 8 2 7 6 5 8 3 6 缺 页 标 记 * * * * * * * *M1 1 1 1 1 1 1 1 6 6 6 6 6M2 8 8 8 8 8 8 8 5 5 5 5M3 7 7 7 7 7 7 8 8 8M4 2 2 2 2 2 3 3缺 页 次 数 =8缺 页 率 =8/12*100