2019 年 全 国 硕 士 研 究 生 招 生 考 试 计 算 机 科 学 与 技 术 学 科 联 考 计 算 机 学 科 专 业 基 础 综 合 试 题 一 、 单 项 选 择 题 ： 1~40 小 题 ， 每 小 题 2 分 ， 共 80 分 。 下 列 每 题 给 出 的 四 个 选 项 中 ， 只 有 一 个 选 项 符 合 试 题 要求 。 1. 设 n 是 描 述 问 题 规 模 的 非 负 整 数 ， 下 列 程 序 段 的 时 间 复 杂 度 是 x=0； while(n>=(x+l)*(x+l)) x=x+l； A. O(log n) B. O(n1/2) C. O(n) D. O(n2) 2. 若 将 一 棵 树 T 转 化 为 对 应 的 二 又 树 BT， 则 下 列 对 BT 的 遍 历 中 ， 其 遍 历 序 列 与 T 的 后 根 遍 历 序 列 相 同 的是 A. 先 序 遍 历 B. 中 序 遍 历 C. 后 序 遍 历 D. 按 层 遍 历 3. 对 n 个 互 不 相 同 的 符 号 进 行 哈 夫 曼 编 码 。 若 生 成 的 哈 夫 曼 树 共 有 115 个 结 点 ， 则 n 的 值 是 A. 56 B. 57 C. 58 D. 60 4. 在 任 意 一 棵 非 空 平 衡 二 又 树 (AVL 树 )T1 中 ， 删 除 某 结 点 v 之 后 形 成 平 衡 二 又 树 T2， 再 将 w 插 入 T2 形 成平 衡 二 又 树 T3。 下 列 关 于 T1 与 T3 的 叙 述 中 ， 正 确 的 是 I.若 v 是 T1 的 叶结 点 ， 则 T1 与 T3 可能不 相 同 Ⅱ.若 v 不 是 T1 的 叶结 点 ， 则 T1 与 T3 一 定不 相 同 Ⅲ.若 v 不 是 T1 的 叶结 点 ， 则 T1 与 T3 一 定相 同 A. 仅 I B. 仅 II C. 仅 I、 Ⅱ D. 仅 I、 Ⅲ 5. 下 图所示的 AOE 网表示一 项 包含 8 个 活动的 工程 。 活动 d的 最早开始时 间 和最迟开始时 间 分 别是 A. 3 和 7 B. 12 和 12 C. 12 和 14 D. 15 和 15 6. 用有 向无环图描 述 表达式(x+y)*((x+y)/x)， 需要 的 顶点 个数 至少是 A. 5 B. 6 C. 8 D. 9 7. 选 择 一 个 排序 算 法时 ， 除 算 法的 时 空 效率外， 下 列 因素中 ，还需要 考 虑的 是 I.数 据的 规 模 Ⅱ.数 据的 存储方式 Ⅲ.算 法的 稳定性 V.数 据的...
VIP
