数据结构期末考试试题A及答案.pdf

《数据结构期末考试试题A及答案.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试试题A及答案.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 数 据 结 构 试 题 答 案 A 卷 姓 名 班 级 题 号 二 三 总 分 题 分 40 30 30 100得 分 一、回 答 下 列 问 题（每 题 5 分，共 40分）1.给 定 序 列(67,45,87,19,55,32,70,60,90,23),写 出 它 的 初 始 堆 序 列。答：调 整 后 的 初 始 堆 序 列(小 根 堆)为:19,23,32,45,55,87,70,60,90,67或 者 是 大 根 堆:90,67,87,60,55,32,70,45,19,2360 90 672.设 一 个 序 列 奇 数 项 和 偶 数 项 分 别 由 小 到 大 有 序，用 什

2、么 方 法 可 以 最 快 得 到 一 个 有 序 序 列，分 析 它 的 时 间 复 杂 度。答：把 奇 数 项 和 偶 数 项 分 为 2 个 有 序 序 列，然 后 进 行 合 并，时 间 复 杂 度 为 0（n）。实 际 上 就 是 把 2 个 有 序 表 合 并 为 一 个 有 序 表。见 教 科 书 算 法 2.7。3.二 叉 排 序 树 中 的 最 大 值 在 二 叉 排 序 树 的 何 处？答：最 大 值 应 该 位 于 二 叉 排 序 树 中 根 的 右 子 树 的 最 右 叶 子 上。4.在 2048个 互 不 相 同 的 关 键 码 中 选 择 最 小 的 5个 关 键

3、码，用 堆 排 序 是 否 比 用 锦 标 赛 排 序 更 快？为 什 么？答：此 题 用 锦 标 赛 排 序 比 堆 排 序 要 快。理 由 是；在 首 次 求 最 小 值 时，锦 标 赛 排 序 对 2048个 结 点 建 树 得 到 最 小 码 只 需 比 较 nT（即 2047）次,而 此 时 堆 排 序 建 初 始 堆 得 到 最 小 码 却 可 能 需 要 比 较 40比 次（因 为 每 个 结 点 的 调 整 都 要 与 左 右 两 边 的 孩 子 相 比。从 第 1024个 结 点 往 前 调 整，有 512个 结 点 可 能 调 整 1 次，但 要 与 左 右 孩 子 都 比

4、 较，有 256个 结 点 可 能 调 整 2 次，每 次 都 要 与 左 右 孩 子 比 较，有 128个 结 点 可 能 调 整 3 次，有 32个 结 点 调 整 5 次，根 结 点 可 能 要 调 整 1 0次，每 次 都 会 与 左 右 孩 子 比 较，所 以 可 能 会 比 2较 2036X2=4072 次）。而 两 种 算 法 对 求 后 面 4 个 次 小 码 的 平 均 效 率 相 同，都 是 logzn,所 以,此 题 用 锦 标 赛 排 序 会 比 堆 排 序 快。5.n 个 顶 点、m 条 边 的 全 连 通 图，至 少 去 掉 几 条 边 才 能 构 成 一 棵 树？

5、答：因 为 树 的 结 构 是 一 对 多，即 n 个 结 点 的 树 只 有 n T 条 边 与 双 亲 结 点 相 连。只 要 再 多 添 一 条 边 就 会 成 为 图 结 构。所 以，m 条 边 的 图 要 去 掉 m-（n T）=m-n+l条 边 才 能 构 成 一 棵 树。这 棵 树 也 就 是 最 小 生 成 树。6.设 模 式 串 为：liuwenliuyuliuyingliyu,求 该 模 式 串 的 next函 数。答：Nextj=0 1 1 1 1 1 1 2 3 4 1 1 2 3 4 17.一 个 二 叉 树 按 层 次 遍 历 的 顺 序 存 储 结 构 如 下,请

6、 画 出 该 二 叉 树（6为 空）。1 2 3 4 5 6 7 8 9 10 11 1213 14 15答：画 出 二 叉 树 如 下:A B D 4)C6E 46F G6 6 H638.设 数 组 A1.1O,1.8 的 基 地 址 为 2000,每 个 元 素 占 2 个 存 储 单 元，若 以 列 序 为 主 序 存 储（按 列 存 储），则 元 素 A4,5 的 存 储 地 址 是 多 少？答：A 4,5 的 存 储 地 址 是 2086得 分 I 二、综 合 题（每 题 10分，共 30分）1.输 入 一 序 列（58,18,29,22,38,81,19,14）,现 分 别 采 用

7、 顺 序 查 找 和 二 叉 排 序 树 查 找，求 等 概 率 条 件 下 二 者 的 平 均 查 找 长 度 ASL；若 改 用 哈 希 查 找（哈 希 函 数 为：Hash（key）=key mod 11,哈 希 表 的 大 小 为 11,采 用 线 性 探 测 法 进 行 冲 突 处 理），求 等 概 率 条 件 下 的 平 均 查 找 长 度 ASL,并 对 这 三 种 查 找 方 法 进 行 比 较。答：采 用 二 叉 排 序 树 查 找 时，二 叉 排 序 树 为：458采 用 二 叉 排 序 树 查 找 时，ASL=l/8 1 X 1+2 X 2+3 X 1+4 X 2+5 X

8、 1+6 Xl=27/8=3.375采 用 顺 序 查 找 时，ASL=l/2(8+1)=4用 采 用 哈 希 查 找 时，查 找 表 为：0 1 2 3 4 5 6 7 8 914(3)29(1)19(1)ASL=l/8(5X 1+2X 2+1X 4)=13/8=1.6252.已 知 用 线 性 有 序 链 表 存 储 整 数 集 合 的 元 素。阅 读 下 面 算 法，并 回 5答 下 列 问 题：(1)写 出 执 行 ABC(a,b)的 返 回 值，其 中 a 和 b 分 别 为 指 向 存 储 集 合 2,4,5,7,9,12 和 2,4,5,7,9 的 链 表 的 头 指 针；(2)

9、简 述 算 法 ABC的 功 能；(3)写 出 算 法 ABC的 时 间 复 杂 度。int ABC(LinkList ha,LinkList hb)/LinkList是 带 有 头 结 点 的 单 链 表/ha和 hb分 别 为 指 向 存 储 两 个 有 序 整 数 集 合 的 链 表 的 头 指 针 LinkList pa,pb;pa=ha-next;pb=hb-next;while(pa&pb&pa-data=pb-data)pa=pa-next;pb=pb-next;)if(pa=NULL&pb=NULL)return 1;else return 0;)答：(1)ABC(a,b)=0

10、;(2)此 函 数 是 判 两 链 表 是 否 相 等 的 函 数。若 二 表 完 全 相 同 将 返 回 函 数 值 1,不 相 同 则 返 回 的 函 数 值 为 0.(3)算 法 ABC 的 时 间 复 杂 度 为 0(min(LinkList a.length,LinkList_b.length)3.对 于 下 面 的 一 串 字 符,根 据 各 字 符 出 现 的 频 度 求 各 个 字 母 的 哈 夫 曼 编 码,并 且 建 树 要 遵 循 二 叉 树 左 边 结 点 的 权 值 W 二 叉 树 右 边 结 点 的 权 值，请 写 出 详 细 的 求 解 过 程。ABCCCEBAA

11、ADCCCAEECCCEDE答：此 题 分 三 步 求 解，第 步 2 分，和 各 4 分。先 统 计 各 字 母 出 现 的 频 度，得 到 下 表：字 母 A B C D E频 度 5 2 9 2 5 哈 夫 曼 树 构 造 如 7 各 个 字 母 的 哈 夫 曼 编 码 如 下:字 母 A B C D E哈 夫 曼 编 码 01 000 11 001 10三、算 法 设 计 题(每 题 10分，共 30分)1.采 用 二 叉 链 表 作 为 存 储 结 构，试 编 写 一 个 算 法 求 二 叉 树 中 结 点 P的 双 亲 结 点 和 孩 子 结 点。答：采 用 先、中、后 序 遍 历

12、 都 可 完 成，基 本 思 想 是：在 遍 历 过 程 中，寻 找 其 左 孩 子 或 者 右 孩 子 是 p 的 节 点，当 访 问 到 p 节 点 以 后，再 把 其 左 右 孩 子 写 出。只 需 将 遍 历 算 法 的 visit(q)一 句 更 换 为：if(q-rchild=p|q-lchild=p)printf(the parent of p is：q-data);printf(the Ichild of p is：,p-lchild-data);printf(the rchild of p is：*,p-rchild-data);exit(或 return)2.若 借 助 栈

13、 由 输 入 序 列 为 1,2,，n 得 到 的 输 出 序 列 为 BP2P-设 计 一 个 算 法 输 出 所 有 可 能 的 序 列，并 分 析 该 算 法 的 时 间 复 杂 度 和 空 8间 复 杂 度。答：算 法 如 下：Outputstack(String t,in t i,in t j)输 出 序 列 t 中 的 第 i 个 到 第 j 个 的 元 素 if(j i)p rin t(n);/换 行 打 印 e=GetElem(t,i);/取 t 中 的 第 i 个 元 素 push(s,e);OutputStack(t,i+1,j);i f(s栈 不 空)(pop(s,e);

14、p rin t(e);OutputStack(t,i+1,j);时 间 复 杂 度：0(n)=0(n!)=0)。空 间 复 杂 度：由 于 需 要 栈 保 存 递 归 参 数，因 此 空 间 复 杂 度 是 递 归 操 作 9中 栈 的 深 度，故 为 0(n)。3.在 游 戏 软 件 和 图 形 软 件 设 计 中，经 常 遇 到 下 面 的 情 况：n 条 直 线 把 屏 幕 分 成 m 个 区 域，见 图。假 设 每 条 直 线 的 方 程 和 交 点 的 坐 标 已 知,设 计 一 个 数 据 结 构 表 示 这 些 区 域，并 设 计 一 个 算 法，判 断 鼠 标(x,y坐 标)落

15、 在 哪 个 区 域，并 分 析 此 算 法 的 时 间 复 杂 度。答：区 域 树 是 一 棵 二 叉 树，随 着 直 线 的 逐 条 输 入 而 生 成。树 中 每 个 结 点 有 四 个 域 Ichild nodenum linenum rchildnodenum为 结 点 编 号，剖 分 过 程 形 成 的 对 应 的 区 域 编 号。linenum是 直 线 的 编 号，当 结 点 对 应 的 是 不 被 分 割 的 基 本 区 域 时 记 为-1,当 在 分 割 过 程 记 下？分 割 它 的 直 线 的 编 号。10Ichild,rchild对 应 每 个 分 割 直 线 的 左

16、 右 两 侧 的 生 成 区 域 it建 立 3个 表：交 点 表：0,1,2区 域 表：0,1,2,310,11,12及 区 域 所 围 成 的 边 直 线 表：直 线 方 程 式 显 然，此 区 域 树 的 叶 子 节 点 表 示 划 分 的 区 域。判 断 鼠 标 落 在 哪 个 区 域 的 算 法 输 入 mouse的 坐 标（x,y）,从 区 域 树 的 根 节 点 开 始，将 x,y 带 入 此 节 点 的 直 线 方 程，大 于 0,走 左 子 树，否 则，走 右 子 树，直 至 叶 子 节 点，则 此 叶 子 节 点 表 示 的 区 域 即 为 鼠 标 落 在 的 区 域。12算 法 复 杂 度 分 析：算 法 的 时 间 复 杂 度 为 区 域 二 叉 树 的 平 均 深 度，因 为 划 分 的 区 域 为 n!个，也 即 叶 子 有 n!个，则 二 叉 树 的 平 均 深 度 为。(n)。13