青岛科技大学2017年硕士研究生入学考试试题2017数据结构.pdf
第 页 ( 共 3页 )1青 岛 科 技 大 学二 一 七 年 硕 士 研 究 生 入 学 考 试 试 题考 试 科 目 : 数 据 结 构注 意 事 项 : 1 本 试 卷 共 三 道 大 题 ( 共 计 22 个 小 题 ) , 满 分 150 分 ;2 本 卷 属 试 题 卷 , 答 题 另 有 答 题 卷 , 答 案 一 律 写 在 答 题 卷 上 , 写 在 该 试 题 卷 上 或 草纸 上 均 无 效 。 要 注 意 试 卷 清 洁 , 不 要 在 试 卷 上 涂 划 ;3 必 须 用 蓝 、 黑 钢 笔 或 签 字 笔 答 题 , 其 它 均 无 效 。 一 选 择 题 (每 题 2分 , 共 30 分 )1 数 据 结 构 通 常 是 研 究 数 据 结 构 的 ( ) 以 及 它 们 的 操 作 。A) 理 想 与 逻 辑 B) 存 储 和 抽 象 C) 理 想 和 抽 象 D) 逻 辑 结 构 和 存 储 结 构2 指 出 下 面 程 序 段 的 时 间 复 杂 度 ( ) 。i=1;While(inext=P; P-next=S; B) S-next=P-next; P=S;C) S-next=P-next; P-next=S; D) P-next=S; S-next=P;7 具 有 n 个 叶 子 结 点 的 哈 夫 曼 树 , 所 有 结 点 个 数 为 ( ) 。A) 2n B) 2n+1 C) 2n-2 D) 2n-18 一 棵 深 度 为 K 的 完 全 二 叉 树 至 少 有 ( )结 点 。A) 2k+1 B) 2k-1 C) 2k-1 -1 D) 2k+19 平 面 上 有 五 个 点 A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。 以 这 五 点 作 为 完 全 图 G 的点 , 每 两 点 之 间 的 距 离 是 图 G 中 对 应 边 的 权 值 。 以 下 哪 条 边 不 是 图 G的 最 小 生 成 树 中 的 ( ) 。第 页 ( 共 3页 )2A) EA B) AD C) DE D) BD10 二 叉 树 T的 层 次 遍 历 序 列 为 A B C D E F G H I, 已 知 A 是 C 的 父 结 点 , D 是 G 的 父 结 点 ,F 是 I 的 父 结 点 , 树 中 所 有 结 点 的 最 大 深 度 为 3( 根 结 点 深 度 设 为 0) , 可 知 F的 父 结 点 为 ( ) 。A) B B) E C) D D) C11 设 栈 的 初 始 状 态 为 空 , 元 素 a,b,c,d,e,f,g 依 次 进 栈 , 以 下 出 栈 序 列 不 可 能 出 现 的 是 ( ) 。A) a,b,c,e,d,f,g B) g,e,f,d,c,b,a C) b,c,a,f,e,g,d D) d,c,f,e,b,a,g12 一 个 n 阶 对 称 矩 阵 , 如 果 以 行 或 列 为 主 序 存 入 内 存 , 则 容 量 为 ( ) 。A) n*n B) n*n/2 C) n*(n+1)/2 D) (n+1)*(n+1)/213 n 个 顶 点 的 强 连 通 图 至 少 有 ( )条 边 , 其 形 状 是 ( ) 。A)n*( n-1), 树 状 B)n+1, 有 回 路 C) n-1, 无 回 路 D)n, 环 状14 若 用 冒 泡 法 对 序 列 (10,14,26,29,41,52)从 大 到 小 排 序 , 则 需 要 进 行 ( ) 次 比 较 。A) 3 B) 15 C) 10 D)2515 具 有 12个 关 键 字 的 有 序 表 , 若 查 找 每 个 元 素 的 概 率 相 同 , 进 行 二 分 查 找 的 平 均 查 找 长 度 为 ( )。A)4 B)2.5 C)3.1 D)5二 应 用 题 ( 60分 )1 ( 15分 ) 什 么 是 最 优 树 ? 假 设 用 于 通 信 的 电 文 仅 由 8 个 字 母 组 成 , 字 母 在 电 文 中 出 现 的 频 率 分别 为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。 试 为 这 8 个 字 母 设 计 赫 夫 曼 编 码 。 试 设 计 另 一 种 由 二 进 制 表 示 的 等 长 编 码 方 案 。 对 于 上 述 实 例 , 比 较 两 种 方 案 的 优 缺 点 。2.( 15 分 ) 什 么 是 关 键 路 径 ? 什 么 是 关 键 活 动 ? 试 对 下 图 所 示 的 AOE-网 : 求 这 个 工 程 最 早 可 能 在 什 么 时 间 结 束 ; 求 每 个 活 动 的 最 早 开 始 时 间 和 最 迟 开 始 时 间 ; 确 定 哪 些 活 动 是 关 键 活 动3 ( 15 分 ) 假 设 线 性 表 的 关 键 字 集 合 为 key=32,75,31,63,48,94,25,47,18,70,散 列 地 址 空 间 为HT11, 若 采 用 除 留 余 数 法 构 造 散 列 函 数 和 链 地 址 法 处 理 冲 突 , 试 求 出 每 一 元 素 的 散 列 地 址 , 画出 最 后 得 到 的 散 列 表 , 并 求 出 等 概 率 下 查 找 成 功 的 平 均 查 找 长 度 。4. (15 分 )阅 读 以 下 算 法 : 该 算 法 是 什 么 样 排 序 算 法 ; 该 算 法 待 排 序 记 录 的 存 储 结 构 是 什 么 ? 简 述 该 排 序 算 法 的 思 想 ; 设 待 排 序 的 关 键 字 序 列 为 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 试 写 出 使 用 该 排序 方 法 , 每 趟 排 序 结 束 后 关 键 字 序 列 的 状 态 ;第 页 ( 共 3页 )3void Sort ( SqList &L ) for ( i = 2; i = L.length ; +i ) L.r0 = L.ri; low = 1 ; high = i-1 ;while ( low = high ) m = ( low + high ) / 2 ;if ( L.r0.key =high+1; - - j ) L.rj+1 = L.rj;L.rhigh+1 = L.r0; / Sort三 算 法 设 计 题 ( 60 分 )1.( 20分 ) 已 知 head是 指 向 带 头 结 点 的 单 链 表 的 头 指 针 , 试 编 写 以 下 算 法 : 统 计 单 链 表 中 结 点 个 数 的 算 法 ; 删 除 单 链 表 中 值 为 x的 算 法 ;2 ( 20 分 ) 设 以 二 叉 链 表 作 为 二 叉 树 的 存 储 结 构 , 写 出 如 下 算 法 : 用 先 序 遍 历 的 方 法 , 统 计 二 叉 树 中 度 为 1的 结 点 的 个 数 ; 用 层 次 遍 历 的 方 法 , 统 计 二 叉 树 中 度 为 1的 结 点 的 个 数 ;3 ( 20分 ) 写 出 如 下 算 法 : 创 建 一 个 有 向 图 邻 接 表 的 存 储 结 构 的 算 法 ; 写 出 利 用 该 存 储 结 构 实 现 对 有 向 图 进 行 拓 扑 排 序 的 算 法 ;