资源描述
第 页 （ 共 3页 ）1青 岛 科 技 大 学二 一 六 年 硕 士 研 究 生 入 学 考 试 试 题考 试 科 目 ： 数 据 结 构注 意 事 项 ： 1 本 试 卷 共 三 道 大 题 （ 共 计 23个 小 题 ） ， 满 分 150 分 ；2 本 卷 属 试 题 卷 ， 答 题 另 有 答 题 卷 ， 答 案 一 律 写 在 答 题 卷 上 ， 写 在 该 试 题 卷 上 或 草纸 上 均 无 效 。 要 注 意 试 卷 清 洁 ， 不 要 在 试 卷 上 涂 划 ；3 必 须 用 蓝 、 黑 钢 笔 或 签 字 笔 答 题 ， 其 它 均 无 效 。 一 、 选 择 题 (每 个 2 分 ， 共 30 分 )1、 在 长 度 为 n的 顺 序 表 的 第 i(1 i n+1)个 位 置 上 删 除 一 个 元 素 ， 移 动 元 素 的 个 数 为 ( ) 。A.i-1 B.n-i+1 C. i D. n-i2、 以 下 哪 一 个 术 语 与 数 据 的 逻 辑 结 构 无 关 ？ （ ）A 哈 希 表 B. 栈 C. 二 叉 树 D. 线 性 表3、 下 面 程 序 段 的 时 间 复 杂 度 为 _。for(inti=0;i=1） 的 满 三 叉 树 中 ， 结 点 总 数 为 （ ） 。A.3k B. 3k-1 C. （ 3k-1） /3 D. （ 3k-1） /28、 AVL树 是 一 种 平 衡 的 二 叉 排 序 树 ， 树 中 任 一 结 点 的 ( ) 。A. 左 、 右 子 树 高 度 差 的 绝 对 值 不 超 过 1 B. 左 、 右 子 树 的 高 度 均 相 同C. 左 子 树 的 高 度 均 大 于 右 子 树 的 高 度 D. 左 子 树 的 高 度 均 小 于 右 子 树 的 高 度第 页 （ 共 3页 ）29、 若 一 个 栈 的 输 入 序 列 为 1,2,3, ,n， 输 出 序 列 的 第 一 个 元 素 是 i， 则 第 j个 输 出 元 素 是 （ ） 。A.i-j-1 B. 不 确 定 的 C.j-i+1 D.i-j10、 适 用 于 折 半 查 找 的 表 的 存 储 方 式 及 元 素 排 列 要 求 为 ( ) 。A 链 接 方 式 存 储 ， 元 素 无 序 B 链 接 方 式 存 储 ， 元 素 有 序C 顺 序 方 式 存 储 ， 元 素 无 序 D 顺 序 方 式 存 储 ， 元 素 有 序11、 设 哈 希 表 长 为 14， 哈 希 函 数 是 H(key)=key%11,表 中 已 有 数 据 的 关 键 字 为 15， 38， 61， 84共四 个 ， 现 要 将 关 键 字 为 49 的 结 点 加 到 表 中 ， 用 二 次 探 测 再 散 列 法 解 决 冲 突 ， 则 放 入 的 位 置 是( )。A 9 B 3 C 5 D 812、 设 单 链 表 中 指 针 p指 向 结 点 m， 若 要 删 除 m之 后 的 结 点 （ 若 存 在 ） ， 则 需 修 改 指 针 的 操 作 为（ ） 。A p=p-next B p-next=p-next-nextC p=p-next-next D p-next=p13、 对 序 列 15， 9， 7， 8， 20， -1， 4进 行 排 序 ， 进 行 一 趟 后 数 据 的 排 列 变 为 4， 9， -1， 8， 20，7， 15； 则 采 用 的 是 （ ） 排 序 。A. 选 择 B. 快 速 C. 冒 泡 D. 希 尔14、 关 键 路 径 是 事 件 结 点 网 络 中 的 （ ） 。A 从 源 点 到 汇 点 的 最 长 路 径 B 从 源 点 到 汇 点 的 最 短 路 径C 最 长 的 回 路 D 最 短 的 回 路15、 在 含 有 n个 结 点 的 二 叉 树 中 有 （ ） 个 分 支 。A.n B.n-1 C.n+1 D.（ n+1） /2二 、 应 用 题 （ 60 分 ）1 （ 12分 ） 回 答 下 列 问 题 ：1 什 么 是 数 据 结 构 ？2 对 于 数 据 结 构 一 般 包 含 哪 三 个 方 面 的 讨 论 ？3 在 编 制 管 理 通 讯 录 的 程 序 时 ， 通 讯 录 数 据 采 用 什 么 样 的 数 据 结 构 合 适 ？4 对 于 第 问 ， 存 储 结 构 采 用 什 么 样 的 结 构 合 适 ？ 为 什 么 ？2 （ 12分 ） 数 组 A 中 ， 每 个 元 素 Ai,j的 长 度 均 为 32个 二 进 位 ,行 下 标 从 -1 到 9， 列 下 标 从 1到11， 从 首 地 址 S开 始 连 续 存 放 主 存 储 器 中 ， 主 存 储 器 字 长 为 16位 。 求 ： 存 放 该 数 组 所 需 多 少 单 元 ？ 存 放 数 组 第 4列 所 有 元 素 至 少 需 多 少 单 元 ？ 数 组 按 行 存 放 时 ， 元 素 A7,4的 起 始 地 址 是 多 少 ？ 数 组 按 列 存 放 时 ， 元 素 A4,7的 起 始 地 址 是 多 少 ？3 （ 12分 ） 设 一 棵 二 叉 树 的 先 序 序 列 ： ABDFCEGH ， 中 序 序 列 ： BFDAGEHC 画 出 这 棵 二 叉 树 。 画 出 这 棵 二 叉 树 的 后 序 线 索 树 。 将 这 棵 二 叉 树 转 换 成 对 应 的 树 （ 或 森 林 ） 。4 （ 12分 ） 请 阅 读 下 列 算 法 ， 回 答 问 题 。for(i=2;i=L.length;+i)第 页 （ 共 3页 ）3if(L.ri.keyL.ri-1.key)L.r0=L.ri; / 复 制 为 监 视 哨for(j=i-1;L.r0.keyL.rj.key; -j)L.rj+1=L.rj; / 记 录 后 移L.rj+1=L.r0; 这 是 什 么 类 型 的 排 序 算 法 ？ ； 该 排 序 算 法 稳 定 吗 ？ 该 排 序 算 法 的 时 间 复 杂 度 与 关 键 字 的 初 始 排 列 顺 序 有 没 有 关 系 ？ 假 定 设 待 排 序 的 关 键 字 序 列 为 12， 2， 16， 30， 28， 10， 16*， 20， 6， 18， 请 写 出 使 用该 排 序 方 法 ， 每 趟 排 序 结 束 后 关 键 字 序 列 的 状 态 。5.（ 12分 ） 假 定 对 有 序 表 ： （ 3， 4， 5， 7， 24， 30， 42， 54， 63， 72， 87， 95） 进 行 折 半 查 找 ，试 回 答 下 列 问 题 ： 画 出 描 述 折 半 查 找 过 程 的 判 定 树 ； 若 查 找 元 素 54， 需 依 次 与 哪 些 元 素 比 较 ？ 若 查 找 元 素 90， 需 依 次 与 哪 些 元 素 比 较 ？ 假 定 每 个 元 素 的 查 找 概 率 相 等 ， 求 查 找 成 功 时 的 平 均 查 找 长 度 。三 、 算 法 设 计 题 （ 60 分 ）1.（ 20分 ） 将 两 个 递 增 的 有 序 链 表 合 并 为 一 个 递 增 的 有 序 链 表 。 要 求 结 果 链 表 仍 使 用 原 来 两 个 链表 的 存 储 空 间 , 不 另 外 占 用 其 它 的 存 储 空 间 。 表 中 不 允 许 有 重 复 的 数 据 。（ 1） 描 述 算 法 的 基 本 设 计 思 想 ；（ 2） 用 类 C 的 语 言 描 述 该 算 法 ， 关 键 之 处 给 出 简 要 注 释 。2.（ 20分 ） 以 二 叉 链 表 作 为 二 叉 树 的 存 储 结 构 ， 编 写 以 下 算 法 ：（ 1） 判 别 两 棵 树 是 否 相 等 ；（ 2） 交 换 二 叉 树 每 个 结 点 的 左 孩 子 和 右 孩 子 。3.（ 20分 ）（ 1） 试 基 于 图 的 深 度 优 先 搜 索 策 略 写 一 算 法 ， 判 别 以 邻 接 表 方 式 存 储 的 有 向 图 中 是 否 存 在 由 顶点 vi到 顶 点 vj的 路 径 （ i j） 。（ 2） 采 用 邻 接 表 存 储 结 构 ， 编 写 一 个 算 法 ， 判 别 无 向 图 中 任 意 给 定 的 两 个 顶 点 之 间 是 否 存 在 一条 长 度 为 为 k的 简 单 路 径 。
展开阅读全文