资源描述
第 一 部 分 ： 数 据 结 构一 、1-5 CCBCC 6-10 BCCBD二 、1-5 X X X 6-10 X X X X三 、(1)广 度 优 先 遍 历 序 列 ： 1; 2, 3, 4; 5; 6(2)最 小 生 成 树 （ prim 算 法 ） 四 、 15、 设 Hn为 n 个 盘 子 的 Hanoi 塔 的 移 动 次 数 。 (假 定 n 个 盘 子 从 钢 针 X 移 到 钢 针 Z， 可借 助 钢 针 Y)则 Hn =2Hn-1+1 /先 将 n-1 个 盘 子 从 X 移 到 Y， 第 n 个 盘 子 移 到 Z， 再 将 那 n-1 个移 到 Z =2（ 2Hn-2+1） +1=22 H n-2+2+1=22（ 2Hn-3+1） +2+1=23 Hn-3+22+2+1= 2k Hn-k+2k-1 +2k-2 +21 +20=2 n-1 H1+2n-2+2n-3+21+20因 为 H1=1， 所 以 原 式 Hn=2n-1+2n-2+21+20=2n-1故 总 盘 数 为 n 的 Hanoi 塔 的 移 动 次 数 是 2n-1五 、答 案 ： (1)表 形 态 ：(2)平 均 查 找 长 度 ： ASL(10)=(1*5+2*4+3*1)/10=1.6六 、(1)排 序 结 束 条 件 为 没 有 交 换 为 止 (2)第 一 趟 奇 数 ： 35,70,33,65,21,24,33 第 二 趟 偶 数 ： 35,33,70,21,65,24,33第 三 趟 奇 数 ： 33,35,21,70,24,65,33 第 四 趟 偶 数 ： 33,21,35,24,70,33,65第 五 趟 奇 数 ： 21,33,24,35,33,70,65 第 六 趟 偶 数 ： 21,24,33,33,35,65,70 第 七 趟 奇 数 ： 21,24,33,33,35,65,70(无 交 换 ) 第 八 趟 偶 数 ： 21,24,33,33,35,65,70(无 交 换 )结 束七 、void PreInCreat(BiTree root,ElemType pre,in,int l1,h1,l2,h2)/根 据 二 叉 树 前 序 序 列 pre 和 中 序 序 列 in 建 立 二 叉 树 。 l1,h1,l2,h2 是 序 列 第 一 和 最后 元 素 下 标 。root=(BiTree)malloc(sizeof(BiNode); /申 请 结 点root-data=prel1; /prel1是 根for(i=l2;ilchild=null; /无 左 子 树elsePreInCreat(root-lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)； /递 归 建 立 左 子 树 if(i=h2) root-rchild=null; /无 右 子 树else PreInCreat(root)-rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2) /递 归 建 立 右 子树 /结 束 PreInCreat第 二 部 分 ： 操 作 系 统一 、DCBBDDBAAC二 、1、 死 锁 ： 多 个 进 程 因 竞 争 资 源 而 造 成 的 一 种 僵 局 ， 若 无 外 力 作 用 ， 这 些 进 程 将 永 远 不能 再 向 前 推 进2、 原 子 操 作 ： 一 个 操 作 中 的 所 有 动 作 要 么 全 做 ， 要 么 全 不 做 ， 它 是 一 个 不 可 分 割 的 操 作 。3、 临 界 区 ： 在 每 个 进 程 中 访 问 临 界 资 源 的 那 段 代 码4、 虚 拟 存 储 器 ： 是 指 仅 把 作 业 的 一 部 分 装 入 内 存 便 可 运 行 作 业 的 存 储 器 系 统 。 也 即 是具 有 请 求 调 入 功 能 和 置 换 功 能 ， 能 从 逻 辑 上 进 行 扩 充 的 一 种 存 储 系 统 。5、 文 件 系 统 ： 是 指 含 有 大 量 的 文 件 及 其 属 性 的 说 明 ， 对 文 件 进 行 操 纵 和 管 理 的 软 件 ，以 及 向 用 户 提 供 的 使 用 文 件 的 接 口 等 的 集 合三 、1、 （ ）2、 （ ） 请 求 分 页 系 统 中 ， 只 能 减 少 外 零 头 ， 而 不 能 减 少 内 零 头 。3、 （ ） 不 一 定 。4、 （ ）5、 （ ） 由 内 存 外 存 容 量 以 及 地 址 结 构 决 定 。6、 （ ） 多 级 文 件 目 录 可 解 决 文 件 重 名 问 题 。 7、 （ ） 进 程 调 度 有 两 种 方 式 ： 剥 夺 方 式 和 非 剥 夺 方 式 。8、 （ ） 程 序 顺 序 执 行 具 有 顺 序 性 ， 封 闭 性 和 可 再 现 性 。9、 （ ） 并 发 是 指 两 个 或 多 个 事 件 在 同 一 时 间 间 隔 内 发 生 ， 而 并 行 是 指 两 个 或 多 个 事 件在 同 一 时 刻 发 生 。10、 （ ）四 、1、 答 ： 死 锁 是 指 多 个 进 程 因 竞 争 资 源 而 造 成 的 一 种 僵 局 ， 若 无 外 力 作 用 ， 这 些 进 程 将 永 远 不 能 再 向 前 推 进 。 产 生 死 锁 的 原 因 可 归 结 为 两 点 ：（ 1） 争 资 源 。（ 2） 进 程 推 进 顺 序 非 法 。在 具 备 下 述 四 个 必 要 条 件 时 ， 就 会 产 生 死 锁 。（ 3） 互 斥 条 件（ 4） 请 求 和 保 持 条 件（ 5） 不 剥 夺 条 件（ 6） 环 路 等 待 条 件2、 什 么 是 多 道 程 序 技 术 ， 它 带 来 了 什 么 好 处 ？答 ： 多 道 程 序 技 术 即 是 指 在 内 存 中 存 放 多 道 作 业 ， 运 行 结 束 或 出 错 ， 自 动 调 度 内 存 中另 一 道 作 业 运 行 。 多 道 程 序 主 要 优 点 如 下 ：（ 1） 资 源 利 用 率 高 。 由 于 内 存 中 装 入 了 多 道 程 序 ， 使 它 们 共 享 资 源 ， 保 持 系 统 资源 处 于 忙 碌 状 态 ， 从 而 使 各 种 资 源 得 以 充 分 利 用 。（ 2） 系 统 吞 吐 量 大 。 由 于 CPU 和 其 它 系 统 资 源 保 持 “忙 碌 ”状 态 ， 而 且 仅 当 作 业 完 成 或 运 行 不 下 去 时 才 切 换 ， 系 统 开 销 小 ， 所 以 吞 吐 量 大 。3、 答 ： 有 结 构 文 件 可 分 为 以 下 三 类 ， 分 别 是 ：（ 1） 顺 序 文 件 。 它 是 指 由 一 系 列 记 录 ， 按 某 种 顺 序 排 列 所 形 成 的 文 件 。（ 2） 索 引 文 件 。 当 记 录 为 可 变 长 度 时 ， 通 常 为 之 建 立 一 张 索 引 表 ， 并 为 每 个 记 录设 置 一 表 项 ， 以 加 速 对 记 录 的 检 索 速 度 。（ 3） 索 引 顺 序 文 件 。 这 是 上 述 两 种 文 件 方 式 的 结 合 ， 它 为 文 件 建 立 一 张 索 引 表 ，为 每 一 组 记 录 中 的 第 一 个 记 录 设 置 一 表 项 。4、 答 ： 分 时 系 统 主 要 有 以 下 特 征 ：（ 1） 多 路 性 （ 2） 独 立 性 (3） 及 时 （ 4） 交 互 性5、 答 ： 分 页 与 分 段 系 统 有 很 多 相 似 之 处 ， 但 两 者 在 概 念 上 完 全 不 同 ， 主 要 表 现 在 ：（ 1） 页 是 信 息 的 物 理 单 位 ， 分 页 是 为 实 现 离 散 分 配 方 式 ， 以 消 减 内 存 的 外 汇 零 头 ，提 高 内 存 利 用 率 。 段 是 逻 辑 单 位 ， 分 段 的 目 的 是 为 了 更 好 的 满 足 用 户 的 需 要 。（ 2） 页 的 大 小 固 定 ， 段 的 长 度 不 固 定（ 3） 分 业 的 作 业 地 址 是 一 维 的 ， 分 段 的 地 址 空 间 是 二 维 的 ， 在 标 识 一 个 地 址 时 ， 要 给 出 段 名 和 段 内 地 址五 、1、 解 ： 响 应 比 =响 应 时 间 /要 求 服 务 时 间 =（ 等 待 时 间 +要 求 服 务 时 间 ） /要 求 服 务 时 间由 于 作 业 1 与 作 业 2 开 始 执 行 时 ， 作 业 3 和 4 均 未 到 达 ， 所 以 1、 2 按 到 达 顺 序 执行 ， 作 业 2 执 行 完 后 ，作 业 3： 响 应 比 =（ 10.8-10.4+0.1） /0.1=5作 业 4： 响 应 比 =(10.8-10.5+0.4)/0.4=1.75因 为 作 业 3 的 响 应 比 高 于 作 业 4,所 以 作 业 3 先 执 行 。周 转 时 间 =完 成 时 间 -提 交 时 间作 业 1 的 周 转 时 间 T1=0.3T2=10.8-10.2=0.6T3=10.9-10.4=0.5T4=11.3-10.5=0.8平 均 周 转 时 间 =(0.3+0.6+0.5+0.8)/4=0.5 带 权 周 转 时 间 =周 转 时 间 /运 行 时 间 (用 P 表 示 )P1=0.3/0.3=1 P2=0.6/0.5=1.2 P3=0.5/0.1=5 P4=0.8/0.4=2平 均 带 权 周 转 时 间 =(1+1.2+5+2)/4=2.32、磁 道 号 最 短 寻 找 时 间 优 先（ 调 度 次 序 ） 电 梯 算 法190 6 10 10 10 6160 5 980 2 290 1 1125 3 730 7 320 9 5140 4 825 8 4
展开阅读全文