二 级 公 共 基 础 知 识 ( 一 ) 一 单 项 选 择 题 1 下 列 链 表 中, 其 逻 辑 结 构 属 于 非 线 性 结 构 的 是 A. 循 环 链 表 B. 双 向 链 表 C. 带 链 的 栈 D. 二 叉 链 表 2 设 循 环 队 列 的 存 储 空 间 为 Q(1:35), 初 始 状 态 为 front=rear=35 现 经 过 一 系 列 入 队 与 退 队 运 算 后,front=15,rear=15, 则 循 环 队 列 中 的 元 素 个 数 为 A.16 B.20 C.0 或 35 D.15 3 下 列 关 于 栈 的 叙 述 中, 正 确 的 是 A. 栈 顶 元 素 一 定 是 最 先 入 栈 的 元 素 B. 栈 操 作 遵 循 先 进 后 出 的 原 则 C. 栈 底 元 素 一 定 是 最 后 入 栈 的 元 素 D. 以 上 三 种 说 法 都 不 对 4 下 列 叙 述 中 正 确 的 是 A. 循 环 队 列 是 队 列 的 一 种 链 式 存 储 结 构 B. 循 环 队 列 是 一 种 逻 辑 结 构 C. 循 环 队 列 是 队 列 的 一 种 顺 序 存 储 结 构 D. 循 环 队 列 是 非 线 性 结 构 5 下 列 叙 述 中 正 确 的 是 A. 栈 是 一 种 先 进 先 出 的 线 性 表 B. 队 列 是 一 种 后 进 先 出 的 线 性 表 C. 栈 与 队 列 都 是 非 线 性 结 构 D. 以 上 三 种 说 法 都 不 对 6 一 棵 二 叉 树 共 有 25 个 结 点, 其 中 5 个 是 叶 子 结 点, 则 度 为 1 的 结 点 数 为 A.4 B.16 C.10 D.6 7 下 列 叙 述 中 正 确 的 是 A. 算 法 的 效 率 只 与 问 题 的 规 模 有 关, 而 与 数 据 的 存 储 结 构 无 关 B. 算 法 的 时 间 复 杂 度 是 指 执 行 算 法 所 需 要 的 计 算 工 作 量 C. 数 据 的 逻 辑 结 构 与 存 储 结 构 是 一 一 对 应 的 D. 算 法 的 时 间 复 杂 度 与 空 间 复 杂 度 一 定 相 关 8 下 面 对 队 列 的 叙 述 正 确 的 是 A. 队 列 属 于 非 线 性 表 B. 队 列 按 先 进 后 出 原 则 组 织 数 据 C. 队 列 在 队 尾 删 除 数 据 D. 队 列 按 先 进 先 出 原 则 组 织 数 据 9 对 下 图 的 二 叉 树 进 行 前 序 遍 历 的 结 果 为 A.DYBEAFCZX B.YDEBFZXCA C.ABDYECFXZ D.ABCDEFXYZ 10 某 二 叉 树 中 有 n 个 度 为 2 的 结 点, 则 该 二 叉 树 中 的 叶 子 结 点 为 A.n+1 B.n-1 C.2n D.n/2
11 下 列 叙 述 正 确 的 是 A. 算 法 就 是 程 序 B. 设 计 算 法 时 只 需 要 考 虑 数 据 结 构 的 设 计 C. 设 计 算 法 时 只 需 要 考 虑 结 果 的 可 靠 性 D. 以 上 三 种 说 法 都 不 对 12 下 列 关 于 线 性 链 表 的 叙 述 中, 正 确 的 是 A. 各 数 据 结 点 的 存 储 空 间 可 以 不 连 续, 但 它 们 的 存 储 顺 序 与 逻 辑 顺 序 必 须 一 致 B. 各 数 据 结 点 的 存 储 顺 序 与 逻 辑 顺 序 可 以 不 一 致, 但 它 们 的 存 储 空 间 必 须 连 续 C. 进 行 插 入 与 删 除 时, 不 需 要 移 动 表 中 的 元 素 D. 以 上 三 种 说 法 都 不 对 13 下 列 关 于 二 叉 树 的 叙 述 中, 正 确 的 是 A. 叶 子 结 点 总 是 比 度 为 2 的 结 点 少 一 个 B. 叶 子 结 点 总 是 比 度 为 2 的 结 点 多 一 个 C. 叶 子 结 点 数 是 度 为 2 的 结 点 数 的 两 倍 D. 度 为 2 的 结 点 数 是 度 为 1 的 结 点 数 的 两 倍 14 下 列 关 于 栈 的 叙 述 正 确 的 是 A. 栈 顶 元 素 最 先 能 被 删 除 B. 栈 顶 元 素 最 后 才 能 被 删 除 C. 栈 底 元 素 永 远 不 能 被 删 除 D. 以 上 三 种 说 法 都 不 对 15 下 列 叙 述 中 正 确 的 是 A. 有 一 个 以 上 根 结 点 的 数 据 结 构 不 一 定 是 非 线 性 结 构 B. 只 有 一 个 根 结 点 的 数 据 结 构 不 一 定 是 线 性 结 构 C. 循 环 链 表 是 非 线 性 结 构 D. 双 向 链 表 是 非 线 性 结 构 16 某 二 叉 树 共 有 7 个 结 点, 其 中 叶 子 结 点 只 有 1 个, 则 该 二 叉 树 的 深 度 为 ( 假 设 根 结 点 在 第 1 层 ) A.3 B.4 C.6 D.7 17 下 列 叙 述 中 正 确 的 是 A. 线 性 表 的 链 式 存 储 结 构 与 顺 序 存 储 结 构 所 需 要 的 存 储 空 间 是 相 同 的 B. 线 性 表 的 链 式 存 储 结 构 所 需 要 的 存 储 空 间 一 般 要 多 于 顺 序 存 储 结 构 C. 线 性 表 的 链 式 存 储 结 构 所 需 要 的 存 储 空 间 一 般 要 少 于 顺 序 存 储 结 构 D. 上 述 3 种 说 法 都 不 对 18 下 列 叙 述 中 正 确 的 是 A. 在 栈 中, 栈 中 元 素 随 栈 底 指 针 与 栈 顶 指 针 的 变 化 而 动 态 变 化 B. 在 栈 中, 栈 顶 指 针 不 变, 栈 中 元 素 随 栈 底 指 针 的 变 化 而 动 态 变 化 C. 在 栈 中, 栈 底 指 针 不 变, 栈 中 元 素 随 栈 顶 指 针 的 变 化 而 动 态 变 化 D. 上 述 3 种 说 法 都 不 对
19 下 列 叙 述 中 正 确 的 是 A. 对 长 度 为 n 的 有 序 链 表 进 行 查 找, 最 坏 情 况 下 需 要 的 比 较 次 数 为 n B. 对 长 度 为 n 的 有 序 链 表 进 行 对 分 查 找, 最 坏 情 况 下 需 要 的 比 较 次 数 为 (n/2) C. 对 长 度 为 n 的 有 序 链 表 进 行 对 分 查 找, 最 坏 情 况 下 需 要 的 比 较 次 数 为 (log 2n) D. 对 长 度 为 n 的 有 序 链 表 进 行 对 分 查 找, 最 坏 情 况 下 需 要 的 比 较 次 数 为 (nlog 2n) 20 算 法 的 时 间 复 杂 度 是 指 A. 算 法 的 执 行 时 间 B. 算 法 所 处 理 的 数 据 量 C. 算 法 程 序 中 的 语 句 或 指 令 条 数 D. 算 法 在 执 行 过 程 中 所 需 要 的 基 本 运 算 次 数 21 下 列 数 据 结 构 中, 属 于 非 线 性 结 构 的 是 A. 循 环 队 列 B. 带 链 队 列 C. 二 叉 树 D. 带 链 栈 22 下 列 数 据 结 构 中, 能 按 照 先 进 后 出 原 则 存 取 数 据 的 是 A. 循 环 队 列 B. 栈 C. 队 列 D. 二 叉 树 23 对 于 循 环 队 列, 下 列 叙 述 中 正 确 的 是 A. 队 头 指 针 是 固 定 不 变 的 B. 队 头 指 针 一 定 大 于 队 尾 指 针 C. 队 头 指 针 一 定 小 于 队 尾 指 针 D. 队 头 指 针 可 以 大 于 队 尾 指 针, 也 可 以 小 于 队 尾 指 针 24 算 法 的 空 间 复 杂 度 是 指 A. 算 法 在 执 行 过 程 中 所 需 要 的 计 算 机 存 储 空 间 B. 算 法 所 处 理 的 数 据 量 C. 算 法 程 序 中 的 语 句 或 指 令 条 数 D. 算 法 在 执 行 过 程 中 所 需 要 的 临 时 工 作 单 元 数 25 下 列 叙 述 中 正 确 的 是 A. 栈 是 先 进 先 出 的 线 性 表 B. 队 列 是 先 进 后 出 的 线 性 表 C. 循 环 队 列 是 非 线 性 结 构 D. 有 序 线 性 表 既 可 以 采 用 顺 序 存 储 结 构, 也 可 以 采 用 链 式 存 储 结 构 26 支 持 子 程 序 调 用 的 数 据 结 构 是 A. 栈 B. 树 C. 队 列 D. 二 叉 树 27 某 二 叉 树 有 5 个 度 为 2 的 结 点, 则 该 二 叉 树 中 的 叶 子 结 点 数 是
A.10 B.8 C.6 D.4 28 一 个 栈 的 初 始 状 态 为 空 现 将 元 素 1 2 3 4 5 A B C D E 依 次 入 栈, 然 后 再 依 次 出 栈, 则 元 素 出 栈 的 顺 序 是 A.12345ABCDE B.EDCBA54321 C.ABCDE12345 D.54321EDCBA 29 下 列 叙 述 中 正 确 的 是 A. 循 环 队 列 有 队 头 和 队 尾 两 个 指 针, 因 此, 循 环 队 列 是 非 线 性 结 构 B. 在 循 环 队 列 中, 只 需 要 队 头 指 针 就 能 反 映 队 列 中 元 素 的 动 态 变 化 情 况 C. 在 循 环 队 列 中, 只 需 要 队 尾 指 针 就 能 反 映 队 列 中 元 素 的 动 态 变 化 情 况 D. 循 环 队 列 中 元 素 的 个 数 是 由 队 头 指 针 和 队 尾 指 针 共 同 决 定 的 30 在 长 度 为 n 的 有 序 线 性 表 中 进 行 二 分 查 找, 最 坏 情 况 下 需 要 比 较 的 次 数 是 A.O(n) B.O(n 2 ) C.O(log 2n) D.O(nlog 2n) 31 下 列 叙 述 中 正 确 的 是 A. 顺 序 存 储 结 构 的 存 储 一 定 是 连 续 的, 链 式 存 储 结 构 的 存 储 空 间 不 一 定 是 连 续 的 B. 顺 序 存 储 结 构 只 针 对 线 性 结 构, 链 式 存 储 结 构 只 针 对 非 线 性 结 构 C. 顺 序 存 储 结 构 能 存 储 有 续 表, 链 式 存 储 结 构 不 能 存 储 有 序 表 D. 链 式 存 储 结 构 比 顺 序 存 储 结 构 节 省 存 储 空 间 32 下 面 选 项 中 不 属 于 面 向 对 象 程 序 设 计 特 征 的 是 A. 继 承 性 B. 多 态 性 C. 类 比 性 D. 封 闭 性 33 下 列 选 项 中 属 于 面 向 对 象 方 法 主 要 特 征 的 是 A. 继 承 B. 自 顶 向 下 C. 模 块 化 D. 逐 步 求 精 34 结 构 化 程 序 所 要 求 的 基 本 结 构 不 包 括 A. 顺 序 结 构 B.goto 跳 转 C. 选 择 ( 分 支 ) 结 构 D. 重 复 ( 循 环 ) 结 构 35 面 向 对 象 方 法 中, 继 承 是 指 A. 一 组 对 象 所 具 有 的 相 似 性 质 B. 一 个 对 象 具 有 另 一 个 对 象 的 性 质 C. 各 对 象 之 间 的 共 同 性 质 D. 类 之 间 共 享 属 性 和 操 作 的 机 制 36 下 列 选 项 中 不 属 于 结 构 化 程 序 设 计 原 则 的 是 A. 可 封 装 B. 自 顶 向 下 C. 模 块 化 D. 逐 步 求 精 37 在 面 向 对 象 方 法 中, 不 属 于 对 象 基 本 特 点 的 是 A. 一 致 性 B. 分 类 性 C. 多 态 性 D. 标 识 唯 一 性 38 在 结 构 化 程 序 设 计 中, 模 块 划 分 的 原 则 是
A. 各 模 块 应 包 括 尽 量 多 的 功 能 B. 各 模 块 的 规 模 应 尽 量 大 C. 各 模 块 之 间 的 联 系 应 尽 量 紧 密 D. 模 块 内 具 有 高 内 聚 度, 模 块 间 具 有 低 耦 合 度 39 数 据 字 典 (DD) 所 定 义 的 对 象 都 包 含 于 A. 程 序 流 程 图 B. 数 据 流 图 (DFD 图 ) C. 方 框 图 D. 软 件 结 构 图 40 软 件 需 求 规 格 说 明 书 的 作 用 不 包 括 A. 软 件 可 行 性 研 究 的 依 据 B. 用 户 与 开 发 人 员 对 软 件 要 做 什 么 的 共 同 理 解 C. 软 件 验 收 的 依 据 D. 软 件 设 计 的 依 据 41 下 面 属 于 黑 盒 测 试 方 法 的 是 A. 逻 辑 覆 盖 B. 语 句 覆 盖 C. 路 径 覆 盖 D. 边 界 值 分 析 42 下 面 不 属 于 软 件 设 计 阶 段 任 务 的 是 A. 数 据 库 设 计 B. 算 法 设 计 C. 软 件 总 体 设 计 D. 制 定 软 件 确 认 测 试 计 划 43 软 件 生 命 周 期 中 的 活 动 不 包 括 A. 软 件 维 护 B. 需 求 分 析 C. 市 场 调 研 D. 软 件 测 试 44 下 面 不 属 于 需 求 分 析 阶 段 任 务 的 是 A. 确 定 软 件 系 统 的 性 能 需 求 B. 确 定 软 件 系 统 的 功 能 需 求 C. 制 定 软 件 集 成 测 试 计 划 D. 需 求 规 格 说 明 书 评 审 45 在 黑 盒 测 试 方 法 中, 设 计 测 试 用 例 的 主 要 根 据 是 A. 程 序 外 部 功 能 B. 程 序 数 据 结 构 C. 程 序 流 程 图 D. 程 序 内 部 逻 辑 46 在 软 件 设 计 中 不 使 用 的 工 具 是 A. 系 统 结 构 图 B. 程 序 流 程 图 C.PAD 图 D. 数 据 流 图 (DFD 图 ) 47 下 列 叙 述 中 正 确 的 是 A. 软 件 测 试 的 主 要 目 的 是 发 现 程 序 中 的 错 误 B. 软 件 测 试 的 主 要 目 的 是 确 定 程 序 中 错 误 的 位 置 C. 为 了 提 高 软 件 测 试 的 效 率, 最 好 由 程 序 编 制 者 自 己 来 完 成 软 件 测 试 工 作 D. 软 件 测 试 是 证 明 软 件 没 有 错 误 48 软 件 按 功 能 可 以 分 为 应 用 软 件 系 统 软 件 和 支 撑 软 件 ( 或 工 具 软 件 ) 下 面
属 于 应 用 软 件 的 是 A. 学 生 成 绩 管 理 系 统 B.C 语 言 编 译 程 序 C.UNIX 操 作 系 统 D. 数 据 库 管 理 系 统 49 某 系 统 总 体 结 构 图 如 下 图 所 示 该 系 统 总 体 结 构 图 的 深 度 是 A.7 B.8 C.3 D.2 50 程 序 调 试 的 任 务 是 A. 设 计 测 试 用 例 B. 验 证 程 序 的 正 确 性 C. 发 现 程 序 中 的 错 误 D. 诊 断 和 改 正 程 序 中 的 错 误 51 在 软 件 开 发 中, 需 求 分 析 阶 段 产 生 的 主 要 文 档 是 A. 软 件 集 成 测 试 计 划 B. 软 件 详 细 设 计 说 明 书 C. 用 户 手 册 D. 软 件 需 求 规 格 说 明 书 52 下 面 描 述 中 错 误 的 是 A. 系 统 总 体 结 构 图 支 持 软 件 系 统 的 详 细 设 计 B. 软 件 设 计 是 将 软 件 需 求 转 换 为 软 件 表 示 的 过 程 C. 数 据 结 构 与 数 据 库 设 计 是 软 件 设 计 的 任 务 之 一 D.PAD 图 是 软 件 详 细 设 计 的 表 示 工 具 答 案 : 一 单 项 选 择 题 1 D [ 解 析 ] 循 环 链 表 双 向 链 表 带 链 的 栈 都 是 线 性 结 构, 二 叉 链 表 是 非 线 性 结 构 二 叉 树 的 链 式 存 储 结 构, 所 以 选 D 2 C [ 解 析 ] 在 循 环 队 列 中, 当 头 指 针 = 尾 指 针 时, 有 两 种 情 况, 一 个 是 队 空 状 态, 一 个 是 队 满 状 态 该 循 环 队 列 的 初 始 状 态 是 队 头 指 针 = 队 尾 指 针 =35, 经 过 一 系 列 入 队 与 退 队 运 算 后, 队 头 指 针 和 队 尾 指 针 都 发 生 了 变 化, 但 还 是 队 头 指 针 等 于 队 尾 指 针, 队 空 时, 循 环 队 列 中 的 元 素 个 数 是 0, 队 满 时, 元 素 个 数 是 循 环 队 列 的 最 大 空 间 35 3 B [ 解 析 ] 栈 是 限 定 在 一 端 进 行 插 入 与 删 除 的 线 性 表 在 栈 中, 允 许 插 入 与 删 除 的 这 一 端 称 为 栈 顶, 不 允 许 插 入 与 删 除 的 另 一 端 称 为 栈 底 栈 是 按 照 先 进 后 出 或 后 进 先 出 的 原 则 组 织 数 据 的, 因 此, 栈 也 被 称 为 先 进 后 出 表 或 后
进 先 出 表 4 C [ 解 析 ] 循 环 队 列 是 一 种 顺 序 存 储 的 线 性 结 构 5 D [ 解 析 ] 栈 和 队 列 都 是 线 性 结 构, 所 以 选 项 C 错 误 ; 栈 是 一 种 先 进 后 出 的 线 性 表, 故 选 项 A 错 误 ; 队 列 是 一 种 先 进 先 出 的 线 性 表, 故 选 项 B 错 误, 所 以 选 D 6 B [ 解 析 ] 由 二 叉 树 的 性 质 3 可 知, 度 为 0 的 结 点 数 ( 即 叶 子 结 点 数 ) 总 是 比 度 为 2 的 结 点 多 一 个, 此 题 中 叶 子 结 点 数 为 5, 所 以 度 为 2 的 结 点 数 为 4, 二 叉 树 的 总 结 点 数 = 叶 子 结 点 数 + 度 为 1 的 结 点 数 + 度 为 2 的 结 点 数, 所 以 此 题 度 为 1 的 结 点 数 为 25-5-4=16 7 B [ 解 析 ] 根 据 算 法 时 间 复 杂 度 和 空 间 复 杂 度 的 定 义 可 知, 算 法 的 时 间 复 杂 度 就 是 执 行 该 算 法 所 需 要 的 计 算 工 作 量, 算 法 所 执 行 的 基 本 运 算 次 数 与 问 题 的 规 模 有 关 ; 而 算 法 的 空 间 复 杂 度 就 是 执 行 该 算 法 所 需 要 的 内 存 空 间 通 常 用 时 间 复 杂 度 和 空 间 复 杂 度 来 衡 量 算 法 的 效 率, 但 是 算 法 的 时 间 复 杂 度 与 空 间 复 杂 度 并 不 一 定 相 关 数 据 的 逻 辑 结 构 是 指 各 个 数 据 元 素 之 间 的 逻 辑 关 系, 反 映 人 们 对 数 据 含 义 的 理 解, 与 数 据 的 存 储 结 构 没 有 关 系, 是 独 立 于 计 算 机 的 算 法 的 执 行 效 率 不 仅 与 问 题 的 规 模 有 关, 还 与 数 据 的 存 储 结 构 有 关 8 D [ 解 析 ] 队 列 是 限 定 了 插 入 和 删 除 操 作 的 线 性 表, 它 只 允 许 在 表 的 一 端 进 行 插 入 操 作, 而 在 另 外 一 端 进 行 删 除 操 作 在 队 列 中, 允 许 插 入 元 素 的 一 端 称 为 队 尾, 允 许 删 除 元 素 的 一 端 称 为 队 头 队 列 按 照 先 进 先 出 的 原 则 组 织 数 据, 因 此 又 称 为 先 进 先 出 的 线 性 表 9 C [ 解 析 ] 前 序 遍 历 二 叉 树 的 操 作 定 义 为 : 若 二 叉 树 为 空, 则 空 操 作 ; 否 则 1) 访 问 根 结 点 ;2) 前 序 遍 历 左 子 树 ;3) 前 序 遍 历 右 子 树 根 据 题 目 可 知, 该 二 叉 树 前 序 遍 历 的 结 果 是 :ABDYECFXZ 10 A [ 解 析 ] 根 据 二 叉 树 的 性 质 3: 在 任 意 一 棵 二 叉 树 中, 度 为 0 的 结 点 ( 即 叶 子 结 点 ) 总 是 比 度 为 2 的 结 点 多 一 个 本 题 中 度 为 2 的 结 点 数 为 n, 故 叶 子 结 点 数 为 n+1 个 11 D [ 解 析 ] 算 法 是 一 系 列 解 决 问 题 的 清 晰 指 令, 也 就 是 说, 能 够 对 一 定 规 范 的 输 入, 在 有 限 时 间 内 获 得 所 要 求 的 输 出 程 序 (program) 是 为 实 现 特 定 目 标 或 解 决 特 定 问 题 而 用 计 算 机 语 言 编 写 的 命 令 序 列 的 集 合 因 此, 算 法 不 等 于 程 序 因 为 每 个 算 法 实 际 上 是 按 解 题 要 求 从 环 境 能 进 行 的 所 有 操 作 中 选 择 合 适 的 操 作 所 组 成 的 一 组 指 令 序 列, 所 以 设 计 算 法 时, 不 仅 要 考 虑 算 法 中 对 数 据 的 运 算 和 操 作, 同 时 还 要 考 虑 算 法 的 控 制 结 构 一 个 算 法 的 功 能 不 但 取 决 于 所 选 用 的 操 作, 而 且 还 与 各 操 作 之 间 的 执 行 顺 序 有 关 算 法 中 各 操 作 之 间 的 执 行 顺 序 称 为 算 法 的 控 制 结 构 12 C [ 解 析 ] 线 性 表 是 一 个 线 性 结 构, 它 是 一 个 含 有 n 0 个 结 点 的 有 限 序 列 线 性 表 的 链 式 存 储 称 为 线 性 链 表, 指 的 是 用 一 组 任 意 的 存 储 单 元 来 依 次 存 放 线 性 表
的 结 点, 这 组 存 储 单 元 既 可 以 是 连 续 的, 也 可 以 是 不 连 续 的, 甚 至 是 零 散 分 布 在 内 存 中 的 任 意 位 置 上 的 因 此, 链 表 中 结 点 的 逻 辑 次 序 和 物 理 次 序 不 一 定 相 同 链 表 是 通 过 每 个 结 点 的 链 域 将 线 性 表 的 n 个 结 点 按 其 逻 辑 次 序 链 接 在 一 起 的 在 线 性 链 表 中 插 入 或 删 除 一 个 元 素, 不 需 要 移 动 表 中 的 数 据 元 素, 只 需 要 改 变 被 插 入 或 删 除 元 素 所 在 结 点 及 其 前 后 结 点 的 指 针 域 即 可 13 B [ 解 析 ] 根 据 二 叉 树 的 性 质, 对 于 任 何 一 棵 二 叉 树, 度 为 0 的 结 点 ( 即 叶 子 结 点 ) 总 是 比 度 为 2 的 结 点 多 一 个 14 A [ 解 析 ] 栈 是 限 定 只 在 一 端 进 行 插 入 与 删 除 的 特 殊 线 性 表 允 许 进 行 插 入 和 删 除 操 作 的 一 端 称 为 栈 顶 (top), 另 一 端 为 栈 底 (bottom) 栈 底 固 定, 而 栈 顶 浮 动 栈 按 照 后 进 先 出 的 原 则 存 储 数 据, 先 进 入 的 数 据 被 压 入 栈 底, 最 后 进 入 的 数 据 在 栈 顶, 需 要 读 数 据 时, 从 栈 项 开 始 弹 出 数 据 ( 最 后 一 个 进 入 的 数 据 被 第 一 个 读 出 来 ) 因 此, 栈 顶 的 元 素 最 先 被 删 除 15 B [ 解 析 ] 线 性 结 构 指 的 是 数 据 元 素 之 间 存 在 一 对 一 线 性 关 系 的 数 据 结 构, 这 样 的 结 构 中 只 有 一 个 根 结 点, 如 循 环 链 表 和 双 向 链 表 非 线 性 结 构 指 的 是 数 据 元 素 之 间 存 在 一 对 一 非 线 性 关 系 的 数 据 结 构, 这 样 的 结 构 中 可 能 有 一 个 根 结 点, 如 树 形 结 构, 也 可 能 有 多 个 根 结 点, 如 网 状 结 构 16 D [ 解 析 ] 叶 子 结 点 个 数 = 度 为 2 的 结 点 个 数 +1 在 此 题 中, 叶 子 结 点 个 数 为 1, 说 明 度 为 2 的 结 点 数 为 0, 即 二 叉 树 中 不 存 在 度 为 2 的 结 点, 只 有 度 为 1 的 结 点 和 叶 子 结 点, 那 么 此 二 叉 树 就 是 一 棵 单 分 支 树, 树 中 结 点 个 数 即 为 树 的 深 度 17 B [ 解 析 ] 顺 序 存 储 结 构 是 存 储 结 构 类 型 中 的 一 种, 该 结 构 把 逻 辑 上 相 邻 的 结 点 存 储 在 物 理 位 置 上 相 邻 的 存 储 单 元 中, 结 点 之 间 的 逻 辑 关 系 由 存 储 单 元 的 邻 接 关 系 来 体 现 由 此 得 到 的 存 储 结 构 为 顺 序 存 储 结 构, 通 常 顺 序 存 储 结 构 借 助 于 计 算 机 程 序 设 计 语 言 的 数 组 来 描 述 顺 序 存 储 结 构 的 主 要 优 点 是 节 省 存 储 空 间, 因 为 分 配 给 数 据 的 存 储 单 元 全 用 于 存 放 结 点 的 数 据, 而 结 点 之 间 的 逻 辑 关 系 没 有 占 用 额 外 的 存 储 空 间 线 性 表 的 链 式 存 储 结 构 的 特 点 是 用 一 组 任 意 的 存 储 单 元 存 储 线 性 表 的 数 据 元 素 ( 这 组 存 储 单 元 可 以 是 连 续 的, 也 可 以 是 不 连 续 的 ) 因 此, 为 了 表 示 每 个 数 据 元 素 与 其 直 接 后 继 数 据 元 素 之 间 的 逻 辑 关 系, 对 数 据 元 素 来 说, 除 了 存 储 数 据 外, 还 需 要 存 储 一 个 到 多 个 指 针, 而 顺 序 存 储 不 需 要 存 储 地 址, 所 以 从 存 储 大 小 来 看, 自 然 是 链 表 占 空 间 大, 不 过 访 问 灵 活 链 表 有 很 大 的 优 势 18 C [ 解 析 ] 栈 是 一 种 特 殊 的 线 性 表, 这 种 线 性 表 只 能 在 固 定 的 一 端 进 行 插 入 和 删 除 操 作, 允 许 插 入 和 删 除 的 一 端 称 为 栈 顶, 另 一 端 称 为 栈 底 一 个 新 元 素 只 能 从 栈 顶 一 端 进 入, 删 除 时, 只 能 删 除 栈 顶 的 元 素, 即 刚 刚 被 插 入 的 元 素 所 以 栈 又 称 后 进 先 出 表, 因 此, 在 栈 中, 栈 底 指 针 不 变, 栈 中 元 素 随 栈 顶 指 针 的 变 化 而 动 态 变 化 19 A [ 解 析 ] 对 长 度 为 n 的 有 序 链 表 进 行 查 找, 最 坏 情 况 是 从 最 小 值 开 始 查 找 最 大 值 ( 或 从 最 大 值 开 始 查 找 最 小 值 ), 这 个 过 程 需 要 比 较 的 次 数 为 n, 故 选 项 A 正 确
对 分 查 找 只 能 针 对 随 机 存 取 的 有 序 表 进 行, 而 有 序 链 表 只 能 进 行 顺 序 存 取, 不 能 进 行 随 机 存 取, 因 此 在 有 序 链 表 上 不 能 进 行 对 分 查 找, 故 B C D 选 项 都 错 误 20 D [ 解 析 ] 所 谓 算 法 的 时 间 复 杂 度, 是 指 执 行 算 法 所 需 要 的 计 算 工 作 量 为 了 能 够 比 较 客 观 地 反 映 出 一 个 算 法 的 效 率, 一 个 算 法 的 工 作 量 不 仅 应 该 与 所 使 用 的 计 算 机 程 序 设 计 语 言 以 及 程 序 编 制 者 无 关, 而 且 还 应 该 与 算 法 实 现 过 程 中 的 许 多 细 节 无 关 为 此, 可 以 用 算 法 在 执 行 过 程 中 所 需 基 本 运 算 的 执 行 次 数 来 度 量 算 法 的 工 作 量 21 C [ 解 析 ] 线 性 结 构 满 足 两 个 条 件 : 有 且 仅 有 一 个 根 结 点 ; 每 个 结 点 最 多 有 一 个 直 接 前 驱, 也 最 多 有 一 个 直 接 后 继 栈 和 队 列 均 满 足 这 两 个 条 件, 属 于 线 性 结 构 二 叉 树 属 于 非 线 性 结 构, 因 为 除 了 叶 子 结 点 外, 其 他 每 个 结 点 都 可 以 有 两 个 直 接 后 继, 不 满 足 线 性 结 构 的 条 件 22 B [ 解 析 ] 栈 是 一 种 特 殊 的 线 性 表, 其 插 入 或 者 删 除 运 算 都 在 表 的 一 端 进 行, 即 按 照 先 进 后 出 原 则 存 取 数 据 23 D [ 解 析 ] 在 循 环 队 列 中 用 队 尾 指 针 (rear) 指 向 队 列 中 的 队 尾 元 素, 用 队 头 指 针 (front) 指 向 队 头 元 素 的 前 一 个 位 置 在 循 环 队 列 结 构 中, 一 般 情 况 下 rear> front 当 存 储 空 间 的 最 后 一 个 位 置 己 被 使 用, 而 要 进 行 入 队 操 作 时, 只 要 存 储 空 间 的 第 一 个 位 置 空 闲, 便 可 将 元 素 加 入 第 一 个 位 置, 即 存 储 空 间 的 第 一 个 位 置 为 队 尾, 此 时 便 有 front>rear 24 A [ 解 析 ] 算 法 的 空 间 复 杂 度 是 指 算 法 在 执 行 过 程 中 所 需 要 的 计 算 机 存 储 空 间 25 D [ 解 析 ] 栈 是 限 定 仅 在 表 尾 进 行 插 入 和 删 除 操 作 的 线 性 表, 又 称 为 后 进 先 出 的 线 性 表 队 列 是 限 定 了 插 入 和 删 除 操 作 的 线 性 表, 又 称 为 先 进 先 出 的 线 性 表 循 环 队 列 是 队 列 的 顺 序 存 储 结 构 线 性 表 ( 无 论 有 序 还 是 无 序 ) 既 可 以 采 用 顺 序 存 储 结 构, 也 可 以 采 用 链 式 存 储 结 构 26 A [ 解 析 ] 栈 是 一 种 只 允 许 在 一 端 进 行 插 入 和 删 除 的 线 性 表, 它 是 一 种 操 作 受 限 的 线 性 表 ; 队 列 是 一 种 只 允 许 在 一 端 进 行 插 入, 而 在 另 一 端 进 行 删 除 的 线 性 表, 它 也 是 一 种 操 作 受 限 的 线 性 表 ; 二 叉 树 是 有 限 元 素 的 集 合, 该 集 合 或 者 为 空, 或 者 由 一 个 称 为 根 的 元 素 及 两 个 不 相 交 的 被 分 别 称 为 左 子 树 和 右 子 树 的 二 叉 树 组 成 这 里 只 有 栈 支 持 子 程 序 调 用 27 C [ 解 析 ] 在 任 意 一 棵 二 叉 树 中, 度 为 0 的 结 点 ( 即 叶 子 结 点 ) 总 是 比 度 为 2 的 结 点 多 一 个 本 题 中 度 为 2 的 结 点 数 为 5, 故 叶 子 结 点 数 为 5+1=6 个 28 B [ 解 析 ] 栈 是 一 种 特 殊 的 线 性 表, 这 种 线 性 表 只 能 在 固 定 的 一 端 进 行 插 入 和 删 除 操 作, 允 许 插 入 和 删 除 的 一 端 称 为 栈 顶, 另 一 端 称 为 栈 底 一 个 新 元 素 只 能 从 栈 顶 一 端 进 入, 删 除 时, 只 能 删 除 栈 顶 的 元 素, 即 刚 刚 被 插 入 的 元 素 这 表 明 栈 的 运 算 规 则 是 先 进 后 出 或 称 后 进 先 出 在 栈 顶 进 行 插 入 运 算, 称 为
进 栈 ( 或 入 栈 ), 在 栈 顶 进 行 删 除 运 算, 称 为 退 栈 ( 或 出 栈 ) 本 题 中, 依 次 进 栈, 即 依 次 插 入 元 素 1 2 3 4 5 A B C D E, 依 次 出 栈, 即 依 次 删 除 元 素, 根 据 栈 先 进 后 出 的 规 则, 应 该 以 倒 序 出 栈, 即 元 素 出 栈 顺 序 为 EDCBA54321 29 D [ 解 析 ] 所 谓 循 环 队 列, 就 是 将 队 列 存 储 空 间 的 最 后 一 个 位 置 绕 到 第 1 个 位 置, 形 成 逻 辑 上 的 环 状 空 间, 供 队 列 循 环 使 用 循 环 队 列 的 头 指 针 front 指 向 队 列 第 一 个 元 素 的 前 一 位 置, 队 尾 指 针 rear 指 向 队 列 最 后 一 个 元 素, 循 环 队 列 的 动 态 变 化 需 要 头 尾 指 针 共 同 反 映 因 为 循 环 队 列 的 长 度 是 (rearfront+maxsize)%maxsize, 所 以 循 环 队 列 的 长 度 由 队 头 和 队 尾 指 针 共 同 决 定 30 C [ 解 析 ] 二 分 法 检 索 要 求 线 性 表 结 点 按 关 键 值 排 序, 且 以 顺 序 方 式 存 储 在 查 找 时, 应 与 表 的 中 间 位 置 上 结 点 的 关 键 值 比 较, 若 相 等 则 检 索 成 功 ; 否 则 根 据 比 较 结 果 确 定 下 一 步 在 表 的 前 半 部 分 或 后 半 部 分 继 续 进 行 二 分 法 检 索 的 效 率 比 较 高, 设 线 性 表 有 n 个 元 素, 则 最 多 的 检 索 次 数 为 大 于 log 2n 的 最 小 整 数, 最 少 的 检 索 次 数 为 1 31 A [ 解 析 ] 顺 序 存 储 结 构 就 是 用 一 组 地 址 连 续 的 存 储 单 元 依 次 存 储 该 线 性 表 中 的 各 个 元 素 ; 链 式 存 储 结 构 中 各 数 据 结 点 的 存 储 序 号 是 不 连 续 的, 并 且 各 结 点 在 存 储 空 间 中 的 位 置 关 系 与 逻 辑 关 系 也 不 一 致 两 者 都 可 以 存 储 线 性 的 有 序 的 逻 辑 结 构 顺 序 结 构 使 用 的 是 连 续 物 理 空 间, 链 式 结 构 可 以 使 用 零 散 的 物 理 空 间 存 储, 链 式 结 构 更 灵 活, 不 存 在 哪 个 更 节 约 空 间 的 说 法 32 C [ 解 析 ] 对 象 是 由 数 据 和 允 许 的 操 作 组 成 的 封 装 体, 与 客 观 实 体 有 直 接 的 对 应 关 系 对 象 之 间 通 过 传 递 消 息 互 相 联 系, 以 模 拟 现 实 世 界 中 不 同 事 物 彼 此 之 间 的 联 系 面 向 对 象 程 序 设 计 的 主 要 特 征 是 : 封 装 性 继 承 性 和 多 态 性 33 A [ 解 析 ] 面 向 对 象 具 有 封 装 性 继 承 性 和 多 态 性 1) 封 装 性 : 封 装 性 使 数 据 和 加 工 该 数 据 的 方 法 ( 函 数 ) 封 装 为 一 个 整 体, 以 实 现 独 立 性 很 强 的 模 块, 使 得 用 户 只 能 见 到 对 象 的 外 特 性 ( 对 象 能 接 收 哪 些 消 息, 具 有 哪 些 处 理 能 力 ), 而 对 象 的 内 特 性 ( 保 存 内 部 状 态 的 私 有 数 据 和 实 现 加 工 能 力 的 算 法 ) 对 用 户 是 隐 蔽 的 2) 继 承 性 : 继 承 性 是 子 类 自 动 共 享 父 类 之 间 数 据 和 方 法 的 机 制 3) 多 态 性 : 同 一 消 息 为 不 同 的 对 象 接 收 时 可 产 生 完 全 不 同 的 行 动, 这 种 现 象 称 为 多 态 性 34 B [ 解 析 ] 结 构 化 程 序 设 计 方 法 主 要 由 以 下 3 种 逻 辑 结 构 组 成 1) 顺 序 结 构 : 一 种 线 性 有 序 的 结 构, 依 次 执 行 各 语 句 模 块 2) 重 复 ( 循 环 ) 结 构 : 重 复 执 行 一 个 或 几 个 模 块, 直 到 满 足 某 一 条 件 为 止 3) 选 择 ( 分 支 ) 结 构 : 根 据 条 件 成 立 与 否 选 择 程 序 执 行 的 通 路 35 D [ 解 析 ] 面 向 对 象 方 法 (object-oriented method) 是 一 种 把 面 向 对 象 的 思 想 应 用 于 软 件 开 发 过 程 中, 指 导 开 发 活 动 的 系 统 方 法, 简 称 OO(Object-Oriented) 方 法, 是 建 立 在 对 象 概 念 基 础 上 的 方 法 学 对 象 是 由 数 据 和 允 许 的 操 作 组 成 的 封 装 体, 与 客 观 实 体 有 直 接 对 应 关 系, 一 个 对 象 类 定 义 了 具 有 相 似 性 质 的 一 组 对 象 而 继 承 性 是 对 具 有 层 次 关 系 的 类 的 属 性 和 操 作 进 行 共 享 的 一 种 方 式 所 谓 面 向 对 象, 就 是 基 于 对 象 概 念, 以 对 象 为 中 心, 以 类 和 继 承 为 构 造 机 制 来
认 识 理 解 刻 画 客 观 世 界 和 设 计 构 建 相 应 的 软 件 系 统 因 此, 面 向 对 象 方 法 中, 继 承 是 指 类 之 间 共 享 属 性 和 操 作 的 机 制 36 A [ 解 析 ] 结 构 化 程 序 设 计 的 基 本 原 则 包 括 : 模 块 化 设 计 自 顶 向 下 原 则 逐 步 求 精 原 则 和 限 制 使 用 goto 语 句 37 A [ 解 析 ] 面 向 对 象 方 法 中 最 基 本 的 概 念 是 对 象, 它 的 基 本 特 点 有 : 标 识 唯 一 性 分 类 性 多 态 性 封 装 性 和 模 块 独 立 性 好 38 D [ 解 析 ] 软 件 设 计 通 常 采 用 结 构 化 设 计 方 法, 模 块 的 独 立 程 度 是 评 价 软 件 设 计 好 坏 的 重 要 度 量 标 准 耦 合 性 与 内 聚 性 是 模 块 独 立 性 的 两 个 定 性 标 准 在 结 构 化 程 序 设 计 中, 模 块 划 分 的 原 则 是 高 内 聚 低 耦 合, 即 减 弱 模 块 之 间 的 耦 合 性 和 提 高 模 块 内 的 内 聚 性, 这 样 有 利 于 提 高 软 件 模 块 的 独 立 性 39 B [ 解 析 ] 数 据 字 典 是 指 对 数 据 的 数 据 项 数 据 结 构 数 据 流 数 据 存 储 处 理 逻 辑 外 部 实 体 等 进 行 定 义 和 描 述, 其 目 的 是 对 数 据 流 图 中 的 各 个 元 素 做 出 详 细 的 说 明 40 A [ 解 析 ] 软 件 需 求 规 格 说 明 书 是 需 求 分 析 阶 段 的 最 终 成 果, 是 软 件 开 发 中 的 重 要 文 档 之 一 软 件 需 求 规 格 说 明 书 的 作 用 包 括 : 1) 便 于 用 户 开 发 人 员 进 行 理 解 和 交 流 2) 反 映 用 户 问 题 的 结 构, 可 以 作 为 软 件 开 发 工 作 的 基 础 和 依 据 3) 作 为 确 认 测 试 和 验 收 的 依 据, 其 中 不 包 括 软 件 可 行 性 研 究 的 依 据 41 D [ 解 析 ] 黑 盒 测 试 也 称 为 功 能 测 试, 它 是 通 过 测 试 来 检 测 每 个 功 能 是 否 都 能 正 常 使 用 在 测 试 中 把 程 序 看 做 一 个 不 能 打 开 的 黑 盒 子, 在 完 全 不 考 虑 程 序 内 部 结 构 和 内 部 特 性 的 情 况 下, 在 程 序 接 口 进 行 测 试, 它 只 检 查 程 序 功 能 是 否 按 照 需 求 规 格 说 明 书 的 规 定 正 常 使 用, 程 序 能 否 适 当 地 接 收 输 入 数 据, 并 产 生 正 确 的 输 出 信 息 黑 盒 测 试 方 法 主 要 有 等 价 类 划 分 法 边 界 值 分 析 法 错 误 推 测 法 因 果 法 等, 主 要 用 于 软 件 确 认 测 试 42 D [ 解 析 ] 软 件 设 计 包 括 总 体 设 计 和 详 细 设 计, 总 体 设 计 又 包 括 最 佳 方 案 设 计 软 件 结 构 设 计 数 据 结 构 及 数 据 库 设 计 ; 详 细 设 计 是 总 体 设 计 进 一 步 的 具 体 化, 其 基 本 任 务 有 : 为 每 个 模 块 进 行 详 细 的 算 法 设 计 为 模 块 内 的 数 据 结 构 进 行 设 计 对 数 据 库 进 行 物 理 设 计, 即 确 定 数 据 库 的 物 理 结 构 界 面 设 计 编 写 文 档 评 审 对 详 细 设 计 成 果 进 行 审 查 和 复 审 43 C [ 解 析 ] 一 个 软 件 产 品 或 软 件 系 统 要 经 历 孕 育 诞 生 成 长 成 熟 衰 亡 等 阶 段, 一 般 称 为 软 件 生 命 周 期 它 把 整 个 软 件 生 存 周 期 划 分 为 若 干 阶 段, 使 得 每 个 阶 段 有 明 确 的 任 务, 使 规 模 大, 结 构 复 杂 和 管 理 复 杂 的 软 件 开 发 变 得 容 易 控 制 和 管 理 通 常, 软 件 生 存 周 期 包 括 可 行 性 分 析 与 开 发 项 计 划 需 求 分 析 设 计 ( 概 要 设 计 和 详 细 设 计 ) 编 码 测 试 维 护 等 活 动, 可 以 将 这 些 活 动 以 适 当 的 方 式 分 配 到 不 同 的 阶 段 完 成 故 选 C 44 C
[ 解 析 ] 需 求 分 析 阶 段 的 任 务 是 深 入 描 述 软 件 的 功 能 和 性 能, 确 定 软 件 设 计 的 约 束 和 软 件 同 其 他 系 统 元 素 的 接 口 细 节, 定 义 软 件 的 其 他 有 效 性 需 求, 借 助 于 当 前 系 统 的 逻 辑 模 型 导 出 目 标 系 统 逻 辑 模 型, 解 决 目 标 系 统 做 什 么 的 问 题 可 分 为 需 求 提 出 需 求 描 述 及 需 求 评 审 3 个 阶 段 由 此 可 以 看 出 需 求 分 析 的 任 务 不 包 括 制 定 软 件 集 成 测 试 计 划 45 A [ 解 析 ] 黑 盒 测 试 也 称 为 功 能 测 试 或 数 据 驱 动 测 试, 它 完 全 不 考 虑 程 序 内 部 的 逻 辑 结 构 和 内 部 特 征, 只 着 眼 于 程 序 的 外 部 结 构, 主 要 用 来 检 查 程 序 功 能 是 否 按 照 需 求 规 格 说 明 书 的 规 定 正 常 使 用 故 选 A 46 D [ 解 析 ] 数 据 流 图 是 结 构 化 分 析 方 法 中 使 用 的 工 具, 它 以 图 形 的 方 式 描 绘 数 据 在 系 统 中 流 动 和 处 理 的 过 程, 由 于 它 只 反 映 系 统 必 须 完 成 的 逻 辑 功 能, 所 以 它 是 一 种 功 能 模 型, 是 在 可 行 性 研 究 阶 段 用 到 的 PAD 图 是 问 题 分 析 图 (Problem Analysis Diagram) 的 英 文 缩 写, 用 于 详 细 设 计 阶 段 系 统 结 构 图 是 对 软 件 系 统 结 构 的 总 体 设 计 的 图 形 显 示, 用 于 概 要 设 计 阶 段 程 序 流 程 图 是 对 程 序 流 程 的 图 形 表 示, 故 选 D 47 A [ 解 析 ] 软 件 测 试 是 为 了 发 现 错 误 而 执 行 程 序 的 过 程 为 了 达 到 良 好 的 测 试 效 果, 由 程 序 的 编 写 者 进 行 测 试 是 不 恰 当 的, 通 常 组 织 其 他 人 员 来 完 成 测 试 工 作 48 A [ 解 析 ] 计 算 机 软 件 (software) 是 计 算 机 系 统 中 与 硬 件 相 互 依 存 的 一 部 分, 是 包 括 程 序 数 据 及 相 关 文 档 的 完 整 集 合 软 件 按 功 能 可 以 分 为 应 用 软 件 系 统 软 件 支 撑 软 件 ( 或 工 具 软 件 ) 应 用 软 件 是 为 解 决 特 定 领 域 的 应 用 而 开 发 的 软 件 系 统 软 件 是 计 算 机 管 理 自 身 资 源, 提 高 计 算 机 使 用 效 率 并 为 计 算 机 用 户 提 供 各 种 服 务 的 软 件 支 撑 软 件 是 介 于 系 统 软 件 和 应 用 软 件 之 间, 协 助 用 户 开 发 软 件 的 工 具 性 软 件, 包 括 辅 助 支 持 开 发 和 维 护 应 用 软 件 的 工 具 软 件 选 项 A 属 于 应 用 软 件, 选 项 B 属 于 支 撑 软 件, 选 项 C 和 选 项 D 属 于 系 统 软 件 49 C [ 解 析 ] 该 系 统 总 体 结 构 图 是 一 种 树 形 结 构 在 树 形 结 构 中, 根 结 点 位 于 第 1 层, 而 树 的 最 大 层 数 称 为 该 树 的 深 度, 因 此, 该 系 统 总 体 结 构 图 的 深 度 为 3 50 D [ 解 析 ] 所 谓 程 序 调 试, 是 在 编 制 的 程 序 投 入 实 际 运 行 前, 用 手 工 或 编 译 程 序 等 方 法 进 行 测 试, 发 现 并 修 正 语 法 错 误 和 逻 辑 错 误 的 过 程 这 是 保 证 计 算 机 信 息 系 统 正 确 性 必 不 可 少 的 步 骤 51 D [ 解 析 ] 软 件 需 求 规 格 说 明 书 是 需 求 分 析 阶 段 的 最 后 结 果, 是 软 件 开 发 中 的 重 要 文 档 52 A [ 解 析 ] 系 统 总 体 结 构 图 支 持 软 件 系 统 的 概 要 设 计