2016考研计算机学科专业基础综合真题及答案.pdf

《2016考研计算机学科专业基础综合真题及答案.pdf》由会员分享，可在线阅读，更多相关《2016考研计算机学科专业基础综合真题及答案.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2 0 1 6 考 研 计 算 机 学 科 专 业 基 础 综 合 真 题 及 答 案一、单 项 选 择 题：1-4 0 小 题，每 小 题 2 分，共 8 0 分，下 列 每 小 题 给 出 的 四 个 选 项 中，只有 一 项 符 合 题 目 要 求 的。请 在 答 题 卡 上 将 所 选 项 的 字 母 涂 黑。)1.设 n 是 描 述 问 题 规 模 的 非 负 整 数，下 面 程 序 片 段 的 时 间 复 杂 度 是x=2;w h i l e(x x=2*x;A.O(l o g 2 n)B.O(n)C.O(n l o g 2 n)D.O(n 2)解 答：A。程 序 中，执 行 频

2、率 最 高 的 语 句 为“x=2*x”。设 该 语 句 执 行 了 t 次，则 2 t+1=n/2，故 t=l o g 2(n/2)-1=l o g 2 n-2=O(l o g 2 n)。2.元 素 a，b，c，d，e 依 次 进 入 初 始 为 空 的 栈 中，若 元 素 进 栈 后 可 停 留、可 出 栈，直到 所 有 元 素 都 出 栈，则 在 所 有 可 能 的 出 栈 序 列 中，以 元 素 d 开 头 的 序 列 个 数 是A.3B.4C.5D.6解 答：B。出 栈 顺 序 必 为 d _ c _ b _ a _，e 的 顺 序 不 定，在 任 意 一 个“_”上 都 有 可 能

3、。3.已 知 循 环 队 列 存 储 在 一 维 数 组 A 0.n-1 中，且 队 列 非 空 时 f r o n t 和 r e a r 分 别 指向 队 头 元 素 和 队 尾 元 素。若 初 始 时 队 列 为 空，且 要 求 第 1 个 进 入 队 列 的 元 素 存 储 在 A 0 处，则 初 始 时 f r o n t 和 r e a r 的 值 分 别 是A.0,0B.0，n-1C.n-1,0D.n-1，n-1解 答：B。插 入 元 素 时，f r o n t 不 变，r e a r+1.而 插 入 第 一 个 元 素 之 后，队 尾 要 指 向 尾 元素，显 然，r e a

4、r 初 始 应 该 为 n-1,f r o n t 为 0。4.若 一 棵 完 全 二 叉 树 有 7 6 8 个 结 点，则 该 二 叉 树 中 叶 结 点 的 个 数 是A.2 5 7B.2 5 8C.3 8 4D.3 8 5解 答：C。叶 结 点 数 为 n，则 度 为 2 的 结 点 数 为 n-1,度 为 1 的 结 点 数 为 0 或 1，本 题 中为 1(总 结 点 数 为 偶 数)，故 而 即 2 n=7 6 8。5.若 一 棵 二 叉 树 的 前 序 遍 历 序 列 和 后 序 遍 历 序 列 分 别 为 1,2,3,4 和 4,3,2,1，则 该 二叉 树 的 中 序 遍

5、历 序 列 不 会 是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1解 答：C。由 前 序 和 后 序 遍 历 序 列 可 知 3 为 根 结 点，故(1,2)为 左 子 树，(4)为 右 子 树，C不 可 能。或 画 图 即 可 得 出 结 果。6.已 知 一 棵 有 2 0 1 1 个 结 点 的 树，其 叶 结 点 个 数 为 1 1 6，该 树 对 应 的 二 叉 树 中 无 右 孩 子的 结 点 个 数 是A.1 1 5B.1 1 6C.1 8 9 5D.1 8 9 6解 答：D。本 题 可 采 用 特 殊 情 况 法 解。设 题 意 中 的 树 是 如 下

6、 图 所 示 的 结 构，则 对 应 的 二叉 树 中 仅 有 前 1 1 5 个 叶 结 点 有 右 孩 子。共 1 1 6 个 叶 结 点7.对 于 下 列 关 键 字 序 列，不 可 能 构 成 某 二 叉 排 序 树 中 一 条 查 找 路 径 的 序 列 是A.9 5,2 2,9 1,2 4,9 4,7 1C.2 1,8 9,7 7,2 9,3 6,3 8B.9 2,2 0,9 1,3 4,8 8,3 5D.1 2,2 5,7 1,6 8,3 3,3 4解 答：A。选 项 A 中，当 查 到 9 1 后 再 向 2 4 查 找，说 明 这 一 条 路 径 之 后 查 找 的 数 都

7、要 比9 1 小，后 面 的 9 4 就 错 了。8.下 列 关 于 图 的 叙 述 中，正 确 的 是.回 路 是 简 单 路 径.存 储 稀 疏 图，用 邻 接 矩 阵 比 邻 接 表 更 省 空 间.若 有 向 图 中 存 在 拓 扑 序 列，则 该 图 不 存 在 回 路A.仅 B.仅、C.仅 D.仅、解 答：C。.回 路 对 应 于 路 径，简 单 回 路 对 应 于 简 单 路 径;.刚 好 相 反;.拓 扑 有 序 的必 要 条 件。故 选 C。9.为 提 高 散 列(H a s h)表 的 查 找 效 率，可 以 采 取 的 正 确 措 施 是.增 大 装 填(载)因 子.设

8、计 冲 突(碰 撞)少 的 散 列 函 数.处 理 冲 突(碰 撞)时 避 免 产 生 聚 集(堆 积)现 象A.仅 B.仅 C.仅、D.仅、解 答：B。I I I 错 在“避 免”二 字。1 0.为 实 现 快 速 排 序 算 法，待 排 序 序 列 宜 采 用 的 存 储 方 式 是A.顺 序 存 储 B.散 列 存 储 C.链 式 存 储解 答：A。内 部 排 序 采 用 顺 序 存 储 结 构。D.索 引 存 储1 1.已 知 序 列 2 5,1 3,1 0,1 2,9 是 大 根 堆，在 序 列 尾 部 插 入 新 元 素 1 8，将 其 再 调 整 为 大 根堆，调 整 过 程 中

9、 元 素 之 间 进 行 的 比 较 次 数 是A.1B.2C.4D.5解 答：B。首 先 与 1 0 比 较，交 换 位 置，再 与 2 5 比 较，不 交 换 位 置。比 较 了 二 次。1 2.下 列 选 项 中，描 述 浮 点 数 操 作 速 度 指 标 的 是A.M I P SB.C P IC.I P CD.M F L O P S解 答：D。送 分 题。1 3.f l o a t 型 数 据 通 常 用 I E E E 7 5 4 单 精 度 浮 点 数 格 式 表 示。若 编 译 器 将 f l o a t 型 变 量 x分 配 在 一 个 3 2 位 浮 点 寄 存 器 F R

10、1 中，且 x=-8.2 5，则 F R 1 的 内 容 是A.C 1 0 4 0 0 0 0 H B.C 2 4 2 0 0 0 0 H C.C 1 8 4 0 0 0 0 H D.C 1 C 2 0 0 0 0 H解 答：A。x 的 二 进 制 表 示 为-1 0 0 0.0 1-1.0 0 0 0 1 2 1 1 根 据 I E E E 7 5 4 标 准 隐 藏 最 高 位的“1”，又 E-1 2 7=3，所 以 E=1 3 0=1 0 0 0 0 0 1 0(2)数 据 存 储 为 1 位 数 符+8 位 阶 码(含 阶 符)+2 3位 尾 数。故 F R 1 内 容 为 1 1 0

11、 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 即 1 1 0 0 0 0 0 1 0 0 0 00 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0，即 C 1 0 4 0 0 0 H1 4.下 列 各 类 存 储 器 中，不 采 用 随 机 存 取 方 式 的 是A.E P R O MB.C D R O MC.D R A MD.S R A M解 答：B。光 盘 采 用 顺 序 存 取 方 式。1 5.某 计 算 机 存 储 器 按 字 节 编 址，主 存 地 址 空 间 大 小 为 6

12、4 M B，现 用 4 M 8 位 的 R A M 芯 片组 成 3 2 M B 的 主 存 储 器，则 存 储 器 地 址 寄 存 器 M A R 的 位 数 至 少 是A.2 2 位B.2 3 位C.2 5 位D.2 6 位解 答：D。6 4 M B 的 主 存 地 址 空 间，故 而 M A R 的 寻 址 范 围 是 6 4 M，故 而 是 2 6 位。而 实 际 的主 存 的 空 间 不 能 代 表 M A R 的 位 数。1 6.偏 移 寻 址 通 过 将 某 个 寄 存 器 内 容 与 一 个 形 式 地 址 相 加 而 生 成 有 效 地 址。下 列 寻 址 方式 中，不 属

13、于 偏 移 寻 址 方 式 的 是A.间 接 寻 址B.基 址 寻 址C.相 对 寻 址D.变 址 寻 址解 答：A。间 接 寻 址 不 需 要 寄 存 器，E A=(A)。基 址 寻 址：E A=A+基 址 寄 存 器 内 同;相 对 寻址：E A A+P C 内 容;变 址 寻 址：E A A+变 址 寄 存 器 内 容。1 7.某 机 器 有 一 个 标 志 寄 存 器，其 中 有 进 位/借 位 标 志 C F、零 标 志 Z F、符 号 标 志 S F 和 溢出 标 志 O F，条 件 转 移 指 令 b g t(无 符 号 整 数 比 较 大 于 时 转 移)的 转 移 条 件 是

14、A.C F+O F=1 B.S F+Z F=1C.C F+Z F=1D.C F+S F=1解 答：C。无 符 号 整 数 比 较，如 A B，则 A-B 无 进 位/借 位，也 不 为 0。故 而 C F 和 Z F 均为 0。1 8.下 列 给 出 的 指 令 系 统 特 点 中，有 利 于 实 现 指 令 流 水 线 的 是.指 令 格 式 规 整 且 长 度 一 致.指 令 和 数 据 按 边 界 对 齐 存 放.只 有 L o a d/S t o r e 指 令 才 能 对 操 作 数 进 行 存 储 访 问A.仅、B.仅、C.仅、D.、解 答：D。指 令 定 长、对 齐、仅 L o

15、a d/S t o r e 指 令 访 存，以 上 三 个 都 是 R I S C 的 特 征。均能 够 有 效 的 简 化 流 水 线 的 复 杂 度。1 9.假 定 不 采 用 C a c h e 和 指 令 预 取 技 术，且 机 器 处 于“开 中 断”状 态，则 在 下 列 有 关 指令 执 行 的 叙 述 中，错 误.的 是A.每 个 指 令 周 期 中 C P U 都 至 少 访 问 内 存 一 次B.每 个 指 令 周 期 一 定 大 于 或 等 于 一 个 C P U 时 钟 周 期C.空 操 作 指 令 的 指 令 周 期 中 任 何 寄 存 器 的 内 容 都 不 会 被 改 变D.当 前 程 序 在 每 条 指 令 执 行 结 束 时 都 可 能 被 外 部 中 断 打 断解 答：C。会 自 动 加 1，A 取 指 令 要 访 存、B 时 钟 周 期 对 指 令 不 可 分 割。2 0.在 系 统 总 线 的 数 据 线 上，不.可 能 传 输 的 是A.指 令C.握 手(应 答)信 号B.操 作 数D.中 断 类 型 号解 答：C。握 手(应 答)信 号 在 通 信 总 线 上 传 输。