2021年广东财经大学809-数据结构硕士研究生入学考研真题.pdf

欢 迎 报 考 广 东 财 经 大 学 硕 士 研 究 生 ， 祝 你 考 试 成 功 ！ （ 第 1 页 共 4 页 ） 1 广东财经大学硕士研究生入学考试试卷考 试 年 度 ： 2021 年 考 试 科 目 代 码 及 名 称 ： 809-数 据 结 构 （ 自 命 题 ）适 用 专 业 ： 085400 电 子 信 息 友 情 提 醒 ： 请 在 考 点 提 供 的 专 用 答 题 纸 上 答 题 ， 答 在 本 卷 或 草 稿 纸 上 无 效 ！ 一 、 单 项 选 择 题 （ 每 小 题 2 分 ， 共 40分 ）1. 关 于 线 性 表 的 说 法 正 确 的 是 （ ） 。A.线 性 表 的 特 点 是 每 个 元 素 都 有 一 个 前 驱 和 一 个 后 继 元 素B.线 性 表 是 特 征 相 同 的 n（ n 0） 个 元 素 构 成 的 有 限 序 列C.线 性 表 采 用 顺 序 存 储 便 于 进 行 插 入 和 删 除 操 作 D.线 性 表 采 用 链 式 存 储 便 于 进 行 随 机 查 找 操 作2. 表 长 为 n 的 顺 序 存 储 的 线 性 表 ， 当 在 任 何 位 置 删 除 一 个 元 素 的 概 率 相 等 时 ， 删 除 一 个 元素 所 需 移 动 元 素 的 平 均 个 数 为 （ ） 。A.(n-1)/2 B.n/2 C.(n+1)/2 D.n3. 假 设 单 链 表 结 点 结 构 为 （ data,next） ， 删 除 指 针 p 所 指 结 点 的 后 继 结 点 q 的 语 句 序 列 是（ ） 。A.p-next=q-next; free(q); B.p-next=q; free(q);C.free(q);p-next=q-next; D.free(q);p-next=q;4. 设 有 一 个 递 归 算 法 如 下 所 示 ， 计 算 F(8)需 要 调 用 该 递 归 函 数 的 次 数 为 （ ） 。int F(int n) if(n=3) return 1;else return F(n-2)+F(n-4)+1; A.7 B.8 C.9 D.10 5. 若 循 环 队 列 Q 存 储 在 数 组 queue0.n中 ， front 是 队 首 位 置 ， rear 是 队 尾 位 置 （ 初 始rear=front=0） ， 则 元 素 e 入 队 的 操 作 是 （ ） 。A.Q.queueQ.rear=e; Q.rear=(Q.rear+1)%n;B.Q.queueQ.rear=e; Q.rear=(Q.rear+1)%(n+1);C.Q.rear=(Q.rear+1)%n; Q.queueQ.rear=e;D.Q.rear=(Q.rear+1)%(n+1); Q.queueQ.rear=e;6. 关 于 串 的 叙 述 中 不 正 确 的 是 （ ） 。A.串 是 字 符 的 有 限 序 列B.空 串 是 由 空 格 构 成 的 串C.串 既 可 以 采 用 顺 序 存 储 ， 也 可 以 采 用 链 式 存 储D.模 式 匹 配 是 串 的 一 种 重 要 运 算7. 按 照 从 上 至 下 、 由 左 至 右 的 顺 序 依 次 编 号 ， 深 度 为 7 的 完 全 二 叉 树 编 号 最 大 的 叶 结 点 编号 是 （ ） 。 A.63 B.64 C.126 D.1278. 已 知 完 全 二 叉 树 的 第 7 层 有 20个 叶 结 点 ， 则 该 二 叉 树 最 多 有 （ ） 个 结 点 。A.83 B.147 C.214 D.2159. 设 F 是 一 个 森 林 ， B 是 由 F 变 换 得 到 的 二 叉 树 。 若 F 中 有 n 个 非 终 端 ， 则 B 中 右 指 针 域为 空 的 结 点 有 （ ） 个 。 欢 迎 报 考 广 东 财 经 大 学 硕 士 研 究 生 ， 祝 你 考 试 成 功 ！ （ 第 2 页 共 4 页 ） 2 A.n-1 B.n C.n+1 D.n+210. 由 权 值 为 15,3,5,10的 四 个 叶 结 点 构 成 的 哈 夫 曼 树 的 带 权 路 径 长 度 为 （ ） 。A.46 B.59 C.66 D.8811. 具 有 n个 顶 点 的 有 向 完 全 图 用 邻 接 表 表 示 时 ， 共 有 （ ） 个 弧 结 点 。A. n(n-1)/2 B.n(n-1) C.2n(n-1) D.n-112. 下 面 的 （ ） 算 法 适 合 构 造 一 个 稠 密 图 的 最 小 生 成 树 。A.Prim算 法 B.Kruskal 算 法 C.Floy算 法 D.Dijkstra算 法13. 如 果 要 求 一 个 线 性 表 既 能 较 快 的 查 找 ， 又 能 适 应 动 态 变 化 的 要 求 ， 最 好 采 用 （ ） 查 找法 。 A.顺 序 查 找 B.折 半 查 找 C.分 块 查 找 D.哈 希 查 找14. 对 50 个 记 录 的 有 序 表 作 折 半 查 找 ， 当 查 找 失 败 时 ， 至 少 需 要 比 较 （ ） 次 关 键 字 。A.4 B.5 C.6 D.715. 关 于 B-树 和 B+树 的 叙 述 不 正 确 的 是 （ ） 。 A.B-树 和 B+树 都 是 平 衡 的 多 叉 树B.B-树 和 B+树 都 可 用 于 文 件 的 索 引 结 构C.B-树 和 B+树 都 能 有 效 支 持 顺 序 检 索D.B-树 和 B+树 都 能 有 效 支 持 随 机 检 索16. 假 设 散 列 表 长 度 为 11， 散 列 函 数 为 H(key)=key%7， 冲 突 处 理 方 法 为 开 放 地 址 法 的 二 次探 测 再 散 列 。 已 知 表 中 已 有 记 录 的 关 键 字 为 32,17,9,27， 现 要 将 关 键 字 为 45的 记 录 加 入 表中 ， 则 放 入 的 位 置 是 （ ） 。A.1 B.3 C.5 D.717. 从 未 排 序 序 列 中 依 次 取 出 元 素 与 已 排 序 列 （ 初 始 时 为 空 ） 中 的 元 素 进 行 比 较 ， 将 其 放 入已 排 序 序 列 的 正 确 位 置 上 的 排 序 方 法 称 为 （ ） 。A.插 入 排 序 B.冒 泡 排 序 C.选 择 排 序 D.归 并 排 序18. 快 速 排 序 法 在 （ ） 情 况 下 最 有 利 于 发 挥 其 长 处 。A.待 排 序 数 据 量 大 B.数 据 中 含 有 多 个 相 同 的 关 键 字 C.数 据 按 关 键 字 已 基 本 有 序 D.数 据 按 关 键 字 完 全 无 序19. 下 列 排 序 算 法 中 ， 占 用 辅 助 空 间 最 多 的 是 （ ） 。A.希 尔 排 序 B.快 速 排 序 C.堆 排 序 D.归 并 排 序20. 下 列 排 序 方 法 中 ， 其 中 （ ） 是 稳 定 的 。A.堆 排 序 ， 冒 泡 排 序 B.快 速 排 序 ， 堆 排 序C.选 择 排 序 ， 归 并 排 序 D.归 并 排 序 ， 冒 泡 排 序二 、 填 空 题 （ 每 空 2 分 ， 共 40分 ）1. 从 逻 辑 结 构 上 看 ， 堆 栈 是 操 作 受 限 的 （ ） 结 构 ， 遵 循 （ ） 存 取 原 则 。2. 图 的 主 要 存 储 结 构 有 四 种 ： （ ） 、 （ ） 、 十 字 链 表 和 邻 接 多 重 表 表 示 法 。3. 如 果 已 知 二 叉 树 的 （ ） 和 （ ） 遍 历 序 列 ， 可 以 唯 一 确 定 该 二 叉 树 。 4. 平 均 查 找 长 度 ASL 和 数 据 元 素 个 数 无 关 的 查 找 方 法 所 使 用 的 数 据 结 构 是 （ ） ， 在快 速 排 序 、 归 并 排 序 和 堆 排 序 中 ， 稳 定 的 排 序 方 法 是 （ ） 排 序 。5. 假 设 记 录 R1和 R2的 关 键 字 相 同 且 R1 在 R2 的 前 面 ， 如 果 排 序 后 R1 仍 在 R2 的 前 面 则 称排 序 方 法 是 （ ） 的 ， 一 般 情 况 下 基 于 （ ） 关 键 字 比 较 的 排 序 算 法 是 稳 定 的 。6. 一 棵 高 度 为 5 的 理 想 平 衡 树 中 ， 最 少 含 有 （ ） 个 结 点 ， 最 多 含 有 （ ） 个 结 欢 迎 报 考 广 东 财 经 大 学 硕 士 研 究 生 ， 祝 你 考 试 成 功 ！ （ 第 3 页 共 4 页 ） 3 点 。7. 通 过 将 树 的 （ ） 存 储 方 式 转 换 为 （ ） 存 储 方 式 ， 可 以 利 用 已 有 的 算 法 解 决树 的 问 题 。8. 已 知 一 颗 完 全 二 叉 树 中 共 有 768结 点 ， 则 该 树 中 共 有 （ ） 个 叶 子 结 点 。 已 知 一 棵度 为 3的 树 有 2个 度 为 1的 结 点 ， 3个 度 为 2的 结 点 ， 4个 度 为 3的 结 点 ， 则 该 树 中 有 （ ）个 叶 子 结 点 。9. G 是 一 个 非 连 通 无 向 图 ， 共 有 28条 边 ， 则 该 图 至 少 有 （ ） 个 顶 点 。 在 有 n个 顶 点的 有 向 图 中 ， 若 要 使 任 意 两 点 间 可 以 互 相 到 达 ， 则 至 少 需 要 （ ） 条 弧 。10. 对 于 一 个 具 有 n个 顶 点 e条 边 的 无 向 图 的 邻 接 表 的 表 示 ， 则 表 头 向 量 大 小 为 （ ） ，邻 接 表 的 边 结 点 个 数 为 （ ） 。三 、 分 析 计 算 题 （ 每 小 题 10 分 ， 共 40分 ） 1.设 一 棵 二 叉 树 的 中 序 序 列 是 ： BDEAFGCKH， 后 序 序 列 是 ： EDBGFKHCA。（ 1） 写 出 该 二 叉 树 的 先 序 序 列 。（ 2） 画 出 该 二 叉 树 的 中 序 线 索 二 叉 树 。（ 3） 将 这 棵 二 叉 树 转 换 成 树 或 森 林 。2.图 -1所 示 是 带 权 的 无 向 网 ， 图 中 顶 点 的 存 储 顺 序 为 图 -2所 示 ， 要 求 ：（ 1） 画 出 该 无 向 网 的 邻 接 表 。 （ 2） 按 步 骤 画 出 根 据 克 鲁 斯 卡 尔 算 法 构 造 最 小 生 成 树 的 过 程 (图 中 标 明 对 应 边 的 权 值 )。（ 3） 计 算 最 小 生 成 树 的 权 值 。3.假 设 Bt 是 元 素 值 为 字 符 的 二 叉 链 表 ， 其 数 据 结 构 的 表 示 以 及 test 函 数 的 调 用 如 图 -3 所示 ， 用 图 -4所 示 的 二 叉 链 表 Bt调 用 test函 数 。 （ 1） 简 述 test函 数 的 功 能 。 欢 迎 报 考 广 东 财 经 大 学 硕 士 研 究 生 ， 祝 你 考 试 成 功 ！ （ 第 4 页 共 4 页 ） 4 （ 2） 尽 量 按 屏 幕 显 示 格 式 写 出 运 行 结 果 。（ 3） 调 用 test的 次 数 是 多 少 ？4.设 待 排 序 数 据 的 关 键 字 序 列 为 49,54,60,75,36,93,27， 回 答 以 下 问 题 ：（ 1） 写 出 创 建 大 顶 堆 的 一 趟 初 始 建 堆 的 过 程 ， 要 求 写 出 中 间 步 骤 。（ 2） 堆 排 序 采 用 何 种 存 储 结 构 ？ 是 否 稳 定 的 排 序 方 法 ？（ 3） 如 果 要 降 序 排 列 全 部 数 据 ， 需 要 创 建 大 顶 堆 还 是 小 顶 堆 ？四 、 算 法 设 计 题 （ 每 小 题 15 分 ， 共 30分 ）1 . 在 一 个 非 递 减 有 序 的 线 性 表 中 ， 有 数 值 相 同 的 元 素 存 在 。 若 存 储 方 式 为 单 链 表 ， 设 计 算法 去 掉 数 值 相 同 的 元 素 ， 使 链 表 中 不 再 有 重 复 元 素 ， 要 求 算 法 时 间 复 杂 度 为 O(N)。 例 如 ： 算 法 输 入 链 表 为 （ 1 9 ， 2 6 ， 2 6 ， 3 2 ， 5 0 ， 6 2 ， 6 2 ， 6 2 ， 8 9 ） ， 则 输 出 为 （ 1 9 ， 2 6 ， 3 2 ， 5 0 ，6 2 ， 8 9 ） 。 作 答 时 ， 给 出 必 要 的 分 析 和 说 明 ， 以 及 注 释 ， 用 类 C 语 言 写 出 尽 量 完 整 的 程 序 。2. 用 非 递 归 的 方 式 写 出 无 向 图 的 深 度 优 先 遍 历 算 法 （ DFS） 。 其 中 图 采 用 邻 接 矩 阵 存 储 ， 例如 定 义 一 个 邻 接 矩 阵 mapNN用 于 存 储 图 ， 定 义 一 个 数 组 visitedN用 于 标 记 相 关 节 点 是否 已 被 访 问 。 作 答 时 ， 给 出 必 要 的 分 析 和 说 明 ， 以 及 注 释 ， 可 以 使 用 伪 代 码 描 述 算 法 。