2015杭州师范大学计算机826计算机基础真题.pdf

杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考 试 科 目 代 码 826 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 6页 ， 第 1 页 ）杭州师范大学2015年招收攻读硕士研究生入学考试题考 试 科 目 代 码 ： 826考 试 科 目 名 称 ： 计 算 机 基 础说 明 ： 考 生 答 题 时 一 律 写 在 答 题 纸 上 ， 否 则 漏 批 责 任 自 负 。第 一 部 分 ： 程 序 设 计 基 础 （ C语 言 ） （ 50 分 ）一 、 单 项 选 择 题 （ 每 小 题 2 分 ， 共 20分 ）1. 以 下 （ ） 为 有 效 变 量 名 。A. 234 B. 1926sum C. afor(i = 0; i 2 int maxCommonFactor(int a, int b);3 int main(void) 4 int a, b, x;5 printf(“Input a, b:“);6 scanf(“%d%d“, a, b);7 x = maxCommonFactor(a,b);8 printf(“MaxCommonFactor=%dn“, x);9 10 int maxCommonFactor(int a, int b) 11 int r;12 do 13 r = a % b;14 a = b;15 b = r;16 while(r != 0);17 return a;18 程 序 中 存 在 的 错 误 在 第 _行 。 （ 5 分 ）杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考 试 科 目 代 码 826 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 6页 ， 第 3 页 ）3. 编 写 一 个 二 分 （ 折 半 ） 查 找 函 数 ：int binarySearch(int key, int list, int arraySize)第 1 个 参 数 key是 需 要 查 找 的 关 键 字 ； 第 2个 参 数 list是 需 要 查 找 的 有 序 数 组 ； 第 3个 参 数arraySize是 数 组 大 小 。 如 果 在 数 组 list中 找 到 与 关 键 字 key匹 配 的 数 组 元 素 ， 则 返 回 该 数组 元 素 的 下 标 ， 否 则 返 回 -1。 （ 10分 ）4. 编 写 程 序 。 猴 子 第 1天 摘 下 若 干 个 桃 子 ， 当 即 吃 了 一 半 ， 还 不 过 瘾 ， 又 多 吃 了 一 个 。 第 2天 早 上 又 将 剩 下 的 桃 子 吃 掉 一 半 ， 又 多 吃 了 一 个 。 以 后 每 天 早 上 都 吃 了 前 一 天 剩 下 的 一 半 另加 一 个 。 到 第 10 天 早 上 想 再 吃 时 ， 就 只 剩 下 一 个 桃 子 了 。 问 第 1 天 共 摘 了 多 少 个 桃 子 。 （ 10分 ）第 二 部 分 ： 数 据 结 构 （ 50 分 ）一 、 单 项 选 择 题 （ 每 小 题 1 分 ， 共 5 分 ）1. 求 整 数 n（ n0） 阶 乘 的 算 法 如 下 ， 其 时 间 复 杂 度 是 ( )int fact(int n) if (n = 1) return 1;else n * fact(n - 1);A. O(log2n) B. O(n) C. O(n log2n) D. O(n2)2. 已 知 两 个 长 度 分 别 为 m和 n的 有 序 表 ， 若 将 它 们 合 并 成 一 个 长 度 为 m+n的 有 序 表 ， 则 最 坏情 况 下 的 时 间 复 杂 度 为 ( )。A. O(n) B. O(m * n) C. O(min(m,n) D. O(m + n)3. 栈 的 特 点 是 ( )A. 先 进 先 出 B. 后 进 先 出 C. 没 有 特 点 D. 后 进 后 出4.假 设 一 个 循 环 队 列 queuemaxSize的 队 头 指 针 为 front， 队 尾 指 针 为 rear， 初 始 时 置 front= rear = 0， 则 循 环 队 列 的 判 空 条 件 为 ( )。A. rear = front B. rear = maxSizeC. rear +1 =front D. front = (rear + 1) % maxSize5. 若 一 棵 二 叉 树 的 先 序 遍 历 序 列 为 a, e, b, d, c， 中 序 遍 历 序 列 分 别 为 e, b, a, d, c，则 该 二 叉 树 的 后 序 遍 历 序 列 为 ( )。A. beadc B. becda C. dceba D. eacdb杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考 试 科 目 代 码 826 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 6页 ， 第 4 页 ）二 、 填 空 题 （ 每 空 格 1 分 ， 共 5 分 ）1. 给 定 一 无 序 整 数 序 列 56, 70, 33, 65, 12, 24, 48, 92, 35, 86， 若 用 堆 排 序 算 法 进 行排 序 ， 则 初 始 建 堆 （ 建 大 顶 堆 ） 的 结 果 为 (1) ； 若 用 归 并 排 序 ， 则 第 一 趟 排 序 结 果 为 (2) ；若 用 第 一 个 数 为 轴 心 元 素 (pivot)的 快 速 排 序 ， 则 第 一 趟 排 序 结 果 为 (3) 。2. 设 一 棵 完 全 二 叉 树 (Complete binary tree)中 有 21 个 结 点 ， 如 果 按 照 从 上 到 下 、 从 左 到右 的 顺 序 从 1 开 始 顺 序 编 号 ， 则 编 号 为 8 的 父 结 点 (parent node)的 编 号 是 （ 4） ， 编 号为 8 的 左 孩 子 结 点 的 编 号 是 （ 5） 。三 、 简 答 题 （ 共 40分 ）1. 给 定 某 有 向 图 的 邻 接 矩 阵 如 下 :(a) 画 出 该 图(b) 给 出 该 图 从 V1出 发 的 深 度 优 先 搜 索 和 宽 度 优 先 搜 索 序 列(c) 该 有 向 图 是 否 可 以 有 拓 扑 排 序 序 列 ？ 如 果 有 ， 请 给 出 一 个 拓 扑 排 序 的 序 列 。（ 10分 ）2. 给 定 一 个 二 叉 树 的 数 组 存 储 方 式 如 下 图 :1 2 3 4 5 6 7 8 9 10 11a b c d g e f(a) 画 出 该 二 叉 树(b) 写 出 该 二 叉 树 的 前 序 遍 历 (preorder order)结 果(c) 写 出 该 二 叉 树 的 中 序 遍 历 (inorder order)结 果(d) 写 出 该 二 叉 树 的 后 序 遍 历 (postorder order)结 果(e) 写 出 该 二 叉 树 的 层 序 遍 历 (level order)结 果（ 20分 ）杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考 试 科 目 代 码 826 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 6页 ， 第 5 页 ）3. 依 次 将 60, 30, 20, 50, 78, 85 插 入 一 棵 二 叉 搜 索 树 (Binary search tree)， 请(a)给 出 二 叉 搜 索 树 定 义 。(b)画 出 每 插 入 一 个 数 后 得 到 的 所 有 二 叉 搜 索 树(c)画 出 将 30删 除 后 的 二 查 搜 索 树（ 10分 ）第 三 部 分 ： 计 算 机 网 络 （ 50分 ）一 、 单 项 选 择 题 （ 每 小 题 2 分 ， 共 20分 ）1. 以 下 关 于 网 络 分 类 的 描 述 中 错 误 的 是 （ ） 。A 连 接 用 户 计 算 机 身 边 10m之 内 计 算 机 等 数 字 终 端 设 备 的 网 络 称 为 WSNB 覆 盖 l0m-l0km 的 网 络 称 为 LANC 覆 盖 l0-l00km 的 网 络 称 为 MAND 覆 盖 l00-l000km的 网 络 称 为 WAN2. 网 络 层 中 传 输 的 数 据 单 位 是 （ ） 。A. 帧 B. IP数 据 报 C 比 特 流 D. 比 特 流 和 帧3. 域 名 WWW.SOHU.COM 中 属 顶 级 域 名 的 是 （ ） 。A WWW B SOHU C COM D WWW.SOHU4. 标 准 的 URL由 3部 分 组 成 ： 服 务 器 类 型 、 主 机 名 和 路 径 及 （ ） 。A. 进 程 名 B. 客 户 名 C. 浏 览 器 名 D.文 件 名5. 远 程 登 录 协 议 Telnet、 电 子 邮 件 协 议 SMTP、 文 件 传 输 协 议 FTP依 赖 于 （ ） 协 议 。A. TCP B. UDP C. ICMP D. IGMP6. 以 下 关 于 网 络 体 系 结 构 的 研 究 方 法 优 点 的 描 述 中 错 误 的 是 （ ） 。A 允 许 隔 层 通 信 是 OSI参 考 模 型 灵 活 性 的 标 志B 各 层 之 间 相 互 独 立C 易 于 实 现 和 标 准 化D 实 现 技 术 的 变 化 都 不 会 对 整 个 系 统 工 作 产 生 影 响7. 在 传 送 TCP报 文 段 时 ， 若 确 认 号 为 20， 表 明 到 序 号 （ ） 为 止 的 数 据 均 正 确 接 收 。A 18 B 19 C 20 D 21杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考 试 科 目 代 码 826 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 6页 ， 第 6 页 ）8. 以 下 选 项 中 不 属 于 自 含 时 钟 编 码 的 是 （ ） 。A. 差 分 曼 彻 斯 特 编 码 B 曼 彻 斯 特 编 码B 非 归 零 码 D 都 不 是9. 一 台 交 换 机 具 有 24个 10/100Mbps 端 口 和 两 个 1Gbps 端 口 ， 如 果 所 有 端 口 都 工 作 在 全 双 工状 态 ， 那 么 交 换 机 的 总 带 宽 最 大 是 （ ） 。A. 4.4Gbps B. 6.4Gbps C. 6.8Gbps D. 8.8Gbps10. 在 路 由 表 中 ， 对 每 一 条 路 由 最 主 要 的 信 息 是 目 的 网 络 地 址 和 （ ） 。A 下 一 跳 地 址 B 网 络 地 址 C 接 口 D 物 理 地 址二 、 综 合 应 用 题 （ 共 30分 ）1. 简 述 虚 拟 局 域 网 相 对 于 传 统 局 域 网 的 优 点 ， 并 举 出 它 三 种 划 分 方 法 。 （ 10分 ）2. 假 设 有 一 个 CSMA/CD 网 络 ， 其 发 送 速 率 为 100Mbps,网 络 电 缆 长 度 为 1Km,区 间 无 中 断 器 ，主 机 A 位 于 网 络 电 缆 的 一 端 ， 信 号 在 电 缆 中 的 速 度 为 200000km/s。 如 果 主 机 A 最 先 发 送 帧 ，并 且 主 机 A 在 检 测 出 冲 突 发 生 的 时 候 还 有 数 据 要 发 送 。 请 回 答 ：（ 1） 主 机 A 检 测 出 冲 突 最 长 需 要 多 少 时 间 ？ （ 5 分 ）（ 2） 该 网 络 的 帧 最 小 长 度 是 多 少 ?（ 5分 ）3. 假 设 某 主 机 的 IP 地 址 为 210.114.105.164， 子 网 掩 码 分 别 为 （ 1） 255.255.255.240和 （ 2）255.255.255.224时 ， 请 问 该 主 机 所 在 网 络 的 广 播 地 址 和 网 络 地 址 分 别 是 什 么 ？ 它 们 可 用 的IP地 址 范 围 分 别 又 是 什 么 ？ （ 10分 ）