2018上海大学计算机考研专业课832真题回忆版.pdf
2 0 1 8 上 海 大 学 计 算 机 考 研 专 业 课 8 3 2 真 题回 忆 版一 选 择 ( 2*30)每 一 道 选 择 题 保 证 是 考 察 的 原 题 , 但 是 具 体 的 数 字 可 能 有 出 入 。 对 于 不 能 保 证 数 字 正 确 的 题目 都 找 到 了 类 似 的 题 目 以 保 证 问 题 与 答 案 的 匹 配 性 。1.下 列 排 序 算 法 稳 定 的 是 ( )A 冒 泡 排 序 , 直 接 插 入 排 序B 基 数 排 序 , 希 尔 排 序C 堆 排 序 , 选 择 排 序D 归 并 排 序 , 快 速 排 序2.下 列 不 同 进 制 数 中 真 值 最 大 的 是 ( )A 00111001( 2)B 45( 8)C 29( 16)D 97( 10)3.以 下 说 法 正 确 的 是 ( )A cache 一 般 采 用 DRAMB SRAM不 需 要 刷 新C SRAM比 DRAM集 成 度 高D DRAM是 非 易 失 性 存 储 器4.下 列 操 作 复 杂 度 为 O( 1) 的 是 ( )A 在 顺 序 表 中 插 入 一 个 元 素B 在 单 链 表 中 访 问 一 个 元 素C 在 单 链 表 中 插 入 一 个 元 素D 在 顺 序 表 中 访 问 一 个 元 素5.数 组 中 有 100个 递 增 存 储 的 整 数 , 折 半 查 找 时 查 找 一 个 元 素 的 比 较 次 数 不 可 能 超 过 ( )A.100 B.25 C.10 D.96.一 个 完 全 二 叉 树 共 有 100个 结 点 , 则 有 共 有 ( ) 个 叶 子 结 点A.26 B.33 C.44 D.457.一 般 家 用 台 式 电 脑 是 ( )A 微 型 机B 小 型 机C 中 型 机D 大 型 机8.微 程 序 存 储 在 ( )A 主 存 储 器B 程 序 计 数 器C 控 制 存 储 器D 指 令 寄 存 器9.一 地 址 指 令 ( )A 可 能 有 一 个 操 作 数 , 也 可 能 有 两 个 操 作 数B 不 可 能 是 数 据 传 送 指 令C 不 可 能 是 运 算 指 令D 以 上 都 对10.决 定 程 序 执 行 顺 序 的 是 ( )A 指 令 寄 存 器B 数 据 寄 存 器C 程 序 计 数 器D 控 制 存 储 器11. 在 指 令 格 式 中 , 采 用 扩 展 操 作 码 设 计 方 案 的 目 的 是 ( )A 减 少 指 令 字 长 度B 增 加 指 令 字 长 度C 保 持 指 令 字 长 度 不 变 而 增 加 操 作 指 令 的 数 量D 保 持 指 令 字 长 度 不 变 而 增 加 寻 址 空 间12.下 列 哪 个 操 作 不 能 由 运 算 器 实 现 ( )A 发 出 “ 读 ” 信 号B 两 个 整 数 比 较 大 小C 欢 迎 补 充D 欢 迎 补 充13.存 储 一 个 n 阶 上 三 角 矩 阵 需 要 数 组 的 大 小 是 ( )A log2nB n2C. n*(n+1)/2D. n*(n-1)/214. 对 于 深 度 为 4 的 栈 , 入 栈 顺 序 为 ABCDEF, 则 出 栈 顺 序 可 能 是 ( )A.AFEDCB B.ABDFEC C.DFABCE D.CEFABD15.下 列 哪 种 排 序 方 式 , 当 待 排 序 数 列 越 有 序 时 , 排 序 速 度 越 慢 ( )A 选 择 排 序B 插 入 排 序C 快 速 排 序D 冒 泡 排 序16.每 一 个 内 存 块 都 可 以 映 射 到 任 意 一 个 cache 块 中 , 这 种 映 射 方 式 称 为 ( )A 直 接 映 射B 全 相 连 映 射C 半 相 连 映 射D 组 相 连 映 射17.下 列 说 法 正 确 的 是 ( )A chche 的 出 现 是 为 了 解 决 cpu与 主 存 间 容 量 差 异 的 矛 盾B 交 叉 存 储 器 技 术 可 以 使 不 同 存 储 器 部 分 块 同 时 串 行 传 输 数 据C 直 接 寻 址 方 式 不 需 要 进 行 地 址 的 运 算D 欢 迎 补 充18.下 列 哪 个 不 是 DMA的 工 作 方 式A 多 路 选 择B 周 期 挪 用C 与 CPU 交 替 访 存D 停 止 CPU访 问 内 存19.二 维 数 组 A79,按 行 优 先 顺 序 存 放 在 首 地 址 是 600的 地 址 连 续 的 内 存 空 间 内 , 每 个 数据 占 两 个 字 节 。 则 A63所 在 的 地 址 是 ( )A 828 B 814 C 714 D 61420.512K*8容 量 的 DRAM, 需 要 的 地 址 线 和 数 据 线 条 数 总 数 是 ( )A.512 B.64 C.27 D.1021. 对 有 序 表 ( 02, 16,24,33,48,57,66,71,79,84,86,91) 进 行 折 半 查 找 , 查 找 成 功 的 平均 查 找 长 度 是 ( )A 37/12 B.37/13 C.39/13 D.49/1222.下 列 关 于 二 叉 树 的 判 断 正 确 的 是 ( )A 二 叉 树 的 度 为 2B 二 叉 树 中 叶 子 结 点 的 个 数 是 度 为 二 的 结 点 个 数 加 一C 对 于 n 个 结 点 的 二 叉 树 , 叶 子 结 点 个 数 的 二 倍 加 上 度 为 一 的 结 点 的 个 数 等 于 n+1D 如 果 二 叉 树 前 序 和 后 序 遍 历 序 列 相 反 , 那 么 二 叉 树 任 一 结 点 都 没 有 做 左 子 树23-30 很 基 础 , 忘 却 了 。 欢 迎 补 充 。二 填 空 ( 30 )31.( 1) 数 据 采 用 奇 校 验 码 校 验 方 式 , 补 充 空 格( ) 0110110; ( ) 1011001; ( ) 0001101( 2) 奇 校 验 码 能 检 出 ( ) 位 错 , 纠 正 ( ) 位 错( 3) 奇 校 验 码 的 码 距 是 多 少 ?32. 一 个 直 接 映 射 的 cache大 小 为 512B, 块 大 小 为 4B, 主 存 以 字 节 编 址 。 主 存 地 址 长 16 位 。问 :( 1) 该 机 器 能 寻 址 多 大 空 间( 2) cache共 分 多 少 块 , 内 存 共 分 多 少 块( 3) 画 出 主 存 格 式 示 意 图 , 标 好 位 数( 4) 给 出 cache 地 址 的 映 射 函 数33.给 出 一 组 数 据 : 45,06,15,33,81,02,64,77。( 1) 写 出 用 冒 泡 排 序 算 法 第 一 趟 排 序 后 的 状 态 。( 2) 写 出 用 快 速 排 序 ( 选 择 第 一 个 数 为 基 准 ) 第 一 趟 排 序 后 的 状 态 。34.( 1) 对 于 n 个 结 点 的 二 叉 树 遍 历 的 时 间 复 杂 度 是 ?( 2) 一 个 二 叉 树 如 图 , 给 出 二 叉 树 的 前 序 , 中 序 , 后 序 遍 历 序 列 。 (非 原 图 )三 简 答 题 (60)35.操 作 数 a, b已 经 分 别 存 放 在 寄 存 器 R2, R3中 , 补 码 表 示 。 ALU有 +, -, M( 传 送 ) 三种 功 能 。( 1) 指 出 哪 些 微 指 令 是 相 容 的 。( 2) 将 ( a+b) *1/2的 结 果 存 放 到 R1中 , 写 出 此 操 作 的 微 指 令 。( 3) 采 用 字 段 直 接 译 码 方 式 定 义 微 指 令 集 , 问 需 要 多 少 字 段 ? 给 出 理 由 。36.有 8K*8的 ROM芯 片 和 8K*4的 RAM芯 片 , 组 成 由 16K*8的 RAM和 8K*8的 ROM组 成的 存 储 器 , 其 中 高 地 址 是 ROM。( 1) 计 算 各 需 要 多 少 芯 片( 2) 画 出 连 线 图 。 ( 必 须 连 的 线 有 地 址 线 , 数 据 线 , RD, WE, CS, MERQ) 。37(10)( 1) 给 出 单 链 表 定 义 代 码( 2) 统 计 数 列 中 比 正 整 数 x小 的 个 数 , 如 12.23.32.45.54.65。 x=33。 返 回 3。 写 出你 的 算 法 程 序 , 必 要 处 予 以 注 释( 3) 把 比 正 数 x大 的 奇 数 从 单 链 表 中 删 除 , 写 出 你 的 算 法 程 序 , 必 要 处 予 以 注 释38 ( 9)有 两 个 字 符 串 A,B, 设 计 一 个 算 法 , 判 断 能 否 在 对 A进 行 若 干 次 循 环 左 移 或 右 移 之 后 出 现 B是 A的 子 串 的 情 况 。 如 A=ABACA,B=CAA, 存 在 ; A=ABCBA,B=BAB,不 存 在 。( 1) 写 出 你 的 算 法 思 想 (3)( 2) 写 出 你 的 算 法 程 序 , 必 要 处 予 以 注 释 (6)39( 11)( 1) 写 出 基 于 邻 接 表 存 储 的 连 通 图 深 度 优 先 遍 历 算 法 程 序( 2) 分 析 你 设 计 的 算 法 的 复 杂 度( 3) 根 据 下 图 写 出 邻 接 表 , 并 根 据 你 的 邻 接 表 给 出 从 结 点 0出 发 的 深 度 优 先 遍 历 序 列( 非 原 图 )