软件设计师

全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 ( 考 试 时 间 14:00~16:30 共 150 分 钟 ) 请 按 下 述 要 求 正 确 填 写 答 题 纸 1. 在 答 题 纸 的 指 定 位 置 填 写 你 所 在 的 省 自 治 区 直 辖 市 计 划 单 列 市 的 名 称 2. 在 答 题 纸 的 指 定 位 置 填 写 准 考 证 号 出 生 年 月 日 和 姓 名 3. 答 题 纸 上 除 填 写 上 述 内 容 外 只 能 写 解 答 4. 本 试 卷 共 7 道 题, 试 题 一 至 试 题 四 是 必 答 题, 试 题 五 至 试 题 七 选 答 1 道 每 题 15 分, 满 分 75 分 5. 解 答 时 字 迹 务 必 清 楚, 字 迹 不 清 时, 将 不 评 分 6. 仿 照 下 面 例 题, 将 解 答 写 在 答 题 纸 的 对 应 栏 内 例 题 2009 年 下 半 年 全 国 计 算 机 技 术 与 软 件 专 业 技 术 资 格 ( 水 平 ) 考 试 日 期 是 (1) 月 (2) 日 因 为 正 确 的 解 答 是 11 月 14 日, 故 在 答 题 纸 的 对 应 栏 内 写 上 11 和 14 ( 参 看 下 表 ) 例 题 解 答 栏 (1) 11 (2) 14 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 1 页 ( 共 15 页 )

试 题 一 ( 共 15 分 ) 阅 读 以 下 说 明 和 数 据 流 图, 回 答 问 题 1 至 问 题 4, 将 解 答 填 入 答 题 纸 的 对 应 栏 内 说 明 现 准 备 为 某 银 行 开 发 一 个 信 用 卡 管 理 系 统 CCMS, 该 系 统 的 基 本 功 能 为 : 1. 信 用 卡 申 请 非 信 用 卡 客 户 填 写 信 用 卡 申 请 表, 说 明 所 要 申 请 的 信 用 卡 类 型 及 申 请 者 的 基 本 信 息, 提 交 CCMS 如 果 信 用 卡 申 请 被 银 行 接 受,CCMS 将 记 录 该 客 户 的 基 本 信 息, 并 发 送 确 认 函 给 该 客 户, 告 知 客 户 信 用 卡 的 有 效 期 及 信 贷 限 额 ; 否 则 该 客 户 将 会 收 到 一 封 拒 绝 函 非 信 用 卡 客 户 收 到 确 认 函 后 成 为 信 用 卡 客 户 2. 信 用 卡 激 活 信 用 卡 客 户 向 CCMS 提 交 激 活 请 求, 用 信 用 卡 号 和 密 码 激 活 该 信 用 卡 激 活 操 作 结 束 后,CCMS 将 激 活 通 知 发 送 给 客 户, 告 知 客 户 其 信 用 卡 是 否 被 成 功 激 活 3. 信 用 卡 客 户 信 息 管 理 信 用 卡 客 户 的 个 人 信 息 可 以 在 CCMS 中 进 行 在 线 管 理 每 位 信 用 卡 客 户 可 以 在 线 查 询 和 修 改 个 人 信 息 4. 交 易 信 息 查 询 信 用 卡 客 户 使 用 信 用 卡 进 行 的 每 一 笔 交 易 都 会 记 录 在 CCMS 中 信 用 卡 客 户 可 以 通 过 CCMS 查 询 并 核 实 其 交 易 信 息 ( 包 括 信 用 卡 交 易 记 录 及 交 易 额 ) 图 1-1 和 图 1-2 分 别 给 出 了 该 系 统 的 顶 层 数 据 流 图 和 0 层 数 据 流 图 的 初 稿 问 题 1 (3 分 ) 根 据 说 明, 将 图 1-1 中 的 E1~E3 填 充 完 整 问 题 2 (3 分 ) 图 1-1 中 缺 少 三 条 数 据 流, 根 据 说 明, 分 别 指 出 这 三 条 数 据 流 的 起 点 和 终 点 ( 注 : 数 据 流 的 起 点 和 终 点 均 采 用 图 中 的 符 号 和 描 述 ) 问 题 3 (5 分 ) 图 1-2 中 有 两 条 数 据 流 是 错 误 的, 请 指 出 这 两 条 数 据 流 的 名 称, 并 改 正 ( 注 : 数 据 流 的 起 点 和 终 点 均 采 用 图 中 的 符 号 和 描 述 ) 问 题 4 (4 分 ) 根 据 说 明, 将 图 1-2 中 P1~P4 的 处 理 名 称 填 充 完 整 E1 拒 绝 函 确 认 函 查 询 / 修 改 个 人 信 息 P0 信 用 卡 管 理 系 统 CCMS 信 用 卡 申 请 信 息 E3 激 活 通 知 E2 交 易 记 录 查 询 请 求 个 人 信 息 信 用 卡 申 请 验 证 结 果 图 1-1 顶 层 数 据 流 图 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 2 页 ( 共 15 页 )

交 易 信 息 交 易 记 录 查 询 请 求 P1 查 询 / 修 改 个 人 信 息 P2 E2 个 人 信 息 激 活 通 知 P3 拒 绝 函 激 活 请 求 E1 信 用 卡 申 请 表 P4 信 用 卡 申 请 信 息 E3 确 认 函 信 用 卡 申 请 验 证 结 果 图 1-2 0 层 数 据 流 图 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 3 页 ( 共 15 页 )

试 题 二 ( 共 15 分 ) 阅 读 下 列 说 明, 回 答 问 题 1 至 问 题 3, 将 解 答 填 入 答 题 纸 的 对 应 栏 内 说 明 某 公 司 拟 开 发 一 多 用 户 电 子 邮 件 客 户 端 系 统, 部 分 功 能 的 初 步 需 求 分 析 结 果 如 下 : (1) 邮 件 客 户 端 系 统 支 持 多 个 用 户, 用 户 信 息 主 要 包 括 用 户 名 和 用 户 密 码, 且 系 统 中 的 用 户 名 不 可 重 复 (2) 邮 件 帐 号 信 息 包 括 邮 件 地 址 及 其 相 应 的 密 码, 一 个 用 户 可 以 拥 有 多 个 邮 件 地 址 ( 如 user1@123.com) (3) 一 个 用 户 可 拥 有 一 个 地 址 薄, 地 址 簿 信 息 包 括 联 系 人 编 号 姓 名 电 话 单 位 地 址 邮 件 地 址 1 邮 件 地 址 2 邮 件 地 址 3 等 信 息 地 址 薄 中 一 个 联 系 人 只 能 属 于 一 个 用 户, 且 联 系 人 编 号 唯 一 标 识 一 个 联 系 人 (4) 一 个 邮 件 帐 号 可 以 含 有 多 封 邮 件, 一 封 邮 件 可 以 含 有 多 个 附 件 邮 件 主 要 包 括 邮 件 号 发 件 人 地 址 收 件 人 地 址 邮 件 状 态 邮 件 主 题 邮 件 内 容 发 送 时 间 接 收 时 间 其 中, 邮 件 号 在 整 个 系 统 内 唯 一 标 识 一 封 邮 件, 邮 件 状 态 有 已 接 收 待 发 送 已 发 送 和 已 删 除 4 种, 分 别 表 示 邮 件 是 属 于 收 件 箱 发 件 箱 已 发 送 箱 和 废 件 箱 一 封 邮 件 可 以 发 送 给 多 个 用 户 附 件 信 息 主 要 包 括 附 件 号 附 件 文 件 名 附 件 大 小 一 个 附 件 只 属 于 一 封 邮 件, 附 件 号 仅 在 一 封 邮 件 内 唯 一 问 题 1 (5 分 ) 根 据 以 上 说 明 设 计 的 E-R 图 如 图 2-1 所 示, 请 指 出 地 址 簿 与 用 户 电 子 邮 件 帐 号 与 邮 件 邮 件 与 附 件 之 间 的 联 系 类 型 图 2-1 电 子 邮 件 客 户 端 系 统 E-R 图 问 题 2 (4 分 ) 该 邮 件 客 户 端 系 统 的 主 要 关 系 模 式 如 下, 请 填 补 (a)~(c) 的 空 缺 部 分 用 户 ( 用 户 名, 用 户 密 码 ) 地 址 簿 ( (a), 联 系 人 编 号, 姓 名, 电 话, 单 位 地 址, 邮 件 地 址 1, 邮 件 地 址 2, 邮 件 地 址 3) 邮 件 帐 号 ( 邮 件 地 址, 邮 件 密 码, 用 户 名 ) 邮 件 ( (b), 收 件 人 地 址, 邮 件 状 态, 邮 件 主 题, 邮 件 内 容, 发 送 时 间, 接 收 时 间 ) 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 4 页 ( 共 15 页 )

附 件 ( (c), 附 件 号, 附 件 文 件 名, 附 件 大 小 ) 问 题 3 (6 分 ) (1) 请 指 出 问 题 2 中 给 出 的 地 址 簿 邮 件 和 附 件 关 系 模 式 的 主 键, 如 果 关 系 模 式 存 在 外 键 请 指 出 (2) 附 件 属 于 弱 实 体 吗? 请 用 50 字 以 内 的 文 字 说 明 原 因 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 5 页 ( 共 15 页 )

试 题 三 ( 共 15 分 ) 阅 读 下 列 说 明 和 UML 图, 回 答 问 题 1 至 问 题 4, 将 解 答 填 入 答 题 纸 的 对 应 栏 内 说 明 某 企 业 为 了 方 便 员 工 用 餐, 为 餐 厅 开 发 了 一 个 订 餐 系 统 (COS:Cafeteria Ordering System), 企 业 员 工 可 通 过 企 业 内 联 网 使 用 该 系 统 企 业 的 任 何 员 工 都 可 以 查 看 菜 单 和 今 日 特 价 系 统 的 顾 客 是 注 册 到 系 统 的 员 工, 可 以 订 餐 ( 如 果 未 登 录, 需 先 登 录 ) 注 册 工 资 支 付 预 约 规 律 的 订 餐, 在 特 殊 情 况 下 可 以 覆 盖 预 订 餐 厅 员 工 是 特 殊 顾 客, 可 以 进 行 备 餐 生 成 付 费 请 求 和 请 求 送 餐, 其 中 对 于 注 册 工 资 支 付 的 顾 客 生 成 付 费 请 求 并 发 送 给 工 资 系 统 菜 单 管 理 员 是 餐 厅 特 定 员 工, 可 以 管 理 菜 单 送 餐 员 可 以 打 印 送 餐 说 明, 记 录 送 餐 信 息 ( 如 送 餐 时 间 ) 以 及 记 录 收 费 ( 对 于 没 有 注 册 工 资 支 付 的 顾 客, 由 送 餐 员 收 取 现 金 后 记 录 ) 顾 客 订 餐 过 程 如 下 : 1. 顾 客 请 求 查 看 菜 单 ; 2. 系 统 显 示 菜 单 和 今 日 特 价 ; 3. 顾 客 选 菜 ; 4. 系 统 显 示 订 单 和 价 格 ; 5. 顾 客 确 认 订 单 ; 6. 系 统 显 示 可 送 餐 时 间 ; 7. 顾 客 指 定 送 餐 时 间 地 点 和 支 付 方 式 ; 8. 系 统 确 认 接 受 订 单, 然 后 发 送 Email 给 顾 客 以 确 认 订 餐, 同 时 发 送 相 关 订 餐 信 息 通 知 给 餐 厅 员 工 系 统 采 用 面 向 对 象 方 法 开 发, 使 用 UML 进 行 建 模 系 统 的 顶 层 用 例 图 和 一 次 订 餐 的 活 动 图 初 稿 分 别 如 图 3-1 和 图 3-2 所 示 问 题 1 (2 分 ) 根 据 说 明 中 的 描 述, 给 出 图 3-1 中 A1 和 A2 所 对 应 的 参 与 者 问 题 2 (8 分 ) 根 据 说 明 中 的 描 述, 给 出 图 3-1 中 缺 少 的 四 个 用 例 及 其 所 对 应 的 参 与 者 问 题 3 (4 分 ) 根 据 说 明 中 的 描 述, 给 出 图 3-2 中 (1)~(4) 处 对 应 的 活 动 名 称 或 图 形 符 号 问 题 4 (1 分 ) 指 出 图 3-1 中 员 工 和 顾 客 之 间 是 什 么 关 系, 并 解 释 该 关 系 的 内 涵 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 6 页 ( 共 15 页 )

图 3-1 COS 系 统 顶 层 用 例 图 (2) (1) (3) (4) 图 3-2 一 次 订 餐 的 活 动 图 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 7 页 ( 共 15 页 )

试 题 四 ( 共 15 分 ) 阅 读 下 列 说 明, 回 答 问 题 1 至 问 题 2, 将 解 答 填 入 答 题 纸 的 对 应 栏 内 说 明 0-1 背 包 问 题 可 以 描 述 为 : 有 n 个 物 品, 对 i = 1, 2,, n, 第 i 个 物 品 价 值 为 v i, 重 量 为 w i (v i 和 w i 为 非 负 数 ), 背 包 容 量 为 W(W 为 非 负 数 ), 选 择 其 中 一 些 物 品 装 入 背 包, 使 装 n 入 背 包 物 品 的 总 价 值 最 大, 即 max vi x i, 且 总 重 量 不 超 过 背 包 容 量, 即 w i x i W, i 1 其 中, x 0,1,xi=0 表 示 第 i 个 物 品 不 放 入 背 包,x i =1 表 示 第 i 个 物 品 放 入 背 包 i 问 题 1 (8 分 ) 用 回 溯 法 求 解 此 0-1 背 包 问 题, 请 填 充 下 面 伪 代 码 中 (1)~(4) 处 空 缺 回 溯 法 是 一 种 系 统 的 搜 索 方 法 在 确 定 解 空 间 后, 回 溯 法 从 根 结 点 开 始, 按 照 深 度 优 先 策 略 遍 历 解 空 间 树, 搜 索 满 足 约 束 条 件 的 解 对 每 一 个 当 前 结 点, 若 扩 展 该 结 点 已 经 不 满 足 约 束 条 件, 则 不 再 继 续 扩 展 为 了 进 一 步 提 高 算 法 的 搜 索 效 率, 往 往 需 要 设 计 一 个 限 界 函 数, 判 断 并 剪 枝 那 些 即 使 扩 展 了 也 不 能 得 到 最 优 解 的 结 点 现 在 假 设 已 经 设 计 了 BOUND( v,w,k,w ) 函 数, 其 中 v w k 和 W 分 别 表 示 当 前 已 经 获 得 的 价 值 当 前 背 包 的 重 量 已 经 确 定 是 否 选 择 的 物 品 数 和 背 包 的 总 容 量 对 应 于 搜 索 树 中 的 某 个 结 点, 该 函 数 值 表 示 确 定 了 部 分 物 品 是 否 选 择 之 后, 对 剩 下 的 物 品 在 满 足 约 束 条 件 的 前 提 下 进 行 选 择 可 能 获 得 的 最 大 价 值, 若 该 价 值 小 于 等 于 当 前 已 经 得 到 的 最 优 解, 则 该 结 点 无 需 再 扩 展 下 面 给 出 0-1 背 包 问 题 的 回 溯 算 法 伪 代 码 函 数 参 数 说 明 如 下 : W: 背 包 容 量 ;n: 物 品 个 数 ;w: 重 量 数 组 ; v: 价 值 数 组 ;fw: 获 得 最 大 价 值 时 背 包 的 重 量 ;fp: 背 包 获 得 的 最 大 价 值 ;X: 问 题 的 最 优 解 变 量 说 明 如 下 : cw: 当 前 的 背 包 重 量 ;cp: 当 前 获 得 的 价 值 ;k: 当 前 考 虑 的 物 品 编 号 ;Y: 当 前 已 获 得 的 部 分 解 BKNAP( W,n,w,v,fw,fp,X ) 1 cw cp 0 2 (1) 3 fp -1 4 while true 5 while k n and cw + w[k] W do 6 (2) 7 cp cp + v[k] 8 Y[k] 1 9 k k + 1 10 if k > n then 11 if fp < cp then n i 1 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 8 页 ( 共 15 页 )

12 fp cp 13 fw cw 14 k n 15 X Y 16 else Y(k) 0 17 while BOUND(cp,cw,k,W) fp do 18 while k 0 and Y(k) 1 do 19 (3) 20 if k = 0 then return 21 Y[k] 0 22 cw cw - w[k] 23 cp cp - v[k] 24 (4) 问 题 2 (7 分 ) 考 虑 表 4-1 的 实 例, 假 设 有 3 个 物 品, 背 包 容 量 为 22 图 4-1 中 是 根 据 上 述 算 法 构 造 的 搜 索 树, 其 中 结 点 的 编 号 表 示 了 搜 索 树 生 成 的 顺 序, 边 上 的 数 字 1/0 分 别 表 示 选 择 / 不 选 择 对 应 物 品 除 了 根 结 点 之 外, 每 个 左 孩 子 结 点 旁 边 的 上 下 两 个 数 字 分 别 表 示 当 前 背 包 的 重 量 和 已 获 得 的 价 值, 右 孩 子 结 点 旁 边 的 数 字 表 示 扩 展 了 该 结 点 后 最 多 可 能 获 得 的 价 值 为 获 得 最 优 解, 应 该 选 择 物 品 (5), 获 得 的 价 值 为 (6) 表 4-1 0-1 背 包 问 题 实 例 物 品 1 物 品 2 物 品 3 重 量 15 10 10 价 值 30 18 17 单 位 价 值 2 1.8 1.7 图 4-1 表 4-1 实 例 的 搜 索 树 对 于 表 4-1 的 实 例, 若 采 用 穷 举 法 搜 索 整 个 解 空 间, 则 搜 索 树 的 结 点 数 为 (7), 而 用 了 上 述 回 溯 法, 搜 索 树 的 结 点 数 为 (8) 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 9 页 ( 共 15 页 )

从 下 列 的 3 道 试 题 ( 试 题 五 至 试 题 七 ) 中 任 选 1 道 解 答 如 果 解 答 的 试 题 数 超 过 1 道, 则 题 号 小 的 1 道 解 答 有 效 试 题 五 ( 共 15 分 ) 阅 读 下 列 说 明 和 C++ 代 码, 将 应 填 入 (n) 处 的 字 句 写 在 答 题 纸 的 对 应 栏 内 说 明 现 欲 构 造 一 文 件 / 目 录 树, 采 用 组 合 (Composite) 设 计 模 式 来 设 计, 得 到 的 类 图 如 5-1 所 示 : C++ 代 码 #include <list> #include <iostream> #include <string> using namespace std; 图 5-1 类 图 class AbstractFile { protected : string name; // 文 件 或 目 录 名 称 public: void printname(){cout << name; // 打 印 文 件 或 目 录 名 称 virtual void addchild(abstractfile *file)=0; // 给 一 个 目 录 增 加 子 目 录 或 文 件 virtual void removechild(abstractfile *file)=0; // 删 除 一 个 目 录 的 子 目 录 或 文 件 virtual list<abstractfile*> *getchildren()=0; // 获 得 一 个 目 录 的 子 目 录 或 文 件 ; 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 10 页 ( 共 15 页 )

class File : public AbstractFile { public : File(string name) { (1) = name; void addchild(abstractfile *file) { return ; void removechild(abstractfile *file) { return ; (2) getchildren() { return (3) ; ; class Folder :public AbstractFile { private : list <AbstractFile*> childlist; // 存 储 子 目 录 或 文 件 public : Folder(string name) { (4) = name; void addchild(abstractfile *file) { childlist.push_back(file); void removechild(abstractfile *file) { childlist.remove(file); list<abstractfile*> *getchildren() { return (5) ; ; void main() { // 构 造 一 个 树 形 的 文 件 / 目 录 结 构 AbstractFile *rootfolder = new Folder("c:\\"); AbstractFile *compositefolder = new Folder("composite"); AbstractFile *windowsfolder = new Folder("windows"); AbstractFile *file = new File("TestComposite.java"); rootfolder->addchild(compositefolder); rootfolder->addchild(windowsfolder); compositefolder->addchild(file); 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 11 页 ( 共 15 页 )

试 题 六 ( 共 15 分 ) 阅 读 下 列 说 明 和 Java 代 码, 将 应 填 入 (n) 处 的 字 句 写 在 答 题 纸 的 对 应 栏 内 说 明 现 欲 构 造 一 文 件 / 目 录 树, 采 用 组 合 (Composite) 设 计 模 式 来 设 计, 得 到 的 类 图 如 6-1 所 示 : Java 代 码 import java.util.arraylist; import java.util.list; 图 6-1 类 图 (1) class AbstractFile { protected String name; public void printname(){system.out.println(name); public abstract boolean addchild(abstractfile file); public abstract boolean removechild(abstractfile file); public abstract List<AbstractFile> getchildren(); class File extends AbstractFile { public File(String name) { this.name = name; public boolean addchild(abstractfile file) { return false; public boolean removechild(abstractfile file) { return false; public List<AbstractFile> getchildren() { return (2) ; class Folder extends AbstractFile { 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 12 页 ( 共 15 页 )

private List <AbstractFile> childlist; public Folder(String name) { this.name = name; this.childlist = new ArrayList<AbstractFile>(); public boolean addchild(abstractfile file) { return childlist.add(file); public boolean removechild(abstractfile file) { return childlist.remove(file); public (3) <AbstractFile> getchildren() { return (4) ; public class Client { public static void main(string[] args) { // 构 造 一 个 树 形 的 文 件 / 目 录 结 构 AbstractFile rootfolder = new Folder("c:\\"); AbstractFile compositefolder = new Folder("composite"); AbstractFile windowsfolder = new Folder("windows"); AbstractFile file = new File("TestComposite.java"); rootfolder.addchild(compositefolder); rootfolder.addchild(windowsfolder); compositefolder.addchild(file); // 打 印 目 录 文 件 树 printtree(rootfolder); private static void printtree(abstractfile ifile) { ifile.printname(); List <AbstractFile> children = ifile.getchildren(); if(children == null) return; for (AbstractFile file:children) { (5) ; 该 程 序 运 行 后 输 出 结 果 为 : c:\ composite TestComposite.java Windows 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 13 页 ( 共 15 页 )

试 题 七 ( 共 15 分 ) 阅 读 以 下 说 明 和 C 程 序, 将 应 填 入 (n) 处 的 字 句 写 在 答 题 纸 的 对 应 栏 内 说 明 现 有 n(n < 1000) 节 火 车 车 厢, 顺 序 编 号 为 1,2,3,...,n, 按 编 号 连 续 依 次 从 A 方 向 的 铁 轨 驶 入, 从 B 方 向 铁 轨 驶 出, 一 旦 车 厢 进 入 车 站 (Station) 就 不 能 再 回 到 A 方 向 的 铁 轨 上 ; 一 旦 车 厢 驶 入 B 方 向 铁 轨 就 不 能 再 回 到 车 站, 如 图 7-1 所 示, 其 中 Station 为 栈 结 构, 初 始 为 空 且 最 多 能 停 放 1000 节 车 厢 图 7-1 车 站 示 意 图 下 面 的 C 程 序 判 断 能 否 从 B 方 向 驶 出 预 先 指 定 的 车 厢 序 列, 程 序 中 使 用 了 栈 类 型 STACK, 关 于 栈 基 本 操 作 的 函 数 原 型 说 明 如 下 : void InitStack(STACK *s): 初 始 化 栈 void Push(STACK *s,int e): 将 一 个 整 数 压 栈, 栈 中 元 素 数 目 增 1 void Pop(STACK *s): 栈 顶 元 素 出 栈, 栈 中 元 素 数 目 减 1 int Top(STACK s): 返 回 非 空 栈 的 栈 顶 元 素 值, 栈 中 元 素 数 目 不 变 int IsEmpty(STACK s): 若 是 空 栈 则 返 回 1, 否 则 返 回 0 C 程 序 #include<stdio.h> /* 此 处 为 栈 类 型 及 其 基 本 操 作 的 定 义, 省 略 */ int main( ){ STACK station; int state[1000]; int n; /* 车 厢 数 */ int begin, i, j, maxno; /*maxno 为 A 端 正 待 入 栈 的 车 厢 编 号 */ printf(" 请 输 入 车 厢 数 : "); scanf("%d",&n); 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 14 页 ( 共 15 页 )

printf(" 请 输 入 需 要 判 断 的 车 厢 编 号 序 列 ( 以 空 格 分 隔 ): "); if (n < 1) return -1; for (i = 0; i<n; i++) /* 读 入 需 要 驶 出 的 车 厢 编 号 序 列, 存 入 数 组 state[] */ scanf("%d",&state[i]); (1) ; /* 初 始 化 栈 */ maxno = 1; for(i = 0; i < n; ){/* 检 查 输 出 序 列 中 的 每 个 车 厢 号 state[i] 是 否 能 从 栈 中 获 取 */ if ( (2) ){/* 当 栈 不 为 空 时 */ if (state[i] == Top(station)){ /* 栈 顶 车 厢 号 等 于 被 检 查 车 厢 号 */ printf("%d ",Top(station)); Pop(&station); i++; else if ( (3) ){ printf("error\n"); return 1; else { begin = (4) ; for(j = begin+1; j<=state[i]; j++) { Push(&station, j); else { /* 当 栈 为 空 时 */ begin = maxno; for(j = begin; j<=state[i]; j++){ Push(&station, j); maxno = (5) ; printf("ok"); return 0; 2009 年 下 半 年 软 件 设 计 师 下 午 试 卷 第 15 页 ( 共 15 页 )

软 件 设 计 师 推 荐 软 件 设 计 师 考 试 政 策 考 试 时 间 :http://www.csairk.com/pxjd/200910121714211235.htm 考 试 大 纲 :http://www.csairk.com/ksdg/201006171615111082.htm 软 件 设 计 师 考 试 辅 导 类 别 一 次 分 期 真 题 模 拟 题 在 线 辅 导 588 388 11 10 查 看 详 情 :http://www.csairk.com/ruankao/kspx.htm 冲 刺 辅 导 388 5 6 查 看 详 情 :http://www.csairk.com/ruankao/kscc.htm 软 件 设 计 师 考 试 视 频 推 荐 视 频 名 称 价 格 内 容 软 件 设 计 师 视 频 教 程 420 3862 分 钟 查 看 详 情 :http://v.educity.cn/chapters.asp?csid=2 软 件 设 计 师 考 试 串 讲 视 频 教 程 198 670 分 钟 查 看 详 情 :http://v.educity.cn/chapters.asp?csid=70 软 件 设 计 师 考 试 真 题 解 析 视 频 218 2599 分 钟 查 看 详 情 :http://v.educity.cn/chapters.asp?csid=49 软 件 设 计 师 考 试 书 籍 推 荐 书 籍 名 称 价 格 软 件 设 计 师 考 试 软 件 设 计 考 点 精 讲 真 题 解 析 与 考 前 必 练 49.00 查 看 详 情 :http://www.csairk.com/book/viewbook.asp?id=204 软 件 设 计 师 考 试 考 点 突 破 程 序 设 计 实 战 练 习 一 本 通 69.00 查 看 详 情 :http://www.csairk.com/book/viewbook.asp?id=200 软 件 设 计 师 考 试 冲 刺 指 南 ( 新 修 订 版 ) 55.00 查 看 详 情 :http://www.csairk.com/book/viewbook.asp?id=159 软 件 设 计 师 考 试 考 点 分 析 与 真 题 详 解 ( 最 新 版 ) 89.90 查 看 详 情 :http://www.csairk.com/book/viewbook.asp?id=138 软 件 设 计 师 考 试 试 题 分 类 精 解 ( 第 3 版 ) 69.80 查 看 详 情 :http://www.csairk.com/book/viewbook.asp?id=135