2020年厦大计算机考研两套模拟卷.pdf
数据结构试卷(一)一 、 单 选 题 ( 每 题 2 分 , 共 20分 )1. 栈 和 队 列 的 共 同 特 点 是 ( )。A.只 允 许 在 端 点 处 插 入 和 删 除 元 素B.都 是 先 进 后 出C.都 是 先 进 先 出D.没 有 共 同 点2. 用 链 接 方 式 存 储 的 队 列 , 在 进 行 插 入 运 算 时 ( ).A. 仅 修 改 头 指 针 B. 头 、 尾 指 针 都 要 修 改C. 仅 修 改 尾 指 针 D.头 、 尾 指 针 可 能 都 要 修 改3. 以 下 数 据 结 构 中 哪 一 个 是 非 线 性 结 构 ? ( )A. 队 列 B. 栈 C. 线 性 表 D. 二 叉 树4. 设 有 一 个 二 维 数 组 Amn, 假 设 A00存 放 位 置 在 644(10), A22存 放 位 置 在676(10), 每 个 元 素 占 一 个 空 间 , 问 A33(10)存 放 在 什 么 位 置 ? 脚 注 (10)表 示 用 10进 制表 示 。A 688 B 678 C 692 D 6965. 树 最 适 合 用 来 表 示 ( )。A.有 序 数 据 元 素 B.无 序 数 据 元 素C.元 素 之 间 具 有 分 支 层 次 关 系 的 数 据 D.元 素 之 间 无 联 系 的 数 据6. 二 叉 树 的 第 k 层 的 结 点 数 最 多 为 ( ).A 2k-1 B.2K+1 C.2K-1 D. 2k-17. 若 有 18个 元 素 的 有 序 表 存 放 在 一 维 数 组 A19中 , 第 一 个 元 素 放 A1中 , 现 进 行 二分 查 找 , 则 查 找 A 3 的 比 较 序 列 的 下 标 依 次 为 ( )A.1, 2, 3 B.9, 5, 2, 3C.9, 5, 3 D.9, 4, 2, 38. 对 n 个 记 录 的 文 件 进 行 快 速 排 序 , 所 需 要 的 辅 助 存 储 空 间 大 致 为A. O( 1) B. O( n) C. O( 1og2n) D. O( n2)9. 对 于 线 性 表 ( 7, 34, 55, 25, 64, 46, 20, 10) 进 行 散 列 存 储 时 , 若 选 用 H( K)=K %9 作 为 散 列 函 数 , 则 散 列 地 址 为 1 的 元 素 有 ( ) 个 ,A 1 B 2 C 3 D 410.设 有 6个 结 点 的 无 向 图 , 该 图 至 少 应 有 ( )条 边 才 能 确 保 是 一 个 连 通 图 。A.5 B.6 C.7 D.8二 、 填 空 题 ( 每 空 1分 , 共 26分 )1. 通 常 从 四 个 方 面 评 价 算 法 的 质 量 : _、 _、 _和 _。2. 一 个 算 法 的 时 间 复 杂 度 为 (n3+n2log2n+14n)/n2, 其 数 量 级 表 示 为 _。3. 假 定 一 棵 树 的 广 义 表 表 示 为 A( C, D( E, F, G) , H( I, J) ) , 则 树 中 所 含 的 结 点 数为 _个 , 树 的 深 度 为 _, 树 的 度 为 _。4. 后 缀 算 式 923+-102/-的 值 为 _。 中 缀 算 式 ( 3+4X) -2Y/3 对 应 的 后 缀 算 式为 _。5. 若 用 链 表 存 储 一 棵 二 叉 树 时 , 每 个 结 点 除 数 据 域 外 , 还 有 指 向 左 孩 子 和 右 孩 子 的 两 个 指针 。 在 这 种 存 储 结 构 中 , n个 结 点 的 二 叉 树 共 有 _个 指 针 域 , 其 中 有 _个指 针 域 是 存 放 了 地 址 , 有 _个 指 针 是 空 指 针 。6. 对 于 一 个 具 有 n个 顶 点 和 e条 边 的 有 向 图 和 无 向 图 , 在 其 对 应 的 邻 接 表 中 , 所 含 边 结 点分 别 有 _个 和 _个 。7. AOV网 是 一 种 _的 图 。8. 在 一 个 具 有 n个 顶 点 的 无 向 完 全 图 中 , 包 含 有 _条 边 , 在 一 个 具 有 n个 顶 点 的 有向 完 全 图 中 , 包 含 有 _条 边 。9. 假 定 一 个 线 性 表 为 (12,23,74,55,63,40), 若 按 Key%4条 件 进 行 划 分 , 使 得 同 一 余 数 的 元素 成 为 一 个 子 表 , 则 得 到 的 四 个 子 表 分 别 为 _、_、 _和 _。10. 向 一 棵 B_树 插 入 元 素 的 过 程 中 , 若 最 终 引 起 树 根 结 点 的 分 裂 , 则 新 树 比 原 树 的 高 度_。11. 在 堆 排 序 的 过 程 中 , 对 任 一 分 支 结 点 进 行 筛 运 算 的 时 间 复 杂 度 为 _, 整 个 堆 排 序过 程 的 时 间 复 杂 度 为 _。12. 在 快 速 排 序 、 堆 排 序 、 归 并 排 序 中 , _排 序 是 稳 定 的 。三 、 计 算 题 ( 每 题 6 分 , 共 24分 )1. 在 如 下 数 组 A中 链 接 存 储 了 一 个 线 性 表 , 表 头 指 针 为 A0.next, 试 写 出 该 线 性 表 。A 0 1 2 3 4 5 6 7data 60 50 78 90 34 40next 3 5 7 2 0 4 12. 请 画 出 下 图 的 邻 接 矩 阵 和 邻 接 表 。3. 已 知 一 个 图 的 顶 点 集 V和 边 集 E分 别 为 : V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用 克 鲁 斯 卡 尔 算 法 得 到 最 小 生 成 树 , 试 写 出 在 最 小 生 成 树 中 依 次 得 到 的 各 条 边 。4. 画 出 向 小 根 堆 中 加 入 数 据 4,2,5,8,3时 , 每 加 入 一 个 数 据 后 堆 的 变 化 。四 、 阅 读 算 法 ( 每 题 7分 , 共 14分 )1. LinkListmynote(LinkListL)/L是 不 带 头 结 点 的 单 链 表 的 头 指 针if(LABC(BT-right);coutdatadata)item=BST-data;/查 找 成 功return _;else if(itemdata)return Find(_,item);else return Find(_,item);/if六 、 编 写 算 法 ( 共 8分 )统 计 出 单 链 表 HL中 结 点 的 值 等 于 给 定 值 X的 结 点 数 。int CountX(LNode* HL,ElemType x)数据结构试卷(二)一 、 选 择 题 (24分 )1 下 面 关 于 线 性 表 的 叙 述 错 误 的 是 ( ) 。(A) 线 性 表 采 用 顺 序 存 储 必 须 占 用 一 片 连 续 的 存 储 空 间(B) 线 性 表 采 用 链 式 存 储 不 必 占 用 一 片 连 续 的 存 储 空 间(C) 线 性 表 采 用 链 式 存 储 便 于 插 入 和 删 除 操 作 的 实 现(D) 线 性 表 采 用 顺 序 存 储 便 于 插 入 和 删 除 操 作 的 实 现2 设 哈 夫 曼 树 中 的 叶 子 结 点 总 数 为 m, 若 用 二 叉 链 表 作 为 存 储 结 构 , 则 该 哈 夫 曼 树 中 总 共有 ( ) 个 空 指 针 域 。(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m3 设 顺 序 循 环 队 列 Q0: M-1的 头 指 针 和 尾 指 针 分 别 为 F和 R, 头 指 针 F总 是 指 向 队 头 元 素的 前 一 位 置 , 尾 指 针 R 总 是 指 向 队 尾 元 素 的 当 前 位 置 , 则 该 循 环 队 列 中 的 元 素 个 数 为( ) 。(A) R-F (B) F-R (C) (R-F+M) M (D) (F-R+M) M4 设 某 棵 二 叉 树 的 中 序 遍 历 序 列 为 ABCD, 前 序 遍 历 序 列 为 CABD, 则 后 序 遍 历 该 二 叉 树得 到 序 列 为 ( ) 。(A) BADC (B) BCDA (C) CDAB (D) CBDA5 设 某 完 全 无 向 图 中 有 n 个 顶 点 , 则 该 完 全 无 向 图 中 有 ( ) 条 边 。(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-16 设 某 棵 二 叉 树 中 有 2000个 结 点 , 则 该 二 叉 树 的 最 小 高 度 为 ( ) 。(A) 9 (B) 10 (C) 11 (D) 127 设 某 有 向 图 中 有 n 个 顶 点 , 则 该 有 向 图 对 应 的 邻 接 表 中 有 ( ) 个 表 头 结 点 。(A) n-1 (B) n (C) n+1 (D) 2n-18 设 一 组 初 始 记 录 关 键 字 序 列 (5, 2, 6, 3, 8), 以 第 一 个 记 录 关 键 字 5 为 基 准 进 行 一 趟 快速 排 序 的 结 果 为 ( ) 。(A) 2, 3, 5, 8, 6 (B) 3, 2, 5, 8, 6(C) 3, 2, 5, 6, 8 (D) 2, 3, 6, 5, 8二 、 填 空 题 (24分 )1. 为 了 能 有 效 地 应 用 HASH 查 找 技 术 , 必 须 解 决 的 两 个 问 题 是 _和_。2. 下 面 程 序 段 的 功 能 实 现 数 据 x进 栈 , 要 求 在 下 划 线 处 填 上 正 确 的 语 句 。typedefstructints100;inttop;sqstack;voidpush(sqstackelse_;_;3. 中 序 遍 历 二 叉 排 序 树 所 得 到 的 序 列 是 _序 列 ( 填 有 序 或 无 序 ) 。4. 快 速 排 序 的 最 坏 时 间 复 杂 度 为 _, 平 均 时 间 复 杂 度 为 _。5. 设 某 棵 二 叉 树 中 度 数 为 0 的 结 点 数 为 N0, 度 数 为 1 的 结 点 数 为 N1, 则 该 二 叉 树 中 度 数 为2 的 结 点 数 为 _; 若 采 用 二 叉 链 表 作 为 该 二 叉 树 的 存 储 结 构 , 则 该 二 叉 树 中 共有 _个 空 指 针 域 。6. 设 某 无 向 图 中 顶 点 数 和 边 数 分 别 为 n 和 e, 所 有 顶 点 的 度 数 之 和 为 d, 则 e=_。7. 设 一 组 初 始 记 录 关 键 字 序 列 为 (55, 63, 44, 38, 75, 80, 31, 56), 则 利 用 筛 选 法 建 立的 初 始 堆 为 _。8 已 知 一 有 向 图 的 邻 接 表 存 储 结 构 如 下 : 从 顶 点 1出 发 , DFS遍 历 的 输 出 序 列 是, BFS 遍 历 的 输 出 序 列 是三 、 应 用 题 (36分 )1 设 一 组 初 始 记 录 关 键 字 序 列 为 (45, 80, 48, 40, 22, 78), 则 分 别 给 出 第 4趟 简 单 选 择排 序 和 第 4趟 直 接 插 入 排 序 后 的 结 果 。2 设 指 针 变 量 p指 向 双 向 链 表 中 结 点 A, 指 针 变 量 q 指 向 被 插 入 结 点 B, 要 求 给 出 在 结 点 A的 后 面 插 入 结 点 B的 操 作 序 列 ( 设 双 向 链 表 中 结 点 的 两 个 指 针 域 分 别 为 llink和 rlink) 。3 设 一 组 有 序 的 记 录 关 键 字 序 列 为 (13, 18, 24, 35, 47, 50, 62, 83, 90), 查 找 方 法 用二 分 查 找 , 要 求 计 算 出 查 找 关 键 字 62 时 的 比 较 次 数 并 计 算 出 查 找 成 功 时 的 平 均 查 找 长度 。4 设 一 棵 树 T 中 边 的 集 合 为 (A, B), (A, C), (A, D), (B, E), (C, F), (C, G), 要 求用 孩 子 兄 弟 表 示 法 ( 二 叉 链 表 ) 表 示 出 该 树 的 存 储 结 构 并 将 该 树 转 化 成 对 应 的 二 叉 树 。5 设 有 无 向 图 G, 要 求 给 出 用 普 里 姆 算 法 构 造 最 小 生 成 树 所 走 过 的 边 的 集 合 。6 设 有 一 组 初 始 记 录 关 键 字 为 (45, 80, 48, 40, 22, 78), 要 求 构 造 一 棵 二 叉 排 序 树 并 给出 构 造 过 程 。四 、 算 法 设 计 题 (16 分 )1 设 有 一 组 初 始 记 录 关 键 字 序 列 ( K1, K2, , Kn) , 要 求 设 计 一 个 算 法 能 够 在 O(n)的 时 间复 杂 度 内 将 线 性 表 划 分 成 两 部 分 , 其 中 左 半 部 分 的 每 个 关 键 字 均 小 于 Ki, 右 半 部 分 的 每个 关 键 字 均 大 于 等 于 Ki。2 设 有 两 个 集 合 A和 集 合 B, 要 求 设 计 生 成 集 合 C=A B的 算 法 , 其 中 集 合 A、 B和 C用 链式 存 储 结 构 表 示 。数 据 结 构 试 卷 ( 一 ) 参 考 答 案选 择 题 ( 每 题 2分 , 共 20分 )1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A二 、 填 空 题 ( 每 空 1分 , 共 26分 )正 确 性 易 读 性 强 壮 性 高 效 率O(n)9 3 3-1 34X*+2Y*3/-2n n-1 n+1e 2e有 向 无 回 路n(n-1)/2 n(n-1)( 12, 40) ( ) ( 74) ( 23,55, 63)增 加 1O(log2n) O(nlog2n)归 并三 、 计 算 题 ( 每 题 6分 , 共 24分 )线 性 表 为 : ( 78, 50, 40, 60, 34, 90)邻 接 矩 阵 : 01110 10101 11011 10101 01110邻 接 表 如 图 11所 示 :图 11用 克 鲁 斯 卡 尔 算 法 得 到 的 最 小 生 成 树 为 :(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20见 图 12图 12 4 4 4 4 42 2 2 5 5 52 28 8 4 3528 3 4读 算 法 ( 每 题 7分 , 共 14分 )( 1) 查 询 链 表 的 尾 结 点( 2) 将 第 一 个 结 点 链 接 到 链 表 的 尾 部 , 作 为 新 的 尾 结 点( 3) 返 回 的 线 性 表 为 ( a2,a3, ,an,a1)递 归 地 后 序 遍 历 链 式 存 储 的 二 叉 树 。法 填 空 ( 每 空 2分 , 共 8 分 )true BST-left BST-right编 写 算 法 ( 8分 )intCountX(LNode*H L,ElemTypex) inti=0;LNode*p=H L;/i为 计 数 器while(p!=NULL)if(P-data=x)i+;p=p-next;/while, 出 循 环 时 i中 的 值 即 为 x结 点 个 数returni;/CountX数 据 结 构 试 卷 ( 二 ) 参 考 答 案一 、 选 择 题1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C二 、 填 空 题构 造 一 个 好 的 H ASH 函 数 , 确 定 解 决 冲 突 的 方 法stack.top+, stack.sstack.top=x有 序O(n2), O(nlog2n)N0-1, 2N0+N1d/2(31, 38, 54, 56, 75, 80, 55, 63)(1, 3, 4, 5, 2), (1, 3, 2, 4, 5)三 、 应 用 题(22, 40, 45, 48, 80, 78), (40, 45, 48, 80, 22, 78)q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;2,ASL=91*1+2*2+3*4+4*2)=25/9树 的 链 式 存 储 结 构 略 , 二 叉 树 略E=(1, 3), (1, 2), (3, 5), (5, 6), (6, 4)略四 、 算 法 设 计 题设 有 一 组 初 始 记 录 关 键 字 序 列 ( K1, K2, , Kn) , 要 求 设 计 一 个 算 法 能 够 在 O(n)的 时 间复 杂 度 内 将 线 性 表 划 分 成 两 部 分 , 其 中 左 半 部 分 的 每 个 关 键 字 均 小 于 Ki, 右 半 部 分 的 每 个关 键 字 均 大 于 等 于 Ki。voidquickpass(intr,ints,intt) inti=s,j=t,x=rs;while(ix)j=j-1;if(inext) for(q=hb;q!=0;q=q-next)if(q-data=p-data)break;if(q!=0)t=(lklist*)malloc(sizeof(lklist);t-data=p-data;t-next=hc;hc=t;