2020年宁波大学硕士研究生考试真题之916【数据结构与算法】.pdf

宁 波 大 学 2020 年 硕 士 研 究 生 招 生 考 试 初 试 试 题 (A 卷 )(答 案 必 须 写 在 考 点 提 供 的 答 题 纸 上 ) 第 1 页 共 7 页 科 目 代 码 ： 916 总 分 值 ： 150 科 目 名 称 ： 数 据 结 构 与 算 法一 、 选 择 题 ： （ 每 个 选 择 2分 ， 共 30 分 ）1. 在 单 链 表 指 针 为 P 的 结 点 之 后 插 入 指 针 为 s 的 结 点 ， 正 确 的 操 作 是 （ ） 。A. p-next=s; s-next=p-next; B. p-next=s-next; p-next=s;C. s-next=p-next; p-next=s; D. p-next=s; p-next=s-next;2. 若 进 栈 序 列 为 1， 2， 3， 4， 5， 6， 且 进 栈 和 出 栈 可 以 穿 插 进 行 ， 则 可 能 出 现 的 出 栈 序 列 为 （ ） 。A 3， 2， 6， 1， 4， 5 B 3， 4， 2， 1， 6， 5C 1， 2， 5， 3， 4， 6 D 5， 6， 4， 2， 3， 13. 循 环 队 列 用 数 组 A0.m-1存 放 其 元 素 值 ， 设 头 尾 指 针 分 别 为 front 和 rear， 则 当 前 队 列 中 的 元 素 个数 是 ( )。 A. rear-front-1 B. rear-front+1 C. (rear-front+m)%m D. rear-front4. 二 分 查 找 算 法 的 时 间 复 杂 度 是 （ ） 。A. O(n*n) B. O(n) C. O(n*log n) D . O(log n)5. 向 顺 序 存 储 的 循 环 队 列 Q 中 插 入 新 元 素 的 过 程 分 为 三 步 ： （ ） 。A.进 行 队 列 是 否 满 的 判 断 ， 存 入 新 元 素 ， 移 动 队 尾 指 针B.进 行 队 列 是 否 空 的 判 断 ， 存 入 新 元 素 ， 移 动 队 尾 指 针C.进 行 队 列 是 否 满 的 判 断 ， 移 动 队 尾 指 针 ， 存 入 新 元 素D.进 行 队 列 是 否 空 的 判 断 ， 移 动 队 尾 指 针 ， 存 入 新 元 素6. 设 x 和 y 是 二 叉 树 中 的 任 意 两 个 结 点 ， 若 在 先 根 序 列 中 x 在 y之 前 ， 而 在 后 根 序 列 中 x 在 y之 后 ， 则x和 y的 关 系 是 ( )。 A. x 是 y 的 左 兄 弟 B. x是 y的 右 兄 弟 C. x 是 y 的 祖 先 D. x 是 y 的 子 孙7. 下 列 二 叉 树 中 ， ( )可 用 于 实 现 符 号 的 不 等 长 高 效 编 码 。A. 最 优 二 叉 树 B. B-树 C. 平 衡 二 叉 树 D. 二 叉 排 序 树8. 已 知 哈 希 表 地 址 空 间 为 A9， 哈 希 函 数 为 H(k)=k mod 7， 采 用 线 性 探 测 再 散 列 处 理 冲 突 。 若 依 次 将数 据 序 列 ： 76,45,88,21,94,77,17 存 入 该 散 列 表 中 ， 则 元 素 17存 储 的 下 标 为 ( )； 在 等 概 率 情 况下 查 找 成 功 的 平 均 查 找 长 度 为 ( )。A. 0 B. 1 C. 2 D. 3E. 4 F. 5 G. 6 H. 79、 设 问 题 规 模 为 N 时 ， 某 递 归 算 法 的 时 间 复 杂 度 记 为 T(N)， 已 知 T(1)=1， T(N)=2T(N/2)+N*N/2，用 O 表 示 的 时 间 复 杂 度 为 （ ） 。 A、 O(logN) B、 O(N) C、 O(N2logN) D O(NlogN) 宁 波 大 学 2020 年 硕 士 研 究 生 招 生 考 试 初 试 试 题 (A 卷 )(答 案 必 须 写 在 考 点 提 供 的 答 题 纸 上 ) 第 2 页 共 7 页 科 目 代 码 ： 916 总 分 值 ： 150 科 目 名 称 ： 数 据 结 构 与 算 法10、 右 图 所 示 带 权 无 向 图 的 最 小 生 成 树 的 权 为 ( )。A.17B.15C.14D.1811、 下 面 说 法 不 正 确 的 是 （ ） 。A、 在 聚 集 分 析 中 ， 堆 栈 操 作 PUSH、 POP、 MULTIPOP的 平 均 代 价 都 是 O(1)。B、 在 记 账 方 法 中 ， 某 些 操 作 的 费 用 比 它 们 的 实 际 代 价 或 多 或 少 。C、 势 能 方 法 中 ， 势 是 与 整 个 数 据 结 构 而 不 是 其 中 的 个 别 对 象 发 生 联 系 的 。 D、 平 摊 分 析 就 是 将 最 坏 和 最 好 情 况 下 的 时 间 代 价 进 行 平 均 计 算 得 到 平 摊 时 间 复 杂 度 。12.求 最 长 公 共 子 序 列 时 最 适 合 使 用 的 算 法 是 （ ） 。A、 分 支 界 限 法 B、 动 态 规 划 法 C、 贪 心 法 D、 回 溯 法13. 下 面 的 叙 述 中 不 正 确 的 是 （ ） 。A 关 键 活 动 不 按 期 完 成 就 会 影 响 整 个 工 程 的 完 成 时 间B 任 何 一 个 关 键 活 动 提 前 完 成 ， 将 使 整 个 工 程 提 前 完 成C 所 有 关 键 活 动 都 提 前 完 成 ， 则 整 个 工 程 将 提 前 完 成D 某 些 关 键 活 动 若 提 前 完 成 ， 将 使 整 个 工 程 提 前 完 成14. 设 计 一 个 判 别 表 达 式 中 左 、 右 括 号 是 否 配 对 出 现 的 算 法 ， 采 用 ( )数 据 结 构 最 佳 。A. 线 性 表 B. 栈 C. 队 列 D. 广 义 表 二 、 填 空 题 ： （ 每 空 2分 ， 共 20分 ）1.在 一 棵 m 阶 B-树 中 ， 除 根 结 点 外 非 叶 结 点 至 少 有 _棵 子 树 ， 至 多 有 _棵 子 树 。2.堆 排 序 的 最 坏 时 间 复 杂 度 为 。3.带 头 结 点 的 单 链 表 逆 置 算 法 如 下 ：void invert(LinkList L)p=L-next; L-next=NULL;while(p) q=p; p=p-next;_;_ ; 宁 波 大 学 2020 年 硕 士 研 究 生 招 生 考 试 初 试 试 题 (A 卷 )(答 案 必 须 写 在 考 点 提 供 的 答 题 纸 上 ) 第 3 页 共 7 页 科 目 代 码 ： 916 总 分 值 ： 150 科 目 名 称 ： 数 据 结 构 与 算 法4. 分 别 采 用 堆 排 序 ， 快 速 排 序 ， 冒 泡 排 序 和 归 并 排 序 ， 对 初 态 为 有 序 的 表 ， 则 最 省 时 间 的 是 _算 法 ， 最 费 时 间 的 是 _算 法 。5. 表 达 式 3+(12*3-2)/4+4*5/7)+18/9 的 后 缀 表 达 式 是 。6. 著 名 的 八 皇 后 问 题 是 在 8x8的 国 际 象 棋 棋 盘 上 放 置 8个 皇 后 ， 使 其 任 意 2个 都 不 在 相 互 攻 击 的 位 置 ，该 问 题 可 以 通 过 _方 法 求 解 ， 总 共 有 _个 解 。三 、 简 答 题 ： （ 每 题 8分 ， 共 40 分 ）1 已 知 一 棵 度 为 m 的 树 中 ： n 1个 度 为 1 的 结 点 ， n2个 度 为 2 的 结 点 ， ， nm个 度 为 m的 结 点 ， 问 该 树 中共 有 多 少 个 叶 子 结 点 ？2 给 定 关 键 字 集 合 12, 21, 3, 13, 4, 43, 35, 64, 5, 14 ， 构 造 哈 希 表 ， 采 用 线 性 探 测 再 散 列 处理 冲 突 方 法 。 设 定 哈 希 函 数 H(key) = key MOD 13 ( 表 长 =13 )。 发 生 冲 突 时 请 给 予 说 明 。3.如 果 二 个 排 序 算 法 A 和 B 的 时 间 复 杂 度 分 别 为 fa(n) = n*log n 和 fb(n) = n1.5， 请 问 哪 个 算 法 时 间复 杂 度 低 ？ 试 给 出 简 要 证 明 。4.已 知 一 组 待 执 行 任 务 的 优 先 级 分 别 如 下 : 37,24,42,6,53,8,72,11,3,9。 假 设 任 务 的 优 先 级 越 小 ， 该 任务 的 优 先 级 别 越 高 ， 请 设 计 合 理 的 数 据 结 构 和 算 法 ， 为 这 些 待 执 行 的 任 务 建 立 一 个 优 先 队 列 。5.已 知 待 排 序 的 一 组 记 录 关 键 字 的 初 始 排 列 如 下 : 37,24,42,6,53,8,72,11,3,9。 需 按 关 键 字 递 增 有 序 排序 ， 请 给 出 ： (1).快 速 排 序 完 成 第 一 趟 划 分 之 后 的 记 录 排 列 序 列 （ 以 第 一 个 关 键 字 为 基 准 ） ；(2).堆 排 序 初 始 建 堆 （ 大 顶 堆 ） 的 序 列 ；(3).第 一 趟 基 数 排 序 后 的 序 列 。四 、 算 法 填 空 题 （ 每 空 3 分 ， 共 36 分 ）1.请 完 善 以 下 的 两 两 顶 点 之 间 的 最 短 路 值 计 算 程 序 ， 其 中 V为 顶 点 集 合 ， |V|为 顶 点 个 数 ， 二 维 数 组 weight初 始 值 为 图 中 连 接 的 加 权 。FPath(matrix weight) for i=1 to |V|for j=1 to |V| for k=1 to |V|if ( （ 1） )weightjk = （ 2） ; 宁 波 大 学 2020 年 硕 士 研 究 生 招 生 考 试 初 试 试 题 (A 卷 )(答 案 必 须 写 在 考 点 提 供 的 答 题 纸 上 ) 第 4 页 共 7 页 科 目 代 码 ： 916 总 分 值 ： 150 科 目 名 称 ： 数 据 结 构 与 算 法2、 一 场 演 唱 会 ， 现 有 N(1=N=200)个 歌 迷 排 队 买 票 。 售 票 处 规 定 ， 一 个 人 每 次 最 多 只 能 买 两 张 票 。 假设 ：（ 1） 第 i(1=i=N)位 歌 迷 买 一 张 票 需 要 时 间 Ti；（ 2） 队 伍 中 相 邻 的 两 位 歌 迷 （ 第 i 个 人 和 第 i+1个 人 ） 可 以 由 其 中 一 人 合 买 两 张 票 ， 则 两 位 歌 迷 买 两张 票 的 时 间 变 为 Ri， 这 样 做 可 以 缩 短 后 面 歌 迷 等 待 的 时 间 。 现 给 出 N,Ti和 Ri， 求 使 所 有 人都 买 到 票 的 最 短 售 票 时 间 。输 入 第 一 行 输 入 人 数 N； 第 二 行 N 个 数 ， 表 示 单 买 的 时 间 代 价 Ti； 第 三 行 N-1个 数 ， 表 示 由 前 1人 合 买 的 时 间 代 价 Ri。输 出 最 短 售 票 时 间 。 #include#include#define N 10010int min2(int a,int b)return （ 3） ;int main()int i,j,n,tN=0,rN=0,dpN=0;scanf(%d,for (i=1;i=n;i+) scanf(%d, for (i=1;i= （ 4） ;i+) scanf(%d,dp1= （ 5） ;for(i=2;i=n;i+)dpi=min2( （ 6） );printf(%dn, （ 7） );return 0; 宁 波 大 学 2020 年 硕 士 研 究 生 招 生 考 试 初 试 试 题 (A 卷 )(答 案 必 须 写 在 考 点 提 供 的 答 题 纸 上 ) 第 5 页 共 7 页 科 目 代 码 ： 916 总 分 值 ： 150 科 目 名 称 ： 数 据 结 构 与 算 法3、 有 一 个 由 数 字 0、 1 组 成 的 方 阵 中 ， 存 在 任 意 形 状 的 一 个 或 多 个 封 闭 区 域 ， 封 闭 区 域 由 数 字 1 完 整包 围 构 成 ， 封 闭 区 域 内 至 少 有 一 个 0 。 每 个 节 点 只 能 走 上 下 左 右 4 个 方 向 。 现 要 求 把 封 闭 区 域 内 的所 有 0空 间 都 填 写 成 2 。输 入 第 一 行 一 个 整 数 n， 表 示 方 阵 的 大 小 (1 n 30)； 接 下 来 n 行 ， 由 0 和 1 组 成 的 n n 的方 阵 。输 出 填 好 数 字 2 的 完 整 方 阵 。#include#define N 32int n,p,q,gridNN= 0,queueN*N2=0; struct Positionint row;int col;void addin(int i, int j)queueq0=i;queueq1=j;(8) ;int main() int i,j;scanf(%d,for (i=1;i=n;i+)for (j=1;j=n;j+)scanf(%d,struct Position offset4;struct Position nbr;offset0.row = 0; offset0.col = 1;offset1.row = 1; offset1.col = 0;offset2.row = 0; offset2.col = -1; (9)for (i = 0; i = n+1; i+) grid0i = gridn+1i = -2; / 边 界 围 栏 宁 波 大 学 2020 年 硕 士 研 究 生 招 生 考 试 初 试 试 题 (A 卷 )(答 案 必 须 写 在 考 点 提 供 的 答 题 纸 上 ) 第 6 页 共 7 页 科 目 代 码 ： 916 总 分 值 ： 150 科 目 名 称 ： 数 据 结 构 与 算 法for (i = 0; i = n+1; i+) (10) = -2;p=0;q=0;for (i=1;i=n;i+)if (grid1i=0) addin(1,i);if (gridni=0) addin(n,i);if (gridi1=0) addin(i,1);if (gridin=0) addin(i,n);while (pq) gridqueuep0queuep1=-1;for (int i = 0; i 4; i+) nbr.row = queuep0 + offseti.row;nbr.col = queuep1 + offseti.col;if (gridnbr.rownbr.col = 0) (11) ;p+; for (i=1;in+1;i+)for (j=1;jn+1;j+)if (gridij=-1) printf(0 );else if (gridij=0) (12) ;else printf(1 );printf(n);return 0; 宁 波 大 学 2020 年 硕 士 研 究 生 招 生 考 试 初 试 试 题 (A 卷 )(答 案 必 须 写 在 考 点 提 供 的 答 题 纸 上 ) 第 7 页 共 7 页 科 目 代 码 ： 916 总 分 值 ： 150 科 目 名 称 ： 数 据 结 构 与 算 法五 、 算 法 设 计 题 ： （ 每 题 12 分 ， 共 24分 ）1.如 果 二 叉 树 的 结 构 定 义 如 下 :typedef struct BiTNode char data;struct BiTNode *lchild,*rchild; BiTNode, *BiTree;试 设 计 程 序 计 算 一 棵 二 叉 树 中 包 含 的 叶 子 结 点 的 总 数 。 2.某 大 学 组 织 n 个 学 生 去 多 家 单 位 实 习 ， 如 果 所 有 单 位 总 共 可 以 提 供 m 个 实 习 岗 位 ， 实 习 生 和 实 习 单 位经 过 洽 谈 后 双 方 自 愿 进 行 ， 校 方 则 希 望 能 够 达 到 实 习 人 数 的 最 大 化 ， 假 设 双 方 对 彼 此 只 有 同 意 或 不 同意 ， 没 有 优 先 程 度 考 虑 ， 试 采 用 合 适 的 二 分 图 结 构 表 示 该 过 程 ， 并 设 计 合 理 的 算 法 实 现 二 分 图 的 最 大匹 配 ， 即 达 到 实 习 人 数 的 最 大 化 。