数 据 结 构 2013 年 春 季 期 末 复 习 提 纲 期 末 考 试 形 式 : 闭 卷 试 卷 试 卷 题 型 :1. 选 择 题 (20 分 ),2. 应 用 题 (30 分 )3. 程 序 填 空 题 (30 分 )4. 算 法 设 计 题 ( 20 分 ) 每 章 复 习 要 点 : 第 1 章 : 概 念 理 解 : 数 据 结 构, 时 间 复 杂 度 程 序 段 : i=1; while(i<=n) i=i*2; 第 2 章 : 表 的 顺 序 存 储 结 构, 链 式 存 储 结 构 ( 单 链 表 循 环 链 表 双 向 链 表 ), 表 的 基 本 操 作 与 应 用, 本 章 所 占 分 值 在 15 分 左 右, 会 考 表 的 算 法 (1) 顺 序 存 储 结 构 1 下 面 关 于 线 性 表 的 叙 述 中, 错 误 的 是 哪 一 个?( ) A. 线 性 表 采 用 顺 序 存 储, 必 须 占 用 一 片 连 续 的 存 储 单 元 B. 线 性 表 采 用 顺 序 存 储, 便 于 进 行 插 入 和 删 除 操 作 C. 线 性 表 采 用 链 接 存 储, 不 必 占 用 一 片 连 续 的 存 储 单 元 D. 线 性 表 采 用 链 接 存 储, 便 于 插 入 和 删 除 操 作 2 对 于 顺 序 表 的 优 缺 点, 以 下 说 法 错 误 的 是 :() A 无 需 为 表 示 节 点 间 的 逻 辑 关 系 而 增 加 额 外 的 存 储 空 间 ; B 可 以 方 便 地 随 机 存 取 表 中 的 任 一 节 点 ; C 插 入 和 删 除 运 算 较 方 便 ; D 由 于 顺 序 表 要 求 占 用 连 续 的 空 间, 存 储 分 配 智 能 预 先 进 行 (2) 链 式 存 储 结 构 1 链 表 不 具 备 的 特 点 是?( ) A. 可 随 机 访 问 任 一 节 点 B. 插 入 删 除 不 需 要 移 动 元 素 C. 不 必 事 先 估 计 存 储 空 间 D. 所 需 空 间 与 其 长 度 成 正 比 2 (1) 静 态 链 表 既 有 顺 序 存 储 的 优 点, 又 有 动 态 链 表 的 优 点 所 以, 它 存 取 表 中 第 i 个 元 素 的 时 间 与 i 无 关 (2) 静 态 链 表 中 能 容 纳 的 元 素 个 数 的 最 大 数 在 表 定 义 时 就 确 定 了, 以 后 不 能 增 加 (3) 静 态 链 表 与 动 态 链 表 在 元 素 的 插 入 删 除 上 类 似, 不 需 做 元 素 的 移 动 以 上 错 误 的 是 ( ) A.(1)(2) B.(1) C.(1)(2)(3) D.(2) 3 对 于 一 个 头 指 针 为 head 的 带 头 结 点 的 单 链 表, 判 定 该 表 为 空 表 的 条 件 是 A head==null B head next==null C head next==head D head!=null 4 如 果 对 线 性 表 的 运 算 只 有 两 种, 即 删 除 第 一 个 元 素, 在 最 后 一 个 元 素 后 面 插 入 新 元 素, 最 好 使 用 () A 只 有 表 头 指 针 而 没 有 表 尾 指 针 的 循 环 单 链 表
B 只 有 表 尾 指 针 而 没 有 表 头 指 针 的 循 环 单 链 表 C 非 循 环 双 链 表 D 循 环 双 链 表 5 线 性 表 ( a1,a2,,an) 以 链 接 方 式 存 储 时, 访 问 第 i 位 置 元 素 的 时 间 复 杂 性 为 ( ) A.O(i) B.O(1) C.O(n) D.O(i-1) 第 3 章 : 栈 的 实 现, 栈 的 应 用 ( 数 制 转 换, 括 号 匹 配 ),Hanoi 塔 不 考, 队 列 的 实 现 ( 其 中 循 环 队 列 重 点 ) 本 章 所 占 分 值 在 10 分 左 右, 可 能 会 考 算 法 (1) 栈 1 一 个 栈 的 输 入 序 列 为 1 2 3 4 5, 则 下 列 序 列 中 不 可 能 是 栈 的 输 出 序 列 的 是 ( ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 2 输 入 序 列 为 ABC, 输 出 为 ABC 时 ( 假 设 元 素 出 栈 则 输 出 ), 经 过 的 栈 操 作 为 ( ) A.push,pop,push,pop,push,pop B.push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop (2) 队 列 1 循 环 队 列 用 数 组 A 0 Maxsize 存 放 其 元 素 值, 头 尾 指 针 是 front 和 rear, 则 队 列 中 元 素 个 数 是 () A (rear-front-1)%maxsize B rear-front C (rear-front+1)%maxsize D (rear-front+maxsize)%maxsize 2 一 个 队 列 的 入 队 序 列 是 1,2,3,4, 则 队 列 的 输 出 序 列 是 ( ) A. 4,3,2,1 B. 1,2,3,4 C.1,4,3,2 D. 3,2,1,4 3 用 一 个 大 小 为 6 的 数 组 来 实 现 循 环 队 列, 且 当 前 rear 和 front 的 值 分 别 为 0 和 3, 当 从 队 列 中 删 除 一 个 元 素, 再 加 入 两 个 元 素 后,rear 和 front 的 值 分 别 为 多 少?( ) A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 第 4 章 : 只 考 计 算 模 式 串 的 NEXT 值, 不 考 算 法, 本 章 所 占 分 值 在 5 分 左 右 1 串 "ababaaababaa" 的 next 数 组 为 ( ) A.012345678999 B.012121111212 C.011234223456 D.012301232234 第 5 章 : 数 组 的 存 储 位 置 计 算, 压 缩 矩 阵 的 存 储 ( 不 考 算 法 ) 本 章 所 占 分 值 在 5 分 左 右 1 n 阶 对 称 矩 阵 A, 将 其 上 三 角 的 元 按 列 优 先 顺 序 压 缩 存 放 在 一 维 数 组 B[1 n(n+1)/2] 中, 第 一 个 元 素 a1,1 存 于 B[1] 中, 则 应 存 放 到 B[k] 中 的 元 素 ai,j(1<=i<=n,i<=j<=n) 的 下 标 i,j 与 k 的 对 应 关 系 是 k=( ) A. i(i+1)/2+j B.i(i-1)/2+j C.j(j+1)/2+i D.j(j-1)/2+i 2 设 有 数 组 A[i,j], 数 组 的 每 个 元 素 长 度 为 3 字 节,i 的 值 为 1 到 8,j 的 值 为 1 到 10, 数 组 从 内 存 首 地 址 BA 开 始 顺 序 存 放, 当 用 以 列 为 主 存 放 时, 元 素 A[5,8] 的 存 储 地 址 为 ( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 第 6 章 : 二 叉 树 的 二 叉 链 表 存 储, 二 叉 树 的 遍 历, 霍 夫 曼 树, 本 章 肯 定 会 考 二 叉 树 相 关 算 法 本 章 所 占 分 值 在 20 分 左 右 1 一 棵 完 全 二 叉 树 上 有 1001 个 结 点, 其 中 叶 子 结 点 的 个 数 是 ( )
A.250 B.500 C.505 D.501 2 已 知 一 棵 二 叉 树 的 前 序 遍 历 结 果 为 ABCDEF, 中 序 遍 历 结 果 为 CBAEDF, 则 后 序 遍 历 的 结 果 为 ( ) A.CBEFDA B.FEDCBA C.CBEDFA D. 不 定 3 已 知 一 棵 二 叉 树 的 先 序 遍 历 序 列 为 ABD#E##FG###C#H##,# 表 示 空 树, 请 画 出 对 应 的 二 叉 树 4 已 知 下 列 字 符 A B C D E F G 的 权 值 分 别 为 3 12 7 4 2 8 11, 试 填 写 出 其 对 应 哈 夫 曼 树 HT 存 储 结 构 的 终 态, 即 把 下 表 填 充 完 整 ( 生 成 的 哈 夫 曼 树 权 值 左 孩 子 小 右 孩 子 大, 权 值 相 等 时 编 号 小 的 先 取 ) weight parent lchild rchild 1 2 5 写 出 求 二 叉 树 高 度 的 算 法 6 一 颗 度 为 7 的 树 有 8 个 度 为 1 的 结 点 7 个 度 为 2 的 结 点 6 个 度 为 3 的 结 点 5 个 度 为 4 的 结 点 4 个 度 为 5 的 结 点 3 个 度 为 6 的 结 点 2 个 度 为 7 的 结 点, 该 树 有 () 个 叶 子 结 点 7 已 知 一 棵 二 叉 树 的 先 序 中 序 和 后 序 序 列 如 下, 其 中 空 缺 了 部 分, 请 画 出 该 二 叉 树 先 序 : _BC_EFG_IJK_ 中 序 :CBED_GAJ_H_L 后 序 :_E_FD_J_L_HA 第 7 章 : 图 的 四 种 存 储 结 构, 图 的 遍 历, 最 小 生 成 树, 拓 扑 排 序, 关 键 路 径 与 最 短 路 径, 本 章 所 占 分 值 在 15 分 左 右, 可 能 会 考 算 法, 但 算 法 主 要 考 察 图 的 遍 历 算 法, 其 他 算 法 不 考 1 已 知 无 向 带 权 连 通 图 G(V, E) 的 邻 接 表 如 下 所 示, 请 画 出 该 图, 并 使 用 Prim 或 Kruskal 算 法 求 出 该 图 的 最 小 生 成 树 其 中 边 结 点 的 3 个 域 为 : 顶 点 号 边 上 的 权 值 指 针 1 2 3 4 5 V1 V2 V3 V4 V5 2 12 3 16 4 18 ^ 1 12 3 2 5 22 ^ 1 16 2 2 4 4 ^ 1 18 3 4 5 10 ^ 2 22 4 10 ^ 2 如 G3 有 向 图 中, 顶 点 表 示 课 程, 弧 表 示 课 程 间 的 先 后 关 系 如 果 每 人 每 学 期 中 学 一 门 课 程, 则 应 当 如 何 安 排 课 程 学 习? 给 出 三 种 方 案
第 9 章 : 顺 序 查 找 表, 折 半 查 找 表, 二 叉 排 序 树 ( 重 点 ), 平 衡 二 叉 树, 哈 希 表, 本 章 所 占 分 值 在 15 分 左 右, 会 考 表 的 算 法 ( 顺 序 查 找, 折 半, 二 叉 排 序 树 相 关 算 法 ) 1 对 长 度 为 8 的 有 序 表, 给 出 折 半 查 找 的 判 定 树, 给 出 等 概 率 情 况 下 的 平 均 查 找 长 度 2 输 入 一 个 正 整 数 序 列 {40,28,6,72,100,3,54,1,80,91,38}, 建 立 一 颗 二 叉 排 序 树 3 依 次 把 结 点 {10,20,50,100,120,30,90,80,70,110,60} 插 入 到 初 始 状 态 为 空 的 平 衡 二 叉 树 中, 使 得 在 每 次 插 入 后 保 持 该 树 仍 然 是 平 衡 二 叉 树 依 次 画 出 每 次 插 入 后 所 形 成 的 平 衡 二 叉 树 4 使 用 哈 希 函 数 H(key)=key % 9, 把 一 个 整 数 值 转 换 成 哈 希 表 下 标, 现 要 把 数 据 1,13, 12,34,38,33,27,22 插 入 到 哈 希 表 中 ( 表 长 为 9) 1) 使 用 线 性 探 测 法 构 造 哈 希 表 2) 使 用 链 地 址 法 构 造 哈 希 表 第 10 章 : 所 有 的 排 序 方 法, 本 章 所 占 分 值 在 15 分 左 右, 会 考 算 法 ( 所 有 的 排 序 方 法 ) 1. 已 知 待 排 序 的 序 列 为 (503,87,512,61,908,170,897,275,653,462), 将 待 排 序 的 序 列 升 序 排 序, 请 用 二 叉 树 的 形 式 画 出 初 建 堆 的 过 程 ( 只 给 出 建 初 始 堆 的 过 程 ) 2. 一 组 记 录 的 关 键 字 为 (22,5,37,14,12), 利 用 快 速 排 序 的 方 法, 以 第 一 个 记 录 为 基 准, 画 出 一 次 划 分 的 过 程 (6 分 ) 3. 将 数 据 序 列 (28,76,54,39,87,14,46,25,78,62) 按 shell 排 序 法 进 行 排 序, 增 量 序 列 为 5,3,1, 请 写 出 每 倘 排 序 完 成 之 后 的 序 列 状 态 4. 将 数 据 序 列 (986,321,123,432,500,654,018,765,987,210) 进 行 基 数 排 序, 请 写 出 每 趟 分 配 收 集 排 序 过 程 5. 将 数 据 序 列 (46,35,78,12,62,38,80,29) 进 行 归 并 排 序, 请 写 出 每 趟 排 序 过 程
2009 年 统 考 计 算 机 考 研 真 题 一. 单 项 选 择 题, 每 小 题 2 分, 共 80 分 1. 为 解 决 计 算 机 与 打 印 机 之 间 速 度 不 匹 配 的 问 题, 通 常 设 置 一 个 打 印 数 据 缓 冲 区, 主 机 将 要 输 出 的 数 据 依 次 写 入 该 缓 冲 区, 而 打 印 机 则 依 次 从 该 缓 冲 区 中 取 出 数 据 该 缓 冲 区 的 逻 辑 结 构 应 该 是 A. 栈 B. 队 列 C. 树 D. 图 2. 设 栈 S 和 队 列 Q 的 初 始 状 态 均 为 空, 元 素 abcdefg 依 次 进 入 栈 S 若 每 个 元 素 出 栈 后 立 即 进 入 队 列 Q, 且 7 个 元 素 出 队 的 顺 序 是 bdcfeag, 则 栈 S 的 容 量 至 少 是 A.1 B.2 C.3 D.4 3. 给 定 二 叉 树 图 所 示 设 N 代 表 二 叉 树 的 根,L 代 表 根 结 点 的 左 子 树,R 代 表 根 结 点 的 右 子 树 若 遍 历 后 的 结 点 序 列 为 3,1,7,5,6,2,4, 则 其 遍 历 方 式 是 A.LRN B.NRL C.RLN D.RNL 4. 下 列 二 叉 排 序 树 中, 满 足 平 衡 二 叉 树 定 义 的 是 5. 已 知 一 棵 完 全 二 叉 树 的 第 6 层 ( 设 根 为 第 1 层 ) 有 8 个 叶 结 点, 则 完 全 二 叉 树 的 结 点 个 数 最 多 是 A.39 B.52 C.111 D.119 6. 将 森 林 转 换 为 对 应 的 二 叉 树, 若 在 二 叉 树 中, 结 点 u 是 结 点 v 的 父 结 点 的 父 结 点, 则 在 原 来 的 森 林 中,u 和 v 可 能 具 有 的 关 系 是 I. 父 子 关 系 II. 兄 弟 关 系 III. u 的 父 结 点 与 v 的 父 结 点 是 兄 弟 关 系
A. 只 有 II B.I 和 II C.I 和 III D.I II 和 III 7. 下 列 关 于 无 向 连 通 图 特 性 的 叙 述 中, 正 确 的 是 I. 所 有 顶 点 的 度 之 和 为 偶 数 II. 边 数 大 于 顶 点 个 数 减 1 III. 至 少 有 一 个 顶 点 的 度 为 1 A. 只 有 I B. 只 有 II C.I 和 II D.I 和 III 9. 已 知 关 键 序 列 5,8,12,19,28,20,15,22 是 小 根 堆 ( 最 小 堆 ), 插 入 关 键 字 3, 调 整 后 得 到 的 小 根 堆 是 A.3,5,12,8,28,20,15,22,19 B. 3,5,12,19,20,15,22,8,28 C.3,8,12,5,20,15,22,28,19 D. 3,12,5,8,28,20,15,22,19 10. 若 数 据 元 素 序 列 11,12,13,7,8,9,23,4,5 是 采 用 下 列 排 序 方 法 之 一 得 到 的 第 二 趟 排 序 后 的 结 果, 则 该 排 序 算 法 只 能 是 A. 起 泡 排 序 B. 插 入 排 序 C. 选 择 排 序 D. 二 路 归 并 排 序 二. 综 合 应 用 题 共 70 分 41.(10 分 ) 带 权 图 ( 权 值 非 负, 表 示 边 连 接 的 两 顶 点 间 的 距 离 ) 的 最 短 路 径 问 题 是 找 出 从 初 始 顶 点 到 目 标 顶 点 之 间 的 一 条 最 短 路 径 假 定 从 初 始 顶 点 到 目 标 顶 点 之 间 存 在 路 径, 现 有 一 种 解 决 该 问 题 的 方 法 : 1 设 最 短 路 径 初 始 时 仅 包 含 初 始 顶 点, 令 当 前 顶 点 u 为 初 始 顶 点 ; 2 选 择 离 u 最 近 且 尚 未 在 最 短 路 径 中 的 一 个 顶 点 v, 加 入 到 最 短 路 径 中, 修 改 当 前 顶 点 u=v; 3 重 复 步 骤 2, 直 到 u 是 目 标 顶 点 时 为 止 请 问 上 述 方 法 能 否 求 得 最 短 路 径? 若 该 方 法 可 行, 请 证 明 之 ; 否 则, 请 举 例 说 明 42.(15 分 ) 已 知 一 个 带 有 表 头 结 点 的 单 链 表, 结 点 结 构 为 data link 假 设 该 链 表 只 给 出 了 头 指 针 list 在 不 改 变 链 表 的 前 提 下, 请 设 计 一 个 尽 可 能 高 效 的 算 法, 查 找 链 表 中 倒 数 第 k 个 位 置 上 的 结 点 (k 为 正 整 数 ) 若 查 找 成 功, 算 法 输 出 该 结 点 的 data 值, 并 返 回 1; 否 则, 只 返 回 0 要 求 : (1) 描 述 算 法 的 基 本 设 计 思 想 (2) 描 述 算 法 的 详 细 实 现 步 骤 (3) 根 据 设 计 思 想 和 实 现 步 骤, 采 用 程 序 设 计 语 言 描 述 算 法 ( 使 用 C 或 C++ 或 JAVA 语 言 实 现 ), 关 键 之 处 请 给 出 简 要 注 释 2010 年 全 国 研 究 生 考 试 计 算 机 统 考 试 题 及 答 案 一 单 选 题
1 若 元 素 a,b,c,d,e,f 依 次 进 栈, 允 许 进 栈 退 栈 操 作 交 替 进 行 但 不 允 许 连 续 三 次 进 行 退 栈 工 作, 则 不 可 能 得 到 的 出 栈 序 列 是 ( ) A:dcebfa B:cbdaef C:dbcaef D:afedcb 2 某 队 列 允 许 在 其 两 端 进 行 入 队 操 作, 但 仅 允 许 在 一 端 进 行 出 队 操 作, 则 不 可 能 得 到 的 顺 序 是 ( ) A:bacde B:dbace C:dbcae D:ecbad 3 下 列 线 索 二 叉 树 中 ( 用 虚 线 表 示 线 索 ), 符 合 后 序 线 索 树 定 义 的 是 ( ) 4 在 下 列 所 示 的 平 衡 二 叉 树 中 插 入 关 键 字 48 后 得 到 一 棵 新 平 衡 二 叉 树, 在 新 平 衡 二 叉 树 中, 关 键 字 37 所 在 结 点 的 左 右 子 结 点 中 保 存 的 关 键 字 分 别 是 ( ) A:13,48 B:24,48 C:24,53 D:24,90 5 在 一 棵 度 为 4 的 树 T 中, 若 有 20 个 度 为 4 的 结 点,10 个 度 为 3 的 结 点,1 个 度 为 2 的 结 点,10 个 度 为 1 的 结 点, 则 树 T 的 叶 节 点 个 数 是 ()
A:41 B:82 C:113 D:122 6 对 n(n 大 于 等 于 2) 个 权 值 均 不 相 同 的 字 符 构 成 哈 夫 曼 树, 关 于 该 树 的 叙 述 中, 错 误 的 是 (B) A: 该 树 一 定 是 一 棵 完 全 二 叉 树 B: 树 中 一 定 没 有 度 为 1 的 结 点 C: 树 中 两 个 权 值 最 小 的 结 点 一 定 是 兄 弟 结 点 D: 树 中 任 一 非 叶 结 点 的 权 值 一 定 不 小 于 下 一 任 一 结 点 的 权 值 7 若 无 向 图 G-(V.E) 中 含 7 个 顶 点, 则 保 证 图 G 在 任 何 情 况 下 都 是 连 通 的, 则 需 要 的 边 数 最 少 是 () A :6 B:15 C:16 D:21 8 对 下 图 进 行 拓 补 排 序, 可 以 得 到 不 同 的 拓 补 序 列 的 个 数 是 (B ) A:4 B:3 C:2 D:1 9 已 知 一 个 长 度 为 16 的 顺 序 表 L, 其 元 素 按 关 键 字 有 序 排 列, 若 采 用 折 半 查 找 法 查 找 一 个 不 存 在 的 元 素, 则 比 较 次 数 最 多 是 () A:4 B:5 C:6 D:7 10 采 用 递 归 方 式 对 顺 序 表 进 行 快 速 排 序, 下 列 关 于 递 归 次 数 的 叙 述 中, 正 确 的 是 () A: 递 归 次 数 与 初 始 数 据 的 排 列 次 序 无 关 B: 每 次 划 分 后, 先 处 理 较 长 的 分 区 可 以 减 少 递 归 次 数 C: 每 次 划 分 后, 先 处 理 较 短 的 分 区 可 以 减 少 递 归 次 数 D: 递 归 次 数 与 每 次 划 分 后 得 到 的 分 区 处 理 顺 序 无 关 11 对 一 组 数 据 (2,12,16,88,5,10) 进 行 排 序, 若 前 三 趟 排 序 结 果 如 下 () 第 一 趟 :2,12,16,5,10,88 第 二 趟 :2,12,5,10,16,88 第 三 趟 :2,5,10,12,16,88
则 采 用 的 排 序 方 法 可 能 是 : A: 起 泡 排 序 B: 希 尔 排 序 C: 归 并 排 序 D: 基 数 排 序 41.(10 分 ) 将 关 键 字 序 列 (30 7 8 11 18 9 14) 散 列 存 储 到 散 列 列 表 中, 散 列 表 的 存 储 空 间 是 一 个 下 标 从 0 开 始 的 一 个 一 维 数 组 散 列 函 数 为 :H(key)=(key 3)MOD T, 处 理 冲 突 采 用 线 性 探 测 再 散 列 法, 要 求 装 填 ( 载 ) 因 子 为 0.7 问 题 : (1) 请 画 出 所 构 造 的 散 列 表 ; (2) 分 别 计 算 等 概 率 情 况 下, 查 找 成 功 和 查 找 不 成 功 的 平 均 查 找 长 度