资源描述
考 试 科 目 ： 数 据 结 构 1/ 8 2020 年 全 国 硕 士 研 究 生 统 一 入 学 考 试 自 命 题 试 题 B 卷*学 科 、 专 业 名 称 ： 网 络 空 间 安 全研 究 方 向 ： 网 络 空 间 安 全 083900考 试 科 目 名 称 及 代 码 ： 数 据 结 构 830考 生 注 意 ： 所 有 答 案 必 须 写 在 答 题 纸 （ 卷 ） 上 ， 写 在 本 试 题 上 一 律 不 给 分 。一 、 单 项 选 择 题 (每 题 2 分 ， 共 30 分 )1. 下 述 关 于 顺 序 存 储 结 构 优 点 的 说 法 ， 哪 个 是 正 确 的 （ ）A. 插 入 运 算 方 便 B. 可 方 便 地 用 于 各 种 逻 辑 结 构 的 存 储 表 示C. 存 储 密 度 大 D. 删 除 运 算 方 便2. 假 设 根 结 点 为 第 1层 ， 深 度 为 h层 的 二 叉 树 至 少 有 ( ) 个 结 点 (h1)；A. 2 h B. 2h-1 C. 2h+1 D.2h-13. 用 单 向 链 表 来 实 现 容 量 为 n的 堆 栈 时 ， 链 表 头 指 针 指 向 堆 栈 顶 部 元 素 ， 链 表 尾 指 针 指 向 堆栈 底 部 元 素 ， 则 以 下 说 法 错 误 的 是 ( )A. 入 栈 操 作 的 复 杂 度 为 O(1) B. 出 栈 操 作 的 复 杂 度 为 O(1)C. 删 除 底 部 元 素 的 复 杂 度 为 O(1) D. 插 入 一 个 新 的 堆 栈 底 部 元 素 复 杂 度 为 O(1)4. 以 下 关 于 递 归 算 法 的 论 述 ， 不 正 确 的 是 ( )A. 递 归 算 法 的 代 码 可 读 性 好 B. 递 归 算 法 可 以 提 高 程 序 运 行 效 率C. 递 归 调 用 层 次 太 深 有 可 能 造 成 堆 栈 溢 出 D. 递 归 调 用 层 次 太 深 会 占 用 大 量 内 存5. 设 有 字 符 集 合 4,6,3,W,S， 将 字 符 序 列 6W43S中 的 字 符 按 顺 序 进 入 堆 栈 ， 出 栈 可 发 生 在 任何 时 刻 。 则 以 下 的 出 栈 序 列 错 误 的 是 （ ） 。A.64WS3 B. 4W36S C.6W34S D.WS4366. 在 管 理 城 市 道 路 交 通 网 络 据 时 ， 最 适 合 采 用 （ ） 数 据 结 构 来 对 其 进 行 存 储 。 A 有 向 图 B 无 向 图 C 树 D 矩 阵7. 具 有 k个 顶 点 的 完 全 有 向 图 的 边 数 为 ( )。A.k(k-1) B.k(k-1)/2 C. k2-1 D.k2+18. 若 线 性 表 最 常 用 的 操 作 是 增 加 或 者 删 除 某 个 元 素 , 则 采 用 ( )存 储 方 式 节 省 时 间 .A. 单 链 表 B. 双 链 表 C. 单 循 环 链 表 D. 顺 序 表9. 由 权 为 6,3,2,8的 四 个 叶 子 结 点 构 造 一 个 哈 夫 曼 树 ， 该 树 的 带 权 路 径 长 度 为 （ ） 。A.36 B.35 C.34 D.3310. 为 了 提 高 哈 希 表 的 查 找 效 率 ， 以 下 方 法 说 法 不 正 确 的 是 ( )。A. 设 计 好 的 哈 希 函 数 B. 增 加 哈 希 函 数 的 个 数C. 增 大 存 储 空 间 D. 采 用 更 好 的 地 址 冲 突 解 决 方 法11. 以 下 数 据 结 构 中 哪 一 个 是 非 线 性 结 构 ？ ( )A. 队 列 B. 栈 C. 线 性 表 D. 二 叉 树 12. 对 于 一 个 整 数 集 合 11， 37， 29， 55， 80， 46， 73， 17进 行 散 列 存 储 时 ， 若 选 用 函 数H（ K） =K%9 作 为 散 列 (哈 希 )函 数 ， 则 散 列 地 址 为 1的 元 素 有 （ ） 个 。A 3 B 4 C 5 D 6 考 试 科 目 ： 数 据 结 构 2/ 8 13. 有 一 个 100*90 的 整 数 稀 疏 矩 阵 ， 其 中 非 0元 素 个 数 为 10； 设 每 个 整 数 占 用 3个 字 节 ， 则用 三 元 组 表 示 该 矩 阵 时 ， 总 共 需 要 的 存 储 空 间 为 ( )字 节 。A 30 B 33 C 90 D 9914. 在 一 个 双 向 链 表 中 ， 当 删 除 结 点 p时 ， 错 误 的 操 作 序 列 为 ( )。A. p=p-prev;p-next-prev=p;p-next=p-next-next;B. p=p-next;p-prev=p-prev-prev;p-prev-next=p;C. p-prev-next=p-next;p-next-prev=p-prev;D.p=p-prev;p-next=p-next-next;p-next-prev=p;15. 在 一 个 具 有 V个 顶 点 的 有 向 连 通 图 中 ， 若 所 有 顶 点 的 入 度 数 之 和 为 N， 所 有 顶 点 的 出 度之 和 为 M， 则 以 下 说 法 正 确 的 是 （ ） 。A V=(M+N)/2 B MV C M=N D NV二 、 填 空 题 (每 空 2 分 ， 共 20 分 ) 1. 对 n个 不 同 的 排 序 码 进 行 冒 泡 排 序 ， 在 元 素 无 序 的 情 况 下 比 较 的 次 数 为 。2. 在 单 链 表 中 ， 要 将 m 所 指 结 点 插 入 到 n 所 指 结 点 之 后 ， 其 语 句 表 示为 。3. 设 有 数 组 Aij， 数 组 的 每 个 元 素 长 度 为 3字 节 ， i的 值 为 1到 8， j的 值 为 1到 10， 数 组从 内 存 首 地 址 BA 开 始 顺 序 存 放 ， 当 用 以 列 为 主 存 放 时 ， 元 素 A58的 存 储 首 地 址为 。4. 设 哈 夫 曼 树 中 有 199个 结 点 ， 则 该 哈 夫 曼 树 中 有 个 叶 子 结 点 。5. 对 22个 记 录 的 有 序 表 作 折 半 查 找 ， 当 查 找 失 败 时 候 ， 至 多 需 要 比 较 次 关 键 字 ，至 少 需 要 比 较 次 关 键 字 。6. 由 3 个 结 点 可 以 构 造 出 种 不 同 的 二 叉 树 。7. 最 大 容 量 为 s 的 循 环 队 列 ， 队 尾 指 针 是 rear， 队 头 是 front， 则 队 满 的 条 件是 。8.G 是 一 个 非 连 通 无 向 图 ， 共 有 28条 边 ， 则 该 图 至 少 有 个 顶 点 。 9. 数 据 表 中 有 10000 个 元 素 ， 如 果 仅 要 求 求 出 其 中 最 大 的 10 个 元 素 ， 则 采 用 排序 算 法 最 节 省 时 间 。三 判 断 题 （ 每 题 1 分 ， 共 10 分 ， 正 确 的 选 T， 错 误 的 选 F）1. 对 n个 记 录 进 行 插 入 排 序 ， 最 多 只 需 要 O(nlog(n)次 两 两 比 较 。 ( )2. 用 链 表 (Linkedlist)来 实 现 的 堆 栈 ， 单 次 入 栈 /出 栈 操 作 的 时 间 复 杂 度 可 达 到 O(1)。 ( )3. 当 图 G中 存 在 权 重 为 负 数 的 边 时 ， Dijkstra算 法 不 能 用 于 计 算 G中 两 结 点 间 最 短 路 径 。 ( )4. 贪 婪 算 法 有 时 候 能 够 求 出 全 局 最 优 解 ， 有 时 候 无 法 求 出 全 局 最 优 解 。 ( )5. 对 含 有 n个 记 录 的 集 合 进 行 快 速 排 序 ， 在 最 坏 情 况 下 的 时 间 复 杂 度 是 O(nlog(n)。 ( )6. 哈 希 表 查 找 效 率 高 ， 当 查 找 主 键 在 范 围 a,b内 所 有 的 记 录 时 ， 也 应 该 优 先 选 择 哈 希 表 。 ( )7. 无 向 图 的 邻 接 矩 阵 是 对 称 的 ， 因 此 可 只 存 储 矩 阵 的 下 三 角 阵 以 节 省 存 储 空 间 。 ( ) 8. 用 Prime 算 法 和 Kruskal 算 法 求 得 的 图 的 最 小 生 成 树 一 定 相 同 。 ( )9. 在 一 个 有 向 图 的 邻 接 表 或 逆 邻 接 表 中 ， 若 某 顶 点 的 链 表 为 空 ， 则 该 顶 点 的 度 为 零 。 ( )10. 在 有 n个 顶 点 的 无 向 图 中 ， 若 边 数 n-1， 则 该 图 必 是 连 通 图 。 ( ) 考 试 科 目 ： 数 据 结 构 3/ 8 四 、 简 答 题 （ 40 分 ）1. 简 述 逻 辑 结 构 的 四 种 基 本 关 系 并 画 出 它 们 的 关 系 图 。 （ 10分 ） 2. 设 二 维 数 组 num1.m,1n含 有 m*n个 整 数 ， 请 分 析 判 断 数 组 中 元 素 是 否互 不 相 同 的 算 法 的 时 间 复 杂 度 。 （ 8分 ） 3. 设 待 排 序 的 关 键 字 序 列 为 12， 2， 16， 30， 28， 10， 16*， 20， 6， 18 ， 请写 出 二 路 归 并 排 序 的 方 法 下 ， 每 趟 排 序 结 束 后 关 键 字 序 列 的 状 态 。 （ 6分 ） 考 试 科 目 ： 数 据 结 构 4/ 8 4. 已 知 图 1所 示 的 有 向 图 ， 请 给 出 （ 1） 每 个 顶 点 的 入 度 与 出 度 ； （ 2） 邻 接 矩阵 。 （ 10分 ） 5. 在 一 棵 空 的 二 叉 排 列 树 中 依 次 插 入 关 键 字 序 列 为 12， 7， 17， 11， 16， 2， 13，9， 21， 4， 请 画 出 所 得 到 的 二 叉 排 列 树 。 （ 6分 ） 五 、 算 法 填 空 （ 共 2 小 题 ， 每 空 2 分 ， 共 20 分 ）1. 在 汉 诺 塔 (hanoitower)游 戏 中 ， 总 共 有 3根 柱 子 和 n个 大 小 不 一 样 的 盘 子 。 初 始 状 态 时 n个 盘 子 从 小 到 大 堆 叠 在 1号 柱 子 ， 下 面 的 递 归 算 法 伪 代 码 能 够 将 这 n个 盘 子 从 1号 柱 子 移 动到 3号 柱 子 。 其 中 ， 该 递 归 算 法 满 足 以 下 条 件 ： (1)每 次 只 移 动 1个 盘 子 ， (2)任 何 一 个 盘 子只 有 当 它 上 面 没 有 堆 放 盘 子 时 才 能 移 动 ， (3)任 何 时 刻 在 任 何 一 个 柱 子 上 永 远 不 能 出 现 大 盘子 堆 在 小 盘 子 之 上 的 情 况 。 请 在 _处 填 上 适 当 内 容 ， 使 其 成 为 一 个 完 整 的 算 法 。 图 1. 有 向 图 考 试 科 目 ： 数 据 结 构 5/ 8 hanoi(from,tmp,to,n) if(n=1)move( (1) , (2) );return;hanoi( (3) );printf(%d,%d),from,to);hanoi( (4) );return; 2. 假 设 一 维 数 组 A保 存 有 N个 整 数 ， 以 下 快 速 排 序 算 法 代 码 能 够 对 数 组 A进 行 排 序 。 请 在_处 填 上 适 当 内 容 ， 使 其 成 为 一 个 完 整 的 算 法 。intpartition(int*A,intN,intp,intr) intx=Ar;inti= (5) ;for(intj=p;j=r-1;j+)if( (6) )i=i+1;inttemp=Ai;Ai=Aj;Aj=temp; inttemp=Ai+1;Ai+1=Ar;Ar=temp;return (7) ;voidQuickSort(int*A,intN,intp,intr) intq;if( (8) ) q=partition(A,N,p,r);QuickSort( (9) );QuickSort( (10) );return; 考 试 科 目 ： 数 据 结 构 6/ 8 voidmain() QuickSort(A,N,0,N-1);return0;六 编 写 算 法 （ 30 分 ）1. 写 一 个 算 法 统 计 在 输 入 字 符 串 中 各 个 不 同 字 符 出 现 的 频 度 并 将 结 果 存 入 文 件 （ 字 符 串 中的 合 法 字 符 为 A-Z这 26个 字 母 与 0-9这 10个 数 字 ） 。 （ 10分 ） 考 试 科 目 ： 数 据 结 构 7/ 8 2. 已 知 f为 单 链 表 的 表 头 指 针 ， 链 表 中 存 储 的 都 是 整 型 数 据 ， 请 写 出 实 现 下 列 运 算 的 递 归算 法 ， 求 （ 1） 链 表 中 最 大 整 数 ； （ 2） 所 有 整 数 的 平 均 值 。 （ 10分 ） 考 试 科 目 ： 数 据 结 构 8/ 8 3. 采 用 邻 接 表 存 储 结 构 ， 编 写 一 个 算 法 ， 判 别 无 向 图 中 任 意 给 定 的 两 个 顶 点 之 间 是 否 存 在一 条 长 度 为 k的 简 单 路 径 。 （ 10分 ）
展开阅读全文