1、2015 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一 、 单 项 选 择 题 ： 第 1 40 小 题 ， 每 小 题 2 分 ， 共 80 分 。 下 列 每 题 给 出 的 四 个 选 项 中 ， 只 有 一 个 选 项 最 符 合 试 题 要 求 。1已知程序如下：程 序 运 行 时 使 用 栈 来 保 存 调 用 过 程 的 信 息 ， 自 栈 底 到 栈 顶 保 存 的 信 息 依 次 对 应 的 是 。A main() S(1) S(0) B S(0) S(1) main()B main() S(0) S(1) D S(1) S(0) main
2、() 2 先 序 序 列 为 a,b,c,d 的 不 同 二 叉 树 的 个 数 是 。A 13 B 14 C 15 D 163 下 列 选 项 给 出 的 是 从 根 分 别 到 达 两 个 叶 结 点 路 径 上 的 权 值 序 列 ， 能 属 于 同 一 棵 哈 夫 曼 树 的 是 。A 24,10,5 和 24,10,7 B 24,10,5 和 24,12,7C 24,10,10 和 24,14,11 D 24,10,5 和 24,14,64 现 有 一 棵 无 重 复 关 键 字 的 平 衡 二 叉 树 （ AVL 树 ） ， 对 其 进 行 中 序 遍 历 可 得 到 一 个 降
3、序 序 列 。 下 列 关 于 该 平 衡 二 叉 树 的 叙 述 中 ， 正 确 的 是 。A 根 结 点 的 度 一 定 为 2 B 树 中 最 小 元 素 一 定 是 叶 结 点C 最 后 插 入 的 元 素 一 定 是 叶 结 点 D 树 中 最 大 元 素 一 定 是 无 左 子 树 5 设 有 向图 G=(V,E)， 顶 点 集 V=V0,V1,V2,V3， 边 集 E=， ， ， 。 若从 顶 点 V0 开 始 对 图 进 行 深 度 优 先 遍 历 ， 则 可 能 得 到 的 不 同 遍 历 序 列 个 数 是 。A 2 B 3 C 4 D 5 6 求 下 面 带 权图 的 最
4、 小 （ 代 价 ） 生 成 树 时 ， 可 能 是 克 鲁 斯 卡 （ Kruskal） 算 法 第 2 次 选 中 但 不 是 普里 姆 （ Prim） 算 法 （ 从 V4 开 始 ） 第 2 次 选 中 的 边 是 。A (V1,V3) B (V1,V4) C (V2,V3) D (V3,V4)7 下 列 选 项 中 ， 不 能 构 成 折 半 查 找 中 关 键 字 比 较 序 列 的 是 。 A 500,200,450,180 B 500,450,200,180int S(int n) return (nlink!=NULL) m=p-link-data0? p-link-data
5、:-p-link-data;if(*(q+m)=0) *(q+m)=1; p=p-link;else r=p-link;p-link=r-link free(r);/判 断 该 结 点 的 data 是 否 已 出 现 过/首次出现/保留/重 复 出 现/删除free(q);typedef struct node int data;struct node *link;NODE;Typedef NODE *PNODE;10【评分说明】若考生设计的算法满足题目的功能要求且正确，则酌情给分。4） 参 考 答 案 所 给 算 法 的 时 间 复 杂 度 为 O(m)， 空 间 复 杂 度 为 O(n)
6、。【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。42解答：1） 图 G 的邻接矩阵 A 如 下 ：2）A 2 如下：0 行 3 列 的 元 素 值 3 表 示 从 顶 点 0 到顶点 3 之 间 长 度 为 2 的 路 径 共 有 3 条 。3） Bm（ 2 m n） 中 位 于 i 行 j 列 （ 0 i， j n-1） 的 非 零 元 素 的 含 义 是 ： 图 中 从 顶 点 i 到 顶 点 j长 度 为 m 的 路 径 条 数 。43解答：1） 程 序 员 可 见 寄 存 器 为 通 用 寄 存 器 （ R0 R3） 和 PC。 因 为 采 用 了 单
7、总 线 结 构 ， 因 此 ， 若 无 暂 存 器 T， 则 ALU 的 A、 B 端 口 会 同 时 获 得 两 个 相 同 的 数 据 ， 使 数 据 通 路 不 能 正 常 工 作 。【 评 分 说 明 】 回 答 通 用 寄 存 器 （ R0 R3） ， 给 分 ； 回 答 PC， 给 分 ； 部 分 正 确 ， 酌 情 给 分 。 设 置 暂 存 器 T 的 原 因 若 回 答 用 于 暂 时 存 放 端 口 A 的 数 据 ， 则 给 分 ， 其 他 答 案 ， 酌 情 给 分 。2） ALU 共 有 7 种 操 作 ， 故 其 操 作 控 制 信 号 ALUop 至 少 需 要
8、3 位 ； 移 位 寄 存 器 有 3 种 操 作 ， 其操 作 控 制 信 号 SRop 至 少 需 要 2 位 。3） 信 号 SRout 所 控 制 的 部 件 是 一 个 三 态 门 ， 用 于 控 制 移 位 器 与 总 线 之 间 数 据 通 路 的 连 接 与 断 开 。【评分说明】只要回答出三态门或者控制连接/断开，即给分。4）端口、须连接到控制部件输出端。【评分说明】答案包含、中任意一个，不给分；答案不全酌情给分。5） 连 线 1， ； 连 线 2， 。【评分说明】回答除上述连线以外的其他连线，酌情给分。6） 因 为 每 条 指 令 的 长 度 为 16 位 ， 按 字 节 编 址 ， 所 以 每 条 指 令 占 用 2 个 内 存 单 元 ， 顺 序 执 行 时 ， 下 条 指 令 地 址 为 (PC)+2。 MUX 的 一 个 输 入 端 为 2， 可 便 于 执 行 (PC)+2 操 作 。44解答：1） 指 令 操 作 码 有 7 位 ， 因 此 最 多 可 定 义 27=128 条 指 令 。2）各条指令的机器代码分别如下：
