CHAPTER 1 绪 论 第 1 章 复 习 要 点 考 题 分 析 年 份 单 选 题 / 分 综 合 题 / 分 考 查 内 容 2010 0 2011 1 2 2012 1 2 2013 1 2 2014 1 2 0 知 识 框 架 复 习 提 示 本 章 内 容 并 不 在 考 研 大 纲 中, 它 是 数 据 结 构 的 一 个 概 述 但 读 者 千 万 不 要 忽 视 本 章, 更 应 该 通 过 对 本 章 的 学 习 初 步 了 解 数 据 结 构 的 基 本 内 容 和 基 本 方 法 分 析 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 是 本 章 的 重 点, 属 必 考 内 容, 一 定 要 熟 练 掌 握, 每 年 都 会 结 合 算 法 设 计 题 而 出 现 最 近 4 年 还 直 接 以 选 择 题 的 形 式 考 查 了 时 间 复 杂 度 的 计 算 掌 握 本 章 的 基 本 概 念, 对 后 续 章 节 的 学 习 以 及 整 个 数 据 结 构 课 程 的 理 解 是 非 常 重 要 的
2016 年 数 据 结 构 联 考 复 习 指 导 1.1 数 据 结 构 的 基 本 概 念 1.1.1 基 本 概 念 和 术 语 1. 数 据 2. 数 据 元 素 数 据 项 注 意 : 不 要 混 淆 数 据 数 据 元 素 数 据 项 之 间 的 概 念, 也 要 注 意 和 数 据 库 中 的 相 关 术 语 进 行 区 别 : 如 数 据 记 录 数 据 字 段 等 概 念 3. 数 据 对 象 N={0, 1, 2, } 4. 数 据 类 型 1 2 3 5. 抽 象 数 据 类 型 ADT 6. 数 据 结 构 结 构 Structure 数 据 结 构 : 逻 辑 结 构 存 储 结 构 数 据 的 运 算 1.1.2 数 据 结 构 的 三 要 素 1. 数 据 的 逻 辑 结 构 002
绪 论 第 第 6 章 1 章 1-1 1-1 2. 数 据 的 存 储 结 构 物 理 结 构 1 2 3 4 Hash 3. 数 据 的 运 算 1.1.3 本 节 试 题 精 选 一 单 项 选 择 题 1. 可 以 用 ( ) 定 义 一 个 完 整 的 数 据 结 构 003
2016 年 数 据 结 构 联 考 复 习 指 导 A. 数 据 元 素 B. 数 据 对 象 C. 数 据 关 系 D. 抽 象 数 据 类 型 2. 以 下 数 据 结 构 中,( ) 是 非 线 性 数 据 结 构 A. 树 B. 字 符 串 C. 队 列 D. 栈 3. 以 下 属 于 逻 辑 结 构 的 是 ( ) A. 顺 序 表 B. 哈 希 表 C. 有 序 表 D. 单 链 表 4. 以 下 与 数 据 的 存 储 结 构 无 关 的 术 语 是 ( ) A. 循 环 队 列 B. 链 表 C. 哈 希 表 D. 栈 5. 以 下 关 于 数 据 结 构 的 说 法 中, 正 确 的 是 ( ) A. 数 据 的 逻 辑 结 构 独 立 于 其 存 储 结 构 B. 数 据 的 存 储 结 构 独 立 于 其 逻 辑 结 构 C. 数 据 的 逻 辑 结 构 唯 一 决 定 了 其 存 储 结 构 D. 数 据 结 构 仅 由 其 逻 辑 结 构 和 存 储 结 构 决 定 6. 在 存 储 数 据 时, 通 常 不 仅 要 存 储 各 数 据 元 素 的 值, 而 且 还 要 存 储 ( ) A. 数 据 的 操 作 方 法 B. 数 据 元 素 的 类 型 C. 数 据 元 素 之 间 的 关 系 D. 数 据 的 存 取 方 法 7. 链 式 存 储 设 计 时, 结 点 内 的 存 储 单 元 地 址 ( ) A. 一 定 连 续 B. 一 定 不 连 续 C. 不 一 定 连 续 D. 部 分 连 续, 部 分 不 连 续 二 综 合 应 用 题 1. 对 于 两 种 不 同 的 数 据 结 构, 逻 辑 结 构 或 物 理 结 构 一 定 不 相 同 吗? 2. 试 举 一 例, 说 明 对 相 同 的 逻 辑 结 构, 同 一 种 运 算 在 不 同 的 存 储 方 式 下 实 现, 其 运 算 效 率 不 同 1.1.4 答 案 与 解 析 一 单 项 选 择 题 1 D ADT 2 A 3 C 4 D 3.2.2 5 A 004
绪 论 第 第 6 章 1 章 6 C 7 A 二 综 合 应 用 题 1 数 据 的 运 算 二 叉 树 二 叉 排 序 树 O(n) O(log 2 n) 2 线 性 表 O(n) O(1) 1.2 算 法 和 算 法 评 价 1.2.1 算 法 的 基 本 概 念 算 法 Algorithm 5 1 有 穷 性 2 确 定 性 3 可 行 性 4 输 入 5 输 出 1 2 3 4 005
2016 年 数 据 结 构 联 考 复 习 指 导 1.2.2 算 法 效 率 的 度 量 1. 时 间 复 杂 度 T(n) n T(n) 最 深 层 循 环 内 T(n) f(n) T(n)=O(f(n)) O T(n) T(n) f(n) C n 0 n n 0 0 T(n) C f(n) n 例 如 A[0 n 1] K (1)i=n 1; (2)while(i>=0&&(A[i]!=k)) (3) i ; (4)return i; 3 n A K A K 3 f(n)=n A K 3 f(n) 0 最 坏 时 间 复 杂 度 平 均 时 间 复 杂 度 最 好 时 间 复 杂 度 a T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))) b T(n)=T1(n) T2(n)=O(f(n)) O(g(n))=O(f(n) g(n)) Ο(1) Ο(log 2 n) Ο(n) Ο(nlog 2 n) Ο(n 2 ) Ο(n 3 ) Ο(2 n ) O(n!) O(n n ) 2. 空 间 复 杂 度 S(n) n S(n)=O(g(n)) f(n) n 1 f(n)=a* n 3 +b* n 2 +c*n O(n 3 ) 006
绪 论 第 第 6 章 1 章 原 地 工 作 O(1) 1.2.3 本 节 试 题 精 选 一 单 项 选 择 题 1. 一 个 算 法 应 该 是 ( ) A. 程 序 B. 问 题 求 解 步 骤 的 描 述 C. 要 满 足 五 个 基 本 特 性 D.A 和 C 2. 某 算 法 的 时 间 复 杂 度 为 O(n 2 ), 表 明 该 算 法 的 ( ) A. 问 题 规 模 是 n 2 B. 执 行 时 间 等 于 n 2 C. 执 行 时 间 与 n 2 成 正 比 D. 问 题 规 模 与 n 2 成 正 比 3. 以 下 算 法 的 时 间 复 杂 度 为 ( ) void fun(int n){ int i=1; while(i<=n) i=i*2; } A.O(n) B.O(n 2 ) C.O(nlog 2 n) D.O(log 2 n) 4. 2011 年 计 算 机 联 考 真 题 设 n 是 描 述 问 题 规 模 的 非 负 整 数, 下 面 程 序 片 段 的 时 间 复 杂 度 是 ( ) x=2 while(x<n/2) x=2*x A.O(log 2 n) B.O(n) C.O(nlog 2 n) D.O(n 2 ) 5. 2012 年 计 算 机 联 考 真 题 求 整 数 n(n 0) 阶 乘 的 算 法 如 下, 其 时 间 复 杂 度 是 ( ) int fact(int n){ if(n<=1) return 1; return n*fact(n 1); } A.O(log 2 n) B.O(n) C.O(nlog 2 n) D.O(n 2 ) 6. 2013 年 计 算 机 联 考 真 题 已 知 两 个 长 度 分 别 为 m 和 n 的 升 序 链 表, 若 将 它 们 合 并 为 一 个 长 度 为 m+n 的 降 序 链 表, 则 最 坏 情 况 下 的 时 间 复 杂 度 是 ( ) A.O(n) B.O(m n) C.O(min(m, n)) D.O(max(m, n)) 007
2016 年 数 据 结 构 联 考 复 习 指 导 7 2014 008 count=0; for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++; A O(log 2 n) B O(n) C O(nlog 2 n) D O(n 2 ) 8. 有 以 下 算 法, 其 时 间 复 杂 度 为 ( ) void fun(int n){ int i=0; while(i*i*i<=n) i++; } A.O(n) B.O(nlogn) C.O( 3 n ) D.O( n ) 9. 程 序 段 for(i=n 1;i>1;i ) for(j=1;j<i;j++) if(a[j]>a[j+1]) A[j] A[j+1] ; 其 中 n 为 正 整 数, 则 最 后 一 行 的 语 句 频 度 在 最 坏 情 况 下 是 ( ) A.O(n) B.O(nlogn) C.O(n 3 ) D.O(n 2 ) 10. 以 下 算 法 中 加 下 划 线 语 句 的 执 行 次 数 为 ( ) int m=0,i,j; for(i=1;i<=n;i++) for(j=1;j<=2*i;j++) m++; A.n(n+1) B.n C.n+1 D.n 2 11. 下 面 说 法 错 误 的 是 ( ). 算 法 原 地 工 作 的 含 义 是 指 不 需 要 任 何 额 外 的 辅 助 空 间. 在 相 同 的 规 模 n 下, 复 杂 度 O(n) 的 算 法 在 时 间 上 总 是 优 于 复 杂 度 O(2 n ) 的 算 法. 所 谓 时 间 复 杂 度 是 指 最 坏 情 况 下, 估 算 算 法 执 行 时 间 的 一 个 上 界. 同 一 个 算 法, 实 现 语 言 的 级 别 越 高, 执 行 效 率 就 越 低 A. B., C., D. 二 综 合 应 用 题 1. 一 个 算 法 所 需 时 间 由 下 述 递 归 方 程 表 示, 试 求 出 该 算 法 的 时 间 复 杂 度 的 级 别 ( 或 阶 ) 1 n 1 T(n) 2T(n/2) n n 1 式 中,n 是 问 题 的 规 模, 为 简 单 起 见, 设 n 是 2 的 整 数 幂 2. 分 析 以 下 各 程 序 段, 求 出 算 法 的 时 间 复 杂 度 i=1;k=0; y=0; while(i<n-1){ k=k+10*i; while((y+1)*(y+1)<=n) y=y+1;
绪 论 第 第 6 章 1 章 i++; } for(i=1;i<=n;i++) for(i=0;i<n;i++) 1.2.4 答 案 与 解 析 for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++; for(j=0;j<m;j++) a[i][j]=0; 一 单 项 选 择 题 1 B 2 C O(n 2 ) T(n) c n 2 c T(n)=O(n 2 ) T(n) n n n 2 3 D i=i*2 T(n) 2 T(n) n T(n) log 2 n=o(log 2 n) 4 A x=2*x t 2 t+1 =n/2 t=log 2 (n/2)-1=log 2 n-2 T(n)=O(log 2 n) 5 B n! n*(n-1)* *1 n T(n)=O(n) 6 D O(max(m, n)) 7 C j<=n j 1 n k<=n k*=2 2 k <=n k<=log 2 n O(n) O(log 2 n) T(n)=T 1 (n)*t 2 (n)=o(n)*o(log 2 n)=o(nlog 2 n) C 8 C i++ T(n) T(n) T(n) T(n) n T(n) 3 n T(n) 3 n =O( 3 n ) 更 加 直 观 和 快 速 的 解 题 方 法 i++ i 1 i 3 =n i= 3 n T(n)= O( 3 n ) 9 D n 1 i 1 n 1 2 T(n) 1 i (n 2)(n 1) / 2 O(n ) i 2 j 1 i 2 最 坏 情 况 下 O(n 2 ) 10 A m++ n 2i n n 1 2i 2 i n(n 1) i 1 j 1 i 1 i 1 11 A n O(n) O(2 n ) 009
2016 年 数 据 结 构 联 考 复 习 指 导 二 综 合 应 用 题 1 O(nlog 2 n) n=2 k (k 0) T(2 k )=2T(2 k 1 )+2 k =2 2 T(2 k 2 )+2 2 k T(2 k )=2 i T(2 k i )+i 2 k T(2 k )=2 k T(2 0 )+k 2 k =(k+1)2 k T(n)=2 log2 n + log 2 n*n=n(log 2 n+1) O(nlog 2 n) 2 k=k+10*i n-2 T(n)=O(n) T(n) y 1 T(n)=y (T(n)) 2 n T(n)=O(n 1/2 ) n i j 1 x++ T(n)=O l =O n 3 i 1 j 1 k 1 6 =O(n3 ) a[i][j]=0 m n m*n T(m, n)=o(m*n) 归 纳 总 结 一 是 循 环 主 体 中 的 变 量 参 与 循 环 条 件 的 判 断 T(n) 1. int i=1; while(i<=n) i=i*2;. 1 i 2 T(n) 2 T(n) n T(n) log 2 n 2 y 1 T(n) T(n)=y-5 y=t(n)+5 (T(n)+5+1) *(T(n)+ 5+1)<n T(n)< n 6 T(n)=O( n ) 二 是 循 环 主 体 中 的 变 量 与 循 环 条 件 无 关 5 T(n)=1+T(n 1)=1+1+T(n 2)= =n 1+T(1) T(n)=O(n) 2. int y=5; while((y+1)*(y+1)<n) y=y+1;. 010
绪 论 第 第 6 章 1 章 8 9 思 维 拓 展 1, n 0,1 F(n) F(n 1) F(n 2), n 1 ( 提 示 : 请 结 合 归 纳 总 结 中 的 两 种 方 法 进 行 解 答 ) 011