暨南大学2021年830数据结构考研真题.pdf
1/ 4 2021 年 全 国 硕 士 研 究 生 统 一 入 学 考 试 自 命 题 试 题 A 卷*学 科 、 专 业 名 称 : 网 络 空 间 安 全研 究 方 向 : 网 络 空 间 安 全 083900考 试 科 目 名 称 及 代 码 : 数 据 结 构 830考 生 注 意 : 所 有 答 案 必 须 写 在 答 题 纸 ( 卷 ) 上 , 写 在 本 试 题 上 一 律 不 给 分 。一 、 单 项 选 择 题 (每 题 2 分 , 共 20 分 )1. 以 下 数 据 结 构 中 哪 一 个 是 非 线 性 结 构 ? ()A. 二 叉 树 B. 栈 C. 线 性 表 D. 队 列2. 当 要 对 线 性 表 进 行 折 半 查 找 时 , 线 性 表 必 须 满 足 以 下 条 件 ( ) 。A. 以 顺 序 方 式 存 储 B. 以 链 表 方 式 存 储C. 以 顺 序 方 式 存 储 且 按 关 键 字 有 序 排 列 D. 以 链 表 方 式 存 储 且 按 关 键 字 有 序 排 列 3. 为 了 提 高 哈 希 表 的 查 找 效 率 , 以 下 方 法 说 法 不 正 确 的 是 ( )。A. 设 计 好 的 哈 希 函 数 B. 增 加 哈 希 函 数 的 个 数C. 增 大 存 储 空 间 D. 采 用 更 好 的 地 址 冲 突 解 决 方 法4. 用 单 向 链 表 来 实 现 容 量 为 n的 堆 栈 时 , 链 表 头 指 针 指 向 堆 栈 顶 部 元 素 , 链 表 尾 指 针 指 向 堆 栈底 部 元 素 , 则 以 下 说 法 错 误 的 是 ( )A. 入 栈 操 作 的 复 杂 度 为 O(1) B.出 栈 操 作 的 复 杂 度 为 O(1)C. 插 入 一 个 新 的 堆 栈 底 部 元 素 复 杂 度 为 O(1) D. 删 除 底 部 元 素 的 复 杂 度 为 O(1)5. 设 一 个 顺 序 有 序 的 一 维 数 组 A1:14中 有 14个 元 素 , 采 用 二 分 查 找 算 法 查 找 到 A4中 的 元 素过 程 中 需 要 比 较 的 元 素 的 顺 序 是 ( )A.A1,A2,A3,A4 B. A7,A3,A5,A4C.A1,A14,A7,A4 D. A7,A5,A3,A46. 稀 疏 矩 阵 一 般 采 用 的 压 缩 存 储 方 法 有 两 种 , 即 ( ) A. 二 维 数 组 和 三 维 数 组 B.三 元 组 和 散 列 C. 三 元 组 和 十 字 链 表 D. 十 字 链 表 和 散 列7. 设 a,b为 一 棵 二 叉 树 上 的 两 个 结 点 , 在 中 序 遍 历 时 先 访 问 a后 访 问 b的 条 件 是 ( )A.a在 B的 左 边 B.a在 b的 右 边 C.a是 b的 祖 先 D.a是 b的 子 孙8. 某 二 叉 树 的 中 序 序 列 为 ABCDEFG, 后 序 序 列 为 BDCAFGE, 则 其 左 子 树 结 点 数 为 ( )A.5 B.4 C.3 D.29. 判 断 一 个 有 向 图 中 是 否 存 在 环 ( 回 路 ) , 可 采 用 以 下 方 法 ( )A. 广 度 优 先 遍 历 B. 求 关 键 路 径 C. 求 最 短 路 径 D. 拓 扑 排 序10. 用 哈 希 表 存 储 7个 整 数 18,25,63,50,42,32,9, 如 果 哈 希 函 数 为 H(x)=xmod9, 则 与 18发 生 地址 冲 突 的 整 数 有 ( ) 个A.1 B.2 C.3 D.4二 、 填 空 题 (每 空 2 分 , 共 20 分 ) 1. 数 据 结 构 的 三 要 素 是 指 ( ) ( ) ( ) 。 2/ 4 2. 在 顺 序 表 中 插 入 或 删 除 一 个 元 素 , 需 要 平 均 移 动 ( ) , 具 体 移 动 的 元 素 个 数 与 ( ) 有 关 。3. 设 栈 S与 队 列 Q的 初 始 状 态 皆 为 空 , 元 素 a1,a2,a3,a4,a5和 a6依 次 通 过 一 个 栈 , 一 个 元 素 出栈 后 即 进 入 队 列 Q, 若 6个 元 素 出 队 列 的 顺 序 是 a3,a5,a4,a6,a2,a1,则 栈 S至 少 应 该 容 纳 ( ) 个元 素 。4. 有 一 个 10 阶 对 称 矩 阵 A, 采 用 压 缩 存 储 方 式 ( 以 行 序 为 主 , 且 A00=1) ,则 A85的 地址 是 ( )5. 含 有 100个 结 点 的 树 有 ( ) 条 边 。6. 已 知 二 叉 树 的 前 序 序 列 为 ABDEGCFHIJ, 中 序 序 列 为 DBGEAHFIJC, 请 写 出 后 序 列 ( ) 。7. 在 一 个 无 向 图 的 邻 接 表 中 , 若 表 结 点 数 目 为 m, 则 图 中 边 的 条 数 为 ( ) 。三 判 断 题 ( 每 题 2 分 , 共 20 分 , 正 确 的 选 T, 错 误 的 选 F) 1. 通 过 使 用 线 性 链 表 来 实 现 堆 栈 , 可 以 使 得 每 次 入 栈 /出 栈 操 作 的 时 间 复 杂 度 为 O(1)。 ( )2. 深 度 优 先 搜 索 的 核 心 数 据 结 构 是 队 列 。 ( )3. 将 包 含 n个 元 素 的 升 序 线 性 链 表 改 成 降 序 线 性 链 表 所 需 要 的 时 间 复 杂 度 为 O(n)。 ( )4. 选 择 排 序 算 法 是 稳 定 的 。 ( )5. 一 棵 高 度 为 h的 完 全 二 叉 树 的 结 点 数 量 比 同 样 高 度 的 一 棵 满 二 叉 树 的 结 点 要 多 。 ( )6. 平 衡 二 叉 树 ( AVL) 的 优 点 是 能 够 保 证 在 最 坏 情 况 下 的 查 找 时 间 复 杂 度 为 O(logN)。 ( )7. 无 向 图 的 邻 接 矩 阵 是 对 称 的 , 因 此 只 需 要 存 储 矩 阵 的 下 三 角 阵 以 节 省 存 储 空 间 。 ( )8. 一 棵 高 度 为 h的 完 全 二 叉 树 可 能 的 最 大 结 点 个 数 为 2h个 。 ( )9. 在 快 速 排 序 、 冒 泡 排 序 、 希 尔 排 序 、 堆 排 序 中 , 空 间 复 杂 度 最 高 的 是 快 速 排 序 。 ( )10. 将 一 棵 树 转 化 成 一 棵 二 叉 树 , 则 该 二 叉 树 的 右 子 树 不 一 定 为 空 。 ( )四 、 简 答 题 ( 共 40 分 )1.描 述 以 下 三 个 概 念 的 区 别 : 头 指 针 , 头 结 点 , 首 元 结 点 ( 第 一 个 元 素 结 点 ) 。 ( 6分 ) 2.简 述 线 性 表 、 队 列 和 堆 栈 这 三 种 数 据 类 型 的 相 同 点 和 差 异 处 。 ( 6分 )3. 在 程 序 设 计 中 , 可 采 用 下 列 三 种 方 法 实 现 输 出 和 输 入 : ( 1) 通 过 scanf 和 printf 语 句 ;(2) 通 过 函 数 的 参 数 显 式 传 递 ;(3) 通 过 全 局 变 量 隐 式 传 递 。 试 讨 论 这 三 种 方 法 的 优 缺 点 。 ( 6分 )4.试 着 描 述 数 据 结 构 和 抽 象 数 据 类 型 的 概 念 与 程 序 设 计 语 言 中 数 据 类 型 概 念 的 区 别 。 ( 6分 )5.试 写 出 一 种 算 法 在 带 头 结 点 的 单 链 表 结 构 上 实 现 线 性 表 操 作 Length(L)。 ( 8分 )6.请 用 顺 序 存 储 的 方 式 , 用 C语 言 写 出 实 现 把 串 S1复 制 到 串 S2的 串 复 制 函 数 strcpy( S1, S2) 。( 8分 )五 、 算 法 填 空 ( 共 2 小 题 , 每 空 2 分 , 共 20 分 )1. 假 设 有 一 棵 二 叉 查 找 树 , 其 每 个 结 点 包 含 键 值 key、 左 孩 子 指 针 left和 右 孩 子 指 针 right, 指针 p指 向 该 二 叉 树 的 根 结 点 。 现 要 查 找 键 值 为 x的 结 点 , 如 果 该 二 叉 树 中 存 在 键 值 为 x的 结点 , 则 返 回 指 向 该 结 点 的 指 针 ; 如 果 不 存 在 , 则 返 回 空 指 针 NULL。 请 填 写 下 面 C代 码 中 空 3/ 4 白 的 部 分 , 使 其 成 为 完 整 的 算 法 以 完 成 对 二 叉 树 的 查 找 。SearchBinaryTree(p,x) if(p=NULL| ( 1) )returnp;if (2)return (3)_;else return (4) ;请 将 以 上 空 白 处 的 答 案 填 写 在 下 面 对 应 位 置 : (1)(2)(3)(4)2 给 定 一 个 单 向 链 表 L, 链 表 中 的 结 点 按 照 键 值 大 小 升 序 排 列 。 以 下 的 代 码 可 以 将 L中 所 有 键值 相 同 的 结 点 从 L中 删 除 , 请 将 代 码 中 空 白 处 填 写 完 整 。Structnodeintkey;node*next; intDeleteDuplicate(node*L)node*p,*q;if(L=NULL|L-next=NULL)return-1;p=L;q=p-next;while(p-next!=NULL)if(p-key!=q-key)( 1) ;( 2) ; elsewhile(( 3) ) node*tmp=q-next;deleteq;( 4) ; if(q=NULL)break; 4/ 4 if(q!=NULL)( 5) ; p=p-next;q=p-next;else( 6) ;请 将 以 上 代 码 的 空 白 处 答 案 填 写 在 下 方 相 应 位 置 :(1) (2)(3)(4)(5)(6)六 编 写 算 法 ( 30 分 )1.假 设 称 正 读 和 反 读 都 相 同 的 字 符 序 列 为 “ 回 文 ” , 例 如 , abba 和 abcba是 回 文 , abcde 和 ababab 则 不 是 回 文 。 试 写 一 个 算 法 判 别 读 入 的 一 个 以 为 结 束 符 的 字 符 序 列 是 否 是 “ 回 文 ” 。 ( 10分 )2. 已 知 由 一 个 线 性 链 表 表 示 的 线 性 表 中 含 有 三 类 字 符 的 数 据 元 素 (如 :字 母 字 符 、数 字 字 符 和 其 他 字 符 ), 试 编 写 算 法 将 该 线 性 表 分 割 为 三 个 循 环 链 表 , 其 中 每 个 循 环 链 表 表 示 的 线 性 表 中 均 只 含 一 类 字 符 。 ( 10分 )3. 已 知 一 棵 具 有 n个 结 点 的 完 全 二 叉 树 被 顺 序 存 储 在 一 维 数 组 An中 , 试 着 编 程一 个 算 法 输 出 Ai的 结 点 的 双 亲 与 所 有 孩 子 。 ( 10分 )